Module 6: CPU Scheduling

Size: px

Start display at page:

Download "Module 6: CPU Scheduling"

진희 금
5 years ago
Views:

1 Chapter 5: CPU Scheduling Operating System Concepts 8 th Edition, Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2009

2 Chapter 5: Process Scheduling Basic Concepts Scheduling Criteria Scheduling Algorithms Thread Scheduling Multiple-Processor Scheduling Operating Systems Examples Algorithm Evaluation 2/50

3 Objectives 멀티프로그래밍 OS 의기본이되는 process scheduling 의개념 각종 process-scheduling algorithm 이상적인알고리즘은? process-scheduling algorithm 을선전하기위한평가방법 3/50

4 Basic Concepts 프로세스스케줄링 장기 job scheduling, 단기 CPU scheduling, 중기 swapping CPU-I/O 버스트주기 (burst cycle)» cycle : CPU 실행 (CPU burst) I/O 대기 (I/O burst)» CPU burst 유형 CPU 스케줄러 I/O bound program : 많은짧은 CPU burst 가짐 CPU bound program : 적은아주긴 CPU burst 가짐» 단기스케줄러 (short-term scheduler) : ready queue 에서선택 FIFO(First-In First-Out) 큐 우선순위큐, 트리, 연결리스트 Burst CPU Burst : Time it takes for the CPU to execute an operation I/O Burst : Time it takes for the CPU to wait for I/O task Goal of processor scheduling : Maximum CPU utilization obtained with multiprogramming 4/50

5 CPU burst vs. IO burst (a) A CPU-bound process (b) An I/O-bound process 5/50 5

6 Alternating Sequence of CPU And I/O Bursts 6/50

7 Histogram of CPU-burst Times 7/50

CPU 스케줄링 (CPU Scheduling) CPU scheduling란대기중인프로세스들ㄷ중에서하나를선택하고 CPU를할당하는절차 선점 / 비선점스케줄링 (Preemptive/Non-Preemptive Scheduling) 선점 (preemptive) 스케줄링 특수하드웨어 (timer) 필요, 공유데이터에대한프로세스동기화필요 Windows95~,

8 CPU 스케줄링 (CPU Scheduling) CPU scheduling란대기중인프로세스들ㄷ중에서하나를선택하고 CPU를할당하는절차 선점 / 비선점스케줄링 (Preemptive/Non-Preemptive Scheduling) 선점 (preemptive) 스케줄링 특수하드웨어 (timer) 필요, 공유데이터에대한프로세스동기화필요 Windows95~, MacxOS8(Power PC)~ 비선점 (non preemptive) 또는협조적 (cooperative) 스케줄링 MS-Windows, 특수하드웨어 (timer) 없음, 종료또는 I/O까지계속 CPU점유 ~Windows 3.x, ~MacOS8 이전버전 Kernel의선점처리 case 1( 초기 Unix) : system call 완료또는 I/O 완료할때까지기다렸다가문맥교환 실시간컴퓨팅, 멀티프로세싱에나쁨 case 2( 대부분의 Unix) : interrupt 중다른 interrupt enable( 우선순위에따라 ) 선점처리 critical section( 공유데이터수정하는코드부분 ) 에있는동안 interrupt disable 해야함 CPU scheduling decision time 1. running waiting : non preemptive 2. running ready (interrupt) : preemptive 3. waiting ready (I/O 완료 ) : preemptive 4. halt : non preemptive 8/50

9 CPU 스케줄링 (CPU Scheduling) 분배기 (Dispatcher) : 단기스케줄러가선택한프로세스에서 CPU 의제어을넘기고다음의작업을담당한다. 문맥교환 사용자모드로전환 프로그램의적절한위치로점프하여프로그램재시작 dispatch latency( 분배기가한프로세스를종료시키고다음프로세스를실행시킬때까지의시간 ) 가짧아야함 Scheduling Criteria 이용률 (CPU utilization) : 40% ~ 90% 처리율 (throughput) : 처리된프로세스개수 / 시갂단위 반환시갂 (turnaround time) : 프로세스가 system in system out 걸린시갂 대기시갂 (waiting time) : ready queue 에서기다린시갂 응답시갂 (response time) : 대화형시스템에서첫응답까지의시갂 9/50

