MLQ scheduling, step by step

0 / 8

Multi-Level Queue (MLQ) Scheduling

Multi-Level Queue (MLQ) scheduling splits the ready queue into several queues and fixes each process in one of them by its type (system, interactive, batch and so on). A lower queue runs only when the queues above it are empty, and even while a lower-queue process is running, the OS stops it when a process arrives in an upper queue (preemption). A process never changes queues once it is in one.

At a bank: there is one counter, but separate VIP and regular lines. Regular customers are served only when the VIP line is empty, and they can't move to the VIP line.

1 / 8

0ms: P1 in the batch queue runs

P1 is a batch process, so it lines up in the batch queue. The two queues above are empty, so it runs right away.

2 / 8

1ms: interactive P2 arrives and P1 is stopped

P2 lines up in the interactive process queue. The interactive queue is above the batch queue, so the OS stops P1 and runs P2. P1 goes back to its own queue (batch) with 4ms left.

3 / 8

2ms: P3 lines up in the batch queue

P3 is also a batch process, so it joins the batch queue. P2 in an upper queue is running, so it waits.

4 / 8

3ms: system P4 arrives and P2 is stopped

The system process queue at the very top comes first. The OS stops P2 and runs P4. P2 goes back to its own queue (interactive) with 1ms left.

5 / 8

5ms: P4 finishes and P2 runs

The system queue is now empty, so P2 in the next queue, the interactive queue, continues.

6 / 8

6ms: the upper two queues are empty, so the batch queue runs

P2 has finished and both upper queues are empty. Only now does P1 in the batch queue continue from where it stopped.

7 / 8

10ms: P1 finishes and P3 runs

P3 waited from 2ms to 10ms. If processes keep arriving in upper queues, a lower queue can wait indefinitely (starvation). Because processes can't change queues, they can't move up no matter how long they wait.

8 / 8

18ms: all done

Waiting times are P1 5ms, P2 2ms, P3 8ms and P4 0ms, an average of 3.75ms. P4 and P2 in the upper queues waited only briefly, while P1 and P3 in the lower queue waited longer.

Figure showing MLQ scheduling: processes are fixed in one of three queues (system, interactive or batch) by their type, upper queues run first, a lower-queue process is stopped when a process arrives in an upper queue, and how long each process waited

CPU Scheduling at a glance

Figure showing MLQ scheduling: processes are fixed in one of three queues (system, interactive or batch) by their type, upper queues run first, a lower-queue process is stopped when a process arrives in an upper queue, and how long each process waited