[운영체제/OS] CPU 스케쥴링 - FIFO, SJF, RR, MLFQ

스케쥴링의 필요성

- 과거의 Uni-programming 컴퓨터 시스템(싱글 프로세스)에서는 CPU 스케쥴링의 개념이 필요하지 않았다. 해당 시스템에서 수행되는 프로세스가 1개이니 분배할 이유가 없었기 때문이다.

- 하지만, 여러개의 프로세스가 수행되는 현대의 컴퓨터 시스템에서는 OS가 CPU를 잘 분배하지 못하면 오랜 기간동안 수행되지 않거나 아예 수행되지 않는 프로세스가 발생할 수 있다.

- 따라서 OS에게는 CPU라는 자원의 분배의 책임이 존재한다.

 

CPU Burst time

- 여러 프로세스가 수행될 때 프로세스가 CPU를 장악하는 시간을 CPU Burst time이라고 한다.

- 프로세스는 I/O등의 이유로 waiting 하는 상태, Ready Queue에서 대기하는 ready 상태를 가질 수 있다.

- 그 밖에 CPU에 의해 실행되는 상태를 running 상태라고 하는데, running 상태의 시작부터 끝까지의 시간을 CPU Burst time이라 칭한다.

- 이 CPU Burst time의 길이에 따라 프로세스를 구분할 수 있는데, CPU Burst Time 이 크면 CPU intensive process, CPU Burst Time이 작으면 I/O intensive process로 구분할 수 있다.

 

CPU Intensive Vs. I/O Intensive

- CPU Intensive 프로세스는 CPU를 많이 사용(오랜 기간동안 선점)하는 프로세스이다. 그 예로는 수학 연산을 많이 하는 프로세스가 있겠다.

- I/O Intensvie 프로세스는 CPU를 많이 선점하기 보단 I/O 연산을 많이 하는 프로세스이다. I/O 연산을 많이 하니 CPU Burst time이 짧을 수 밖에 없게 된다. 

 

CPU 스케쥴링 동작 개요

CPU 스케쥴러는 다음과 같은 이벤트가 발생하면 동작한다.

- 어떤 프로세스가 running 되다가 waiting으로 변경되는 경우 (I/O 연산 등)

- 어떤 프로세스가 running 되다가 ready로 변경되는 경우

- 어떤 프로세스가 waiting 하다가 ready로 변경되는 경우

 

위와 같은 상황에서 스케쥴러가 트리거되어 동작한다.

 

디스패처(Dispatcher)

- 스케쥴러가 트리거되어 동작한다는 것은 CPU를 선점하는 프로세스가 변경된다는 의미이다.

- 프로세스가 변경될 때 문맥 교환등의 작업이 이루어지는데 이것을 디스패치 모듈이 진행한다.

- 디스패치 작업이 이루어질 때 반드시 오버헤드가 발생한다. (Trade-off)

 

스케쥴링 Policies

스케쥴링을 통해 얻고자 하는 것들엔 다음과 같은 것이 있다.

- 자원 사용률의 극대화: 만약 CPU와 같은 자원이 사용되지 않고 Idling 하는 시간이 많다면 그것은 비효율적이기 때문

- 오버헤드의 최소화: 다수의 프로세스를 동시에 사용하는 것처럼 착각하도록 오버헤드를 줄여야한다.

- 문맥교환의 최소화: 문맥교환은 오버헤드를 발생시키기 때문에 그러한 측면에서 문맥 교환을 최소화 하여야 한다.

 

FIFO

정의

먼저 도착한 프로세스가 먼저 수행되는 스케쥴링 Policy

특징

- CPU Burst time이 큰 프로세스가 먼저 수행된다면 그 뒤에 수행되는 프로세스들을 그것의 수행을 모두 기다려야한다.

- 이것을 convoy effect 라고 한다. convoy effect가 발생하면, 하나의 프로세스가 오랜기간 CPU를 독점하게된다.