10 Scheduling Algorithm 척도 : 평균대기시간 (average waiting time) 단일프로세서알고리즘 1. 선입선처리 (First-Come, First-Served) 스케줄링 2. 최소작업우선 (Shortest-Job-First) 스케줄링 3. 우선순위 (Priority) 스케줄링 4. 순환할당 (Round-Robin) 스케줄링 5. 다단계큐 (Multilevel Queue) 스케줄링 6. 다단계귀환큐 (Multilevel Feedback Queue) 스케줄링 스레드스케줄링 (Thread scheduling) 다중프로세서스케줄링 (Multiple-Processor Scheduling) 실시간스케줄링 EDF (Earliest Deadline First) Rate Monotonic Rate Monotonic vs. EDF 실례 : Solaris 2 Scheduling, Windows XP Scheduling, Linux Scheduling 10/50

11 Scheduling Algorithm 1. 선입선처리 (First-Come, First-Served) 스케줄링 들어온순서대로처리, e.g. supermarket, bank tellers, McDonalds, etc FIFO queue : First-in tail, First-out head 호위효과 (convoy effect) : 큰 job 하나가끝나기를모두기다림 (CPUbound process 가끝나기를 I/O bounded process 들이기다림 ) non-preemptive 임 (time-sharing 에서는곤란 ) Jobs are treated equally: no starvation 11/50

12 예 )First-Come, First-Served (FCFS) Scheduling 예 1 FCFS: Process Burst Time P 1 24 P 2 3 P 3 3 프로세스들이 P 1, P 2, P 3 순으로도착한다면스케줄을위한트차트 (Gantt Chart): P 1 P 2 P 대기시간 (Waiting time) for P 1 = 0; P 2 = 24; P 3 = 27 평균대기시간 (Average waiting time): ( )/3 = 17 12/50

13 FCFS Scheduling (Cont) 예 2) 프로세스도착순서가 P 2, P 3, P 1 이면 스케줄을위한간트차트 (Gantt chart) 는 : P 2 P 3 P 대기시간 (waiting time) for P 1 = 6; P 2 = 0 ; P 3 = 3 평균대기시간 (average waiting time): ( )/3 = 3 Much better than previous case! 호위효과 (Convoy effect): short process behind long process 13/50

14 Scheduling Algorithm 2. 최소작업우선 (Shortest-Job-First) 스케줄링 Shortest Next CPU Burst Scheduling 다음 CPU burst 시간이가장짧은프로세스를먼저실행시킨다. 두가지스케줄링기법 non-preemptive SJF preemptive SJF = Shortest Remaining Time First Scheduling 최적 (Optimal) 단점 : 기아상태 (starvation) long-term scheduling 에좋음 프로세스시간의사용자예측치이용 short-term scheduling 에는덜좋음 차기 CPU burst 시간파악이어려워서 차기 CPU 버스트시간예측모델 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 였음 14/50

15 비선점형 SJF(Example of Non-Preemptive SJF) 예 NP-SJF Process Arrival Time Burst Time P P P P SJF (non-preemptive) Average waiting time = ( )/4 = 4 P1 0=0-0 P2:8-2.0=6 P3:7-4.0=3 P4:12-5.0=7 0: P1(7) =>P1(7) p1(7) ~ 7:P2(4),P3(1),P4(4) => P3(1) p3(1) ~ 8: P2(4),P4(4) =>P2(4) p2(4) ~ 12:P4(4)=>P4(4) p4(4) ~ /50

16 선점형 SJF(Example of Preemptive SJF) 예 P SJF Process Arrival Time Burst Time P P P P SJF (preemptive) (= SRTF) Average waiting time = ( )/4 = 3 P1: =9 P2: =1 P3=4-4.0=0 P4:7-5=2 0 : P1(7) =P1(7) P1(7) ~ 2.0 p2(4) : P1(5), p2(4) => p2(4) P2(4) ~ 4.0 p3(1) : p1(5), p2(2), p3(1) => p3(1) P3(1) ~ 5.0 p4(4) : p1(5),p2(2), p4(4) =>P2(2) P2(2) ~ 7.0 : p1(5),p4(4) =>P4(4) p4(4) ~ 11.0 : P1(5) =>P1(5) p1(5) ~ 16.0 : 16/50

