Phase 2Ch 2.1 Basic scheduling algorithms
ACompressed recap
TAT = CT − AT; WT = TAT − BT; RT = first start − AT. FCFS (convoy effect, idle gaps). SJF (non-pre-emptive, optimal average WT), SRTF (re-decide at every arrival), exponential averaging τₙ₊₁ = αtₙ + (1 − α)τₙ. Priority (both kinds), starvation, aging; HRRN (W + S)/S. Running example averages: FCFS 11.4, SJF 8.2, SRTF 6.6, priority 10.6 / 9.6.
BMerged rule card
2.1.1 Scheduling basics: the times we measure; first-come first-served
- AT, BT given; CT from the Gantt chart; TAT = CT − AT; WT = TAT − BT; RT = first start − AT.
- Non-pre-emptive: keep the CPU till done; pre-emptive: can be interrupted.
- FCFS: arrival order, non-pre-emptive, convoy effect; idle gaps when nothing has arrived.
2.1.2 Shortest job first and shortest remaining time first
- SJF: when free, pick the smallest burst; non-pre-emptive; optimal average WT.
- SRTF: at each arrival/completion, run the smallest remaining time; pre-emptive; optimal among pre-emptive.
- Both can starve long jobs; bursts predicted by τₙ₊₁ = αtₙ + (1 − α)τₙ.
2.1.3 Priority scheduling, starvation and aging; highest response ratio next
- Priority: pick the most important ready process (state the direction of numbers); non-pre-emptive or pre-emptive.
- Starvation of low priorities; aging raises priority over time.
- HRRN: non-pre-emptive; pick the largest (W + S)/S; no starvation.
- SJF = priority by burst length.
CInterleaved GATE-style questions
Q1 · NAT · 2 mark(s) — FCFS
FCFS: P1 (AT 0, BT 5), P2 (AT 1, BT 3), P3 (AT 2, BT 8), P4 (AT 3, BT 6). Average waiting time?
Numerical answer: ________
Q2 · NAT · 1 mark(s) — Response time
Running example under FCFS: response time of P4?
Numerical answer: ________
Q3 · NAT · 2 mark(s) — SJF
SJF (non-pre-emptive): P1 (AT 0, BT 7), P2 (AT 2, BT 4), P3 (AT 4, BT 1), P4 (AT 5, BT 4). Average waiting time?
Numerical answer: ________
Q4 · NAT · 2 mark(s) — SRTF
SRTF: P1 (AT 0, BT 7), P2 (AT 2, BT 4), P3 (AT 4, BT 1), P4 (AT 5, BT 4). Average waiting time?
Numerical answer: ________
Q5 · NAT · 1 mark(s) — Prediction
α = 0.25, previous prediction 16, actual burst 8. Next prediction?
Numerical answer: ________
Q6 · MCQ · 1 mark(s) — Pre-emption
Which of these is pre-emptive?
- (A) SRTF
- (B) HRRN
- (C) SJF
- (D) FCFS
Q7 · NAT · 2 mark(s) — HRRN
At time 10 the CPU is free. Ready: X (arrived 2, burst 4), Y (arrived 6, burst 1), Z (arrived 0, burst 8). Largest response ratio?
Numerical answer: ________
Q8 · MCQ · 1 mark(s) — Priority
SJF can be viewed as priority scheduling where priority is based on:
- (A) process ID
- (B) predicted CPU burst
- (C) arrival time
- (D) memory size
DAnswer Vault
Try the questions first. Open when you are ready to check.
🔐 Open the Answer Vault
Q1 Answer: 5.75 · 2 mark(s)
Starts 0, 5, 8, 16: waits 0, 4, 6, 13.
Re-read: Lesson 2.1.1 — Scheduling basics: the times we measure; first-come first-served
Q2 Answer: 18 · 1 mark(s)
Starts at 21, arrived at 3.
Re-read: Lesson 2.1.1 — Scheduling basics: the times we measure; first-come first-served
Q3 Answer: 4 · 2 mark(s)
P1 0–7, P3 7–8, P2 8–12, P4 12–16: waits 0, 6, 3, 7.
Re-read: Lesson 2.1.2 — Shortest job first and shortest remaining time first
Q4 Answer: 3 · 2 mark(s)
P1 0–2, P2 2–4, P3 4–5, P2 5–7, P4 7–11, P1 11–16: waits 9, 1, 0, 2.
Re-read: Lesson 2.1.2 — Shortest job first and shortest remaining time first
Q5 Answer: 14 · 1 mark(s)
0.25 × 8 + 0.75 × 16.
Re-read: Lesson 2.1.2 — Shortest job first and shortest remaining time first
Q6 Answer: (A) · 1 mark(s)
It interrupts on shorter arrivals.
- (B) is wrong: Non-pre-emptive.
- (C) is wrong: Non-pre-emptive.
- (D) is wrong: Non-pre-emptive.
Re-read: Lesson 2.1.2 — Shortest job first and shortest remaining time first
Q7 Answer: 5 · 2 mark(s)
X (8 + 4)/4 = 3; Y (4 + 1)/1 = 5; Z (10 + 8)/8 = 2.25.
Re-read: Lesson 2.1.3 — Priority scheduling, starvation and aging; highest response ratio next
Q8 Answer: (B) · 1 mark(s)
Shorter burst = higher priority.
- (A) is wrong: Arbitrary.
- (C) is wrong: That is FCFS.
- (D) is wrong: Unrelated.
Re-read: Lesson 2.1.3 — Priority scheduling, starvation and aging; highest response ratio next