[Operating Systems] Multi Level Feedback Queue

Overview

각각의 Level을 갖는 여러 개의 Queue가 존재하며, 새로운 Job이 도착하면 이 Queue 안에서 특정 규칙에 따라 우선순위가 변하면서 

여러 가지 Job들 중에 하나를 선정해 실행하는 Scheduling 방법론이다.

아래는 기본적 특징이다.

여러 개의 Queue를 가지며, 각각의 Queue는 Priority를 가진다.

여러 개의 작업들 중, 어떤 작업을 선정하여 실행할 것인지를 결정하기 위해 Priority를 기준으로 사용한다.

Job의 Priority는 계속해서 변하며, 그 작업이 CPU를 얼마나 점유하는지를 기반으로 결정된다.

(오래 점유할수록 Priority는 밀려난다)

Basic Rule

위와 같은 특성으로 보았을 때 우리는 기본적 규칙 몇 가지를 발견할 수 있다.

1. A의 Priority가 B보다 높을 때, A가 실행된다. (B는 실행되지 않는다)

2. A와 B의 Priority가 같을 때, A와 B는 Round Robin으로 실행된다.

이제 몇 가지 시도를 통해 다른 규칙들을 추가해 나갈 것이다.

How to change priority

다음과 같은 Rule을 추가해 보자.

3. Job이 System에 도착하면, 가장 높은 Priority를 가진다.

4-1. Job이 주어진 time slice동안 모두 CPU를 사용한다면 Priority는 감소한다.

4-2. Job이 주어진 time slice 중간에 CPU를 포기한다면, Priority는 유지된다.

예를 들어 A라는 CPU-Intensive(CPU-Bound)한 Job이 System에 도착했다고 해 보자.

우선순위 가장 높음: AAAA--------------------------------------------------

우선순위 중간:        -------AAAA------------------------------------------

우선순위 가장 낮음: ---------------AAAAAAAAAAAAAAAAAAAAAAAAAA

과 같은 형태로 time slice가 끝날 때 마다 우선순위는 낮은 곳으로 밀려나다가 최하위 우선순위에 도착하면 그곳에서 계속 실행될 것이다.

그러나 여기에는 큰 문제가 존재한다.

만약 여기에 B라는 CPU와 I/O에 관해 interactive한 작업이 추가된다고 해 보자. 그렇다면

우선순위 가장 높음: BB-----BB-----BB-----BB-----BB-----BB-----

우선순위 중간:        -----------------------------------------------

우선순위 가장 낮음: ----AA-----AA----AA-----AA----AA-----AA

의 형태가 될 것이다. 여기에서는 문제가 되지 않는다.

잠시 Basic Rule로 돌아가 가정 2(A와 B의 Priority가 같을 때, A와 B는 Round Robin으로 실행된다)에 주목해 보자.

그리고 B와 같은 특성을 가진 C라는 작업이 추가된다고 해 보자. 

그러면

우선순위 가장 높음: BBCCBBCCBBCCBBCCBBCCBBCCBBCCBBCC

우선순위 중간:        -----------------------------------------------

우선순위 가장 낮음: -----------------------------------------------

와 같은 형태가 되어 A는 B와 C가 완전히 종료될 때 까지 CPU를 전혀 점유하지 못하는 상태가 될 것이다.

이러한 현상을 Starvation(굶주림)이라고 한다.

어떻게 이 문제를 해결할 수 있는가?

The Priority Boost

해결법은 간단하다.

주기적으로 모든 Job의 Priority들을 최고 우선순위를 가지게끔 Boost 시켜주는 것이다.

그러므로 규칙 하나를 더 추가한다.

"설정한 어떤 주기 S가 되었을 때, 모든 Job의 우선순위를 최고치로 높인다."

그러면 CPU-Intensive한 Job들도 주기적으로 Priority가 가장 높게 될 것이기 때문에 Starvation을 피할 수 있을 것이다.

그렇다면, Priority Boost의 주기는 몇으로 설정해야 하는가?

너무 짧다면 각각의 Job들이 Priority를 갖는 의미가 사라질 것이고

너무 길다면 CPU-Intensive한 Job들은 Starvation에 오래 노출될 것이다.

따라서 Priority의 period를 잘 선정하는 것이 MLFQ에서 중요하다.

The Problem: Gaming of Scheduler

현재까지 설정했던 가정들을 살펴보자.

1. A의 Priority가 B보다 높을 때, A가 실행된다. (B는 실행되지 않는다)

2. A와 B의 Priority가 같을 때, A와 B는 Round Robin으로 실행된다.

3. Job이 System에 도착하면, 가장 높은 Priority를 가진다.

4-1. Job이 주어진 time slice동안 모두 CPU를 사용한다면 Priority는 감소한다.

4-2. Job이 주어진 time slice 중간에 CPU를 포기한다면, Priority는 유지된다.

5. 설정한 어떤 주기 S가 되었을 때, 모든 Job의 우선순위를 최고치로 높인다.

당신이 어떤 program을 개발한다면, 당연하게도 당신의 program이 높은 우선순위를 가지기를 희망할 것이다.

그래서 CPU-Intensive한 program이라도 높은 우선순위를 가지기 위해 다음과 같은 꼼수(?)를 사용할 수 있다고 생각할지도 모른다.

"계속해서 CPU를 점유하다가 Time Slice가 끝나기 직전에 의미없는 I/O를 통해 CPU점유를 포기하여 우선순위 유지"

따라서 우리는 이러한 현상을 막기 위해 규칙 4-1과 4-2를 조금 수정해야만 한다. 

Scheduler는 그 작업을 계속해서 감시하면서 CPU 점유를 언제 포기했는지가 아닌 주어진 time slice에서 얼마나 CPU를 사용했는지에 관한 비율을 통해 Priority를 결정해야만 한다.

즉, 규칙 4는 

"만약 어떤 Job이 할당받은 시간동안 CPU를 오래 점유한다면(언제 포기했는지, 얼마나 많이 포기했는지에 관계없이) Priority는 감소한다."

로 수정되어야만 한다.

MLFQ Rules

1. A의 Priority가 B보다 높을 때, A가 실행된다. (B는 실행되지 않는다)

2. A와 B의 Priority가 같을 때, A와 B는 Round Robin으로 실행된다.

3. Job이 System에 도착하면, 가장 높은 Priority를 가진다.

4. 만약 어떤 Job이 할당받은 시간동안 CPU를 오래 점유한다면(언제 포기했는지, 얼마나 많이 포기했는지에 관계없이) Priority는 감소한다.

5. 설정한 어떤 주기 S가 되었을 때, 모든 Job의 우선순위를 최고치로 높인다.

--------------------------------------------------

Reference

Operating Systems: Three Easy Pieces (Remzi H. Arpaci-Dusesdau, Andrea C. Arpaci-Dusesdau)