Multi-Level Feedback Queue (MFQ)
A MQF is scheduling algorithm with multiple priority levels managed using Round Robin queues, where a task is moved between priority levels based on how much processing time it has used.
Very important
Most commercial operating systems, including Windows, MacOS, and Linux, are variations of this scheduling algorithm. (from the OS book)
- Linux uses the
Priority + round robin
Learned in SE350.
Feedback-Based Scheduling
When a process enters the system, it starts in the highest-priority queue (RQ0). After each preemption, it is demoted to the next lower-priority queue. Short processes complete quickly without descending far, while longer processes drift downward.
Scheduling scheme
- All queues except the lowest use FCFS
- Processes in the lowest queue are handled in a Round Robin until they finish
Figure 9.10 shows the process flow through the queues in this multilevel feedback system, where the OS reallocates processor time based on priority changes.
MFQ vs. Round-Robin
I don’t get how this MFQ scheduler is so much better than round-robin?
- So round-robin is super fair. Every process gets an equal time slice, because they’re preempted whenever their time quanta has exceeded.
- MFQ is similar, but by introducing these levels, the idea is that at these different levels, there are different time quantas
MLFQ
MLFQ adjusts to how processes behave. Processes that need a quick response, like short I/O-bound or interactive tasks (think typing in a text editor), are promoted to higher-priority queues with shorter time slices. This makes the system more responsive to user input or interactive programs. CPU-bound processes are pushed to lower-priority queues with larger time slices, reducing overhead caused by frequent context switches.
- The scheduler will always choose a process from the highest-priority queue that has processes ready to run. It will only look at the lower-priority queues if the higher-priority queues are empty.
MLFQ overcomes this issue by using different time quanta for different queues. Higher-priority queues (usually containing interactive or short processes) have smaller time quanta, ensuring quick responsiveness, while lower-priority queues (with longer CPU-bound processes) have larger quanta to reduce context switching overhead.
MLFQ, on the other hand, adapts dynamically to process behavior:
- Short, interactive, or I/O-bound processes are promoted to higher-priority queues and given faster access to the CPU.