17 ( 예 ) SJF 스케줄링 연습문제 non-preemptive / preemptive SJF Process Burst Time P 1 24 P 2 3 P 3 2 프로세스들이 P 1, P 2, P 3 순으로도착한다면스케줄을위한간트차트 (Gantt Chart)? 0 대기시간 (Waiting time) for P 1 = ; P 2 = ; P 3 = 평균대기시간 (Average waiting time): ( + + )/3 = 17/50

18 Determining Length of Next CPU Burst 다음의 CPU burst 시간을예측 이전 CPU 버스트시간들의지수적편균 (exponential averaging) 으로예측가능 th 1. t n actual length of n CPU burst 2. n 1 predicted value for the next CPU burst 3., Define : n 1 tn n 1. 18/50

19 Prediction of the Length of the Next CPU Burst 10, 0.5, t 0 t t 1 t *6 0.5* *4 0.5* *6 0.5*6 6 19/

20 Scheduling Algorithm 3. 우선순위 (priority) 스케줄링 높은우선순위의프로세스를먼저 ready queue : priority queue FCFS : equal priority(non-priority) SJF : priority : Preemptive,nonpreemptive proirity 에영향을미치는 OS 내부요인 시간제한 (time limit), 메모리요구량, 오픈화일수,(average I/O burst)/(average CPU burst) 비율등 proirity 에영향을미치는 OS 외부요인 프로세스의중요도, 컴퓨터사용료형태와금액, 작업부서, 정치적요인등 무한정지 (blocking) 또는기아상태 (starvation) Aging : 재기시간이길어지면우선순위를높여준다. P184 예제 20/50

21 Priority Scheduling Abstractly modeled as multiple priority queues Put ready job on Queue associated with its priority 21/50

22 Scheduling Algorithm 4. 순환할당 (Round Robin,RR) 스케줄링 FCFS +preemptive scheduling circular ready queue (FIFO) time quantum : 프로세스가 cpu 를사용하느시간보통 milliseconds. Performance quantum -> : FIFO quantum -> 0 : processor sharing If small, then context switches are frequent incurring high overhead (CPU utilization drops) If large, then response time drops A rule of thumb: 80% of the CPU bursts should be shorter than the time quantum 22/50

23 Example of RR with Time Quantum = 4 Process Burst Time P 1 24 P 2 3 P 3 3 The Gantt chart is: 평균대기시간 (average waiting time): (?+?+?) / 3 =? 평균반환시간 (average turnaround) : ( ) / 3 = 15.6 일반적으로 SJF보다평균반환시간 (average turnaround) 은길지만 응답시간 (response time) 은짧다. queue : p1(24),p2(3),p3(3) 0 : p1(24) : p2(3),p3(3) timer 4:p2(3) : p3(3),p1(20) release 7 : p3(3) : p1(20), release 10:p1(20) : timer 14:p1(16): timer 18:p1(12): timer 22:p1(8): timer 26:p1(4): timer 30: * lease :non-preempted, timer : preempted P 1 P 2 P 3 P 1 P 1 P 1 P 1 P 1 23/50

24 ( 예 ) RR with Time Quantum = 20 예 ) RR Process Burst Time P 1 53 P 2 17 P 3 68 P 4 24 The Gantt chart is: P 1 P 2 P 3 P 4 P 1 P 3 P 4 P 1 P 3 P 평균대기시간 (average waiting time) = (? +? +? +? )/4 =? 평균반환시간 ( average turnaround) = (? +? +? +? )/4 =? 24/50

25 Time Quantum and Context Switch Time 25/50

26 Turnaround Time Varies With The Time Quantum At Q2=5, turnaround time=?+?+?+?= /50