- convoy effect를 방지하기 위해 time-slice 기법을 적용할 수 있다.

 

Shortest Job First(SJF)

정의

CPU Burst time이 짧은 것부터 수행시키는 스케쥴링 Policy

특징

- 각 프로세스들의 CPU Burst time을 알고 있다는 가정하에 수행할 수 있는 Policy이다.

- 그리디하게 동작하는 Policy 이지만 항상 최적해를 낸다는 특징이 있다.

- 하지만, 각 프로세스들의 CPU Burst time을 안다는 것은 불가능하기 때문에 성능의 측정 척도로 사용된다.

 

바리에이션

비선점형 SJF

특징

- CPU가 프로세스를 할당받은 후, 해당 Job을 모두 수행한 뒤에 다른 프로세스를 수행할 수 있는 방식

- 비선점식으로 동작하기 때문에 비선점형 SJF라 불린다.

 

선점형 SJF

특징

- 수행해야할 프로세스가 추가될때마다 "가장 Remain time이 적게 남은 프로세스"를 골라 수행하는 방식

- 프로세스가 추가되면 기존에 수행하던 프로세스의 수행을 멈추고 스케쥴링을 하기 때문에 선점형 SJF라고 불린다.

 

일반적으로 비선점형 SJF의 평균 대기 시간이 더 짧지만, 비선점형 SJF는 프로세스가 추가될 때 마다 스케쥴링을 한다는 것을 간과하면 안된다.

 

Round Robin (RR)

정의

Time-slice 기법을 적용한 스케쥴링 Policy.

특징

- FIFO의 문제점이 무엇이었는가? CPU Burst time이 큰 프로세스가 먼저 수행되면 그 뒤에 수행되는 프로세스의 대기시간이 길어진다는 것이 문제였다.

- RR 기법은 그것을 해결하기 위해 Time-slice 기법을 적용한다.

- 프로세스가 수행되고 일정 시간(time-slice)만큼의 시간이 지나면 해당 프로세스를 Run-queue에 재삽입한다. (재배치)

- Time-slice 마다 인터럽트가 발생하여 스케쥴링이 동작한다는 점에서, 불필요한 인터럽트가 다수 발생할 수 있고 컨텍스트 스위칭의 비용이 크게 발생할 수 있다.

 

Multi-level Feedback Queue

정의

큐를 여러개 두어 우선순위를 갱신하는 스케쥴링 Policy.

키 아이디어

- SJF 방식에서 알아봤듯이, CPU Burst Time이 짧은 프로세스를 먼저 수행하고 반대로 긴 프로세스를 나중에 수행하면 평균 대기시간이 짧았다.

- 그러나 SJF 방식은 CPU Burst Time을 아는 상황에만 적용할 수 있는 스케쥴링 기법이다.

- MLFQ 방식은 큐를 여러개 두어 CPU Burst Time에 따라 우선순위를 피드백하는 방식이다.

 

알고리즘 설명

- 새롭게 추가되는 프로세스는 높은 우선순위를 가지도록 설정한다.

- Time-slice 만큼 시간이 지나 프로세스가 선점적으로 스케쥴링 될 때, 해당 프로세스가 Blocking 연산을 했는지 조사한다.

- 만약 Blocking 연산을 했다면 I/O 연산보다는 CPU 연산을 더 많이 하는 프로세스라는 것을 의미한다.

- 따라서 해당 프로세스의 우선순위를 낮춘다. 더불어, CPU 연산을 많이 하는 프로세스이기 때문에 Time-slice도 2배 해준다.

- 이런식으로 동작하면 I/O 연산을 많이 하는 프로세스는 빠르게 수행되고, CPU 연산을 많이 하는 프로세스는 I/O 연산을 많이 하는 프로세스가 끝나고 수행되기 때문에 Convoy effect 또한 발생하지 않는다.