Chapter 2.2 Lock-in

ACompressed recap

RR: FIFO queue, run min(q, remaining), arrivals at the same instant before the pre-empted process; large q → FCFS; useful fraction q/(q + s); count switches between different processes. Multilevel queues (fixed classes) vs MLFQ (demote on full quantum, aging promotes). CPU/I/O mixes: only CPU bursts compete, I/O overlaps; idle at the start and end; utilisation 1 − pⁿ.

BMerged rule card

2.2.1 Round robin and the time quantum

• RR: FIFO ready queue; run min(q, remaining); unfinished → back; arrivals at the same instant queue before the pre-empted process.
• Large q → FCFS; small q → overhead; useful fraction q/(q + s); max wait between turns (n − 1)q.
• RR: worse average WT than SJF, better response time.
• Context switches: count changes between different processes.

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

• 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ⁿ.

CInterleaved GATE-style questions

Q1 · NAT · 2 mark(s) — RR

All at 0 with bursts 24, 3, 3; RR with q = 4. Average waiting time (2 decimals)?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — RR

RR with q = 3: P1 (AT 0, BT 5), P2 (AT 1, BT 3), P3 (AT 2, BT 1). Completion time of P1?

Numerical answer: ________

Q3 · NAT · 1 mark(s) — Overhead

q = 20 ms, context switch 5 ms. Fraction of CPU time spent on useful work?

Numerical answer: ________

Q4 · MCQ · 1 mark(s) — Response

Compared with SJF, round robin generally gives:

1. (A) better average waiting time
2. (B) fewer context switches
3. (C) better response time
4. (D) starvation of short jobs

Q5 · NAT · 1 mark(s) — Bound

RR with q = 10 ms and 6 processes always in the queue. Longest wait between two consecutive turns of one process?

Numerical answer: ________

Q6 · NAT · 2 mark(s) — Utilisation

3 processes each wait for I/O 50% of the time. CPU utilisation?

Numerical answer: ________

Q7 · MCQ · 1 mark(s) — Starvation

In a multilevel queue with fixed priority between queues, starvation can affect:

1. (A) the highest-priority queue
2. (B) no queue
3. (C) only I/O-bound processes
4. (D) the lowest-priority queue

Q8 · NAT · 2 mark(s) — MLFQ

MLFQ with quanta 4 and 8 in the top two queues, then FCFS. A process needs 25 ms of CPU. How many ms does it run in the FCFS queue?

Numerical answer: ________