Suppose the following jobs are to be executed in a uniprocessor system.…
Suppose the following jobs are to be executed in a uniprocessor system. Multilevel Feedback Queue (MLFQ) is used with queues numbered 1-10, quantum = 2i, where i is the queue level number and processes are initially placed in the first queue (i.e., level 1). In this scheduling policy, each process executes at a particular level for one quantum and then moves down a level; processes never move up a level and assume context switch delay of 1ms. The average process turnaround time, the normalized turnaround time for process 2, and the processor efficiency using MLFQ is,
Answer: D. None of these — Concept: In a Multilevel Feedback Queue (MLFQ) scheduler, several priority queues run from highest to lowest. Every process starts in the topmost queue and is…
- A.
11.4, 2, 83.3%
- B.
11.6, 3.75, 80.6%
- C.
18.6, 3.375, 71.4%
- D.
None of these
Attempted by 163 students.
Show answer & explanation
Correct answer: D
Concept: In a Multilevel Feedback Queue (MLFQ) scheduler, several priority queues run from highest to lowest. Every process starts in the topmost queue and is served First-Come-First-Served within a queue. Each time a process is dispatched it runs for at most that queue's time quantum; if it does not finish within the quantum it is demoted one level (a process is never promoted back up). Turnaround time = completion time − arrival time, normalized turnaround = turnaround ÷ burst time, and processor efficiency = total CPU-busy time ÷ total elapsed time (busy time plus every scheduling overhead such as the context-switch delay).
Applying this to the given jobs:
Process | Arrival Time | Burst |
|---|---|---|
1 | 0 | 4 |
2 | 1 | 8 |
3 | 3 | 2 |
4 | 10 | 6 |
5 | 12 | 5 |
Assumptions used to build the schedule:
Queues are numbered 1 to 10; the quantum at level i is 2i (so level 1 = 2 ms, level 2 = 4 ms, level 3 = 8 ms, ...).
All processes initially enter level 1 and are served FCFS within a level.
Each time a process runs at a level it runs for one quantum (or until completion) and is then demoted one level if not finished.
A 1 ms context-switch interval is inserted before every dispatch, including the very first one.
The process to dispatch next is decided the moment the CPU becomes free; a process that arrives only after that decision joins its queue for the following decision, not the current one.
Dispatch order and Gantt-chart timeline (context switches and running intervals):
0–1 ms: context switch.
1–3 ms: P1 runs at level 1 for 2 ms (remaining burst = 2).
3–4 ms: context switch.
4–6 ms: P2 runs at level 1 for 2 ms (remaining burst = 6).
6–7 ms: context switch.
7–9 ms: P3 runs at level 1 for 2 ms and completes (burst was 2).
9–10 ms: context switch.
10–12 ms: P1 runs at level 2 (quantum 4 ms) but needs only 2 ms and completes.
12–13 ms: context switch.
13–15 ms: P4 runs at level 1 for 2 ms (remaining burst = 4).
15–16 ms: context switch.
16–18 ms: P5 runs at level 1 for 2 ms (remaining burst = 3).
18–19 ms: context switch.
19–23 ms: P2 runs at level 2 for 4 ms (remaining burst = 2).
23–24 ms: context switch.
24–28 ms: P4 runs at level 2 for 4 ms and completes.
28–29 ms: context switch.
29–32 ms: P5 runs at level 2 for up to 4 ms but needs only 3 ms and completes.
32–33 ms: context switch.
33–35 ms: P2 runs at level 3 for its remaining 2 ms and completes.
Finish time, turnaround, and normalized turnaround for every process:
Process | Finish (ms) | Turnaround (ms) | Normalized turnaround |
|---|---|---|---|
1 | 12 | 12 | 12 / 4 = 3.0 |
2 | 35 | 34 | 34 / 8 = 4.25 |
3 | 9 | 6 | 6 / 2 = 3.0 |
4 | 28 | 18 | 18 / 6 = 3.0 |
5 | 32 | 20 | 20 / 5 = 4.0 |
Cross-check: total elapsed time must equal total CPU-busy time plus total context-switch overhead. Sum of bursts = 4 + 8 + 2 + 6 + 5 = 25 ms. The timeline above inserts a context switch before every one of its ten dispatches, i.e. 10 ms of overhead. 25 + 10 = 35 ms, which matches the last completion time in the trace — confirming the schedule is internally consistent before using it to compute the efficiency figure.
Final results: average turnaround = (12 + 34 + 6 + 18 + 20) / 5 = 90 / 5 = 18 ms; normalized turnaround for process 2 = 34 / 8 = 4.25; processor efficiency = 25 / 35 ≈ 71.4%. None of the three numeric triples listed as options equals (18, 4.25, 71.4%), so “None of these” is the option consistent with the full trace.