Consider a system that uses a Multilevel Feedback Queue (MLFQ) scheduling…
Consider a system that uses a Multilevel Feedback Queue (MLFQ) scheduling algorithm with the following configuration:
Queue Q1 (Highest Priority): Time Quantum = 4 ms (Round Robin)
Queue Q2: Time Quantum = 8 ms (Round Robin)
Queue Q3 (Lowest Priority): FCFS
New processes always enter Q1. If a process does not complete within its time quantum, it is demoted to the next lower queue.
The following processes arrive at time 0:
Process | Burst Time |
|---|---|
P1 | 5 |
P2 | 12 |
P3 | 8 |
P4 | 3 |
Construct the Gantt Chart and calculate the average waiting time of the processes.
Attempted by 6 students.
Show answer & explanation
Understanding MLFQ Behavior
All processes start in Q1
If not completed → move to Q2, then to Q3
Higher priority queues are always executed first
Step-by-Step Execution
Queue Q1 (Time Quantum = 4 ms)
0–4: P1 executes (remaining = 1) → moves to Q2
4–8: P2 executes (remaining = 8) → moves to Q2
8–12: P3 executes (remaining = 4) → moves to Q2
12–15: P4 executes (completes)
Queue Q2 (Time Quantum = 8 ms)
Remaining processes: P1(1), P2(8), P3(4)
15–16: P1 executes (completes)
16–24: P2 executes (completes)
24–28: P3 executes (completes)
Gantt Chart
| P1 | P2 | P3 | P4 | P1 | P2 | P3 |
0 4 8 12 15 16 24 28Completion Time (CT), TAT, WT
Process | BT | CT | TAT = CT | WT = TAT - BT |
|---|---|---|---|---|
P1 | 5 | 16 | 16 | 11 |
P2 | 12 | 24 | 24 | 12 |
P3 | 8 | 28 | 28 | 20 |
P4 | 3 | 15 | 15 | 12 |
Average Waiting Time
Average WT = (11+12+20+12 ) / 4 = 55 / 4 = 13.75
Answer
Average Waiting Time = 13.75 ms