Multilevel Feedback Queue (MLFQ) Scheduling Algorithm

Introduction

Multilevel Feedback Queue Scheduling, or MLFQ, is an extension of Multilevel Queue Scheduling. The key difference is feedback.

In MLQ, a process stays in its assigned queue. In MLFQ, processes can move between queues depending on how they behave during execution.

Why MLFQ Scheduling Is Needed

MLQ is rigid because each process remains in the queue where it was first classified. If that classification is wrong, the scheduler does not adapt in the basic MLQ model.

MLFQ solves this by using observed behavior. A process that behaves like an interactive job can stay near the top, while a CPU-heavy process gradually moves to lower-priority queues.

Core Idea of MLFQ

MLFQ uses multiple priority queues. Higher queues have higher priority and usually smaller time quanta, while lower queues have lower priority and may have larger time quanta.

Common rules are:

• Higher queues run first: A process in a higher-priority queue is chosen before lower-priority work.

• Same queue uses Round Robin: Processes at the same priority level usually share CPU time.

• New jobs enter the top queue: New processes are treated optimistically at first.

• Full quantum causes demotion: A process that uses its entire time quantum is moved down.

• Priority boost prevents starvation: Waiting processes may be moved up after some time.

MLFQ Scheduling Example

Consider five processes:

Queue setup:

All new jobs enter Q0. Using the full quantum causes demotion. No priority boost is used in this short example.

The compact scheduling flow is:

• P1 runs from 0 to 2 in Q0 and moves down.

• P2 runs from 2 to 4 in Q0 and moves down.

• P3 runs from 4 to 6 in Q0 and moves down.

• P4 runs from 6 to 8 in Q0 and moves down.

• P5 runs from 8 to 10 in Q0 and finishes.

• P1 runs from 10 to 14 in Q1 and moves down.

• P2 runs from 14 to 16 in Q1 and finishes.

• P3 runs from 16 to 19 in Q1 and finishes.

• P4 runs from 19 to 21 in Q1 and finishes.

• P1 runs from 21 to 24 in Q2 and finishes.

Metric Calculation

The main formulas are:

• CT: time when the process finishes

• TAT: CT - AT

• WT: TAT - BT

• RT: first CPU start time - AT

Average TAT = 16.6, average WT = 11.8, and average RT = 2.6.

Strengths and Weaknesses of MLFQ

Summary

MLFQ scheduling uses multiple priority queues and allows processes to move between them. New jobs usually enter the top queue, CPU-heavy jobs move down, and waiting jobs may be boosted up to reduce starvation.

It improves on rigid MLQ by using feedback from process behavior instead of fixed classification alone. Its main challenges are choosing queue levels, time quanta, demotion rules, and boost intervals carefully.