5 장. CPU 스케줄링 1
목표 multiprogramming 운영체제의기반인 CPU 스케줄링소개 다양한 CPU 스케줄링알고리즘 CPU 스케줄링알고리즘선택을위한평가기준 스케줄링알고리즘사례 2
5.1 기본개념 multiprogramming 의목적 CPU 이용률최대화 CPU-I/O Burst Cycle 프로세스실행은 CPU 실행과 I/O 대기의사이클로구성됨 CPU burst 분포 (see next page) CPU burst I/O burst 3
CPU-burst 시간의분포도 exponential ( e - x ) or hyperexponential distribution I/O bound program a large number of short CPU burst a small number of long CPU burst CPU bound program 4
CPU Scheduler CPU scheduler (short-term scheduler) ready queue 에있는프로세스들중하나를선택하여이프로세스에게 CPU 를할당함 Job Queue 5
CPU Scheduling 시점 CPU scheduling 결정은 process 가다음상황일때발생가능함 1. running 상태에서 waiting 상태로전환 ( 예. I/O wait, child termination wait) 2.running 상태에서 ready 상태로전환. (e.g. time-out) 3. waiting 상태에서 ready 상태로전환. (e.g. I/O completion, event occur) 4. Terminate. 비선점 (non-preemptive) 스케줄링 cooperative 스케줄링 1 번, 4 번경우는선택의여지가없으며, 이경우에만스케줄링 반드시스케줄링하여새프로세스를선택해야함 프로세스는종료하거나 block 될때까지 CPU 를계속점유 ( 예 ) windows 3.x, 예전 Mac OS 선점 (preemptive) 스케줄링 모든경우에스케줄링이가능 (2, 3 번경우포함 ) CPU 독점을방지하거나 (timer 사용 ), 프로세스우선순위를반영하고자할때 2, 3 번의경우 (ready queue 가변화 ) 에스케줄링할수있음 ( 예 ) 대부분의현대 OS 6
Preemptive 스케줄링의문제점과해결책 공유데이터의일관성 (consistence) 유지문제 선점스케줄링방식에서, process 는프로세스는데이터를변경하는도중에다른프로세스에게선점되어변경된데이터를저장하기전에 CPU 를내어놓을수있다. 다수의프로세스가데이터를공유할때에경쟁적으로데이터를변경하면데이터일관성이유지되지않을수가있다. 경쟁조건 해결책 : 공유데이터접근에대한조정이필요 동기화방식 (6 장 ) user mode 에서의 preemption 선점형스케줄링을하는운영체제에서, 한프로세스가데이터를변경하는동안선점되어다른프로세스가같은데이터를읽거나수정한다면, 데이터일관성이유지되지않을수있음 사용자프로그램은운영체제가제공하는동기화방식을사용하여데이터일관성문제가발생하지않도록작성해야한다. 7
Kernel mode 에서의 preemption Kernel mode 에서의공유데이터접근문제 모든커널루틴은커널데이터를공유함 커널은 system call 을통하여요청된프로세스의작업을처리할수있으며, 공유데이터를접근하는커널루틴이실행되는동안에, 인터럽트로인해서다른커널루틴에게선점되면공유데이터일관성유지가되지않을수있다. 커널에서의이러한문제발생은시스템전체에영향을주므로위험함 운영체제커널에서의 preemption 처리방법 비선점형커널 커널내에서의 preemption을허용하지않음 (1) system call이완료되거나 (2) I/O block이발생할때까지기다린후에 context switching을수행 실시간컴퓨팅을지원하는데부적합 선점형커널 커널내에서 preemption 을허용 커널내에서공유데이터접근에대한동기화를사용하여커널을작성해야함 실시간컴퓨팅지원에적합 8
디스패처 (Dispatcher) Dispatcher CPU 의제어권을 CPU 스케줄러가선택한프로세스에게주는모듈 다음작업수행 context 스위칭 CPU 동작모드를 user mode 로전환 선택한프로세스가다시시작하도록, user program 의적절한위치로이동 (jump) Dispatch 지연 (latency) 한프로세스를정지하고, 다른프로세스의수행을시작할때까지소요되는시간 dispatch latency은가능한한작아야함 ( 빠르게동작 ) 9
5.2 Scheduling 기준 (Criteria) CPU 이용률 (utilization) 0 100% (CPU 를가능한한바쁘게유지 ) 처리량 (Throughput ) 단위시간당수행이완료된프로세스 총처리시간 (Turnaround time) 프로세스를실행하는데소요된시간 대기시간 (Waiting time) ready queue 에서대기하는시간 (CPU 실행과 I/O 대기가아닌시간 ) 응답시간 (Response time) 대화형시스템에서요청을한후에 ( 첫번째 ) 응답을받을때까지의소요시간 ( 최종출력을얻는시간이아님 )) 10
최적화기준 스케줄링알고리즘최적화기준 CPU 이용률과처리량 : 최대화 총처리시간, 대기시간, 응답시간 : 최소화 최적화하는값 대부분의경우평균값을최적화 일부경우에는평균값대신에최대값또는최소값을최적화 대화형시스템은, 응답시간의변동폭 (variance) 를최소화 합리적이고예측가능한응답시간제공 11
5.3 스케줄링알고리즘 (Scheduling Algorithm) 선입선처리 (First-Come First-Serve:FCFS) 스케줄링 최단작업우선 (Shortest-Job-First:SJF) 스케줄링 우선순위 (Priority) 스케줄링 라운드로빈 (Round Robin:RR) 스케줄링 다단계큐 (Multilevel Queue) 스케줄링 12
First-Come, First-Served (FCFS) Scheduling Example: Process Burst Time P 1 24 P 2 3 P 3 3 Arrival order: P 1, P 2, P 3 (arrival time t=0) The Gantt Chart for the schedule P 1 P 2 P 3 0 24 27 30 대기시간 : P 1 = 0; P 2 = 24; P 3 = 27 평균대기시간 : (0 + 24 + 27)/3 = 17 13
FCFS Scheduling ( 계속 ) Arrival order: P 2, P 3, P 1. (arrival time t=0) The Gantt chart for the schedule is: P 2 P 3 P 1 0 3 6 30 대기시간 : P 1 = 6;P 2 = 0 ; P 3 = 3 평균대기시간 : (6 + 0 + 3)/3 = 3 이전의경우보다더좋음 호위효과 (Convoy effect) 긴프로세스뒤에짧은프로세스들이있는경우에짧은프로세스는긴프로세스의 CPU busrt가끝날때까지기다려야함 짧은프로세스들이먼저처리되도록할때보다 CPU와장치이용률이저하됨 14
Shortest-Job-First (SJF) Scheduling 최단작업우선 (SJF) 스케줄링 Shortest Process Next(SPN), Shortest Request Next(SRN) 라고도함 프로세스는다음 CPU burst 길이가연관되며최단다음 CPU burst 를갖는프로세스를스케줄링 문제점 : 다음 CPU burst 를알기어려움 해결책 : 예측 (prediction) 두가지방식의 SJF 스케줄링 비선점 SJF process 는 CPU burst 를끝낼때까지선점되지않음 선점 SJF ( 새프로세스의 CPU burst < 현재프로세스의잔여시간 ) 이면현재프로세스가선점되어스케줄링 Shortest-Remaining-Time-First (SRTF). preemptive SJF = SRTF SJF 는대기시간이최적임 최소평균대기시간을제공. 15
( 예 ) Non-Preemptive SJF Example Process Arrival Time Burst Time P 1 0.0 7 P 2 2.0 4 P 3 4.0 1 P 4 5.0 4 SJF (non-preemptive) P 1 P 3 P 2 P 4 0 2 4 5 7 8 12 16 P 1 P 2 P 3 P 4 평균대기시간 = (0 + 6 + 3 + 7)/4 = 4 16
( 예 ) Preemptive SJF Example Process Arrival Time Burst Time P 1 0.0 7 P 2 2.0 4 P 3 4.0 1 P 4 5.0 4 SJF (preemptive) P 1 P 2 P 3 P 2 P 4 P 1 0 2 4 5 7 11 16 P 1 P 2 P 3 P 4 평균대기시간 = (9 + 1 + 0 +2)/4 = 3 17
다음 CPU Burst 길이예측 다음 CPU Burst 길이를미리알수없음 해결책 : 다음 CPU Burst 길이예측 이전 CPU Burst 길이를사용하여다음 CPU Burst 길이를예측 가정 : 다음 CPU Burst 길이는이전의값과비슷할것이다. 예측값 : 지수평균 (exponential average) 사용 다음예측값 = n ( 이전예측값 ) 과 t n ( 이전 CPU Burst) 의지수평균 n 1 t n 1 n initial 0 : 상수또는전체평균으로정의 1. 2. 3. 4. t n n 1, 0 actual length of 1 Define : n 1 t n n predicted value for the next CPU th CPU burst n 1 burst 18
지수평균 지수평균의예 =0: n+1 = n 최근값을고려하지않고, 이전예측값사용 =1: n+1 = t n 최근값만사용하고, 이전예측값사용하지않음. 일반적으로 =1/2 최근값과이전예측값의평균을사용 0, (1 - ) 1 n+1 은 n 또는 t n 보다가중치가작다. 지수평균식확장 n+1 = t n +(1- ) t n-1 + +(1- ) j t n-j + +(1- ) n t o +(1- ) n+1 0 19
Next CPU Burst 길이예측 actual burst prediction 20
우선순위 (Priority) Scheduling 우선순위스케줄링 프로세스는우선순위번호와연관됨 대개우선순위가높을수록작은우선순위번호를가짐 CPU는가장높은우선순위를가진프로세스에게 CPU를할당 우선순위정의에고려되는요인 내부적 : 시간제한, 메모리요구, open file 수, I/O와 CPU의비율등 외부적 : 프로세스중요성, 비용의유형과액수, 정치적요인등 두가지방식의Priority Scheduling 선점, 비선점 SJF 스케줄링은 priority 스케줄링의특별한경우임 priority = 다음 CPU burst time의예측값 ( 작을수록높은우선순위 ) 문제점 : 기아상태 (starvation)/ 무한봉쇄 (indefinite blocking) 낮은우선순위의 process가무한히대기하여수행되지못할수있음 해결책 노화 (aging) 오랫동안대기하는 process는우선순위를점진적으로증가시킴 21
Priority Queueing 22
Round Robin (RR) Scheduling Round Robin 스케줄링 시분할시스템을위해서설계됨 CPU 공유 각프로세스에게작은양의 CPU 시간 (time quantum) 할당 크기 : 대개 10-100 msec 실행프로세스는이시간경과후선점되어 ready queue 의끝으로이동 타이머인터럽트사용 최대대기시간 n개의 ready process가존재하고, time quantum q 일때 max. waiting time = (n-1)q 성능 q large FIFO (FCFS) 와같게됨 q s q small q 가 context switch time 에비해서는커야함. 그렇지않으면 switching overhead 가너무크게됨. 시간할당량 (time quantum) 을정하는경험법칙 전체 CPU burst time 의 80% 정도가 quantum time 보다짧도록정함 23
예 : RR 스케줄링 (Time Quantum = 20) Example Process Burst Time P1 53 P2 17 P3 68 P4 24 The Gantt chart is: P 1 P 2 P 3 P 4 P 1 P 3 P 4 P 1 P 3 P 3 0 20 37 57 77 97 117 121 134 154 162 성능 SJF 보다는평균총처리시간 (turnaround time) 이더크다. 응답시간 (response time) 이더짧다. 24
Time Quantum 과 Turnaround Time 의관계 time quantum 크기가증가함에따라서평균총처리시간이반드시개선되는것은아니다. 1 2 3 4 5 6 7 1 2 3 4 1 2 4 1 2 4 1 4 1 4 1 4 4 for q=1, turnaround time = (3+9+15+17)/4 =44/4=11 25
다단계큐스케줄링 다단계큐 (Multilevel Queue) 스케줄링 Ready queue 가여러개의큐로분할됨 각큐는자신의스케줄링알고리즘사용 ( 예 ) foreground (interactive) 용큐 RR background (batch) 용큐 FCFS 스케줄링은큐들간에도있어야함 고정우선순위스케줄링 ( 예 ) foreground 작업을모드처리한후에 background 작업을수행 기아상태 (starvation) 가능성 Time slice 각큐마다 CPU 사용량 / 비율을정해서할당 ( 예 ) foregound 큐에 80%, background 큐에 20% 할당 26
( 예 ) 다단계큐의예 27
다단계피드백 (Multilevel Feedback) 큐스케줄링 다단계큐스케줄링은 process 생성시에하나의 queue에영구할당 다단계피드백큐스케줄링 process가여러큐들사이의이동하는것을허용함 aging 구현 다단계피드백큐스케줄러의매개변수 큐개수 각큐에대한스케줄링알고리즘 큐승급 / 강등시점 진입할큐결정방법 highest queue upgade 시점 새 ready process lowest queue demote 시점 28
( 예 ) 다단계피드백큐 I/O bound or Interactive processes Q 0 RR (high priority) Q 1 RR CPU bound or Batch processes Q 2 Example: 새작업 => queue Q 0 (q=8, FCFS) 8 ms 내에끝나지않으면 => queue Q 1. (q=16, FCFS) 추가 16ms 내에끝나지않으면 => queue Q 2. priority: Q 0 > Q 1 > Q 2 Q 2 에있는프로세스는 Q 0 and Q 1 이비어있을때에만수행됨 작업특성에따라서큐의작업들이자동적으로분류됨 29
5.4 Thread 스케줄링 Thread 스케줄링 운영체제는 kernel-level thread들을스케줄링 user-level 스케줄링은 thread library에의해서수행됨 스케줄링경쟁범위 (contention scope) 프로세스경쟁범위 (Process-contention scope: PCS) user-level thread를가용lwp 상에스케줄링 (CPU스케줄링아님 ) 같은 process의 thread들간에스케줄링경쟁 many-to-one 또는 many-to-many 맵핑모델에서사용 시스템경쟁범위 (System-contention scope:scs) 커널이 kernel-level thread들을 CPU 스케줄링 system의모든thread들간에스케줄링경쟁 one-to-one 맵핑모델에서사용 Pthread 스케줄링정책 thread 생성시에지정허용 PTHREAD_SCOPE_PROCESS: PCS scheduling (many-to-many) PTHREAD_SCOPE_SYSTEM: SCS scheduling (one-to-one) 30
Pthread 스케줄링 API 사용예 일부시스템에서는특정 contention scope 값만허용됨 31
5.5 다중프로세서스케줄링 다중프로세서 (Multiple-processor) 스케줄링 여러개의 CPU 가있는경우에는 CPU 스케줄링이더복잡해짐 여기서는모든프로세서가동일한 (homogeneous) 시스템을가정함 다중프로세서스케줄링접근방법 비대칭 (Asymmetric) 다중처리 한프로세서 (master processor) 가스케줄링, 입출력처리, 시스템활동을처리 ( 운영체제커널수행 ) 나머지프로세서들은 user code 만수행함 자료공유필요성을배제하므로간단한설계 대칭 (Symmetric) 다중처리 (SMP) 각프로세서는독자적으로스케줄링 (self-scheduling) ready queue 공동큐 모든프로세서가함께사용 ( 자료공유문제 ) 분리큐 프로세서마다분리된자신의큐를사용 ( 자료공유배제 ) 거의모든현대운영체제에서사용 32
프로세서친화성 (Affinity) 프로세서친화성 (Processor Affinity) process 가현재실행중인프로세서에서다른프로세서로의이주 (migration) 를피하고다음스케줄링에서도현재프로세서에서계속실행을시도하는것 프로세서를이동하면캐쉬무효화와채우기를해야하므로비용이증가 프로세서친화성형태 연성친화성 (soft affinity) 프로세서지정하지않음. 이주가능 강성친화성 (hard affinity) 프로세서 ( 집합 ) 을지정. 시스템의형태 ( 특히주메모리구조 ) 가프로세서친화성에영향을줌 NUMA(non-uniform memory access) 시스템과 CPU 스케줄링 affinity a process allocated 33
부하균등화 (Load Balancing) 부하균등화 (Load balancing) 모든프로세서들간에부하 ( 작업 ) 가고르게배분하려는시도 공통큐를갖는시스템에서부하균등화는불필요 분리된개인큐를갖는시스템의부하균등화방식 push migration 특정 task 가주기적으로각프로세서의부하를검사 과부하프로세서가발견되면 process 들을 idle 또는 less-busy 프로세서로이주시킴 pull migration idle processor 가 busy processor 에서대기중인 process 들을자신에게로이주시킴 두방식은배타적이아니며, 함께사용할수있음 Linux 는 200ms 마다 push 이주알고리즘을, ready queue 가비게되면 pull 이주알고리즘을수행하여부하균등화시도 부하균등화는프로세서친화도의장점과상충됨 34
멀티쓰레드프로세서 멀티쓰레드 (Multithreaded) 프로세서 하나의물리적프로세서 (core) 에다수의논리적프로세서를제공하는프로세서. 연산장치를공유 논리적프로세서는별도의레지스터집합을가짐 빠른 context 전환 메모리접근동안연산장치를다른논리프로세서가이용함 하드웨어가논리프로세서에게물리프로세서를스케줄링 single threaded processor multithreaded processor 35
멀티코어프로세서 멀티코어 (Multicore) 프로세서 같은칩에다수의프로세서 (multi-threaded) 코어를보유한프로세서 a multithreaded multicore processor 멀티코어프로세서스케줄링 운영체제 thread 에게논리프로세서 (hardware thread) 를스케줄링 coarse-grained multithreading CPU 하드웨어 hardware thread 에게 core 를스케줄링 fine-grained multithreading 운영체제가이러한시스템에서수행하는것을알고있다면알맞은스케줄링알고리즘을사용할수있음 성능향상 36
5.6 실시간스케줄링 생략 37
5.7 운영체제사례 Linux scheduling Windows scheduling Solaris scheduling 38
Linux 스케줄링 예전버전 kernel version 2.5 이전 표준 UNIX scheduling algorithm 의변형을사용 SMP systems 을위한적절한지원을제공하지않음 task 수가증가함에따라서성능이저하됨 규모확장성부족 kernel version 2.5/2.6 : 상수시간에실행. O(1) scheduling time O(1) scheduling time - task 수와관계없음. SMP 에대한향상된지원 프로세서친화도, 부하균등화기능포함 선점형, 우선순위기반스케줄링 두가지우선순위영역 낮은값이높은우선순위 real-time: a real-time range (0-99) 0 : the highest priority time-sharing: a nice value (100-140) 다른 OS 와같지않게, 우선순위가높을수록큰 time quantum 을부여 39
Linux 스케줄링 v2.5/2.6 ( 계속 ) Epoch 기반스케줄링 time slice 가남아있으면 task 는실행가능 (runnable) active time slice 가남아있지않으면, 다른 task 가그들의 time slice 를모두사용할때까지실행가능하지않음. expired 모든 runnable tasks 는 per-cpu runqueue 자료구조로관리함 Two priority arrays active, expired ( 그림참조 ) 우선순위를 index 로사용하여 active array 가참조됨 active task 가없으면, active 와 expired 배열을서로교환함 잘동작하지만 interactive process 의응답시간이느림 40
Linux 스케줄링 - Version 2.6.23+ Completely Fair Scheduler(CFS) 완전공평스케줄러 스케줄링클래스 각 task 는특정우선순위가짐 스케줄러는가장높은클래스에서가장우선순위가높은 task 선택 고정된양의 time quantum 대신에우선순위 (nice값) 에따라서 CPU 시간비율을결정 두개의스케줄링클래스, 다른클래스도추가가능 default CFS 스케줄링 real-time Time quantum 계산 -20 부터 +19 까지의 nice value 를기반으로계산 (-20 이높은우선순위 ) target latency 계산 모든수행가능한 task 가최소한번실행할수있는시간간격. CPU 시간비율은 target latency 값으로부터할당됨 target latency 는 default 값과최소값을가지며 active task 의수가임계값이상으로증가하면 target latency 가증가할수있음 41
Linux 스케줄링 - Version 2.6.23+ ( 계속 ) CFS 스케줄러는 task 별로가상실행시간 (virtual run time) 을관리 변수 vruntime 사용 task 의우선순위에따라감쇠지수 (decay factor) 와정해짐 낮은우선순위가감쇠율이높음 ( > 1) 보통우선순위작업 : 가상실행시간 = 실제실행시간 낮은우선순위작업 : 가상실행시간 > 실제실행시간 높은우선순위작업 : 가상실행시간 < 실제실행시간 가장작은가상실행시간을갖는 task 를선택하여스케줄링 ready 상태의 task 들은 vruntime 을 key 값으로하여이진균형트리인 red-black tree 로관리 빠른탐색 (O(logN) 연산 ) I/O 중심작업 CPU 중심작업 42
Windows 스케줄링 a priority-based, preemptive 스케줄링 Windows 우선순위 variable class: 1-15 priority class relative priority within each of the priority classes time quantum 만료 우선순위낮아짐 wait 해제 우선순위높여줌 (wait 이유에따라서증가정도가다름 ) foreground process가 background process보다더높은우선순위 (3배) 43
Solaris 스케줄링 우선순위기반스케줄링 6개의스케줄링클래스 1. time sharing (TS) default scheduling class 2. interactive (IA) window applications 3. real time (RT) real-time processes 4. system (SYS) kernel threads (e.g. scheduler, paging daemon) 5. fair share (FSS) introduce with Solaris 9 6. fixed priority (FP) 각클래스마다다른우선순위, 다른스케줄링알고리즘존재 Time sharing class 다단계피드백큐스케줄링을사용하여동적으로 priority 변경하고다른길이의 time slice 를할당 interactive process higher priority, smaller time slice (response) CPU-bound processes lower priority, larger time slice (throughput) 전역우선순위 클래스고유의우선순위를전역우선순위로바꾸어서스케줄링 44
Solaris scheduling (cont') 실시간프로세스 높은우선순위, 응답시간보장 우선순위고정 기본스케줄링클래스 프로세스집합 (project 라고불림 ) 에할당 우선순위대신에 CPU 공유량 (share) 사용 윈도우응용용 ( 더나은성능 ) 45
Solaris Dispatch Table new priority TS 와 IA class ms time quantum expired: priority 를낮춤 return from sleep: priority 를높임 inverse relationship 46
5.8 스케줄링알고리즘평가 특정시스템을위한알고리즘선택방법 알고리즘선택기준정의 알고리즘평가 평가방법 결정론적 (Deterministic) 모델 : 특정한미리정의된부하사용 Queueing 모델 : 부하를확률분포로기술 Queueing network의수학적분석 시뮬레이션 : 시스템모델을프로그래밍하는작업포함 부하 : (1) by random-number generator (2) trace tape 구현 (Implementation) 실제부하사용 47