What is multilevel feedback queue scheduling?

A multilevel feedback queue (MLFQ) is a CPU scheduling algorithm that uses multiple queues with varying priorities to manage process execution. It dynamically adjusts priorities based on process behavior, promoting or demoting processes between queues.

The MLFQ scheduling algorithm efficiently manages tasks, prioritizing responsiveness and resource utilization, which helps reduce starvationStarvation in OS scheduling occurs when a process is unfairly denied access to resources for an extended period, causing it to be stuck or delayed indefinitely.. Its dynamic nature is well-suited for systems with various processes, enhancing overall performance and user experience.

Features of MLFQ

MLFQ employs multiple queues with different priorities, typically arranged hierarchically. This allows for more favorable treatment of time-critical tasks while ensuring that lower-priority processes still receive a fair share of CPU time.

  • Multiple queues: MLFQ maintains multiple queues with different priorities.

  • Feedback mechanism: The feedback mechanism in MLFQ scheduling allows the adjustment of process priority based on its past behavior. If a process exhausts its time slice in a lower-priority queue, it can be promoted to a higher-priority queue to receive more CPU time.

  • Time slicing: Each process is assigned a specific time quantum Time quantum, also known as time slice or time interval, refers to the fixed duration of time allocated to a process for execution in a preemptive scheduling algorithm.to execute in its current queue.

  • Dynamic priority adjustment: The feedback mechanism allows the adjustment of process priority based on its behavior over time.

  • Preemption: It enables a high-priority process to interrupt and take precedence over a low-priority process to ensure it receives the necessary CPU time.

Functionality of MLFQ

MLFQ scheduling requires configuring parameters such as the number of queues, time quantum, and priority adjustment. These parameters enable efficient resource utilization and ensure fairness in executing processes.

The diagram below illustrates the structure of an MLFQ. A new process is initially added to Queue 1, and if it fails to complete its execution, it moves to Queue 2 and vice versa. Once a process completes its execution, it is removed from the queue. Additionally, the MLFQ can utilize boosting to elevate low-level processes to higher queues.

MLFQ architecture
MLFQ architecture

The steps involved in MLFQ scheduling when a process enters the system.

  1. When a process enters the system, it is initially assigned to the highest priority queue.

  2. The process can execute for a specific time quantum in its current queue.

  3. If the process completes within the time quantum, it is removed from the system.

  4. If the process does not complete within the time quantum, it is demoted to a lower priority queue and given a shorter time quantum.

  5. This promotion and demotion process continues based on the behavior of the processes.

  6. The high-priority queues take precedence over low-priority queues, allowing the latter processes to run only when high-priority queues are empty.

  7. The feedback mechanism allows processes to move between queues based on their execution behavior.

  8. The process continues until all processes are executed or terminated.

Example of MLFQ

There are various scheduling algorithms that can be applied to each queue, including FCFS, shortest remaining time, and round robin. Now, we will explore a multilevel feedback queue configuration consisting of three queues.

  • Queue 1 (Q1) follows a round robin schedule with a time quantum of 8 milliseconds.

  • Queue 2 (Q2) also uses a round robin schedule with a time quantum of 15 milliseconds.

  • Finally, Queue 3 (Q3) utilizes a first come, first serve approach.

  • Additionally, after 110 milliseconds, all processes will be boosted to Queue 1 for high-priority execution.

1 of 18

In the diagram, the purple processes represent the ones in the ready state, while the green ones indicate the currently running processes. A clock displays the elapsed time since the start. There are 5 processes, with the 5th process arriving in the middle and the other 4 processes starting at T = 0ms.

Code

Now we will see a basic example of an MLFQ in Python, demonstrating how the algorithm works. In this MLFQ, we have three queues where in each queue we are using Round Robin with quantum = 4s. 

class Process:
    def __init__(self, name, arrival_time, burst_time):
        self.name = name
        self.arrival_time = arrival_time
        self.burst_time = burst_time
class MLFQ:
    def __init__(self, queues):
        self.queues = queues
    def schedule(self, processes):
        for process in processes:
            self.queues[0].append(process)  # Add process to the highest priority queue (Queue 0)
        current_queue = 0
        while True:
            if len(self.queues[current_queue]) > 0:
                process = self.queues[current_queue][0]  # Get the first process from the current queue
                print("Running process:", process.name, "from Queue", current_queue,"with burst time:",process.burst_time)
                # Perform the CPU burst for the process (execute until the burst time is fully consumed)
                time_slice = 4
                if process.burst_time <= time_slice:
                    process.burst_time = 0
                else:
                    process.burst_time -= time_slice
                if process.burst_time > 0:
                    if current_queue + 1 < len(self.queues):
                        self.queues[current_queue + 1].append(process)  # Move the process to the next lower priority queue
                    else:
                        self.queues[current_queue].append(process)  # If already in the lowest priority, stay in the same queue
                else:
                    print("Process", process.name, "completed.")
                self.queues[current_queue].pop(0)  # Remove the executed process from the current queue
            if self._all_queues_empty():
                break
            if len(self.queues[current_queue]) == 0: 
                current_queue = (current_queue + 1) % len(self.queues)
    def _all_queues_empty(self):
        for queue in self.queues:
            if len(queue) > 0:
                return False
        return True
# Example usage
queues = [[] for _ in range(3)]  # Three queues with different priorities
mlfq = MLFQ(queues)
processes = [
    Process("P1", 0, 8),
    Process("P2", 1, 4),
    Process("P3", 2, 10)
]
mlfq.schedule(processes)

  • Lines 1–7: The code defines a Process class with attributes for the process name, arrival time, and burst time.

  • Lines 9–15: The MLFQ class manages a multi-level feedback queue with a list of queues representing different priorities. The schedule method handles process scheduling, taking a list of processes as input.

  • Lines 13–46: The main function is schedule which implements scheduling in different queues.

    • Lines 14–15: All the processes are initially added to the highest priority queue (Queue 0).

    • Lines 19–21: The method then enters a scheduling loop until all queues are empty. Inside the loop, it checks if the current queue has any processes. If there are processes in the current queue, it selects the first process from the queue for execution.

    • Lines 25–30: The code executes the process for a fixed time slice (in this case, 4 seconds) or until its burst time is fully consumed.

    • Lines 33–41: After each time slice, the code checks if the process has completed its burst time. If not, it moves the process to a low-priority queue. If completed, a completion message is printed, and the process is removed from the current queue.

    • Lines 43–46: The code schedules processes in a round robin manner, moving to the next queue if the current one is empty. The scheduling loop continues until all queues are empty, checked by the _all_queues_empty method.

  • Lines 55–64: The example usage at the end of the code initializes the MLFQ with three queues of different priorities. It creates a list of processes with their arrival times and burst times. The schedule method is then called to start the scheduling process.

Conclusion

The multilevel feedback queue (MLFQ) scheduling algorithm is a versatile approach to CPU scheduling. It optimizes resource utilization by dynamically adjusting priorities and utilizing multiple queues. MLFQ enhances system responsiveness and overall performance with features like preemption and task prioritization.

Advantages

Disadvantages

Flexible scheduling

Algorithm is too complex.

Facilitates the movement of processes across multiple queues.

Transition between different queues results in increased CPU overheads.

Helps in preventing starvation.

To choose the optimal scheduler, alternative methods are necessary to determine the values.


Free AI Mock Interviews
Coding Interview
Coding PatternsFree Interview
Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.
System Design
You TubeFree Interview
Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved