CPU 스케쥴링

CPU burst time 분포

→ IO bound job(CPU를 잡고 계산하는 시간보다 IO에 많은 시간이 필요한 job) 은 빈도가 많지만 CPU 를 짧게 쓴다. CPU bound job(계산 위주의 job) 은 빈도가 적지만 CPU 를 길게 쓴다. job 의 종류가 섞여있다.

→ 여러 종류의 job(process)이 섞여 있기때문에 CPU 스케쥴링이 필요

CPU Scheduler

•

ready 상태의 프로세스 중 CPU 를 줄 프로세스를 고른다.

•

운영 체제 안에서 cpu scheduling 을 하는 코드가 있다.

•

어떤 프로세스에 줄 것인지, 중간에 언제 뺏을 것인지 두 가지 이슈

Dispatcher

•

CPU 의 제어권을 CPU Scheduler 에 의해 선택된 프로세스에게 넘긴다.

•

이 과정을 context switching 

CPU 스케쥴링이 필요한 경우

•

Running → Blocked

◦

IO 요청하는 시스템 콜

•

Running → Ready

◦

timer interrupt

•

Blocked → Ready

◦

IO 완료 후 interrupt

•

Terminate

•

preemptive(강제로 빼앗음, 선점형) vs non-preemptive(자진 반납, 비선점형)

Scheduling Criteria(Performance Index)

•

CPU utilization(이용률)

◦

keep the CPU as busy as possible

•

Throughput(처리량)

◦

complete processes’ execution per time unit

•

Turn-around time(소요 시간)

◦

amount of time to execute a particular process

•

Waiting time(대기 시간)

◦

amount of time a process has been waiting in the ready queue

•

Response time(응답 시간)

◦

하나의 요청이 submit 되고 응답이 produce 될 때까지 걸린 시간, not output

◦

사용자 응답과 관련하여 중요하기때문에 존재

→ 대기 시간은 queue 에서 총 기다린 시간, 응답 시간은 처음 queue 에 들어와서 처음 CPU 를 얻기까지 기다린 시간, 소요 시간은 CPU에 들어와서 나갈 때까지 총 걸린 시간

•

위 두개는 시스템 상, 아래 세개는 프로세스 상

•

→ 중국집 주방장, 손님 예시

•

FCFS(First Come First Served)

◦

average waiting time = (0 + 24 + 27) / 3 = 17

◦

프로세스 도착 순서에 따라 variation(분산) 이 크다.

◦

은행, 화장실 예시

◦

비선점형

◦

비효율적, 공평함

◦

convoy effect: short process behind long process

•

SJF(Shortest Job First)

◦

CPU 사용 시간이 가장 짧은 프로세스를 먼저 스케쥴

◦

전체 queue 가 줄어드는 효과

◦

minimum average waiting time 보장

◦

two schemes

▪

비선점형

•

일단 CPU 를 잡으면 CPU burst 가 완료될 때까지 CPU 를 놓지 않음

▪

선점형

•

현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time 을 가지는 프로세스가 도착하면 CPU 를 빼앗김

•

이 방법을 SRTF(Shortest Remaining Time First)

▪

비선점형은 CPU 사용이 완료 됐을 때 스케쥴링, 선점형은 도착, 완료 둘 다 스케쥴링

◦

문제 1: starvation(기아 현상) 발생 가능

◦

문제 2: CPU burst time 을 예측할 수 없는 프로세스가 있다.

▪

과거 사용 흔적으로 예측(exponential averaging)

▪

보통 interactive IO 는 짧고, 계산하는 프로세스는 길다.

•

Priority Scheduling

◦

정수로 우선순위가 주어짐

◦

작은 수가 우선순위가 높은 것

◦

문제: starvation

◦

해결책: aging 방식, 오래되면 우선순위를 높인다.

•

Round Robin

◦

현대적인 CPU 스케쥴링은 RR 을 기반

◦

각 프로세스는 동일 크기의 CPU 할당 시간(time quantum)을 가진다. 일반적으로 10-100 ms

◦

장점: 응답 시간(response time)이 빠르다.

◦

할당 시간이 끝나면 인터럽트가 발생해서 CPU를 빼앗기고 아직 처리가 되지 않았다면 큐의 제일 뒤에 가서 대기

◦

할당 시간이 길면 FCFS, 할당 시간이 짧으면 context switch 가 빈번하게 발생하여 오버헤드가 커짐

◦

n 개의 프로세스가 CPU 큐에 있는 경우

▪

최대 (n-1) * 할당시간

▪

대기시간이 프로세스의 CPU 사용 시간에 비례

◦

예시

Multi-level Queue

•

Ready queue 를 여러 개로 분할

◦

foreground(interactive)

◦

background(batch)

•

각 큐는 독립적인 스케쥴링 알고리즘

◦

foreground - RR

◦

background - FCFS

•

큐에 대한 스케쥴링

◦

Fixed priority scheduling

▪

starvation

◦

time slice

▪

각 큐에 CPU time 을 적절한 비율로 할당

Multi-level Feedback Queue

•

프로세스가 다른 큐로 이동 가능

•

aging 방식

•

CPU 사용 시간이 짧은 프로세스에게 우선순위를 높게 침 

•

사용 시간 예측 불필요

Multi-Processor Scheduling

•

CPU 가 여러 개인 경우 복잡해짐

•

homogeneous processor

◦

queue 를 한줄로 세우기

◦

특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우(미용실 전담 디자이너 예시)

•

load sharing

◦

부하 조절

◦

별개의 큐 vs 공동 큐

•

symmetric multiprocessing

◦

각 프로세서가 각자 알아서 스케쥴링

•

asymmetric multiprocessing

◦

하나의 프로세서가 시스템 데이터 접근, 공유 책임

◦

나머지 프로세서는 거기에 따름

Real-Time Scheduling

•

deadline 이 있는 job

•

정해진 시간안에 일이 수행되어야 하는 job

•

hard real time system

◦

정해진 시간 안에 반드시 끝내는 스케쥴링

•

soft real time computing

◦

일반 프로세스보다 높은 priority

Thread Scheduling

•

local scheduling

◦

user level thread 의 경우 사용자 프로세스가 직접 thread 를 관리하고 운영 체제는 쓰레드의 존재를 모름

◦

사용자 프로세스가 쓰레드의 스케쥴을 결정함

•

global scheduling

◦

kernel level thread 의 경우 운영 체제가 쓰레드의 존재를 알고 있다.

◦

운영 체제가 프로세스 스케쥴링 하듯이 쓰레드의 스케쥴 결정

Algorithm Evaluation

•

queueing model

◦

이론적임

◦

확률 분포로 주어지는 arrival rate 와 service rate 등을 통해 각종 performance index 값을 계산

•

implementation & measurement

◦

실제 시스템에 알고리즘을 구현하여 실제 작업에 대해 성능 측정 및 비교

•

simulation

◦

모의 프로그램으로 작성 후 더미 데이터를 넣어 결과 측정