8. Scheduling: The Multi-Level Feedback Queue

 

Multi-Level Feedback Queue(MLFQ)

Objective

• Optimize turnaround time => Run short jobs first
• Minimize response time for interactive jobs

=> SJF는 turnaround time이 좋고 response time은 안좋고

=> RR은 turnaround time이 안좋고 response time은 좋은데

=> MLFQ는 이 두개를 합쳐서 둘다 좋게 만들려고 함

 

 

 

MLFQ : Basic Rules

• 다른 priority level을 가진 여러개의 Ready queue를 가지고 있음 
• higher queue에 있는 애들을 먼저 실행 , 같은 priority level 일 때는, RR 방식으로 실행 
• 각 job의 priority 는 실행하면서 계속 동적으로 조정된다. 

• 새로 생긴 job 들은, 처음에 가장 높은 priority를 부여받는다.
• 만약 I/O intensive job 이면, priority를 계속 유지 
• CPU intensive job이면, priority를 한 칸 낮춘다. 

I/O intensive(bound) vs CPU intensive(bound)

• I/O intensive job : time slice 동안 CPU만 사용하는 것이 아닌, I/O 처리와 그 외에 blocked 되는 여러 처리를 수행함
• CPU intensive : time slice 동안 한번도 blocked 되지 않고, 계속 CPU를 사용하는 job

 

Rule 1: If Priority(A) > Priority(B), A runs (B doesn't).
Rule 2: If Priority(A) = Priority(B), A & B run in RR.
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.
Rule 4b :  If a job gives up the CPU before the time slice is up, it stays at the same priority level 

 

• 이 방식으로 MLFQ는 SJF를 근사할 수 있다.

=> I/O bound 한 job들이 높은 queue에 계속 남아 있음. 즉, blocked 되어 있는 동안 다른 job이 선점할 수 있는데, 이게 shortest 한 job을 먼저 수행하는 SJF와 비슷한 퍼포먼스를 낸다고 말할 수 있음

 

 

 

Problem with the Basic MLFQ

 

1. Starvation

• interactive job이 너무 많으면 cpu bound job들은 실행 될 기회를 받지 못함(우선순위가 낮아서)

2. Game the scheduler

• time slice의 99% 를 사용하고, 남은 1%에 I/O를 실행해서 interactive job인 것처럼 scheduler를 속임
• 계속 높은 queue에 남으며, cpu time을 많이 가져감

3. A program may change its behavior over time

• cpu bound 였다가 I/O bound로 실행 중에 변하는 job이 있을 수 있음
• 처음에 cpu bound여서 우선순위가 낮아지면, 나중에 I/O bound로 바뀌어도 높은 queue로 올라오지 못함

 

 

The Priority Boost 

• 위의 문제를 해결하기 위해 새로운 룰 추가

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

• 일정 주기가 되면 모든 job을 다 가장 높은 queue로 옮김
• 위 문제의 1번, 3번은 해결이 가능하지만, 2번은 여전히 해결 불가 

 

Better Accounting

• 2번 문제를 해결하기 위해 Rule 4를 고침

Rule 4 : Once a job uses up its time allotment at a given level, its priority is reduced 

• time slice를 전부 다 써야 우선순위가 낮아지는 것이 아닌, 일정 비율 이상 사용하면 우선순위를 낮추는 것으로 변경

 

 

Tuning MLFQ And other Issues

• 높은 queue에 있는 job은 time slice를 짧게 할당
• 낮은 queue에 있는 job은 time slice를 길게 할당 

=> 이렇게 하는 것이 더 효율적이다

=> 낮은 queue에 있는 job들은 response time이 나빠지지만, 이 job들에게는 CPU 점유율이 더 중요하므로 신경쓰지 않음

 

 

 

The Solaris MLFQ implementation

• Solaris에서 사용하는 OS의 예
• 60개의 queue 사용 
• time slice의 길이를 천천히 높임
• priorities boosted는 1s 정도로 설정

 

 

MLFQ summary

 

최종 개정 MLFQ Rule

Rule 1: If Priority(A) > Priority(B), A runs (B doesn't).
Rule 2: If Priority(A) = Priority(B), A & B run in RR.
Rule 3 : When a job enters the system, it is placed at the highest priority.
Rule 4 : Once a job uses up its time allotment at a given level, its priority is reduced 
Rule 5 : After some time period S, move all the jobs in the system to the topmost queue