제5장 CPU스케줄링(CPU Scheduling)

Presentation on theme: "제5장 CPU스케줄링(CPU Scheduling)"— Presentation transcript:

1 제5장 CPU스케줄링(CPU Scheduling)
운영체제 5장 제5장 CPU스케줄링(CPU Scheduling) 프로세스 스케줄링 장기 job scheduling 단기 CPU scheduling 중기 swapping 5.1 기본 개념(Basic Concepts) CPU-I/O 버스트 주기(burst cycle) cycle : CPU 실행(CPU burst) <--> I/O 대기(I/O burst) CPU burst 유형 I/O bound program : 많은 짧은 CPU burst 가짐 CPU bound program : 적은 아주 긴 CPU burst 가짐 CPU 스케줄러 단기 스케줄러(short-term scheduler) : ready queue에서 선택 FIFO(First-In First-Out)큐 우선순위 큐 트리 연결리스트

2 제5장 CPU스케줄링(CPU Scheduling) [cont.]
운영체제 5장 제5장 CPU스케줄링(CPU Scheduling) [cont.] 선점 스케줄링(Preemptive Scheduling) 선점(preemptive) 스케줄링 특수하드웨어(timer)필요 공유 데이타에 대한 프로세스 동기화 필요 비선점(non preemptive) 스케줄링 MS-Windows, 특수 하드웨어(timer) 없음 종료 또는 I/O까지 계속 CPU점유 비선점 kernel : Unix versions case 1 : 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

3 제5장 CPU스케줄링(CPU Scheduling) [cont.]
운영체제 5장 제5장 CPU스케줄링(CPU Scheduling) [cont.] 분배기(Dispatcher) 문맥 교환 사용자 모드로 전환 프로그램의 적절한 위치로 점프하여 프로그램 재시작 dispatch latency가 짧아야 함 5.2 스케줄링 기준(Scheduling Criteria) 이용률(CPU utilization) : 40% ~ 90% 처리율(throughput) : 처리된 프로세스 개수/시간 단위 반환시간(turnaround time) : system in -> system out 걸린 시간 대기시간(waiting time) : ready queue에서 기다린 시간 응답시간(response time) : 대화형 시스템에서 첫 응답까지의 시간

4 5.3 스케줄링 알고리즘(Scheduling Algorithm)
운영체제 5장 5.3 스케줄링 알고리즘(Scheduling Algorithm) 척도 : 평균 대기 시간(average waiting time) 선입 선처리(First-Come, First-Served) 스케줄링 들어온 순서대로 FIFO queue : First-in<- tail First-out<- head p 예(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) long-term scheduling에 좋음(프로세스 시간의 사용자 예측 치 이용) short-term scheduling 에는 나쁨 : 차기 CPU burst 시간 파악이 어려워서 차기 CPU 버스트 시간 예측 모델: p144

5 5.3 스케줄링 알고리즘(Scheduling Algorithm) [cont.]
운영체제 5장 5.3 스케줄링 알고리즘(Scheduling Algorithm) [cont.] 우선순위(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 높여 줌

6 5.3 스케줄링 알고리즘(Scheduling Algorithm) [cont.]
운영체제 5장 5.3 스케줄링 알고리즘(Scheduling Algorithm) [cont.] 순환 할당(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 스케줄링 부담 적으나 융통성이 적음

7 5.3 스케줄링 알고리즘(Scheduling Algorithm) [cont.]
운영체제 5장 5.3 스케줄링 알고리즘(Scheduling Algorithm) [cont.] 다단계 귀환 큐(Multilevel Feedback Queue) 스케줄링 프로세스가 여러 큐 사이를 이동 : p153 그림 5.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 임

8 5.4 다중 프로세서 스케줄링(Multiple-Processor Scheduling)
운영체제 5장 5.4 다중 프로세서 스케줄링(Multiple-Processor Scheduling) 동종 다중 프로세서(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 master-slave(asymmetric) : asymmetric master만 kernel system data structure에 접근 가능 한 프로세서가 다른 프로세서 스케줄링 master server : all system activity client : user code only

9 5.5 Real-Time Scheduling [cont.]
운영체제 5장 5.5 Real-Time Scheduling [cont.] hard real-time system 보조기억장치나 가상기억 장치사용 시스템에서는 불가능 특수 H/W상에서 수행되는 특수 S/W로 구성됨 soft real-time system 중요 프로세스가 우선(general-purpose computer system에서도 가능) multimedia, high-speed interactive graphics등(soft real-time computing이 필요) soft real-time OS 기능의 요구사항 1. 우선순위 스케줄링을 해야함(must have priority scheduling) 실시간 프로세스는 최상위 우선 순위를 유지해야 함 2. 디스패치의 지연시간이 최소여야함 (the dispatch latency must be small) Unix Kernel : context switching 하기 전에 일어난 system call 또는 I/O block을 기다려야 함. -> 해결 ① system call을 preemptible하게 긴 system call안에 preemption points(더 높은 우선 순위의 프로세스가 있나 check, 있으면 interrupt) ② kernel전체를 preemptible하게 Kernel data보호를 위한 synchronization 필요. (예) Solaris 2 : 우선순위 역전(priority inversion) 즉 kernel data 수정중일 때는 cotrol을 넘겨 주지 않음 (Cf.) Mach : threads one nonpreemptible, threads are synchronous

10 5.5 Real-Time Scheduling [cont.]
운영체제 5장 5.5 Real-Time Scheduling [cont.] 우선순위 역전(priority inversion) kernel data 수정중인 우선순위가 낮은 프로세스가 선점하려는 우선순위 프로세스에 우선하여 수행됨. 우선순위 상속 프로토콜(priority inheritance protocol) kernel data 수정중인 낮은 우선 순위의 프로세스가 선점하려는 프로세스의 높은 우선순위를 상속 받음, 끝나면 원래의 값으로 갈등 단계(complict phase)의 내용 : p157 그림 5.2 1. 커널에서 실행 중인 프로세스를 선점 2. 자원 회수(우선 순위 낮은 프로세스는 우선 순위 높은 프로세스가 요구하는 자원을 놓아줌) 3. 우선순위 높은 프로세스로 문맥 교환 (예) Solaris 2 dispatch latency nonpreemptible = 100 ms dispatch latency preemptible = 2 ms

11 5.6 알고리즘 평가(Algorithm Evaluation)
운영체제 5장 5.6 알고리즘 평가(Algorithm Evaluation) 결정성 모형화(Deterministic Modeling) 작업부하(workload)에 따른 성능 비교 : p 예제 참고 반환시간 대기시간 등 CPU 버스트 시간 등 많은 정확한 정보 요구 큐잉 모형(Queueing Models) CPU-I/O 버스트 뿐아니라 프로세스 도착시간의 분포도 평가에 고려해야 도착율과 서비스율 알면 이용율, 평균 큐 길이, 평균대기시간 알 수 있음 Little의 공식 : (평균 큐 길이) = (도착 율) x (평균대기 시간) 모든 경우에 적용가능하나 근사치일 뿐 모의 실험(Simulations) clock variable, system state variables등의 통계 사건 분포는 수학적(균일, 지수, 포아송), 또는 경험적으로 정의 사건 생성 순서 정보 제공 위해 trace tapes 이용 정확하나 비용이 많이 듬 구현(Implementation) 가장 정확하나 비용 많고 사용자 적응이 문제 가장 융통성 있는 스케줄링 알고리즘(flexible scheduling algorithm) tunable scheduling : 시스템 관리자가 스케줄러 변수들을 변경할 수 있음

12 리포트 제출방법 운영체제 5장 isis.inchon.ac.kr 에 접근 $cd ~mysung/osreport
pwd를 사용하여 현재위치를 확인 $mkdir s학번(예:s941111) $cd s941120 (본인ID) 현재 디렉토리는 /home1/prof/mysung/osreport/s941120 <소스파일 copy> $cp ~s941120/checkmail.c checkmail.c (~본인ID) <실행파일 copy> $cp ~s941120/checkmail checkmail $ls -al drwxr-xr-x 2 s 월 31일 20:13 . drwxr-xrwx 3 mysung prof 월 31일 20:03 .. -rwxr-xr-x 1 s 월 31일 20:13 checkmail -rw-r--r s 월 31일 20:13 checkmail.c $chmod 700 * -rwx s 월 31일 20:13 checkmail -rwx s 월 31일 20:13 checkmail.c 위와 같이 나오면 정상적으로 된 것