Multi-Level Feedback Queue (MLFQ)
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). See Unix Scheduler.
MLFQ = Priority + round robin.
Learned in SE350.
Resources
There's also MLQ
MLQs are essentially like MLFQs, but there is no moving around between priorities based on how long the process actually runs.
How it works: 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.
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.
Time-slicing:
- Each queue is assigned a time quantum or time slice, which determines how much CPU time a process in that queue is allowed to use before it is preempted and moved to a lower priority queue.
Preemption:
- Preemption is allowed in MLFQ scheduling, meaning that a higher-priority process can preempt a lower-priority process to ensure it gets the CPU time it needs.
MFQ vs. Round-Robin
I am confusion
I don’t get how this MFQ scheduler is so much better than round-robin?
MFQ improve system responsiveness.
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, and at each different levels, there are different time quantas:
- Higher-priority queues (usually containing interactive or short processes) have smaller time quanta, ensuring quick responsiveness
- Lower-priority queues (with longer CPU-bound processes) have larger quanta to reduce context switching overhead
How?
MLFQ, compared to Round Robin, adapts dynamically to process behavior:
- Processes that need a quick response are promoted to higher-priority queues with shorter time slices
- CPU-bound processes are demoted to lower-priority queues with larger time slices, reducing overhead caused by frequent context switches
This makes the system more responsive to user input or interactive programs.
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.
- Short, interactive, or I/O-bound processes are promoted to higher-priority queues and given faster access to the CPU.
Example
Taken from geeksforgeeks.
Let’s suppose that queues 1 and 2 follow round robin with time quantum 4 and 8 respectively and queue 3 follow FCFS.
Implementation of MFQS is given below:
- When a process starts executing the operating system can insert it into any of the above three queues depending upon its priority . For example, if it is some background process, then the operating system would not like it to be given to higher priority queues such as queues 1 and 2. It will directly assign it to a lower priority queue i.e. queue 3. Let’s say our current process for consideration is of significant priority so it will be given queue 1 .
- In queue 1 process executes for 4 units and if it completes in these 4 units or it gives CPU for I/O operation in these 4 units then the priority of this process does not change and if it again comes in the ready queue then it again starts its execution in Queue 1.
- If a process in queue 1 does not complete in 4 units then its priority gets reduced and it is shifted to queue 2.
- Above points 2 and 3 are also true for queue 2 processes but the time quantum is 8 units. In a general case if a process does not complete in a time quantum then it is shifted to the lower priority queue.
- In the last queue, processes are scheduled in an FCFS manner.
- A process in a lower priority queue can only execute only when higher priority queues are empty.
- A process running in the lower priority queue is interrupted by a process arriving in the higher priority queue.