운영체제 (Operating System) (하드웨어와 응용 프로그램 사이의 인터페이스 역할을 담당하는 시스템 소프트웨어) 4.CPU 스케줄링 A200812032조사선

CPU 스케쥴링 프로세스간의 CPU 배정 준비 상태 프로세스들 중 선택하는 원칙 CPU의 효율적 이용에 의한 생산성 개선 다중 프로그래밍 입출력은 I/O Controller에 의해 수행 프로세스의 입출력시 CPU를 효율적 활용 한 프로세스가 입출력을 할 때 다른 프로세스 수행 한 프로세스의 독점을 막기 위해 타임 아웃 스케쥴링 개념 스케쥴되는 프로세스 사용자 프로세스 시스템 호출에 의해 발생되는 시스템 프로세스 스케쥴되지 않는 작업 인터럽트 처리 오류 처리 사용자의 시스템 호출에 있어서의 사전 처리

CPU와 입출력의 버스트의 교대 순 CPU-I/O 버스트 주기 (burst cycle) cycle : CPU burst 유형 CPU 실행(CPU burst) <->I/O 대기(I/O burst) CPU burst 유형 I/O bound program : 많은 짧은 CPU burst 가짐 CPU bound program : 적은 아주 긴 CPU burst 가짐

CPU버스트 타임의 히스토그램 CPU 스케줄러 단기 스케줄러 (short-term scheduler) : ready queue에서 선택 FIFO(First-In First-Out)큐 우선순위 큐 트리 연결리스트

프로세스 제어 블록 프로세스 상태 프로그램 계수기 CPU 레지스터 주 기억 장치 관리 정보 계정 정보 입출력 상태 정보 생성,준비,실행,유후,중단 등의 상태를 표시 프로그램 계수기 프로세스를 수행하기 위한 다음 명령의 주소를 표시 CPU 레지스터 누산기, 색인 레지스터, 범용 레지스터, 조건 코드 등에 관한 정보를 말하며 컴퓨터구조에 따라 수나 형태가 변화 한다 주 기억 장치 관리 정보 기준 레지스터, 한계 레지스터, 페이지 표를 포함 한다 계정 정보 CPU 사용 시간, 실제 사용 시간, 한정된 시간, 계정 번호, 작업이나 프로세스 번호등을 포함 한다 입출력 상태 정보 특별한 입출력 요구 프로세스에 할당된 입출력 장치, 개방된 파일의 목록등을 가지고 있다

성능의 기준 이용률(CPU utilization) : 처리율(throughput) : 가능한 놀리지 말아야 한다 40% ~ 90% 처리율(throughput) : 처리된 프로세스 개수/시간 단위 반환 시간(turnaround time) : system in -> system out 걸린 시간 대기 시간(waiting time) : ready queue에서 기다린 시간 반응 시간(response time) : 대화형 시스템에서 첫 응답까지의 시간

CPU스케줄링(CPU Scheduling) 선점 스케줄링(Preemptive Scheduling) 선점(preemptive) 스케줄링 특수하드웨어(timer)필요 공유 데이타에 대한 프로세스 동기화 필요 비선점(non preemptive) 또는 협조적(cooperative) 스케줄링 MS-Windows, 특수 하드웨어(timer) 없음 종료 또는 I/O까지 계속 CPU점유 Kernel의 선점 처리 case 1(초기 Unix) : system call 완료 또는 I/O 완료할 때 까지 기다렸다가 문맥교환 실시간 컴퓨팅이나 멀티 프로세싱에 나쁨 case 2 : interrupt 중 다른 interrupt enable(우선순위에 따라) 선점 처리: system call만 preemptible critical section(공유 데이터 수정하는 코드 부분)에 있는 동안 interrupt disable 해야 함 CPU scheduling decision time running -> waiting : non preemptive running -> ready (interrupt) : preemptive waiting -> ready (I/O 완료) : preemptive halt : non preemptive 분배기(Dispatcher) 문맥 교환 사용자 모드로 전환 프로그램의 적절한 위치로 점프하여 프로그램 재 시작 (dispatch latency가 짧아야 함)

스케줄링 알고리즘 (Scheduling Algorithm) 척도 : 평균 대기 시간(average waiting time) 선입 선처리(First-Come, First-Served) 스케줄링 들어온 순서대로 FIFO queue : First-in<- tail First-out<- head p141-142 예(Gantt chart) 호위 효과(convoy effect) : 큰 job하나가 끝나기를 모두 기다림(CPU-bound process가 끝나기를 I/O bounded process들이 기다림) non-preemptive임(time-sharing에서는 곤란) 최소 작업 우선(Shortest-Job-First) 스케줄링 Shortest Next CPU Burst Scheduling 다음 CPU burst 시간이 가장 짧은 프로세스에게 두 가지 스케줄링 기법 non-preemptive SJF : p143 예 preemptive SJF = Shortest Remaining Rime First Scheduling : p145 예 최적(Optimal) 단점 : 기아 상태(starvation) long-term scheduling에 좋음(프로세스 시간의 사용자 예측 치 이용) short-term scheduling 에는 나쁨 : 차기 CPU burst 시간 파악이 어려워서 차기 CPU 버스트 시간 예측 모델

스케줄링 알고리즘 (Scheduling Algorithm) 우선순위(Priority) 스케줄링 높은 우선 순위의 프로세스에게 ready queue = priority queue -> heap구조가 좋음 FCFS : equal-priority SJF : p =1/T (T = 차기 CPU 버스트 시간 예측 값) priority요인(OS내부) 시간 제한(time limits) 메모리 요구량 오픈 화일 수 (average I/O burst)/(average CPU burst) 비율 등 priority요인(OS외부) 프로세스 중요도 컴퓨터 사용료 형태와 금액 작업 부서 정치적 요인 등 preemptive 일 수도 non-preemptive 일 수도 문제점 = 무한 정지(blocking) 또는 기아 상태(starvation) CPU를 영원히 기다림 : 결국 실행되거나 system crash 때 사라지거나 (예) IBM 7094 at MIT 1973, 1967 job 해결 -> aging : wait 시간 길어지면 priority 높여 줌

스케줄링 알고리즘 (Scheduling Algorithm) 순환 할당(Round-Robin) 스케줄링 FCFS + preemption (time slice 마다) ready queue = 원형 FIFO queue preemptive 임 time sharing에서time quantum의 크기가 중요 1 time quantum > context switching time 80% CPU burst < 1 time quantum p148, p150 예 다단계 큐(Multilevel Queue) 스케줄링 각 프로세스는 우선 순위가 다른 여러 개의 큐 중 하나에 영원히 할당: p151 그림 5.6 각 queue는 자신의 고유한 scheduling algorithm 가짐 foreground (interactive) queue : RR알고리즘 background (batch) queue : FCFS알고리즘 queue들 사이의 scheduling : 고정 우선 순위 선점 스케줄링(fixed priority preemptive scheduling) 큐 사이의 CPU time slice 할당 예 80% for RR 20% for FCFS 스케줄링 부담 적으나 융통성이 적음

스케줄링 알고리즘 (Scheduling Algorithm) 다단계 귀환 큐(Multilevel Feedback Queue) 스케줄링 프로세스가 여러 큐 사이를 이동 : 그림 6.7 짧은 프로세스(I/O bound, interactive processes)가 우선 긴 프로세스는 자꾸 낮은 큐로 이동 aging(오래 기다리면 우선순위 높여 기아 상태 예방) preemptive 임(큐 사이) the most sophisticated, the most complex 가장 일반적 -> 해당 시스템에 맞게 설정해야(configure) 큐의 개수 각 큐의 스케줄링 알고리즘 높은 우선 순위로 올려 주는 시기 낮은 우선 순위로 내려 주는 시기 어느 큐에 들어갈 것인가 HRN(Highest-Response-ratio Next) 스케줄링 1971 Brinch Hansen SJF의 단점 보완 dynamic priority = (time waiting + service time) / (service time) 오래 기다린 프로세스는 time waiting이 증가하므로 priority 커지고 short process일수록 priority 커짐 non-preemptive 임

스케줄링 알고리즘 (Scheduling Algorithm) 동종 다중 프로세서(homogeneous multiprocessor) 프로세서는 큐에 있는 어떤 프로세스(any processes)든 실행 부하 공유(load sharing) 별도의 준비 큐(separate ready queue) 공동 준비 큐(common ready queue) 이종 다중 프로세서(heterogeneous multiprocessor) 프로세서는 정해진(dedicated) 프로세스만 실행 distributed systems 공동 준비 큐 동종 다중 프로세서 시스템 (common ready queue on homogeneous multiprocessor)의 스케줄링 각 프로세서가 스스로 스케줄링(self-scheduling) : symmetric (SMP) master-slave(asymmetric) : asymmetric master만 kernel system data structure에 접근 가능 한 프로세서가 다른 프로세서 스케줄링 master server : all system activity client : user code only

스케줄링 알고리즘 (Scheduling Algorithm) FIFO 스케줄링 – nonpreemptive 프로세스들은 대기 큐에 도착한 순서대로 CPU를 할당 받는다 일괄처리 시스템에서 주로 사용, 작업 완료 시간을 예측하기 용이 짧은 작업이 긴 작업을 기다리게 됨 중요하지 않은 작업이 중요한 작업을 기다리게하여 불합리 라운드로빈(round robin) 스케줄링 FCFS에 의해서 프로세스들이 보내지며 각 프로세스는 같은 크기의 CPU 시간을 할당 받는다 시분할 방식에 효과적, 할당시간의 크기가 매우 중요 할당시간이 크면 FCFS와 같게되고, 작으면 문맥교환이 자주 일어난다 SJF(shortest job first) 스케줄링 – nonpreemptive 준비큐내의 작업중 수행시간이 가장 짧다고 판단되는 것을 먼저 수행 FCFS보다 평균 대기 시간을 감소, 큰 작업은 시간 예측이 어렵다 짧은 작업에 유리 SRT(short remaining time) 스케줄링 가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 수행 남은 처리 시간이 더 짧다고 판단는 프로세스가 준비큐에 생기면 언제라도 실행중인 프로세스가 선점됨 긴 작업은 SJF보다 대기 시간이 길다