6. Virtualization) Multi-level Feedback

Multi-level Feed-back Queue (MLFQ)는 두가지 문제를 개선하려 한다.
1. turnaround time 최적화

SJF또는 STCF가 프로세스의 실행시간과 같은 지식을 필요로 했던 것과 달리, 이러한 지식이 없는 상태에서 최적화를 해야한다.

2. response time 최소화

interactive유저들에게 반응적이어야한다. round robin은 response time을 줄였지만 turnaround time에서는 좋지 않았다.

 

즉, job의 길이에 대한 사전지식 없이 response time을 최소화 하는 동시에 turnaround time 또한 줄일 수 있는 스케줄러를 설계해야한다.

 

MLFQ : Basic Rules

OS마다 MLFQ에 대한 구현은 다 다르지만 알고리즘은 비슷하므로 이에 대해 알아볼 것이다.

 

MLFQ는 여러개의 queue들을 갖고 있고, 각 queue는 서로 다른 priority level이 부여되어 있다.

실행할 준비가 된 ready 상태의 job은 하나의 queue에 올라간다.

이때 MLQL은 각 queue의 priority level으로 어떤 job을 실행할지 결정한다. priority level이 더 높은 job이 실행된다.

• Rule 1 : If Priority(A) > Priority(B), A runs (B doesn't).

• Rule 2 : If Priority(A) = Priority(B), A&B run in Round Robin.

8.1을 보면 8개의 queue가 있고 A,B,C,D 4개의 ready 상태의 job이 queue에 들어있다.

A,B는 가장 높은 priority의 queue에, C는 5번째 priority queue에, D는 가장 낮은 priority에 있고

MFLQ는 priority가 가장 높은 A와 B를 time slice마다 switch하며 실행할 것이다.(round robin)

 

그러므로 MLFQ스케줄링의 핵심은 스케줄러가 어떻게 priority를 부여하냐에 달려있다.

MLFQ는 job들의 관찰된 행동을 기반으로 priority를  결정한다. 

예를들어, 어떤 job이 I/O이벤트 등으로 반복해서 CPU를 포기하면, MLQL은 이 job에 높은 priority부여한다.

반대로, 어떤 job이 CPU를 오랜기간 집중적으로 사용할 시, MLQL은 이 job의 priority를 떨어뜨린다.

이렇듯 MLFQ는 프로세스가 실행될때 그 프로세스에 대해 학습하고 해당 프로세스의 history를 파악함으로써 미래의 행동을 예측한다.

더 자세히 알아보도록 하자.

Attempt #1 : How To Change Priority

MLFQ는 job의 life time동안 계속해서 priority를 변경한다.

이 때 workload를 중요하게 고려하는데, job이 자주 CPU를 포기하면서 짧게 실행 되는지 아니면 CPU를 오랫동안 잡아먹는 "CPU-bound" job인지를 고려한다.

• Rule 3 : When a job enters the system, it is placed at the highest priority (the topmost queue).

• Rule 4a : If a job uses up an entire time slice while running, its priority is reduced (it moves down one queue).

• Rule 4b : If a job gives up the CPU before the time slice is up, it stays at the same priority level.

8.2를 보면 CPU bound job이 실행되고 있는 것을 알 수 있다. 처음 job이 실행될 때는 가장 높은 priority queue인 Q2에서 실행된다.

후에 time slice(10초)동안 실행되고, 스케줄러는 해당 job의 priority를 낮춘다. job은 Q1에서 실행되다 또 time slice를 전부 소모하고 가장 낮은 priority queue인 Q0으로 떨어진다.

8.3의 예에서는 MLFQ가 SJF와 비슷한 것을 확인할 수 있다.

A는 cpu bound job이고 B는 짧게 실행되는 job이다. A는 처음에는 제일 높은 priority에서 실행되다가 계속해서 time slice를 소모하고 Q0으로 떨어진다. 100초때 B가 도착해 가장 높은 priority queue에 들어오고 스케줄러는 더 높은 priority인 B를 실행한다.

B는 가장 낮은 priority로 떨어지기 전에 실행을 마치고 후에 가장 낮은 priority인 A가 실행된다.

 

자! 우리는 job의 실행시간에 대한 정보 없이 오로지 예측하면서 스케줄링 하고 있다. 실행시간이 짧은것 같은 job인 높은 priority를 주고 그렇지 않으면 점차적으로 priority를 낮춘다. 이 과정을 통해 짧은 실행시간의 job을 먼저 완료하고 이는 SJF와 상당히 유사하다(turnaround time을 줄인다).

그럼 I/O이벤트가 포함되면 어떨까.

Rule 4b에 따라 B는 time slice를 다 사용하기 전에 I/O이벤트로 CPU를 포기하고 동일한 priority를 유지하게 된다.

8.4에서 Rule 4b의 의도를 명확히 알 수 있다. "키보드 또는 마우스등의 입력을 받는 interactive job에는 패널티를 주지 않는다."

이로써 response time을 줄이려는 목표에 더 가까워진다.

 

하지만 현재 MLFQ에는 몇가지 문제점이 있다.

1. starvation

만약 interactive job이 너무 많으면, cpu bound job은 priority에 밀려 절대 CPU time을 받을 수 없을 것이다.

즉, 기아상태에 가까워질것이다.

2. game the scheduler

"game the scheduler"란 말은 이런 뜻이다. "스케줄러를 속여서 fair한 share보다 더 많은 자원을 받아내는 것".

예를 들어, time slice의 99%를 소모하고 CPU를 포기하는 것이다. 이렇게 하면 계속 높은 priority를 유지할 수 있고 결국 CPU를 독점할 수 있다.

3. change its behavior

예를 들어, CPU bound job이 중간에 interactive job으로 바뀔 수도 있다.

 

Attempt #2 : The Priority Boost

먼저 첫번째 문제 starvation을 해결해보자. 어떻게 CPU bound job에게 최소한의 cpu 사용을 보장해줄 수 있을까?

가장 간단한 아이디어는 주기적으로 모든 job의 priority를 boost해주는 것이다.

• Rule 5 : After some time period S, mobe all the jobs in the system to the topmost queue.

priority boost로 인해 starvation을 방지할 뿐만 아니라 3번째 문제 또한 해결할 수 있다.

cpu bound에서 Interactive하게 바뀐 job은 priority boost를 통해 다시 높은 priority를 부여받을 수 있다.

8.5를 보면 priority boost가 있을 때와 없을 때를 비교해 볼 수 있다.

cpu bound job이 하나 있고 두개의 interactive job이 있다.

왼쪽의 priority boost가 없을 때에는 cpu bound job은 interactive job에 밀려 starve하게 된다.

오른쪽의 priority boost가 있을 때에는 50초마다 priority boost가 발생하고, cpu bound job에 최소한의 cpu를 보장하게 된다.

 

물론 priority boost의 주기인 S를 어떻게 정해야 될지 의문이 생길 수 있다. 하지만 이는 난제다... 옳다는 답이 없어 이를 voo-doo constants라고 한다. 고로 개인의 결정에 달려있다. S가 너무 길면 cpu bound job이 굶주릴 것이고, S가 너무 짧으면 interactive job의 cpu사용 시간이 줄어들 것이다.

 

Attempt #3 : Better Accounting

이제 남은 문제 2번을 해결해 보자. 어떻게 gaming of scheduler를 방지할 수 있을까?

간단한 해결 방식은 각 queue에서 CPU time을 계산하는 것이다. 

스케줄러는 각 queue마다 프로세스의 실행 시간을 측정하고, 일정 시간이 넘어가면 priority를 떨어뜨리는 것이다.

(앞서 각 queue마다 time slice길이는 다를 수 있다고 했다. 마찬가지로 time allotment 또한 다를 수 있다.)

따라서 Rule 4a와 4b를 Rule 4로 다시 작성할 것이다.

• Rule 4 : Once a job uses up its time allotment at a given level (regardless of how many times it has given up the CPU), its priority is reduced.

8.6을 보면 이를 비교할 수 있다.

왼쪽에서는 gaming을 통해 두번째 job이 CPU를 독점하고 있고 오른쪽에서는 cpu time을 측정하고 priority를 떨어뜨림으로써 이를 개선한 것이 확인된다.

 

Tuning MLFQ And Other Issues

여전히 MLFQ에는 다른 이슈들이 많다. queue가 몇개가 있어야 할까? 각 queue마다 time slice 주기를 어떻게 주어야 할까? 얼마나 자주 priority boost를 발생시켜야 할까? 

여기에 정해진 값은 없지만 여러 경험 값으로 최대한 균형을 맞추는 수밖에 없다.

예를 들어, 대부분의 MLFQ는 queue마다 time slice값을 다르게 적용한다. 

보통 interactive job에 responsive하게 반응하기 위해, high priority queue들에는 짧은 time slice를 적용하고,

cpu bound job이 많은 low priority queue들에는 긴 time slice를 적용한다.

바로 8.7의 예와 같이 말이다.

 

MLFQ : Summary

이때까지 MLFQ를 개선해 보았다. 그러니 다시한번 정리해보자.

• Rule 1 : If Priority(A) > Priority(B), A runs (B doesn't).

• Rule 2 : If Priority(A) = Priority(B), A&B run in roud-robin fahion using the time slice of the given queue.

• Rule 3 : When a job enters the system, it is placed at the highest priority (the topmost queue).

• Rule 4 : Once a job uses up its time allotment at a. given level (regardless of how many times it has given up       the CPU), its priority is reduced (it moves down one queue).

• Rule 5 : After some time period S, move all the jobs in the system to the topmost queue.

 

MLFQ는 job의 길이에 대한 사전 정보 없이, short-running interactive job들과 long-running CPU-intensive job 둘 다에게 최적의 성능을 주기 때문에 BSD UNIX, Solaris, Windows Nt등 많은 OS들에서 기본 스케줄러로 사용되고 있다.