CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 5 of 7 · 3 min read

MLFQ

Think of it this way. A post office has several lines. New customers join the quick line. Anyone who takes too long at the counter is sent to a slower line, and customers who ask for something quick stay in the quick line. Without asking anyone, the post office sorts the short tasks from the long ones. The analogy stops in one place: a post office sorts customers once, while a scheduler keeps re-sorting.

In plain words: A multilevel feedback queue (MLFQ) has several queues, each with its own priority and quantum. Short quanta go with high priority. The rules, in one common form, are:

  1. The scheduler always takes a process from the highest non-empty queue.
  2. Within one queue, processes run in round robin.
  3. A new process enters the top queue.
  4. A process that uses its whole quantum is moved down one queue. A process that gives up the processor early (it waits for I/O) stays where it is.
  5. A process that becomes ready in a higher queue preempts the running one.

The effect: a CPU-bound process uses its quanta up and sinks to the lower queues, while an I/O-bound or interactive process always gives up the processor early and stays in the top queue, where it is served first. The scheduler learns the burst length from the behaviour, with no need to ask.

An example, made up to show the idea. Three queues have quanta 2, 4 and 8. Process L is CPU-bound and needs 12 units. Process I does four rounds of 1 unit of computing followed by 2 units of waiting for I/O. Both arrive at time 0, with L first in the queue.

Time Running What happens
0 to 2 L (queue 0) L uses its quantum of 2, so it moves to queue 1
2 to 3 I (queue 0) I computes 1 unit and waits for I/O until time 5, so it stays in queue 0
3 to 5 L (queue 1) I wakes at 5 and preempts L, which has used 2 of 4
5 to 6 I I computes and waits until 8
6 to 8 L (queue 1) L finishes its quantum of 4, so it moves to queue 2
8 to 9 I second wait ends, I runs again
9 to 11 L (queue 2) I wakes at 11 and preempts L
11 to 12 I I finishes its fourth round
12 to 16 L (queue 2) L runs its last 4 units

I finished at 12 and L at 16. I got the processor each time it woke, and never waited behind L for more than a unit. L sank to queue 2 and finished, using all 12 units of its work. A program using a simple loop to trace this, written from the five rules, printed LLILLILLILLILLLL, the same sequence.

Multilevel feedback queue

A multilevel feedback queue is a scheduler with several ready queues of different priorities, where new processes start in the highest queue, a process that uses its whole quantum moves down a queue, and a process that gives up the processor early stays, so that the position of a process reflects its recent behaviour.

Example: an interactive process that always waits before its quantum ends stays in the top queue and is served first, while a long computation sinks to the bottom queue.

Check yourself: 1. Why did I stay in queue 0? 2. At time 5, why did I preempt L? 3. In which queue was L when it finished?