Multilevel Feedback Queue Scheduling
Multilevel Feedback Queue (MLFQ) scheduling allows a process's priority level to change as it receives CPU service. In this simulator, every new arrival starts in Q1. The highest nonempty queue runs first.
Feedback changes queue membership
The default preset uses RR in Q1-Q3 and FCFS in Q4. Unfinished work moves down after consuming its current level's cumulative CPU allotment. Waiting does not consume that allotment, and an interruption does not refill it.
The particular number of levels and promotion rules belong to the configured policy. They are not universal constants of every MLFQ design.
The preset used here
| Queue | Policy | CPU allotment before demotion |
|---|---|---|
| Q1 | Round Robin | 2 |
| Q2 | Round Robin | 4 |
| Q3 | Round Robin | 8 |
| Q4 | FCFS | No lower queue |
Aging is off for this example.
| Process | Arrival | Burst |
|---|---|---|
| P1 | 0 | 16 |
| P2 | 1 | 1 |
| P3 | 4 | 1 |
One CPU · One burst per process · No I/O · Dispatch cost 0 · Aging off. Times are abstract units.
P1 consumes the Q1 allotment of 2 and moves down. Each level counts cumulative CPU service, excluding waiting.
At 4, P3 interrupts P1 in Q2. Its remaining allowance is 3. At 5, it resumes with the same allowance; the interruption has not refilled it.
The full trace is P1 [0, 2), P2 [2, 3), P1 [3, 4), P3 [4, 5), P1 [5, 8), P1 [8, 16), P1 [16, 18). The ledger below derives service at each level from those exact intervals.
P1: Q2 · remaining 13
Q2 allowance left: 3
P1: Q2 · remaining 13
Q2 allowance left: 3
- P1 / Q1: [0, 2)
- P2 / Q1: [2, 3)
- P1 / Q2: [3, 4)
- P3 / Q1: [4, 5)
- P1 / Q2: [5, 8)
- P1 / Q3: [8, 16)
- P1 / Q4: [16, 18)
At 8 and 16, P1 changes level while remaining the CPU owner. A demotion is not automatically a process change or an idle interval.
Follow P1's CPU allotments
| Level | Service intervals | Service used | What follows |
|---|---|---|---|
| Q1 | [0, 2) | 2 | Demote to Q2 |
| Q2 | [3, 4) and [5, 8) | 1 + 3 = 4 | Demote to Q3 |
| Q3 | [8, 16) | 8 | Demote to Q4 |
| Q4 | [16, 18) | 2 | Complete |
At 8 and 16, P1 changes level while remaining the CPU owner. A demotion is not automatically a process change or an idle interval.
Calculate the result
| Process | Completion | Waiting | Turnaround | Response |
|---|---|---|---|---|
| P1 | 18 | 2 | 18 | 0 |
| P2 | 3 | 1 | 2 | 1 |
| P3 | 5 | 0 | 1 | 0 |
P1: turnaround = 18 − 0 = 18. Waiting = 18 − 16 = 2. 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 = (2 + 1 + 0) / 3 = 1 units. Mean response ≈ 0.333 units.
Aging and custom policies
Lower queues can wait when higher-priority work keeps arriving. This app optionally promotes a process one level after a configured period of continuous Ready waiting. That is individual aging, not a periodic boost of every process at once. It is disabled in the example above.
The default RR/RR/RR/FCFS priority behavior does not choose a level by looking at future burst length. The simulator still needs burst values to know when the example's work completes.
The app also offers SRTF in upper queues and SJF or HRRN in Q4 as custom teaching configurations. Those choices use known service information and should be identified separately from the default preset. This notebook's one-burst model does not include I/O blocking.