Multilevel Queue Scheduling
In many situations, processes are easily classified into different groups. For example, a common division is between foreground (interactive) processes and background (batch) processes. These two types of processes have very different response-time requirements and scheduling needs.
A Multilevel Queue scheduling algorithm partitions the ready queue into several separate queues. The processes are permanently assigned to one queue based on properties like memory size, process priority, or process type.
Real-Life Example
Think of a hospital emergency room. Patients aren't put into one massive First-Come, First-Served line. They are triaged into different queues. Queue 1 is for life-threatening trauma (handled immediately with absolute priority). Queue 2 is for severe but stable injuries. Queue 3 is for minor cuts and colds (handled only when Queue 1 and Queue 2 are completely empty). You never mix a trauma patient with someone who has a sprained ankle.
Example 1: Absolute Priority Between Queues
In addition to scheduling algorithms within the queues, there must be scheduling *between* the queues. The most common approach is fixed-priority preemptive scheduling. Let's assume we have two queues:
- Queue 1 (Foreground): Absolute priority, uses Round Robin (Time Quantum = 2).
- Queue 2 (Background): Lower priority, uses FCFS.
Consider the following processes arriving at time 0:
| Process | Queue Assignment | Burst Time (ms) |
|---|---|---|
| P1 | Queue 1 (Foreground) | 4 |
| P2 | Queue 1 (Foreground) | 3 |
| P3 | Queue 2 (Background) | 5 |
No process in Queue 2 can run as long as there is anything in Queue 1.
1. Q1 runs its Round Robin schedule. P1 runs for 2 ms. Then P2 runs for 2 ms. Then P1 runs for its final 2 ms. Then P2 runs for its final 1 ms.
2. At time 7, Q1 is finally empty.
3. Q2 can now execute. P3 runs using FCFS for 5 ms.
Here is the Gantt chart:
+-------+-------+-------+----+---------+
| P1(Q1)| P2(Q1)| P1(Q1)|P2 | P3(Q2) |
+-------+-------+-------+----+---------+
0 2 4 6 7 12Let's calculate the Turnaround Time (Completion Time - Arrival Time):
- P1 finishes at 6 ms: 6 - 0 = 6 ms.
- P2 finishes at 7 ms: 7 - 0 = 7 ms.
- P3 finishes at 12 ms: 12 - 0 = 12 ms.
Average Turnaround Time = (6 + 7 + 12) / 3 = 8.33 ms.
Let's calculate the Waiting Time (Turnaround Time - Burst Time):
- P1: 6 - 4 = 2 ms.
- P2: 7 - 3 = 4 ms.
- P3: 12 - 5 = 7 ms.
Average Waiting Time = (2 + 4 + 7) / 3 = 4.33 ms.
Example 2: Inter-Queue Preemption
What happens if a background process is happily running, and suddenly a new foreground process arrives? Because Queue 1 has absolute priority, the OS will immediately preempt the background process!
| Process | Queue Assignment | Arrival Time (ms) | Burst Time (ms) |
|---|---|---|---|
| P1 | Queue 2 (Background) | 0 | 6 |
| P2 | Queue 1 (Foreground) | 2 | 3 |
1. At time 0, only P1 is in the system. It belongs to Q2. It starts executing.
2. At time 2, P2 arrives. It belongs to Q1. Since Q1 has higher priority than Q2, P1 is forcefully preempted! P1 still has 4 ms of burst remaining.
3. P2 runs for 3 ms (until time 5) and finishes.
4. At time 5, Q1 is empty again. The OS looks at Q2 and resumes P1.
5. P1 runs for its final 4 ms (until time 9).
Here is the Gantt chart:
+---------+---------+---------+
| P1 (Q2) | P2 (Q1) | P1 (Q2) |
+---------+---------+---------+
0 2 5 9Let's calculate the Turnaround Time (Completion Time - Arrival Time):
- P1: 9 - 0 = 9 ms.
- P2: 5 - 2 = 3 ms.
Average Turnaround Time = (9 + 3) / 2 = 6 ms.
Let's calculate the Waiting Time (Turnaround Time - Burst Time):
- P1: 9 - 6 = 3 ms.
- P2: 3 - 3 = 0 ms.
Average Waiting Time = (3 + 0) / 2 = 1.5 ms.
The Fatal Flaw: Starvation
If there is an absolute priority between queues, Multilevel Queue Scheduling suffers from the exact same flaw as basic Priority Scheduling: Starvation. If foreground processes keep entering the system continuously, the background processes in the lower queues will never get a chance to execute.
To solve this, modern operating systems use a variation called Multilevel Feedback Queue Scheduling, which allows a process to dynamically move between queues (e.g., if a process uses too much CPU time, it gets moved to a lower-priority queue).
Advantages
- Highly customizable, as the OS can assign the perfect scheduling algorithm to different types of processes.
- Low scheduling overhead because processes are permanently assigned to a specific queue and don't move around.
Disadvantages
- Inflexible. Since a process cannot change its queue, it cannot adapt to dynamic changes in its behavior.
- Highly prone to Starvation for processes permanently stuck in lower-priority queues.
Multilevel Queue Knowledge Check
Question 1 of 1Test your understanding of how multiple queues interact.