Skip to article
SchedNotebookCPU Scheduling Simulator
ContentsMLQ
Learn/Chapter 07 of 08

Multilevel Queue Scheduling

Multilevel Queue (MLQ) scheduling separates processes into fixed classes. This simulator uses four queues with strict priority: Q1 is highest and Q4 is lowest.

Fixed queues and two scheduling decisions

There are two decisions. First choose the highest nonempty queue. Then use that queue's policy to choose its process. Higher-priority work can interrupt a lower queue, regardless of which burst is shorter. A process retains its assigned queue.

The preset used here

Example queue settings
QueuePolicyQuantum
Q1Round Robin2
Q2Round Robin4
Q3Round Robin8
Q4FCFSNo quantum
Scroll horizontally for all columns
Example inputs
ProcessArrivalBurstFixed queue
P104Q4
P215Q3
P323Q2
P432Q1
Scroll horizontally for all columns

One CPU · One burst per process · No I/O · Dispatch cost 0. Times are abstract units.

P1 begins in Q4. At 1, P2 in Q3 interrupts it. The incoming job has 5 units versus 3 left for P1: class priority outweighs shorter work.

P3 and P4 subsequently enter their higher classes. Work returns to lower queues after higher work finishes. The full CPU trace is P1 [0, 1), P2 [1, 2), P3 [2, 3), P4 [3, 5), P3 [5, 7), P2 [7, 11), P1 [11, 14).

Worked trace MLQ

Fixed class assignment · not the current Ready queue

Q1Highest priorityP4
Q2↓P3
Q3↓P2
Q4Lowest priorityP1

At t = 1: Q3 outranks Q4. P2's 5 units take priority over P1's 3 remaining.

CPU execution: MLQP1 in Q4 runs [0, 1); P2 in Q3 runs [1, 2); P3 in Q2 runs [2, 3); P4 in Q1 runs [3, 5); P3 in Q2 runs [5, 7); P2 in Q3 runs [7, 11); P1 in Q4 runs [11, 14). Segment widths show elapsed time. Diamond markers show arrivals. ARRIVALSP1P2P3P4P1Q4P2Q3P3Q2P4Q1P3Q2P2Q3P1Q40123571114Time → Intervals are half-open [start, end). No dispatch overhead.
Scroll horizontally for all intervals
Complete CPU trace · [start, end)
  1. P1 / Q4: [0, 1)
  2. P2 / Q3: [1, 2)
  3. P3 / Q2: [2, 3)
  4. P4 / Q1: [3, 5)
  5. P3 / Q2: [5, 7)
  6. P2 / Q3: [7, 11)
  7. P1 / Q4: [11, 14)
Priority follows the fixed class. Returning to a lower queue resumes its waiting work; no process changes its assigned class.
Open this example in the simulator

Calculate the result

Per-process results
ProcessCompletionWaitingTurnaroundResponse
P11410140
P2115100
P37250
P45020
Scroll horizontally for all columns

P1: turnaround = 14 − 0 = 14. Waiting = 14 − 4 = 10. First response = 0 − 0 = 0.

First response measures only the first service. Waiting also includes later periods when this process is ready but another process owns the CPU.

Mean waiting = (10 + 5 + 2 + 0) / 4 = 4.25 units. Mean response = 0 units.

Queue policy does not remove class priority

FCFS in Q4 controls ordering inside Q4. It does not prevent a higher queue from interrupting the Q4 process. In this app, interruptions preserve unused RR allowance, and the selected nonpreemptive Q4 job is resumed when its queue can run again.

A sustained supply of higher-priority work can keep lower queues waiting. Fixed classes do not adapt automatically to a process's CPU behavior. The MLFQ article introduces changing queue membership.

Connect the ideas

Continue with these related notes: