[운영체제] CPU 스케줄링 (1)

 

CPU-burst Time의 분포

여러 종류의 job(=process)이 섞여 있기 때문에 CPI 스케줄링이 필요

-interactive job에게 적절한 response 제공 요망

-CPU의 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용

 

프로세스으의 특성 분류

프로세스는 그 특성에 따라 다음 두 가지로 나눔

📍I/O-bound process

-CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job

-many short CPU bursts

📍CPU-bound process

계산 위주의 job

-few very long CPU bursts

 

CPU Scheduler & Dispatcher

CPU Scheduler

Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다

 

Dispatcher

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

이 과정을 context switch(문맥 교환)라고 한다

 

CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우이다
1. Running -> Blocked (Ex. I/O 요청하는 시스템 콜)
2. Running -> Ready (Ex. 할당시간만료로 timer interrupt)
3. Blocked -> Ready (Ex. I/O 완료 후 인터럽트)
4. Terminate

1,4에서의 스케줄링은 nonpreemptive(=강제로 빼앗지 않고 자진 반납)
All other scheduling is preemptive(=강제로 빼앗음)

 

스케줄링 성능

CPU utilization(이용률)

Throughput(처리량)

Turnaround time(소요시간, 반환시간)

Waiting time(대기 시간)

Response time(응답 시간)

 

FCFS(First-Come First-Served)

 

 

 

SJF(Shortest-Job-First)

각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용

CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄

Nonpreemptive

일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점 당하지 않음

 

Preemptive

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

이 방법을 Shortest-Remaining-Time-First(SRTF)이라고도 부른다

SJF is optimal-> 주어진 프로세스들에 대해 minimum average waiting time(최소한의 평균 대기 시간)을 보장

but Starvation(기아현상) 발생

 

 

 

Priority Scheduling

-highest priority를 가진 프로세스에게 CPU 할당

-SJF는 일종의 priority scheduling이다

-Starvation 문제 -> Aging 해결

 

 

Round Robin (RR)

각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐(일반적으로 10-100 milliseconds)

할당 시간이 지나면 프로세스는 선점(preempted) 당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다

n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다=>어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다

q large -> FCFS
q small -> context switch 오버헤드가 커진다