Multilevel queues, CPU and I/O bursts, CPU utilisation

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. RR with a huge quantum behaves like? from Lesson 2.2.1
2. SRTF re-decides when? from Lesson 2.1.2
3. Which scheduler admits jobs (degree of multiprogramming)? from Lesson 1.1.2

1 · The Hook

A real computer runs keyboard handlers, a video call, a compiler and a backup at the same time: very different needs. One queue can't suit them all, so operating systems use several queues with different rules. And processes don't just compute: they alternate between CPU bursts and I/O waits. GATE's harder scheduling questions mix both: "processes do I/O, then compute, then I/O; find the CPU idle time".

3 · Core Concept

Predict First — the answer

Yes. During I/O the process is Waiting and needs no CPU; the scheduler gives the CPU to someone else. That overlap is the whole point of multiprogramming.

In plain words

Split processes into classes, each with its own queue and its own scheduling rule, and decide between queues by priority or time-sharing (multilevel queues). Let processes move between queues according to how they behave (multilevel feedback queue). When processes alternate CPU and I/O, schedule only the CPU parts; the I/O parts run at the same time on the devices.

1. Multilevel queue

• Fixed classes: e.g. system, interactive (foreground, RR), batch (background, FCFS).
• Between queues: fixed priority (a lower queue runs only when all higher ones are empty: starvation possible) or time slicing (e.g. 80% of CPU time to foreground, 20% to background).
• A process stays in its queue forever.

2. Multilevel feedback queue (MLFQ)

• Processes move between queues.
• New processes start in the top queue (small quantum, e.g. 8 ms). If a process uses its whole quantum, it is demoted to the next queue (larger quantum, e.g. 16 ms), and the bottom queue may be FCFS.
• Short, interactive processes finish quickly at the top; long CPU-bound ones sink. Aging (promotion after long waits) prevents starvation.
• Most flexible and most complex: defined by the number of queues, each queue's algorithm, and the promotion/demotion rules.

3. CPU and I/O bursts together

A process alternates CPU burst → I/O burst → CPU burst …. Rules for questions: only the CPU bursts compete for the CPU; each process does its I/O on its own device in parallel; when its I/O ends it rejoins the ready queue. Classic example (pre-emptive shortest-remaining-CPU-burst): three processes arrive at 0 with total times 10, 20, 30; each spends the first 20% on I/O, the next 70% computing, the last 10% on I/O.

• A: I/O 0–2, CPU 2–9, I/O 9–10.
• B: I/O 0–4, ready at 4 (needs 14) but A has less left → CPU 9–23, I/O 23–25.
• C: I/O 0–6, CPU 23–44, I/O 44–47.
• CPU idle: 0–2 and 44–47 = 5 of 47 → 10.6% idle.

4. CPU utilisation from I/O probability

If each of n processes spends a fraction p of its time waiting for I/O (independently), the CPU is idle only when all wait: utilisation ≈ 1 − pⁿ. p = 0.8, n = 4 → 1 − 0.4096 ≈ 59%.

4 · Visual

A multilevel feedback queue: CPU-hungry processes sink; long-waiting ones can be promoted back up.

CPU + I/O example (shortest remaining CPU burst first)

time:  0   2         9 10            23     44  47
CPU : [idle][   A    ][      B      ][    C    ][idle]
A   :  I/O   CPU      I/O
B   :  I/O(0-4) waits    CPU            I/O
C   :  I/O(0-6) waits ............ CPU            I/O

5 · Worked Examples

Example 1 Easy

In a multilevel queue with fixed priority, can a batch process starve?

Solution

Yes, if the higher-priority queues are never empty.

Example 2 Medium

In an MLFQ with quanta 8 and 16 (then FCFS), a process needs 30 ms of CPU. How much does it get in each queue?

Solution

8 in queue 0, 16 in queue 1, the remaining 6 in queue 2.

Example 3 GATE

4 processes each wait for I/O 70% of the time (independently). Approximate CPU utilisation?

Solution

1 − 0.7⁴ = 1 − 0.2401 ≈ 0.76.

6 · GATE Traps

• Multilevel queue: processes never move; multilevel feedback queue: they move.
• I/O bursts run in parallel with other processes' CPU bursts.
• Count CPU idle time at the start (everyone doing I/O) and at the end (last process doing its final I/O).
• 1 − pⁿ assumes independent processes; p is the I/O-wait fraction, not the CPU fraction.

7 · Memory Hook

"Different queues for different jobs; feedback lets jobs sink or rise; I/O overlaps CPU."

8 · Connect the Dots

Phase 2 is complete. When processes share data, the order in which the scheduler interleaves them can corrupt that data. Phase 3, synchronization, is about preventing that.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 2 mark(s) — CPU idle

Three processes arrive at 0 with total times 10, 20, 30; each spends the first 20% on I/O, the next 70% on CPU, the last 10% on I/O (pre-emptive shortest remaining CPU burst). Percentage of time the CPU is idle (1 decimal)?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — Utilisation

5 processes each wait for I/O 60% of the time. Approximate CPU utilisation (3 decimals)?

Numerical answer: ________

Q3 · NAT · 2 mark(s) — CPU + I/O

FCFS for the CPU, separate I/O devices. P1 (AT 0): CPU 3, I/O 4, CPU 2. P2 (AT 0): CPU 2, I/O 5, CPU 1. P3 (AT 1): CPU 4, I/O 1, CPU 3. When does P3 finish?

Numerical answer: ________

Q4 · MCQ · 1 mark(s) — MLFQ

In a multilevel feedback queue, a process that keeps using its full quantum is usually:

1. (A) promoted
2. (B) moved to the Waiting state
3. (C) terminated
4. (D) demoted to a lower-priority queue

Q5 · MCQ · 1 mark(s) — Multilevel queue

The key difference between a multilevel queue and a multilevel feedback queue is that in the feedback version:

1. (A) processes can move between queues
2. (B) every queue uses FCFS
3. (C) there is only one queue
4. (D) there is no pre-emption

10 · Rule Card

• Multilevel queue: fixed classes, fixed priority or time-sliced between queues; no movement.
• MLFQ: start at the top; full quantum used → demote; aging → promote; defined by queues, algorithms, move rules.
• CPU/I/O bursts: only CPU bursts compete; I/O overlaps; count idle at the start and end.
• Utilisation ≈ 1 − pⁿ.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

multilevel queue schedulingforeground and background queuesfixed-priority vs time-sliced queuesmultilevel feedback queuedemotion and promotionCPU and I/O burstsoverlapping I/O with computationCPU idle timeCPU utilisation 1 − pⁿ