Chapter 5. CPU 스케줄링 (CPU Scheduling) Questions of the day 가장 이상적인 스케줄링 알고리즘은? 우선순위 큐를 구현하는 자료구조에는? 자료구조의 히프(heap) 구조의 삽입과 삭제 연산의 시간복잡도는? 스케줄링 예 운영체제

기본 개념(Basic Concepts) 프로세스 스케줄링 장기 job scheduling 단기 CPU scheduling 중기 swapping 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)큐 우선순위 큐 트리 연결리스트 운영체제

(Alternating Sequence of CPU And I/O Bursts) CPU와 I/O 버스트의 교차 (Alternating Sequence of CPU And I/O Bursts) 운영체제

CPU 버스트 시간 히스토그램 (Histogram of CPU-burst Times) 운영체제

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 running  waiting : non preemptive running  ready (interrupt) : preemptive waiting  ready (I/O 완료) : preemptive halt : non preemptive 운영체제

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) : 대화형 시스템에서 첫 응답까지의 시간 운영체제

스케줄링 알고리즘(Scheduling Algorithm) 척도 : 평균 대기 시간(average waiting time) 단일 프로세서 알고리즘 선입 선처리(First-Come, First-Served) 스케줄링 최소 작업 우선(Shortest-Job-First) 스케줄링 우선순위(Priority) 스케줄링 순환 할당(Round-Robin) 스케줄링 다단계 큐(Multilevel Queue) 스케줄링 다단계 귀환 큐(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 운영체제

스케줄링 알고리즘 (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에서는 곤란) 운영체제

(예) First-Come, First-Served (FCFS) 스케줄링 예: Process Burst Time P1 24 P2 3 P3 3 프로세스가 P1 , P2 , P3 순으로 도착했다면 스케줄을 위한 간트 차트(Gantt Chart)는: 대기시간(waiting time): P1 = 0; P2 = 24; P3 = 27 평균대기시간(average waiting time): (0 + 24 + 27)/3 = 17 P1 P2 P3 24 27 30 운영체제

(예) FCFS 스케줄링 프로세스 도착 순서가 P2 , P3 , P1 이면 스케줄을 위한 간트 차트(Gantt chart)는: 대기시간(waiting time) for P1 = 6; P2 = 0; P3 = 3 평균대기시간(average waiting time): (6 + 0 + 3)/3 = 3 Much better than previous case! 호위효과(Convoy effect): short process behind long process P1 P3 P2 6 3 30 운영체제

스케줄링 알고리즘 (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 였음 운영체제

(예) 비선점형 SJF (Non-Preemptive SJF) Process Arrival Time Burst Time P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 SJF (non-preemptive) 평균대기시간(average waiting time) = (0 + 6 + 3 + 7)/4 = 4 P1 P3 P2 P4 3 7 8 12 16 운영체제

(예) 선점형 SJF (Preemptive SJF) Process Arrival Time Burst Time P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 SJF (preemptive) 평균대기시간(average waiting time) = (9 + 1 + 0 +2)/4 = 3 P1 P2 P3 P2 P4 P1 11 16 2 4 5 7 운영체제

(예) SJF 스케줄링 예: Process Burst Time P1 24 P2 3 P3 3 스케줄을 위한 간트 차트(Gantt Chart)는 ? 대기시간(waiting time): P1 = ?; P2 = ?; P3 = ? 평균대기시간(average waiting time): ( ? + ? + ? )/3 = ? 30 운영체제

차기 CPU 버스트 시간의 결정 (Determining Length of Next CPU Burst) 이전 CPU 버스트 시간들의 지수적 평균(exponential averaging)으로 예측 운영체제

(예) 지수적 평균 (Exponential Averaging)  =0 n+1 = n 최근의 실제 CPU 버스트 시간은 고려 않음  =1 n+1 = tn 마지막 실제 CPU 버스트 시간만 고려 식을 확장하면: n+1 =  tn+ (1 - ) n =  tn+ (1 - ) ( tn-1 + (1 - ) n-1 ) =  tn+ (1 - )  tn-1 + (1 - ) 2 n-1 =  tn+ (1 - )  tn-1 + (1 - ) 2 ( tn-2 + (1 - ) n-2 ) =  tn+ (1 - )  tn-1 + (1 - ) 2  tn-2 + (1 - ) 3 n-2 =  tn+ (1 - )  tn-1 + (1 - ) 2  tn-2 + (1 - ) 3  tn-3 … + (1 -  ) j  tn-j + … + (1 -  ) n+1 0 와 (1 - )이 1보다 작으므로, 후속되는 각 항목은 이전 항목보다 가중 값(weight)이 더 작아짐  0.5, 0.25, 0.125, 0,0625 … n =  tn-1+ (1 - ) n-1 n-1 =  tn-2+ (1 - ) n-2 운영체제

차기 CPU 버스트 시간 예측 (Prediction of the Length of the Next CPU Burst) 운영체제

스케줄링 알고리즘 (Scheduling Algorithm) 3. 우선순위(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 높여 줌 p184 예제 꼭 해보세요 운영체제

스케줄링 알고리즘 (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 운영체제

(예) RR with Time Quantum = 4 Process Burst Time P1 24 P2 3 P3 3 간트 차트(Gantt chart): 평균대기시간(average waiting time) = ( ? + ? + ? )/3 = ? 일반적으로, SJF 보다 평균반환시간은 길지만, 짧은 응답시간 P1 P2 P3 4 7 10 14 18 22 26 30

(예) RR with Time Quantum = 20 Process Burst Time P1 53 P2 17 P3 68 P4 24 The Gantt chart is: 평균대기시간(average waiting time) = ( ? + ? + ? + ? )/4 = ? 일반적으로, SJF 보다 평균반환시간은 길지만, 짧은 응답시간 P1 P2 P3 P4 20 37 57 77 97 117 121 134 154 162 운영체제

Time Quantum에 따른 Context Switch 횟수 운영체제

Time Quantum에 따른 반환시간(Turnaround Time)의 변화 운영체제

스케줄링 알고리즘 (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 스케줄링 부담 적으나 융통성이 적음 운영체제

다단계 큐 스케줄링 (Multilevel Queue Scheduling) 운영체제

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

다단계 피드백 큐 (Multilevel Feedback Queues) 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로 이동 운영체제

스레드 스케줄링 (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) 운영체제

Pthread 스케줄링 POSIX.1b scheduling: 실시간 스케줄링을 위한 확장 (Unix) $ man sched.h (Linux) $ man sched_setscheduler “RT” (real-time) scheduling SCHED_FIFO: a first-in, first-out policy 스레드는 FIFO 큐를 이용하는 FCFS 정책으로 스케줄 우선순위 높은 작업 또는 신호에 의해 선점(pre-emption)되지 않는 한 종료까지 수행 같은 우선순위 스레드들의 time-slicing 없음 SCHED_RR: a round-robin policy 같은 우선순위 스레드들의 time-slicing 있는 것 제외하고 SCHED_FIFO와 유사 “Normal” (non-real-time) scheduling SCHED_OTHER: the standard round-robin time-sharing policy SCHED_BATCH: for batch style execution of processes SCHE_IDLE: for running very low priority background jobs 운영체제

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"); 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 */ 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); 운영체제

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"); else { if (policy == SCHED_OTHER) printf("SCHED_OTHER\n"); else if (policy == SCHED_RR) 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) != 0) fprintf(stderr, "Unable to get policy.\n"); else { if (policy == SCHED_OTHER) printf("SCHED_OTHER\n"); else if (policy == SCHED_RR) 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 */ pthread_join(tid[i], NULL); * The thread will begin control in this function. void *runner(void *param) { /* do some work ... */ pthread_exit(0); 운영체제

다중 프로세서 스케줄링(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) = 분산 시스템 컴파일된 프로세스들의 기계어가 실행하고자 하는 프로세서의 기계어와 동일한 경우만 실행 가능 운영체제

전형적인 SMT 구조

SMP(Symmetric Multiprocessing) Architecture

NUMA (Non-Uniform Memory Access and CPU Scheduling 같은 보드에 있는 CPU의 메모리 접근시간이 더 적은 경우 강한 친화성(affinity)

멀티코어 프로세서 (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

A Dual-Core Design one chip

Solaris 2 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) 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) 운영체제

Solaris 2 Scheduling 운영체제

대화형과 시분할 스레드를 위한 Solaris 디스패치 테이블 우선순위 낮음 우선순위 높음 Solaris & Windows XP: 높은 우선순위 프로세스에 짧은 time quantum 할당 운영체제

base priority=normal  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 부여 운영체제

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 교환 운영체제

Linux Scheduling (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 round-robin time-sharing policy SCHED_BATCH: for batch style execution of processes SCHE_IDLE: for running very low priority background jobs “RT (real-time) scheduling SCHED_FIFO: a first-in, first-out policy SCHE_RR: a round-robin policy 운영체제

우선순위와 시간 조각 (Time-slice) 길이와의 관계 운영체제

우선순위에 따라 인덱스된 태스크 리스트 (List of Tasks Indexed According to Priorities) 운영체제

(예) 초기 Unix의 프로세스 스케줄링 CPU=decay(CPU)=CPU/2 60 clock interrupts per second 시간 프로세스A 프로세스B 프로세스C 우선순위 CPU계수 우선순위 CPU계수 우선순위 CPU계수 60 0 1 2 • • 60 30 60 60 1 75 60 60 0 1 2 • • 60 30 2 67 15 75 60 0 1 2 • • 60 30 3 63 7 8 9 • • 67 33 67 15 75 4 63 67 15 76 7 8 9 • • 67 33 5 68 16 76 63 7 운영체제

실시간 스케줄링 (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 되기를 기다려야 함  해결 ① system call을 preemptible하게 긴 system call안에 preemption points(더 높은 우선 순위의 프로세스가 있나 check, 있으면 interrupt) ② kernel전체를 preemptible하게 Kernel data보호를 위한 synchronization 필요 (예) Solaris 2: 우선순위 역전(priority inversion) 즉 kernel data 수정 중일 때는 control을 넘겨 주지 않음 (cf.) Mach: threads are nonpreemptible, threads are synchronous 운영체제

디스패치 지연 (Dispatch Latency) 운영체제

실시간 스케줄링 (Real-Time Scheduling) 우선순위 역전(priority inversion) kernel data 수정중인 프로세스의 우선순위가 선점하려는 프로세스의 우선순위 보다 낮은 상황  우선순위 상속 프로토콜로 해결 우선순위 상속 프로토콜(priority inheritance protocol) kernel data 수정중인 낮은 우선 순위의 프로세스가 선점하려는 프로세스의 높은 우선순위를 상속 받음, 끝나면 원래의 값으로 갈등 단계(conflict phase)의 내용 : 그림 19.5 (19장) 1. 커널에서 실행 중인 프로세스를 선점 2. 자원 회수(우선 순위 낮은 프로세스는 우선 순위 높은 프로세스가 요구하는 자원을 놓아줌) (예) Solaris 2 dispatch latency nonpreemptible = 100 ms dispatch latency preemptible = 2 ms 운영체제

레이트 모노토닉(Rate Monotonic) vs. EDF 운영체제

알고리즘 평가(Algorithm Evaluation) 결정성 모형화(Deterministic Modeling) 작업부하(workload)에 따른 성능 비교 : 5.7.1절 예제(p205-206) 꼭 보세요!!! 반환시간 대기시간 등 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 이용하여 응용의 동작 예측 가능하게 함 운영체제

Evaluation of CPU Schedulers by Simulation 운영체제

In-5.7 (p205)

In-5.8 (p205)

In-5.9 (p206)

(참고) 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 yield() method로 공평한 수행 (time slicing 효과) cooperative multitasking 운영체제

(참고) 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. 운영체제

(참고) 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 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. 운영체제

(참고) Round-Robin Scheduler public class Scheduler extends Thread { public Scheduler() { timeSlice = DEFAULT_TIME_SLICE; queue = new CircilarList(); } public Scheduler(int quantum) { timeSlice = quantum; 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; 운영체제

(참고) 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); 운영체제

(참고) 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); } 운영체제