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) 큐 우선순위큐 트리 연결리스트 6.1
Alternating Sequence of CPU And I/O Bursts 6.2
Histogram of CPU-burst Times 6.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 6.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) : 대화형시스템에서첫응답까지의시간 6.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) 스케줄링 다중프로세서스케줄링 (Multiple-Processor Scheduling) 실시간스케줄링» EDF (Earliest Deadline First)» Rate Monotonic» Rate Monotonic vs. EDF 실례» Java Thread Scheduling» Solaris 2 Scheduling» Thread Scheduling» Linux Scheduling 6.6
스케줄링알고리즘 (Scheduling Algorithm) 1. 선입선처리 (First-Come, First-Served) 스케줄링» 들어온순서대로» FIFO queue : First-in<- tail, First-out<- head» p168-169 예 (Gantt chart), p191 예» 호위효과 (convoy effect) : 큰 job하나가끝나기를모두기다림 (CPU-bound process가끝나기를 I/O bounded process들이기다림 )» non-preemptive임 (time-sharing에서는곤란 ) 6.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 6.8
FCFS Scheduling (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 P 1 = 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 6.9
스케줄링알고리즘 (Scheduling Algorithm) 2. 최소작업우선 (Shortest-Job-First) 스케줄링» Shortest Next CPU Burst Scheduling» 다음 CPU burst 시간이가장짧은프로세스에게» 두가지스케줄링기법 non-preemptive SJF : p170 예, p191 예 preemptive SJF = Shortest Remaining Time First Scheduling : p172 예» 최적 (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 였음 6.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 6.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 Average waiting time = (9 + 1 + 0 +2)/4 = 3 16 6.12
Determining Length of Next CPU Burst CPU 버스트시간정확히알수는없지만예측가능 이전 CPU 버스트시간들의지수적평균 (exponential averaging) 으로예측 1. t n = actual lenght of n th CPU burst 2. t n+ + 1 = predicted value for the next CPU burst (Greek T : 3. a, 0 a 1 4. Define : t = a t + ( 1-a ) t. n+ 1 n n tau) 6.13
Examples of Exponential Averaging a =0» t n+1 = t n» 최근의실제 CPU 버스트시간은고려않음 a =1» t n+1 = t n» 마지막실제 CPU 버스트시간만고려 식을확장하면 : t n+1 = a t n + (1 - a) t n = a t n + (1 - a) (a t n-1 + (1 - a) t n-1 ) = a t n + (1 - a) a t n-1 + (1 - a) 2 t n-1 = a t n + (1 - a) a t n-1 + (1 - a) 2 (a t n-2 + (1 - a) t n-2 ) = a t n + (1 - a) a t n-1 + (1 - a) 2 a t n-2 + (1 - a) 3 t n-3 = a t n + (1 - a) a t n-1 + (1 - a) 2 a t n-2 + (1 - a) 3 a t n-3 +(1 - a ) j a t n-j + +(1 - a ) n+1 t 0 a 와 (1 - a) 이 1 보다작으므로, 후속되는각항목은이전항목보다가중값 (weight) 이더적어짐 6.14
Prediction of the Length of the Next CPU Burst 6.15
스케줄링알고리즘 (Scheduling Algorithm) ~ 3. 우선순위 (Priority) 스케줄링» 높은우선순위의프로세스에게» ready queue = priority queue -> heap구조가좋음» FCFS : equal-priority» SJF : p =1/T (T = 차기 CPU 버스트시간예측값 )» p173 예해보세요» 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.16
스케줄링알고리즘 (Scheduling Algorithm) ~ 4. 순환할당 (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» p175, p191 예 6.17
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 Typically, higher average turnaround than SJF, but better response. 6.18
How a Smaller Time Quantum Increases Context Switches 6.19
Turnaround Time Varies With The Time Quantum 6.20
스케줄링알고리즘 (Scheduling Algorithm) ~ 5. 다단계큐 (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» 스케줄링부담적으나융통성이적음 6.21
Multilevel Queue Scheduling 6.22
스케줄링알고리즘 (Scheduling Algorithm) 6. 다단계귀환큐 (Multilevel Feedback Queue) 스케줄링» 프로세스가여러큐사이를이동 : 그림 6.7» 짧은프로세스 (I/O bound, interactive processes) 가우선» 긴프로세스는자꾸낮은큐로이동» aging( 오래기다리면우선순위높여기아상태예방 )» preemptive 임 ( 큐사이 )» the most sophisticated, the most complex» 가장일반적 -> 해당시스템에맞게설정해야 (configure) 큐의개수 각큐의스케줄링알고리즘 높은우선순위로올려주는시기 낮은우선순위로내려주는시기 어느큐에들어갈것인가 6.23
Multilevel Feedback Queues 6.24
Example of Multilevel Feedback Queue 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 로이동 6.25
초기 Unix 의프로세스스케줄링예 CPU=decay(CPU)=CPU/2 우선순위 = ( 최근의 CPU 사용량 )/2 + ( 기본수준사용자우선순위 60) Unix 시스템의최고우선순위는 0 ( 우선순위값이작을수록우선순위높음 ) 0 시간프로세스 A 프로세스 B 프로세스 C 우선순위 CPU계수우선순위 CPU계수우선순위 CPU계수 1 2 3 4 5 60 75 67 63 76 68 0 1 2 60 30 15 7 8 9 67 33 6.26 60 0 60 60 75 67 63 0 1 2 60 30 15 7 8 9 67 33 16 76 63 7 60 60 75 67 0 0 0 1 2 60 30 15
다중프로세서스케줄링 (Multiple-Processor Scheduling) 동종다중프로세서 (homogeneous multiprocessor)» 프로세서는큐에있는어떤프로세스 (any processes) 든실행» 부하공유 (load sharing) 별도준비큐 (separate ready queue): unfair 공동준비큐 (common ready queue): fair» 공동준비큐동종다중프로세서시스템 (common ready queue on homogeneous multiprocessor) 의스케줄링 대칭적스케줄링 (symmetric scheduling)» 각프로세서가스스로스케줄링 (self-scheduling)» 공유자료구조접근에대한세심한처리필요» 대부분의현대 OS가지원 : Windows XP, Windows 2000, Solaris, Linux, Max OS X 비대칭적스케줄링 (asymmetric scheduling): master/slave» 한프로세서 (master) 가다른프로세서 (slaves) 스케줄링» master만 kernel system data structure에접근가능 공유자료구조접근동기화필요없어처리가간단» Asymmetric Multiprocessing master server : all system activity client processors: user code only» 처리기친근성 (processor affinity): 한프로세서에서작업하면 cash hit-ratio 높아져효율적 연성친근성 (soft affinity): 친근노력하나프로세스이주 (process migration) 발생가능 경성친근성 (hard affinity): 절대친근보장 ( 예, Linux에서시스템호출로요청 )» 부하균형 (load balancing): 별도준비큐경우일부담의균등분배 push migration: 과부하프로세서가자신의프로세스를노는프로세서로이주시킴 pull migration: 노는프로세서가바쁜프로세서에서대기중인프로세스를끌어옴 이종다중프로세서 (heterogeneous multiprocessor)» 컴파일된프로세스들의기계어가실행하고자하는프로세서의기계어와동일한경우만실행가능» 14장참조 6.27
실시간스케줄링 (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 6.28
실시간스케줄링 (Real-Time Scheduling) 우선순위역전 (priority inversion)» kernel data 수정중인우선순위가낮은프로세스가선점하려는우선순위프로세스에우선하여수행됨 우선순위상속프로토콜 (priority inheritance protocol)» kernel data 수정중인낮은우선순위의프로세스가선점하려는프로세스의높은우선순위를상속받음, 끝나면원래의값으로 갈등단계 (conflict phase) 의내용 : 그림 6.8 1. 커널에서실행중인프로세스를선점 2. 자원회수 ( 우선순위낮은프로세스는우선순위높은프로세스가요구하는자원을놓아줌 ) ( 예 ) Solaris 2 dispatch latency nonpreemptible = 100 ms dispatch latency preemptible = 2 ms 6.29
Dispatch Latency 6.30
Rate Monotonic vs. EDF 6.31
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 6.32
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. 6.33
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 ( 그림 6.11 참조 )» scheduler ss queue 에 addthread(): priority 2» 실행위해선택되면 : priority 4» 스케줄러는 1 time quantum 동안잠들고 CPU는 priority 4인 thread로» 1 time quantum 후잠에서깨어난스케줄러가 priority 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. 6.34
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; } 6.35
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); } } 6.36
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); } } 6.37
Thread Scheduling 2 thread levels» 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 결정 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 만사용 6.38
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, &scope)!= 0) fprintf(stderr, "Unable to get scheduling scope\n"); else { 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"); } /* set the scheduling algorithm to PCS or SCS */ pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);s /* 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); 6.39
Solaris 2 Scheduling Solaris 2 Scheduling» priority-based process scheduling» 4 classes ( 그림 6.9 참조 ) real time: 최상위우선순위 system: 우선순위결정된후불변 interactive: multi-level feedback queue scheduling» windowing application에높은우선순위 time sharing: default class, multi-level feedback queue scheduling» the higher the priority, the smaller the time slice interactive processes» the lower the priority, the larger the time slice CPU-bound processes» Scheduler가 class-specific priorities를 global priorities로변환» 우선순위같을때는 round-robin» 수행중인 thread가멈추는경우 blocks time slice 완료 더높은우선순위의 thread가선점 (preempt) 6.40
Solaris 2 Scheduling 6.41
Solaris Dispatch Table for Interactive & Time-sharing threads 우선순위낮음 우선순위높음 Solaris & Windows XP: 높은우선순위프로세스에짧은 time quantum 할당 6.42
priority class Windows XP Priorities 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 받은후우선순위낮아짐 good response times to interactive threads» priority boost( 인상 ): keybord I/O boost > disk I/O boost good performance for interactive processes» foreground process (currently selected): 3 배 time quantum 부여» background process (not selected) 6.43
Linux Scheduling (Linux kernel 2.5) 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: 0~99» 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 교환 Two algorithms: time-sharing and real-time Time-sharing» Prioritized credit-based process with most credits is scheduled next» Credit subtracted when timer interrupt occurs» When credit = 0, another process chosen» When all processes have credit = 0, recrediting occurs Based on factors including priority and history Real-time» Soft real-time» static priority» Posix.1b compliant two classes FCFS and RR Highest priority process always runs first 6.44
The Relationship Between Priorities and Time-slice length 6.45
List of Tasks Indexed According to Priorities 6.46
알고리즘평가 (Algorithm Evaluation) 결정성모형화 (Deterministic Modeling)» 작업부하 (workload) 에따른성능비교 : p158-159 예제참고 반환시간 대기시간등» CPU 버스트시간등많은정확한정보요구 큐잉모형 (Queueing Models)» CPU-I/O 버스트뿐아니라프로세스도착시간의분포도평가에고려해야» 도착율과서비스율알면이용율, 평균큐길이, 평균대기시간알수있음» Little의공식 : ( 평균큐길이 ) = ( 도착율 ) x ( 평균대기시간 )» 모든경우에적용가능하나근사치일뿐 모의실험 (Simulations)» 소프트웨어자료구조로 clock variable, system state variables 등표현하고통계» 사건분포는수학적 ( 균일, 지수, 포아송 ), 또는경험적으로정의» 사건생성순서정보제공위해 trace tapes 이용» 정확하나비용이많이듬 구현 (Implementation)» 가장정확하나비용많고사용자적응이문제» 가장융통성있는스케줄링알고리즘 (flexible scheduling algorithm) è tunable scheduling 시스템관리자가응용영역에따라스케줄러변수들을변경할수있음 몇몇 Unix 버전에서세밀한 tuning 가능 Yield() 나 setpriority() API 이용하여응용의동작예측가능하게함 6.47
Evaluation of CPU Schedulers by Simulation 6.48