The Multi-Level Feedback Queue

Multi-Level Feedback Queue(MLFQ)

 

A Scheduler that learns from the past to predict the future.

 

목표는 2가지이다.

 

1. Optimize turnaround time -> Run shorter jobs first

2. Minimize response time without a priority knowledge of job length.

 

 

MLFQ has a number of distinct queues.

 

- Each queues is assigned a different priority level.

 

A job that is ready to run is on a single queue.

 

- A job on a higher queue is chosen to run.

- Use round-robin scheduling among jobs in the same queue.

 

예시를 하나 들어보도록 하자.

 

Process 가 임의로 여러개 있다고 하고 priority 3 => 2 => 1 순으로 있다고 할 때,

 

Priority                  Process               

      3        p1     /   p10   /   p5     /   p8

     2        p2     /   p3     /   p4    /   p9

     1        p12   /   p15   /   p20   /   p6

 

이런식으로 있다고 할 때, priority 가 가장 높은 3을 먼저 선택한다.

 

즉, priority 가 가장 높은 higher queue를 선택하고 선택된 queue 에 존재하는 여러 process 를 가지고

 

Round-Robin(RR) Scheduling 을 한다고 보면 된다. (time slice를 이용한 스케쥴링)

 

 

정리하자면 다음과 같이 정리할 수 있다.

 

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

Rule 2 : If Priority(A) = Priority(B), A & B run in RR.   

 

 

 Basic Rules

 

MLFQ variee the priority of a job based on its observed behavior.

 

- A job repeatedly relinquished the CPU while waiting IOs  =>  Keep its priority high

 

- A job uses the CPU intensively for long periods of time  =>  Reduce its priority.

 

이 2개를 정리해보면, CPU를 장시간동안 점유할 경우 priority 가 줄어들고

I/O 를 하고 있는 시간이 길수록 priority 가 늘어난다는 것을 알 수 있다.

 

2개의 code 가 있다고 가정해보자.

 

for(i = 0; i < N; i++){
    read(fp, buf, 4kb);
}

 

I/O 만 주구장창하는 code가 있다. 

 

이러한 경우 I/O를 많이 사용하고 CPU를 굉장히 조금 사용한다는 것을 알 수 있으며 short job 이라고 

부르며 priority 가 높다는 것을 짐작할 수 있다.

 

for(i = 0; i < N; i++){
    read(fp, buf, 1Mb);
    sort(v.begin(), v.end());
    reverse(s.begin(), s.end());
    ... // 다양한 memory operation
}

 

이러한 경우는 I/O를 위와 같이 동일하게 하는것처럼 보이지만 그 밑에 호출되는 sort, reverse 등

다양한 memory operation 를 하는것을 볼 수 있다.

 

즉, sorting 하고 reverse 하는 과정에서 CPU를 I/O에 비해 많이 사용하는 것으로 알 수 있으며 

이러한 경우를 long job 이라고 부르며 priority 가 작다는 것을 짐작할 수 있다.

 

How to Change Priority?

 

지금까지 본 것으로는 long job, short job 인 경우의 priority 가 결정되는 것과

priority 가 높은 Queue의 process들을 RR Scheduling 을 하는것 까지만 봤다.

 

그렇다면 어떻게 Priority 를 변경할 수 있을까?

 

적용되는 알고리즘을 살펴보도록 하자.

 

MLFQ priority adjustment algorithm

 

Rule 3 : When a job enters the system, it is placed at the highest priority.

 

Rule 4a : If a job uses up an entire time slice while running, its priority is reduced.

              (it moves down on queue)

 

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

 

알고리즘을 정리해보면 다음과 같다.

 

job이 들어올 때 먼저 가장 높은 priority에 배치하고 실행하면서 time slice 안에 CPU 를 내주거나 

지속적으로 붙잡고 있는 경우에 priority 를 올리거나 내리는 방법이다.

 

예를 들어보자.

 

