CPU 스케줄링

출처 : KMOOC / 운영체제 / 이화여대 반효경 교수님

 

CPU bound job

CPU를 길게 쓰는 프로그램. 중간에 I/O를 자주 사용하지 않는 프로그램

 

I/O bound job

CPU를 짧게 쓰는 프로그램. 중간에 I/O를 자주 사용하는 프로그램. 주로 사람하고 상호작용하는 프로그램.

 

I/O bound job에게 더 빠른 응답을 제공할 필요가 있음

- CPU를 빨리 쓰고 I/O 하러 가면 된다

- 사람과 자주 상호작용 하니까 더 중요하다

 

CPU Scheduler

CPU를 넘겨줄 프로세스를 결정하는 OS 내부 코드

 

Dispatcher

- 결정된 프로세스에게 실제로 CPU를 넘기는 OS 내부 코드

- 문맥 교환

CPU를 뺏긴 프로세스의 context를 save

CPU를 얻은 프로세스의 context를 load

 

참고

3번은 경우에 따라 어떤 프로세스는 I/O 끝나자마자 CPU를 써야 하고 이런 상황도 나올 수 있어서 적어둔 것

 

CPU utilization

- CPU를 놀리지 않고 사용한 시간의 비율

 

Throughput

- 시간당 완료한 프로세스의 개수

 

Response time

- 프로세스가 CPU burst에 진입해서(즉, CPU를 사용하러 와서) 최초로 CPU를 얻기까지 걸리는 시간

- CPU를 처음 사용

 

Waiting time

- 프로세스가 CPU burst에 진입해서 ready queue에서 대기한 시간의 총량

- CPU를 뺏기고 다시 ready queue에서 

 

Turnaround time

- CPU burst에서 사용한 전체 시간

- 즉, Waiting time + 실제로 CPU를 사용한 시간

 

Example

프로세스 A가 CPU burst에 진입

$\rightarrow$ ready queue에서 3초 대기

$\rightarrow$ CPU 2초 사용 후 빼앗김

$\rightarrow$ ready queue에서 3초 대기

$\rightarrow$ CPU 2초 사용 후 종료

 

Response time : 3s

Waiting time : 6s

Turnaround time : 10s

 

CPU 스케줄링 알고리즘

I. FCFS (First-come Fisrt-served)

nonpreemptive

 

II. SJF (Shortest Job First)

현재 CPU에서 수행중인 프로세스보다 remaining time이 더 짧은 프로세스가 새로 도착했을 때 처리 방법에 따라 구현이 달라질 수 있다

 

SJF는 predicted next CPU burst time을 priority로 사용하는 priority scheduling의 일종

 

SJF의 약점

1. starvation $\rightarrow$ aging(오래 기다리면 priority를 증가 시키는 방식)으로 해결

2. remaining time은 exponential averaging을 통해 예측만 할 수 있다

 

III. Round Robin (RR)

- timer 세팅해서 cpu 독점을 막는 방식

- I/O bound job은 짧은 할당시간 안에 모두 처리 가능

- CPU bound job에게도 처리할 수 있는 기회가 계속 주어진다

 

- 할당 시간이 너무 길면 FCFS나 다름 없어진다

- 할당 시간이 너무 짧으면 CPU를 너무 자주 뺏고 빼앗겨서 context switch가 너무 자주 발생

 

- long job이 많을 때는 average turnaround time이 길어지고 쓸 데 없이 context switch가 자주 일어나는 문제가 존재 

 

<비유>

- FCFS : 그냥 운빨

- SJF : long job은 그냥 죽어라

- RR : short job은 조금 기다리고 long job은 오래 기다린다

 

Multi-level Queue

foreground

- 응답 시간이 중요

 

background

- long job은 context switch가 적을수록 좋다

 

Fixed priority scheduling

- foreground 큐에 고정적으로 더 높은 우선순위를 부여

- 모든 foreground 큐가 처리된 이후에 background 큐를 처리한다

- starvation의 가능성 존재

 

Time slice

- foreground에 priority를 주기는 하지만 CPU time을 적절히 할당

 

프로세스는 다른 큐로 이동할 수 없다

 

프로세스가 다른 큐로 이동 가능한 방식이다

 

아래 2장도 그냥 하나의 예시에 불과하고 다양한 방법으로 구현할 수 있다

 

Multi-Processor Scheduling

Symmetric Multiprocessing

모든 CPU가 대등한 관계

 

Asymmetric Multiprocessing

하나의 CPU가 대장 CPU 역할을 맡는다

 

Real-Time Scheduling

 

Thread Scheduling

 

Local Scheduling

- OS가 thread의 존재를 모른다

- OS가 CPU를 해당 프로세스한테 주면 프로세스가 알아서 어느 thread에게 CPU를 줄지 결정

 

Global Scheduling

- OS가 thread의 존재를 안다

- CPU 스케줄링 할 때 어느 thread에게 CPU를 줄지 결정

 

Algorithm Evaluation

Queueing model

- 복잡한 수식을 계산해서 이론적으로 성능을 예측하는 방법

- 예전에 많이 사용한 방법

 

Implementation & Measurement

- 실제로 구현해보고 성능 테스트

- 현실적으로 쉽지 않다

 

Simulation

- 실제로 구현하는 것이 아니라 $P_1$, $P_2$, ... 이런 데이터(trace)를 만들어서 성능 계산을 해본다