Multi-Level Feedback Queue (MLFQ)
- A Scheduler that learns from the past to predict the future
- Optimizie turnaround time -> Run shorter job first
- Minimize response time for interactive jobs
MLFQ는 turnaround time에 sensitive한 SJF와 response time에 sensitive한 RR의 장점을 혼합한 방식이다.
Basic Rules
- MLFQ는 다른 priority level을 가지는 ready queue가 여러 개 존재한다.
- Rule 1 : 우선순위가 높은 큐에 존재하는 process를 먼저 실행한다.
- Rule 2 : 우선순위가 같은 큐에 존재하는 process들은 Round Robin 방식으로 실행한다.
- Rule 3 : Job이 system에 도착하면, 우선순위가 가장 높은 큐에 배치한다.
- Rule 4a : Job이 time slice동안 CPU에서만 실행되면(cpu bound) 우선순위를 낮춘다.
- Rule 4b : Job이 time slice동안 다른 작업도 진행하면(I/O bound) 우선순위를 유지한다.
-> I/O bound한 job들이 CPU bound한 job보다 run time이 짧은데 우선순위가 높은 큐에 배치되어 먼저 실행된다. 결국 SJF와 비슷한 방식이 되는 것이다.
time slice가 10ms라고 해보자.
위의 그림처럼 time slice동안 CPU에서만 실행되면 우선순위가 낮은 큐로 이동한다.
A는 CPU-bound한 job이며 B는 I/O-bound한 job이다.
B의 runtime은 20ms이고 100ms에 도착한다고 하자.
새로운 job이 system에 도착하면 우선순위가 가장 높은 큐에 배치되므로 B는 처음에 Q2에 위치한다.
time slice인 10ms동안 CPU에서 실행되기 때문에 우선순위가 낮아진다.
A는 CPU-bound job이고 B는 I/O-bound(interactive) job이다.
B는 1ms 실행되고 I/O 작업이 수행된다고 하자.
그렇다면 A보다 B가 높은 우선순위 큐에 위치해있기 때문에 B가 먼저 1ms 실행되고 I/O 작업을 수행하는 동안 A가 실행되는 모습이다.
Problems with the Basic MLFQ
-
Starvation
우선순위가 높은 큐에 존재하는 job의 개수가 많으면, 우선순위가 낮은 큐에 있는 job이 실행되지 못하는 현상이다. -
Game the scheduler
time slice의 99% 지점에서 의미없는 I/O 작업을 수행하여 interactive job인 것처럼 scheduler를 속여 우선순위가 높은 큐에 남아 있는 현상 -
Program may change its behavior over time
program이 실행 중간에 CPU bound -> I/O bound로 바뀐다면 CPU bound 였기 때문에 우선순위가 가장 낮은 큐에 위치해 있을 것이다. I/O bound로 바뀐다고 해서 우선순위가 변하지 않는 문제
The Priority Boost
- Rule 5 : 일정 주기로 system의 모든 job들을 우선순위가 가장 높은 큐로 boost하기
Reboot를 하면서 1, 3번 문제를 해결할 수 있다.
Starvation이 해결되는 이유는 CPU-bound job들이 한 번이라도 실행될 수 있기 때문이다.
Better Acounting
- Rule 4 (Rewrite Rule 4a and 4b) : 큐에 할당된 시간을 전부 실행에 사용하면 우선순위가 낮아진다.
우선순위가 다른 큐면 할당된 시간(비율)도 달라진다.
Tuning MLFQ and other issues
- high-priority queue -> short time slice
- low-priority queue -> long time slice
우선순위가 낮으면 run-time이 길어 time slice를 길게 설정한다.
time slice가 길면 response time이 길어지긴 하지만 별로 중요하게 생각하지 않는다.
MLFQ : Summary
- Rule 1 : 우선순위가 높은 큐에 있는 job들이 먼저 실행된다.
- Rule 2 : 우선순위가 같은 큐에 있는 job들은 RR 방식으로 실행된다.
- Rule 3 : Job이 system에 도착하면 우선순위가 가장 높은 큐에 배치된다.
- Rule 4 : 큐에 할당된 시간을 run time에 전부 소모하면 우선순위가 낮아진다.
- Rule 5 : 일정 주기로 모든 job을 우선순위가 가장 높은 큐로 boost한다.
