MLFQ scheduling, step by step

0 / 11

Multi-Level Feedback Queue (MLFQ) Scheduling

Multi-Level Feedback Queue (MLFQ) scheduling also splits the ready queue into several queues like MLQ, but processes move between them. A new process starts in the top queue, and if it can't finish within that queue's quantum, the OS stops it (preemption) and moves it down one queue. Lower queues run later but have larger quanta, and the bottom queue runs as RR. Even while a lower-queue process is running, the OS stops it when a new process arrives in an upper queue.

At a bank: there is one counter but three lines. Every customer first joins the 1-minute line; a customer who isn't done in 1 minute moves to the 2-minute line, and if still not done there, to the 4-minute line. A lower line is served only when the lines above it are empty.

1 / 11

0ms: P1 runs in queue 0

Every new process lines up in the top queue, queue 0. In queue 0, a process can run for only 1ms at a time.

2 / 11

1ms: P1 moves down to queue 1

P1 used up its 1ms quantum without finishing (4ms left), so it moves down one level to queue 1. P2, which arrived at 1ms, runs in queue 0.

3 / 11

2ms: P2 also moves down to queue 1

P2 also runs for 1ms and lines up in queue 1 with 2ms left. P3, which arrived at 2ms, runs in queue 0.

4 / 11

3ms: P3 also moves down to queue 1

P3 lines up in queue 1 with 7ms left. P4, which arrived at 3ms, runs in queue 0.

5 / 11

4ms: queue 0 is empty, so queue 1 runs

P4 also lines up in queue 1 with 1ms left. Queue 0 is empty, so P1 at the front of queue 1 runs. In queue 1, a process can run for up to 2ms at a time.

6 / 11

6ms: P1 moves down to queue 2

P1 used up its 2ms quantum and still has 2ms left, so it moves down to the bottom queue, queue 2. P2 in queue 1 runs.

7 / 11

8ms: P2 finishes

P2 finished its remaining 2ms within the 2ms quantum. P3 runs.

8 / 11

10ms: P3 moves down to queue 2

P3 lines up in queue 2 with 5ms left. P4 in queue 1 runs.

9 / 11

11ms: P4 finishes, so queue 2 runs

P4 had only 1ms left, so it finished quickly. Queues 0 and 1 are both empty, so P1 in queue 2 runs. In queue 2, a process can run for up to 4ms at a time.

10 / 11

13ms: P1 finishes and P3 runs

P1 had 2ms left, so it finished within the quantum. Even when P3 uses up its quantum at 17ms, no process is waiting, so it keeps running.

11 / 11

18ms: all done

Waiting times are P1 8ms, P2 4ms, P3 8ms and P4 6ms, an average of 6.5ms. Without knowing run times in advance, the short P2 and P4 finished in queue 1, while the long P1 and P3 went down to queue 2. A process that has waited too long in a lower queue is sometimes moved up to an upper queue (aging).

Figure showing MLFQ scheduling: a new process starts in the top queue and moves down one queue if it doesn't finish within that queue's quantum, lower queues have larger quanta, and how long each process waited

CPU Scheduling at a glance

Figure showing MLFQ scheduling: a new process starts in the top queue and moves down one queue if it doesn't finish within that queue's quantum, lower queues have larger quanta, and how long each process waited