운영체제 - CPU 스케쥴링(3)

운영체제 - CPU 스케쥴링(3)

- CPU 스케쥴링은 CPU Burst 단위로 일어난다.

앞서, CPU 스케쥴링 기법으로 ①FIFO, ②SJF, ③Round Robin을 알아보았다.

SJF(Shortest Job First)는 가장 이상적인 스케쥴링 기법이지만 운영체제가 각 프로세스의 CPU Burst size를 예측할 수 없기 떄문에 불가능한 기법이라고 하였다.

그에따라 FIFO를 대체할 기법으로 Round Robin이 등장하였는데 항상 Round Robin이 FIFO보다 성능이 우수할까?

예를들어, 100 time을 요구하는 process 10개가 Ready Queue에 있다고 가정해보자.

Response time을 각 스케쥴링 기법에 대해 측정해보면

FIFO의 평균 Response time : (100+200+300+ ... + 1000) / 10

Round Robin의 평균 Response time : 대략 1000

위 경우에는 FIFO가 Round Robin보다 우수한 성능을 보여준다.

즉, 작업의 Workload에 따라서 스케쥴링기법의 성능이 달라짐을 보여주는 사례이다.

따라서, 작업의 Workload에 따라 스케쥴링 방식을 변경할 수 있는 기법. 즉, Adaptive Scheduling이 요구되었다.

* Adaptive Scheduling?

- workload의 특성에 따라 time slice의 크기를 동적으로 바꿔주는 스케쥴링 기법이다.

- FIFO의 경우 Time slice가 무한이라고 할 수 있다.

- Round Robin의 경우 Time slice를 임의의 값으로 설정했었다.

- FIFO의 정반대를 RR(TS=0)이라고 할 수 있다.

프로세스를 크게 두 종류로 나눌 수 있다.

1) I/O Bound process

- CPU Burst size가 작고 I/O Burst size가 큰 process이다.

- 예를들어, process(A)가 1ms cpu burst, 10ms I/O burst를 가지고 있다고 하자.

2) CPU Bound process

- CPU Burst size가 크고 I/O Burst size가 작은 process이다.

- 예를들어, process(B)가 계속 cpu 연산만 수행한다고 가정해보자

프로세스 A, B가 Ready Queue에 존재 할때 RR(TS=100ms), RR(TS=1ms) 스케쥴링 기법을 적용할 때 어떤 성능차이를 보일까?

RR(TS=100ms)를 사용하는 경우

1. CPU utilization = 100%
2. I/O utilization = 10/101 = 10%

RR(TS=1ms)를 사용하는 경우

1. CPU utilization = 100%
2. I/O utilization = 10/11 = 90%

위 지표로만 바라보면 RR(TS=1ms)인 경우 성능이 좋다고 할 수 있겠으나 사실 1ms단위마다 timer h/w interrupt가 발생하므로 CPU Bound process는 1ms마다 불필요한 오버헤드를 갖게되는 것이다.

즉, CPU Bound process는 큰 Time slice 단위를 요구하고,

I/O Bound process는 작은 Time slice 단위를 요구한다.

이렇게 workload에 따라 adaptive한 스케쥴링 기법을 적용한 것이 Multi-level Feedback Queue이다.

Multi-level Feedback Queue

I/O Bound process, 즉 Time slice가 적은 process는 1번 큐에 대기시킨다.

CPU Bound process, 즉 Time slice가 큰 process는 3번 큐에 대기시킨다.

이렇게 process의 특성(CPU Bound, I/O Bound)에 따라 각기 다른 Time slice를 적용시킴으로써 workload에 adaptive한 성능이 우수한 스케쥴링을 완성시킬 수 있다.

Multi-level scheduling이 적용된 예

PROC 1 runs for 1 ms and blocks

PROC 2 runs for 1 ms and doesn’t block

PROC 2 gets priority-1, time slice 2

PROC 2 runs for 2 ms and doesn’t block

PROC 2 gets priority-2, time slice 4

PROC 2 runs for 4 ms and doesn’t block

PROC 2 gets priority-3, time slice 8

PROC 2 runs for 3 ms and gets preempted

PROC 1 runs for 1 ms and blocks

PROC 2 runs for 5

PROC 1 runs for 1 ms and blocks

PROC 2 runs until PROC 1 is ready and preempts it

현대 CPU 스케쥴링 기법

Real-time system

- 작업 수행이 요청되었을 때, 이를 주어진 시간안에 성공적으로 마쳐야 하는 시스템

- 이러한 경우, 우선순위 기반 스케쥴링이 요구된다.

- 프로세스들에게 우선순위를 매기고 우선순위가 높은 프로세스를 먼저 수행하는 스케쥴링 기법이다.

- 우선순위 스케쥴링에서는 starvation이 발생한다.

* starvation?

- 수행할 준비를 마치고 CPU를 할당받기를 기다리는 프로세스가 무기한 연기되는 현상

Fair share scheduling(=Bandwidth scheduling)

- workload에 따라 response time이 달라지면 multi-media(동영상) 서비스를 제공할 수 없다.

- Fair share 스케쥴링 기법은 대기중인 프로세스들에게 정해진 비율에 따라 CPU의 bandwidth를 분배하는 스케쥴링 기법이다.

- Ex. CFS(Complete Fair Scheduling). 리눅스 운영체제가 채택한 방법이다.