27 Scheduling Algorithm 5. 다단계큐 (Multilevel Queue) 스케줄링 각프로세스는우선순위가다른여러개의큐중하나에영원히할당 ( 그림 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 스케줄링부담적으나융통성이적음 27/50

28 Multilevel Queue Scheduling(Fig.5.6) 28/50

29 Scheduling Algorithm 6. 다단계피드백큐 (Multilevel Feedback Queue) 스케줄링 프로세스가여러큐사이를이동 ( 그림 5.7) 짧은프로세스 (I/O bound, interactive processes) 가우선 긴프로세스는자꾸낮은큐로이동 aging( 오래기다리면우선순위높여기아상태예방 ) preemptive 임 ( 큐사이 ) the most sophisticated, the most complex 가장일반적 => 해당시스템에맞게설정해야 (configure) 큐의개수 각큐의스케줄링알고리즘 높은우선순위로올려주는시기 낮은우선순위로내려주는시기 어느큐에들어갈것인가 29/50

30 Scheduling Algorithm Three queues: Q0 time quantum 8 milliseconds Q1 time quantum 16 milliseconds Q2 FCFS Scheduling FCFS queue Q0 에새로들어온작업이 8 milliseconds 동안 CPU 를받고도작업이끝나지않으면선점되어 queue Q1 으로이동 Q1 의작업은 FCFS 로 16 additional milliseconds 을받고그래도끝나지않으면선점되어 queue Q2 로이동 30/50

31 2 스레드지원수준 User level: process local scheduling Thread Scheduling threads library 가사용가능한 LWP 에 thread 를할당 ( 실제로 CPU 차지했다는뜻아님 ) Kernel level: system global scheduling kernel 이다음실행할 kernel thread 를결정 (CPU 차지 ) pthread scheduling 프로세스 - 경쟁 - 범위 (process-contention scope; PCS): pthread library 가사용가능한 LWP 에 user-level thread 할당, CPU 차지하기위한투쟁이한프로세스내에서일어남 PTHREAD_SCOPE_PROCESS many-to-many mapping 시스템 - 경쟁 - 범위 (system-contention scope; SCS): kernel 이 CPU 차지할 kernel thread 결정, CPU 차지위한투쟁이전체시스템에서일어남 (Linux, Mac OS 는시스템 - 경쟁 - 범위만지원 ) pthread IPC PTHREAD_SCOPE_SYSTEM one-to-one mapping pthread_attr_setscope(pthread_attr-t *attr, int scope) pthread_attr_getscope(pthread_attr-t *attr, int *scope) 스레드매핑모델별적용 many-to-many 또는 many-to-one: PCS & SCS one-to-one: SCS 맊사용 (Linux, Windows XP, Solaris 9) 31/50

32 Pthread Scheduling API for POSIX #include <pthread.h> #include <stdio.h> #define NUM THREADS 5 int main(int argc, char *argv[]) { int I, scope; pthread_t tid[num THREADS]; pthread_attr_t attr; /* get the default attributes */ pthread_attr_init(&attr); /* first inquire on the current scope */ if (pthread_attr_getscope(&attr, &scope)!= 0) printf(stderr, Unable to get scheduling scope\n ); else { if (scope == PTHREAD_SCOPE_PROCESS) pritnf( PTHREAD_SCOPE_PROCESS ); else if (scope == PTHREAD_SCOPE_SYSTEM) pritnf( PTHREAD_SCOPE_SYSTEM ); else printf(stderr, Illegal scope value.\n ); } } /* set the scheduling algorithm to PCS(PROCESS) or (SCS)SYSTEM */ pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM); /* set the scheduling policy - FIFO, RT, or OTHER pthread_attr_setschedpolicy(&attr, SCHED OTHER); */ /* create the threads */ for (i = 0; i < NUM_THREADS; i++) pthread_create(&tid[i],&attr,runner,null); /* now join on each thread */ for (i = 0; i < NUM THREADS; i++) pthread_join(tid[i], NULL); /* Each thread will begin control in this function */ void *runner(void *param) { } /* do some work */ printf("i am a thread\n"); pthread exit(0); 32/50

33 다중프로세서스케줄링 (Multiple-Processor Scheduling) 동종다중프로세서 (homogeneous multiprocessor) 프로세서는큐에있는어떤프로세스 (any processes) 든실행 : 부하공유 (load sharing) 별도준비큐 (separate ready queue): unfair SMP 경우 load balancing 필요할까? 공동준비큐 (common ready queue): fair SMP 경우 load balancing 필요할까? AMP(Asymmetric Multiprocessing): 비대칭적스케줄링 (asymmetric scheduling) 한프로세서 (master) 가다른프로세서 (slaves) 스케줄링 master server : all system activity, client processors: user code only master 만 kernel system data structure 에접근가능 공유자료구조접근동기화필요없어처리가간단 SMP(Symmetric Multiprocessing): 대칭적스케줄링 (symmetric scheduling) 각프로세서가스스로스케줄링 (self-scheduling) 공유자료구조접근에대한세심한처리필요 대부분의현대 OS 가지원 : Windows XP, Windows 2000, Solaris, Linux, Max OS X 처리기친근성 (processor affinity): 한프로세서에서작업하면 cash hit-ratio 높아져효율적 약한친화성 (soft affinity): 친근노력하나프로세스이주 (process migration) 발생가능 강한친화성 (hard affinity): 절대친근보장, 이주불허도가능 ( 예, Linux 에서시스템호출로요청 ) 부하균형 (load balancing): 별도준비큐경우일부담의균등분배 push migration: 과부하프로세서가자신의프로세스를노는프로세서로이주시킴 pull migration: 노는프로세서가바쁜프로세서에서대기중인프로세스를끌어옴 Linux scheduler 는 push & pull 모두지원 이종다중프로세서 (heterogeneous multiprocessor) = 분산시스템 컴파일된프로세스들의기계어가실행하고자하는프로세서의기계어와동일한경우만실행가능 33/50

34 다중프로세서스케줄링 (Multiple-Processor Scheduling) Symmetric multithreading(smt) Hyperthreading technology in Intel company OS offers logical processor to each thread 34/50

35 다중프로세서스케줄링 (Multiple-Processor Scheduling) SMP(Symmetric Multiprocessing) Architecture 35/50

36 다중프로세서스케줄링 (Multiple-Processor Scheduling) NUMA (Non-Uniform Memory Access and CPU Scheduling 같은보드에있는 CPU 의메모리접근시갂이더적은경우강한친화성 (affinity) 36/50

다중프로세서스케줄링 (Multiple-Processor Scheduling) 멀티코어프로세서 (Multicore Processors) 최근추세는하나의칩에다수의프로세서를위치시킴 빠르고파워소모적음 각코어가독자적으로다중스레드처리하는추세 멀티스레디드프로세서코어 (multithreaded processor cores) 메모리의데이터가사용가능할때까지상당한메모리지연

37 다중프로세서스케줄링 (Multiple-Processor Scheduling) 멀티코어프로세서 (Multicore Processors) 최근추세는하나의칩에다수의프로세서를위치시킴 빠르고파워소모적음 각코어가독자적으로다중스레드처리하는추세 멀티스레디드프로세서코어 (multithreaded processor cores) 메모리의데이터가사용가능할때까지상당한메모리지연 (memory stall) 시간이있음을발견, 하나의코어에 2 개이상의하드웨어스레드를할당하여메모리지연시간을최대한활용 Intel Itanium: dual-threaded dual-core system = 4 logical processors, urgency(0~7) hardware thread scheduling UltraSPARC T1 CPU: 8 cores * 4 hardware threads per core = 32 logical processors, simple RR hardware thread scheduling Memory stall (fig.5.10) Multithread multicore system(fig. 5.11) 37/50

38 다중프로세서스케줄링 (Multiple-Processor Scheduling) A Dual-Core Design 38/50

39 사례 운영체제사례 (Operating System Examples) Solaris scheduling,windows XP scheduling, Linux scheduling Solaris 2 scheduling 우선순위기반스레드스케줄링 (priority-based process scheduling) 6 classes (OSC version 8) (TS) 시분할 (time sharing): default class multi-level feedback queue scheduling 우선순위가높을수록, time slice(20ms) 작고, 우선순위가낮을수록 time slice(200ms) 큼 CPU-bound processes 우선순위낮아짐 sleep 에서복귀한스레드는높은우선순위 (IA) 대화형 (interactive) multi-level feedback queue scheduling windowing application 에높은우선순위 (RT) 실시간 (real time): 최상위우선순위 (SYS) 시스템 (system): 우선순위결정된후불변 (FSS) 공평공유 (fair share): CPU 공유량을기준으로스케줄 (FP) 고정우선순위 (fixed priority): 시분할스레드와같은우선순위이나고정 Scheduler 가 class-specific priorities 를 global priorities 로변환 우선순위같을때는 round-robin 수행중인 thread 가멈추는경우 blocks time slice 완료 더높은우선순위의 thread 가선점 (preempt) 39/50

40 Solaris 2 Scheduling 40/50

41 Solaris 2 Scheduling = 대화형과시분할스레드를위한 Solaris 디스패치테이블 (Solaris Dispatch Table for time-sharing and interactive threads) Low (ms) high Solaris & Windows XP: 높은우선순위프로세스에짧은 time quantum 할당 41/50

Windows XP Scheduling Windows XP Priorities priority class 불변 가변 가변가변가변 가변 relative priority base priority=normal 32-level priority scheme 0: memory management 1~15: variable class 16~31: real-time

42 Windows XP Scheduling Windows XP Priorities priority class 불변 가변 가변가변가변 가변 relative priority base priority=normal 32-level priority scheme 0: memory management 1~15: variable class 16~31: real-time class 각우선순위마다하나의큐가짐 (a queue for each scheduling priority) idle thread: ready thread 없을때 dispatcher 가실행 보통 NORMAL_PRIORITY_CLASS, base priority=normal 1 time quantum 받은후우선순위낮아짐 대화형스레드 (interactive threads ) 에좋은응답시갂 (response times) 제공» priority boost( 인상 ): keybord I/O boost > disk I/O boost» 스크린에서활성화된전위프로세스 (foreground process) 에게활성화되지않은후위프로세스 (background process) 보다 3 배많은 time quantum 부여 42/50

43 Windows Thread Scheduling Example(c#) Thread.Proity Property Example Namespace: System.Threading Assembly: mscorlib (in mscorlib.dll) System.Threading.ThreadPriority public enum ThreadPriority {Lowest,BelowNormal,Normal,AboveNoraml,Higest} Thread T = new Thread(new ThreadStart(p.method)); T.Priority = ThreaPriority.BelowNormal; T.Start(); 예제시나리오 쓰레드생성 T1 :Normal Priority, T2 : Below Normal Priority 두프로세스가동시에정수를세게하고 10 초후에정지시키고센수를점검하여 T1 의수가더큰지를점검한다. 즉 Thread Scheduling 에의하여우선순위가높은 Thread 가더많이 CPU 를사용을배정하여더셀수있었는지를검증 43/50

Windows Thread Scheduling Example(c#) static void Main() { PriorityTest p = new PriorityTest(); Thread T1=new ThreadStart(p.ThreadMethod); Thread T2=new ThreadStart(p.ThreadMethod); T1.

44 Windows Thread Scheduling Example(c#) static void Main() { PriorityTest p = new PriorityTest(); Thread T1=new ThreadStart(p.ThreadMethod); Thread T2=new ThreadStart(p.ThreadMethod); T1.Name= ThreaOne ; //T1 : Normal Prioty T2.Name= ThreadTwo; T2.Prioty = ThreaPrioty.BelowNormal; T1.Start(); T2.Start(); Thread.Sleep(10000); p.loopswitch.false; 실행결과 class P { bool loopswitch; public P() { loopswitch = true; } public bool LoopSwitch { set{ loopswitch = value; } } public void ThreadMethod() { long threadcount = 0; while(loopswitch) { threadcount++; } Console.WriteLine( "{0} with {1,11} priority has a count = {2,13}", Thread.CurrentThread.Name, Thread.CurrentThread.Priority.ToString(), threadcount.tostring("n0")); } } 44/50

45 Linux Scheduling (Linux kernel 2.5) Linux kernel version 2.5 이후 SMP 지원향상 : processor affinity, load balancing 공평몫스케줄링 (fair-share scheduling) 지원 interactive task 지원 Linux scheduler: preemptive, priority-based algorithm 2 priority ranges: 낮은값이높은우선순위 real-time tasks: 0~99 other tasks (nice): 100~140 긴 sleep time (interactive): nice value -5 짧은 sleep time (CPU-bound): nice value +5 높은우선순위프로세스에긴 time-quantum 할당 (Solaris, Windows XP 등대부분 OS 와다름 ) 각프로세서는자신의 runqueue (active array, expired array) 유지 active: time quantum 남은프로세스 expired: time quantum 소진한프로세스 한번 time quantum 받은프로세스는 expired queue 로이동 active array 의모든프로세스들이 time quantum 소진하면, 두 array 교환 45/50

46 Linux Scheduling (Linux kernel 2.5) Priorities and Time-slice length Constant order O(1) scheduling time Two priority ranges: time-sharing and real-time Real-time range from 0 to 99 and nice value from 100 to /50

47 Linux Scheduling (Linux kernel 2.5) 우선순위에따라인덱스된태스크리스트 (List of Tasks Indexed According to Priorities) 47/50

48 알고리즘평가 (Algorithm Evaluation) 결정성모형화 (Deterministic Modeling) 작업부하 (workload) 에따른성능비교 : 5.7.1절예제 (p ) 꼭보세요!!! 반환시간 대기시간등 CPU 버스트시간등많은정확한정보요구 큐잉모형 (Queueing Models) CPU-I/O 버스트뿐아니라프로세스도착시간의분포도평가에고려해야 도착율과서비스율알면이용율, 평균큐길이, 평균대기시간알수있음 Little의공식 : n = x W ( 평균큐길이 ) = ( 도착율 ) x ( 평균대기시간 ) ( 예 ) 초당평균 7 개프로세스가도착하고, 큐에평균 14 개프로세스가있다면, 평균대기시간은 2 초 모든경우에적용가능하나근사치일뿐 모의실험 (Simulations) 소프트웨어자료구조로 clock variable, system state variables 등표현하고통계 사건분포는수학적 ( 균일, 지수, 포아송 ), 또는경험적으로정의 사건생성순서정보제공위해 trace tapes 이용 정확하나비용이많이듬 구현 (Implementation) 가장정확하나비용많고사용자적응이문제 가장융통성있는스케줄링알고리즘 (flexible scheduling algorithm) tunable scheduling 시스템관리자가응용영역에따라스케줄러변수들을변경할수있음» 몇몇 Unix 버전에서세밀한 tuning 가능 Yield() 나 setpriority() API 이용하여응용의동작예측가능하게함 48/50

49 알고리즘평가 (Algorithm Evaluation) Evaluation of CPU schedulers by Simulation 49/50

알고리즘평가 (Algorithm Evaluation) Deterministic modeling 예 (p205) Process : p1 p2 p3 p4 p5 Burst time(ms) : 10 29 3 7 12 FCFS scheduling

50 알고리즘평가 (Algorithm Evaluation) Deterministic modeling 예 (p205) Process : p1 p2 p3 p4 p5 Burst time(ms) : FCFS scheduling algorithm Averaging waiting time : ( )/5 = 28 ms SJF scheduling algorithm(p 205) Averaging waiting time : ( )/5=13 ms 50/50

51 알고리즘평가 (Algorithm Evaluation) Deterministic modeling 예 (p206) Process : p1 p2 p3 p4 p5 Burst time(ms) : RR at time quantum = 10ms Averaging waiting time : ( )/5 = 23 ms p1 : 0 p2 : =32 p3 : 20 p4 : 23 p5 : 30+10=40 51/50

52 End of Chapter 5 Operating System Concepts 8 th Edition, Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2009

Alternating Sequence of CPU And I/O Bursts 6.2

Alternating Sequence of CPU And I/O Bursts 6.2 CPU 스케줄링 (CPU Scheduling) ~ 프로세스스케줄링» 장기 job scheduling» 단기 CPU scheduling» 중기 swapping 기본개념 (Basic Concepts) CPU-I/O 버스트주기 (burst cycle)» cycle : CPU 실행 (CPU burst) I/O 대기 (I/O burst)» CPU burst