Process C, D가 있다고 할 때, fork()를 띄워서 A, B가 들어오면서 스케쥴링을 한다고 하자.

(A, B는 short job, C는 medium job, D는 long job)

 

Priority                 Process

 4(2ms)                A     B

 3(4ms)                         

 2(16ms)                  C   

 1(64ms)                  D   

 

예를 들어서 Process D 가 9ms 에서 CPU를 relinquish 해버리는 경우라면 priority 가 2로 올라갈 수 있다.

 

여기서 가장 priority가 높은 4 에서 process를 실행하는데 C, D는 scheduling 되지 않는다.

 

즉, A, B가 끝나면 priority 2로 내려와서 C가 실행되고 그 다음 D가 실행되는

이러한 현상을 starvation 이라고 불린다.

 

 

 

 

Assumption :

 

- job A : A long-running CPU-intensive job

- job B : A short-running interactive job (20ms runtime)

- A has been running for some time, and then B arrives at time T = 100.

 

 

여기서 A는 검은색, B는 옅은 회색을 의미한다.

 

보면 A process가 Q2 => Q1 => Q0 로 이동하면서 계속해서 실행하는 모습이다.

 

그리고 B가 100 ms 에 도착할 때, Q2 로 B가 들어오고 Q1 으로 이동해서 10ms 씩 총 2번을

거쳐서 총 20ms 의 runtime 이 이뤄져서 Q1 에서 CPU 를 relinquish 하고 끝나게 된다.

 

그래서 기존의 A process가 Q0에서 계속해서 실행하는 모습이다. 

 

 

 

 

Assumption : 

 

- job A : A long-running CPU-intensive job

- job B : An interactive job that need the CPU only for 1ms before performing an I/O

 

 

The MLFQ approach keeps an interactive job at the highest priority.

 

이게 좀 어려워 보인다.

 

A, B가 있는데 A는 CPU를 가장 오래쓰는 long job, B는 CPU를 1ms만 쓰는 short job 이다.

 

A는 long job 이므로 priority 가 가장 아래인 Q0 로 깔리게 되고 B는 short job 이므로 

priority 가 가장 높은 Q2 에 있는 모습이다.

 

A에서 timer interrupt 가 실행되면 Q2의 B가 실행된다.

 

이 과정을 Process State 관점으로 보면 다음과 같다.

 

Q2 에서 B가 Running state이고 A는 run을 기다리고 있는 Ready state이다.

 

1ms 가 지나면 A는 I/O, B는 CPU를 사용하므로 A는 Blocked state, B는 Running state 이다.

 

그렇게 반복하는 과정이 이뤄진다.

 

 

Problems with the Basic MLFQ

 

Starvation

 

- If there are "too many" interactive jobs in the system.

- Long-running jobs will never receive any CPU time.

 

Starvation 문제는 interactive job이 많을수록 long time job을 받을 수 없다는 점이다. (위에서 간단히 봄)

 

Game the scheduler

 

- After running 99% of a time slice, issue an I/O operation.

- The job gain a higher percentage of CPU time.

 

악의적인 공격이라고 볼 수 있는데 time slice 10ms 에서 끝나기 바로 99% 즉, 9.9 ms 에서

I/O operation 을 한 경우이다.

 

예를 들어서 99퍼쯤에 끝날때쯤에 dummy I/O 를 실행함으로써 아무짓도 안하지만 I/O를 읽어버리는 악의적인 코드가 있다고 한다.

 

이러한 process가 있다면 계속 우선순위가 높은 곳에 배치될 수 밖에 없다.

 

결국에 이런 프로세스는 우선순위가 높은 곳에 배치되기 때문에 실행시간을 잡아먹어버릴 수 밖에 없다.

 

자연스럽게 starvation도 발생해버리고 CPU cycle을 독식해버리는 상황이 발생한다.

 

A program may change its behavior over time.

 

- CPU bound process => I/O bound process

 

즉, process의 behavior이 바껴서 priority를 위로 올릴 수는 없다.