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 유형 I/O bound program : 많은짧은 CPU burst 가짐 CPU bound program : 적은아주긴 CPU burst 가짐 CPU 스케줄러» 단기스케줄러 (short-term scheduler) : ready queue 에서선택 FIFO(First-In First-Out) 큐우선순위큐트리 연결리스트 5.1
Alternating Sequence of CPU And I/O Bursts 5.2
Histogram of CPU-burst Times 5.3
CPU 스케줄링 (CPU Scheduling) 선점 / 비선점스케줄링 (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 5.4
CPU 스케줄링 (CPU Scheduling) 분배기 (Dispatcher)» 문맥교환» 사용자모드로전환» 프로그램의적절한위치로점프하여프로그램재시작 (dispatch latency 가짧아야함 ) 스케줄링기준 (Scheduling Criteria) 이용률 (CPU utilization) : 40% ~ 90% 처리율 (throughput) : 처리된프로세스개수 / 시간단위 반환시간 (turnaround time) : system in -> system out 걸린시간 대기시간 (waiting time) : ready queue 에서기다린시간 응답시간 (response time) : 대화형시스템에서첫응답까지의시간 5.5
스케줄링알고리즘 (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) 실례» Solaris 2 Scheduling» Windows XP Scheduling» Linux Scheduling 실시간스케줄링» EDF (Earliest Deadline First)» Rate Monotonic» Rate Monotonic vs. EDF 5.6
스케줄링알고리즘 (Scheduling Algorithm) 1. 선입선처리 (First-Come, First-Served) 스케줄링» 들어온순서대로» FIFO queue : First-in<- tail, First-out<- head» 호위효과 (convoy effect) : 큰 job 하나가끝나기를모두기다림 (CPU-bound process가끝나기를 I/O bounded process들이기다림 )» non-preemptive 임 (time-sharing 에서는곤란 ) 5.7
First-Come, First-Served (FCFS) Scheduling Example: Process Burst Time P 1 24 P 2 3 P 3 3 Suppose that the processes arrive in the order: P 1, P 2, P 3 The Gantt Chart for the schedule is: P 1 P 2 P 3 0 24 27 30 Waiting time for P 1 = 0; P 2 = 24; P 3 = 27 Average waiting time: (0 + 24 + 27)/3 = 17 5.8
FCFS Scheduling g( (Cont.) Suppose that the processes arrive in the order P 2, P 3, P 1. The Gantt chart for the schedule is: P 2 P 3 P 1 0 3 6 30 Waiting time for P1 P = 6; P 2 = 0 ; P 3 = 3 Average waiting time: (6 + 0 + 3)/3 = 3 Much better than previous case. Convoy effect short process behind long process 5.9
스케줄링알고리즘 (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 Response Next) 스케줄링 1971 Brinch Hansen SJF의단점보완 dynamic priority = (time waiting + service time) / (service time) 오래기다린프로세스는 time waiting이증가하므로 priority 커지고 short process일수록 priority 커짐 non-preemptive 였음 5.10
Example of Non-Preemptive SJF 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 3 7 8 12 16 Average waiting time = (0 + 6 + 3 + 7)/4 = 4 5.11
Example of Preemptive SJF 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 Average waiting time = (9 + 1 + 0 +2)/4 = 3 5.12
Determining Length of Next CPU Burst CPU 버스트시간정확히알수는없지만예측가능 이전 CPU 버스트시간들의지수적평균 (exponential averaging) 으로예측 th 1. t n actual lenght of n CPU burst 2. predicted value for the next CPU burst (Greek T : tau 4. n 1 3., 0 1 Define : 1. n t 1 n n 미( 터) 영( 타우 ) 5.13
Examples of Exponential Averaging g =0» 1 =» n+1 = n» 최근의실제 CPU 버스트시간은고려않음 =1» n+1 = t n» 마지막실제 CPU 버스트시간만고려 식을확장하면 : n+1 = t n + (1 - ) n = t n + (1 - ) ( t n-1 + (1 - ) n-1 ) = t + (1 - ) t n-1 + (1 - ) 2 n n-1 = t n + (1 - ) t n-1 + (1 - ) 2 ( t n-2 + (1 - ) n-2 ) = t n + (1 - ) t n-1 + (1 - ) 2 t n-2 + (1 - ) 3 n-3 = t n + (1 - ) t n-1 + (1 - ) 2 t n-2 + (1 - ) 3 t n-3 n ( ) n 1 ( ) n 2 ( ) n 3 +(1 - ) j t n-j + +(1 - ) n+1 0 와 (1 - ) 이 1 보다작으므로, 후속되는각항목은이전항목보다가중값 (weight) 이더작아짐 5.14
Prediction of the Length of the Next CPU Burst 5.15
스케줄링알고리즘 (Scheduling Algorithm) 3. 우선순위 (Priority) 스케줄링» 높은우선순위의프로세스에게» ready queue = priority queue -> heap구조가좋음» FCFS : equal-priority» SJF : p =1/T (T = 차기 CPU 버스트시간예측값 )» p184 예해보세요» 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 높여줌 5.16
스케줄링알고리즘 (Scheduling Algorithm) 4. 순환할당 (Round-Robin) 스케줄링» FCFS + preemption (time slice 마다 )» ready queue = 원형 FIFO queue» preemptive p 임» time sharing에서time quantum의크기가중요 1 time quantum > context switching time 80% CPU burst < 1 time quantum 5.17
Example of RR with Time Quantum = 4 Process Burst Time P 1 24 P 2 3 2 P 3 3 The Gantt chart is: P 1 P 2 P 3 P 1 P 1 P 1 P 1 P 1 0 4 7 10 14 18 22 26 30 Average waiting time = (? +? +?)/3 =? Typically, higher average turnaround than SJF, but better response 5.18
Example: RR with Time Quantum = 20 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 3 0 20 37 57 77 97 117 121 134 154 162 Average waiting time = (? +? +?)/? =? Typically, higher average turnaround than SJF, but better response. 5.19
How a Smaller Time Quantum Increases Context Switches 5.20
Turnaround Time Varies With The Time Quantum 5.21
스케줄링알고리즘 (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» 스케줄링부담적으나융통성이적음 5.22
다단계큐스케줄링 (Multilevel Queue Scheduling) 5.23
스케줄링알고리즘 (Scheduling Algorithm) 6. 다단계피드백큐 (Multilevel Feedback Queue) 스케줄링» 프로세스가여러큐사이를이동 : 그림 5.7» 짧은프로세스 (I/O bound, interactive processes) 가우선» 긴프로세스는자꾸낮은큐로이동» aging( 오래기다리면우선순위높여기아상태예방 )» preemptive 임 ( 큐사이 )» the most sophisticated, the most complex» 가장일반적 -> 해당시스템에맞게설정해야 (configure) 큐의개수 각큐의스케줄링알고리즘 높은우선순위로올려주는시기 낮은우선순위로내려주는시기 어느큐에들어갈것인가 5.24
다단계피드백큐 (Multilevel Feedback Queues) Three queues:» Q 0 time quantum 8 milliseconds» Q 1 time quantum 16 milliseconds» Q 2 FCFS Scheduling» FCFS queue Q 0 에새로들어온작업이 8 milliseconds 동안 CPU를받고도작업이끝나지않으면선점되어 queue Q 1 으로이동» Q 1 의작업은 FCFS 로 16 additional milliseconds 을받고그래도끝나지않으면선점되어 queue Q 2 로이동 5.25
스레드스케줄링 (Thread Scheduling) 2 스레드지원수준» User level: process local 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_SCOPE_SYSTEM one-to-one mapping pthread IPC» 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) 5.26
Pthread 스케줄링 POSIX.1b scheduling: 실시간스케줄링을위한확장» (Unix) $ man sched.h dh» (Linux) $ man sched_setscheduler» RT (real-time) scheduling SCHED_FIFO: a first-in, first-out policy» 스레드는 FIFO 큐를이용하는 FCFS 정책으로스케줄» 우선순위높은작업또는신호에의해선점 (pre-emption) 되지않는한종료까지수행» 같은우선순위스레드들의 time-slicing 없음 SCHE_RR: a round-robin policy» 같은우선순위스레드들의 time-slicing 있는것제외하고 SCHED_FIFO와유사» Normal (non-real-time) scheduling SCHED_OTHER: the standard round-robin robin time-sharing policy SCHED_BATCH: for batch style execution of processes SCHE_IDLE: for runnung very low priority background jobs 5.27
Pthread Scheduling API #include <pthread.h> #include <stdio.h> #define NUM_THREADS 5 void *runner(void *param); 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, attr &scope)!= 0) fprintf(stderr, "Unable to get scheduling scope\n"); else { if(scope == PTHREAD_SCOPE_PROCESS) PROCESS) printf("pthread_scope_process\n"); else if(scope == PTHREAD_SCOPE_SYSTEM) printf("pthread_scope_system\n"); else fprintf(stderr, "Illegal scope value.\n"); } /* set the scheduling algorithm to PCS or SCS */ pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM if(scope == PTHREAD_SCOPE_PROCESS) printf("pthread_scope_process\n"); else if(scope == PTHREAD_SCOPE_SYSTEM) printf("pthread_scope_system\n"); else fprintf(stderr, "Illegal scope value.\n"); /* 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 the thread %d\n", *(int*)param); pthread_exit(0); } 5.28
Pthread Scheduling API ( 그림 19.11) #include <pthread.h> #include <stdio.h> #define NUM_THREADS 5 /* the thread runs in this function */ void *runner(void *param); main(int argc, char *argv[]) { int i, policy; pthread_t tid[num_threads]; /* the thread identifier */ pthread_attr_t attr; /* set of attributes for the thread */ /* get the default attributes */ pthread_attr_init(&attr); /* get the current scheduling policy */ if (pthread_attr_getschedpolicy(&attr,&policy)!= 0) fprintf(stderr, "Unable to get policy.\n \n"); else { if (policy == SCHED_OTHER) printf("sched_other\n"); else if (policy == SCHED_RR) printf("sched _O OTHER\n"); else if (policy == SCHED_FIFO) printf("sched_fifo\n"); } /* set the scheduling policy - FIFO, RR, or OTHER */ if (pthread_attr_setschedpolicy(&attr, SCHED_FIFO)!= 0) printf("unable to set scheduling policy to SCHED_OTHER \n"); if (pthread_attr_getschedpolicy(&attr,&policy) tt t h d (& tt & )!= 0) fprintf(stderr, "Unable to get policy.\n"); else { if (policy == SCHED_OTHER) printf("sched_other\n"); else if (policy == SCHED_RR) printf("sched_other\n"); else if (policy == SCHED_FIFO) printf("sched_fifo\n"); } /* 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); } /** * The thread will begin control in this function. */ void *runner(void *param) { /* do some work... */ } pthread _ exit(0); 5.29
다중프로세서스케줄링 (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, it client processors: user code only master만 kernel system data structure에접근가능» 공유자료구조접근동기화필요없어처리가간단» SMP(Symmetric Multiprocessing): 대칭적스케줄링 (symmetric scheduling) 각프로세서가스스로스케줄링 (self-scheduling) 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) = 분산시스템» 컴파일된프로세스들의기계어가실행하고자하는프로세서의기계어와동일한경우만실행가능 5.30
전형적인 SMT 구조 5.31
NUMA (Non-Uniform Memory Access and CPU Scheduling 같은보드에있는 CPU 의메모리접근시간이더적은경우강한친화성 (affinity) 5.32
멀티코어프로세서 (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 5.33
A Dual-Core Design one chip 5.34
Solaris 2 Scheduling Solaris 2 Scheduling» 우선순위기반스레드스케줄링 (priority-based process scheduling» 6 classes ( 그림 5.10 참조 ) (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) 고정우선순위 (fixed priority): 시분할스레드와같은우선순위이나고정 (FP) 공평공유 (fair share): CPU 공유량을기준으로스케줄» Scheduler가 class-specific priorities를 global priorities로변환» 우선순위같을때는 round-robinrobin» 수행중인 thread가멈추는경우 blocks time slice 완료 더높은우선순위의 thread 가선점 (preempt) 5.35
Solaris 2 Scheduling 5.36
대화형과시분할스레드를위한 Solaris 디스패치테이블 우선순위낮음 우선순위높음 Solaris & Windows XP: 높은우선순위프로세스에짧은 time quantum 할당 5.37
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 부여 5.38
Linux Scheduling g( (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 it 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 ed queue 로이동 active array의모든프로세스들이 time quantum 소진하면, 두 array 교환 5.39
Linux Scheduling g( (Linux kernel 2.5) 2개알고리즘 : time-sharing and real-time» 시분할 (Time-sharing) 우선순위신뢰값 (prioritized credit) 기반 : 신뢰값이큰프로세스를다음작업으로선택 신뢰값은매타이머인터럽트마다감소 신뢰값이 0이되면다른프로세스선택 신뢰값이 0 이된후우선순위와이력에따라서신뢰값재배정» 실시간 (Real-time) soft real-time 고정우선순위 (static priority) Posix.1b 호환 (compliant) two classes» FCFS 와 RR» 높은우선순위프로세스가항상먼저실행됨 POSIX scheduling» (Linux) $ man sched_setscheduler» (Unix) $ man sched.h» Normal (non-real-time) scheduling SCHED_OTHER: the standard d round-robin time-sharing i policy SCHED_BATCH: for batch style execution of processes SCHE_IDLE: for runiung very low priority background jobs» RT (real-time) scheduling SCHED_FIFO: a first-in, in first-out policy SCHE_RR: a round-robin policy 5.40
우선순위와시간조각 (Time-slice) 길이와의관계 5.41
List of Tasks Indexed According to Priorities 5.42
초기 Unix 의프로세스스케줄링예 CPU=decay(CPU)=CPU/2 우선순위 = ( 최근의 CPU 사용량 )/2 + ( 기본수준사용자우선순위 60) 0» Unix 시스템의최고우선순위는 0 ( 우선순위값이작을수록우선순위높음 )» 60 clock interrupts per second 시간 프로세스A 프로세스B 프로세스C 우선순위 CPU계수우선순위 CPU계수우선순위 CPU계수 1 2 3 4 5 60 60 0 60 75 0 1 2 60 30 60 60 67 15 75 60 0 63 76 68 7 8 9 67 33 67 63 0 1 2 60 30 15 7 8 9 67 33 16 76 63 7 5.43 75 67 0 0 1 2 60 30 15
알고리즘평가 (Algorithm Evaluation) 결정성모형화 (Deterministic Modeling)» 작업부하 (workload) 에따른성능비교 : 5.7.1절예제 (p205-206) 예제꼭보세요 반환시간 대기시간등» CPU 버스트시간등많은정확한정보요구 큐잉모형 (Queueing Models)» CPU-I/O 버스트뿐아니라프로세스도착시간의분포도평가에고려해야» 도착율과서비스율알면이용율, 평균큐길이, 평균대기시간알수있음» Little의공식 : n = xw ( 평균큐길이 ) = ( 도착율 ) x ( 평균대기시간 )» 모든경우에적용가능하나근사치일뿐 모의실험 (Simulations)» 소프트웨어자료구조로 clock variable, system state variables등표현하고통계» 사건분포는수학적 ( 균일, 지수, 포아송 ), 또는경험적으로정의» 사건생성순서정보제공위해trace tapes 이용» 정확하나비용이많이듬 구현 (Implementation)» 가장정확하나비용많고사용자적응이문제» 가장융통성있는스케줄링알고리즘 (flexible scheduling algorithm) tunable scheduling 시스템관리자가응용영역에따라스케줄러변수들을변경할수있음 몇몇 Unix 버전에서세밀한 tuning 가능 Yield() 나 setpriority() API 이용하여응용의동작예측가능하게함 5.44
Evaluation of CPU Schedulers by Simulation 5.45
In-5.7 5.46
In-5.8 5.47
In-5.9 5.48
실시간스케줄링 (Real-Time Scheduling) 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) 대부분의 OS: context switching 하려면실행중인 system call이완료되거나 I/O를위해 block 되기를기다려야함 -> 해결 1 system call을 preemptible하게» 긴 system call안에 preemption points( 더높은우선순위의프로세스가있나 check, 있으면 interrupt) 2 kernel 전체를 preemptible 하게» Kernel data보호를위한 synchronization 필요» ( 예 ) Solaris 2: 우선순위역전 (priority inversion) 즉 kernel data 수정중일때는 control을넘겨주지않음 (cf.) Mach: threads are nonpreemptible, threads are synchronous 5.49
디스패치지연 (Dispatch Latency) 5.50
실시간스케줄링 (Real-Time Scheduling) 우선순위역전 (priority inversion)» kernel data 수정중인우선순위가낮은프로세스가선점하려는우선순위프로세스에우선하여수행됨 우선순위상속프로토콜 (priority inheritance protocol)» kernel data 수정중인낮은우선순위의프로세스가선점하려는프로세스의높은우선순위를상속받음, 끝나면원래의값으로 갈등단계 (conflict phase) 의내용 : 그림 19.5 (19 장 ) 1. 커널에서실행중인프로세스를선점 2. 자원회수 ( 우선순위낮은프로세스는우선순위높은프로세스가요구하는자원을놓아줌 ) ( 예 ) Solaris 2 dispatch latency nonpreemptible p = 100 ms dispatch latency preemptible = 2 ms 5.51
레이트모노토닉 (Rate Monotonic) vs. EDF 5.52
( 참고 ) Java Thread Scheduling JVM은스케줄링할때» Preemptive, Priority-Based Scheduling Algorithm 이용» 우선순위같으면 FIFO Queue 이용 (RR algorithm) Time slicing» time-sliced: a thread runs until time quantum exit the Runnable state preempted» not time-sliced: a thread runs until exit the Runnable state preempted yield() method로공평한수행 (time slicing 효과 )» cooperative multitasking 5.53
( 참고 ) Time-Slicing JVM 스레드가 Time-Slicing을지원하는지하지않는지에대해명시하지않음 ( 시스템마다다름 )» time-slicing 지원않는시스템에서는 the yield() Method로 time-sharing while (true) { // perform CPU-intensive task... Thread.yield(); } This Yields Control to Another Thread of Equal Priority. 5.54
( 참고 ) Java Thread Scheduling Thread priority» 최상위우선순위 thread 가 Runnable thread 로선택됨» Thread 생성시 defalut priority( 부모와같음 ) -> setpriority() 로수정 Thread.MIN_PRIORITY : 1 Thread.MAX_PRIORITY : 10 Thread.NORM_PRIORITY: 5 (default priority) setpriority(thread.norm_priority + 2); Java-Based Round-Robin Scheduler: thread with priority 6» scheduler s queue에 addthread(): priority 2» 실행위해선택되면 : priority 4» 스케줄러는 1 time quantum 동안잠들고 CPU는 priority 4인 thread로» 1 time quantum 후잠에서깨어난스케줄러가 priority it 4 인 thread 를선점 (preempt)» CircularList class에 queue가비었는지알아내는 isempty() 추가하고큐가비었을때는잠들었다가다시 queue 조사하게하여 busy-wait 방지 JVM이다음실행할 thread를스케줄하는시점 :» 현재수행중이던 thread가 Runnable State를빠져나갈때» 높은우선순위의 thread가 Runnable State로들어왔을때 * Note the JVM Does Not Specify Whether Threads are Time-Sliced or Not. 5.55
( 참고 ) Round-Robin Scheduler public class Scheduler extends Thread { public Scheduler() { timeslice = DEFAULT_TIME_SLICE; queue = new CircilarList(); } public Scheduler(int quantum) { timeslice = quantum; queue = new CircilarList(); } public void addthread(thread t) { t.setpriority(2); queue.additem(t); } private void scheculersleep() { try { thread.sleep(timeslice); } catch (InterruotedException e) { }; } public void run() { Thread current; this.setpriority(6); while (true) { //get the next thread current = (Thread)queue.getNext(); if ((current!= null) && (current.isalive())) { current.setpriority(4); schedulersleep(); current.setpriority(2); } } } private CircularList queue; private int timeslice; private static final int DEFAULT_TIME_SLICE = 1000; } 5.56
( 참고 ) TestThread class TestThread extends Thread { private String name; } public TestThread(String id) { name = id; this.setpriority(thread.norm_priority); } public void run() { /* * The thread does something **/ while (true) { for (int i = 0; i < 500000; i++) ; System.out.println("I am thread " + name); } } 5.57
( 참고 ) TestScheduler public class TestScheduler { } public static void main(string args[]) { Thread.currentThread().setPriority(Thread.MAX_PRIORITY); Scheduler CPUScheduler = new Scheduler(); CPUScheduler.start(); TestThread t1 = new TestThread("Thread 1"); t1.start(); CPUScheduler.addThread(t1); TestThread t2 = new TestThread("Thread 2"); t2.start(); CPUScheduler.addThread(t2); TestThread t3 = new TestThread("Thread 3"); t3.start(); CPUScheduler.addThread(t3); } 5.58