CPU Scheduling Algorithms

CPU scheduling is a numerically heavy, high-frequency OS topic — expect Gantt-chart problems computing average waiting/turnaround time, plus conceptual questions on starvation and preemption. It's a scoring area if you know the formulas.

Preemptive vs non-preemptive

Non-preemptive: a process keeps the CPU until it blocks or finishes. Preemptive: the OS can forcibly take the CPU (e.g. on a timer or higher-priority arrival).

The core algorithms

Algorithm	Type	Key property
FCFS	non-preemptive	simple; convoy effect
SJF	non-preemptive	optimal avg wait; starvation
SRTF	preemptive SJF	optimal; needs burst prediction
Priority	either	starvation → fix with aging
Round Robin	preemptive	fair; depends on time quantum

Key metrics

• Turnaround time = completion − arrival.
• Waiting time = turnaround − burst.
• Response time = first-CPU − arrival.
  SJF gives the minimum average waiting time (provably optimal).

Exam Tricks & Tips

• 🎯 SJF/SRTF gives the minimum average waiting time — but is impractical because it needs the (unknown) next CPU burst.
• 🎯 FCFS causes the convoy effect — one long job delays all short ones behind it.
• 🎯 Round Robin fairness hinges on the quantum: too large → behaves like FCFS; too small → excessive context-switch overhead.
• 🎯 Priority scheduling starves low-priority processes; fix it with aging (gradually raising priority over waiting time).
• 🎯 Waiting time = Turnaround − Burst; Turnaround = Completion − Arrival — memorise these to solve Gantt problems fast.
• 🎯 Round Robin and SRTF are preemptive; plain FCFS and SJF are non-preemptive.
• ❌ Common mistake: forgetting arrival times in the Gantt chart, so waiting/turnaround come out wrong.

Expected pattern

Gantt-chart numericals (compute avg waiting/turnaround for FCFS/SJF/RR), "which algorithm minimises waiting time?", "what is the convoy effect?", "how does aging prevent starvation?", and "effect of RR quantum size".

Quick recap

Non-preemptive: FCFS (convoy effect), SJF (optimal avg wait, starvation). Preemptive: SRTF, Round Robin (fair, quantum-sensitive), Priority (starvation→aging). Turnaround = Completion−Arrival; Waiting = Turnaround−Burst. SJF minimises average waiting time but needs burst prediction.

Cover the answer, recall, then check. 12 cards on CPU scheduling.

Q1. Difference between preemptive and non-preemptive scheduling?
A1. Preemptive can forcibly take the CPU from a running process; non-preemptive lets it run until it blocks or finishes.

Q2. Which algorithm gives the minimum average waiting time?
A2. Shortest Job First (SJF) / SRTF — provably optimal, but needs the next burst length, which is unknown.

Q3. What is the convoy effect?
A3. In FCFS, one long process holds the CPU and delays all shorter processes queued behind it.

Q4. How does time quantum affect Round Robin?
A4. Too large → behaves like FCFS; too small → too many context switches (high overhead). It must be balanced.

Q5. What problem does Priority scheduling have and how is it fixed?
A5. Starvation of low-priority processes; fixed by aging (gradually increasing a waiting process's priority).

Q6. Formula for turnaround time?
A6. Turnaround time = Completion time − Arrival time.

Q7. Formula for waiting time?
A7. Waiting time = Turnaround time − Burst time.

Q8. What is response time?
A8. Time from a process's arrival until it first gets the CPU.

Q9. Which common algorithms are preemptive?
A9. Round Robin, SRTF (preemptive SJF), and preemptive Priority scheduling.

Q10. What is SRTF?
A10. Shortest Remaining Time First — the preemptive version of SJF; the process with the least remaining burst runs.

Q11. Which non-preemptive algorithm is simplest and most fair by arrival?
A11. FCFS (First-Come First-Served) — processes run in arrival order, but it suffers the convoy effect.

Q12. Why is SJF hard to implement in practice?
A12. It requires knowing each process's next CPU burst length in advance, which must be estimated/predicted.

When several processes are Ready, the scheduler decides who runs next. The chosen algorithm directly shapes responsiveness, fairness and throughput — and computing waiting/turnaround times by hand is a guaranteed exam exercise.

Core idea: a CPU scheduling algorithm picks the next Ready process for the CPU to optimise some metric — turnaround time (completion − arrival), waiting time (turnaround − burst), response time (first run − arrival), or throughput. Schedulers are non-preemptive (run to completion/block) or preemptive (can be interrupted).

How it works

Beginner — the classic algorithms

• FCFS (First-Come First-Served): run in arrival order. Simple, but a long job delays everyone (the convoy effect). Non-preemptive.
• SJF (Shortest Job First): run the shortest burst next. Optimal for minimum average waiting time, but needs to know burst lengths and can starve long jobs. Preemptive variant = SRTF.
• Round Robin (RR): each process gets a fixed time quantum, then goes to the back of the queue. Fair, good response time; performance depends heavily on the quantum. Preemptive.
• Priority: run the highest priority first; risks starvation, fixed by aging (raise priority over time).

Intermediate — computing the metrics

For a set of processes, build a Gantt chart of execution order, then per process:

• Completion time (CT): when it finishes on the chart.
• Turnaround time (TAT) = CT − Arrival.
• Waiting time (WT) = TAT − Burst.
  Average WT and TAT summarise the schedule.

Advanced — preemption and trade-offs

Preemptive algorithms (SRTF, RR, preemptive priority) react to new arrivals and improve response time but add context-switch overhead. RR's quantum is a knob: too large → behaves like FCFS; too small → thrashing on context switches. SJF/SRTF minimise average waiting time but are impractical without burst prediction and can starve long jobs — real systems (Linux CFS) approximate "fairness" instead.

Worked example — FCFS vs SJF

Processes (arrival 0, bursts): P1=6, P2=8, P3=7, P4=3.
FCFS (order P1,P2,P3,P4): completions 6, 14, 21, 24.

• WT = CT − burst − arrival: P1=0, P2=6, P3=14, P4=21 → avg (0+6+14+21)/4 = 10.25.

SJF (shortest first: P4=3, P1=6, P3=7, P2=8): completions 3, 9, 16, 24.

• WT: P4=0, P1=3, P3=9, P2=16 → avg (0+3+9+16)/4 = 7.0.

Same jobs, same total time (24), but SJF's average waiting time (7.0) beats FCFS (10.25) — a concrete demonstration that scheduling order alone changes waiting time, and why SJF is optimal for it.

Interview & exam relevance

Extremely common: "compute average waiting/turnaround time for FCFS/SJF/RR", "which algorithm minimises average waiting time?" (SJF), "what is the convoy effect / starvation / aging", and "preemptive vs non-preemptive". Drawing the Gantt chart correctly (especially with arrival times and RR quanta) is the graded skill.

Tricks & gotchas

• SJF is optimal for average waiting time — but only if bursts are known and it may starve long jobs.
• In RR, a smaller quantum improves response time but increases context-switch overhead.
• Watch arrival times: a process can't be scheduled before it arrives (idle gaps appear in the Gantt chart).
• Mnemonic: "FCFS fair-but-slow, SJF short-but-starves, RR round-and-fair, Priority-plus-aging."

Worked Example

Problem: Four processes arrive at time 0 with burst times P1=6, P2=8, P3=7, P4=3. Compute the average waiting time under (i) FCFS in arrival order P1,P2,P3,P4 and (ii) non-preemptive SJF. Compare.

Solution:
Waiting time = (start time) − (arrival time). All arrive at 0, so waiting time = start time = sum of prior bursts.

(i) FCFS, order P1,P2,P3,P4. Gantt chart:
| P1 (0–6) | P2 (6–14) | P3 (14–21) | P4 (21–24) |

• Waiting: P1=0, P2=6, P3=14, P4=21.
• Average = (0 + 6 + 14 + 21) / 4 = 41 / 4 = 10.25.

(ii) SJF picks the shortest burst first: order P4(3), P1(6), P3(7), P2(8). Gantt chart:
| P4 (0–3) | P1 (3–9) | P3 (9–16) | P2 (16–24) |

• Waiting: P4=0, P1=3, P3=9, P2=16.
• Average = (0 + 3 + 9 + 16) / 4 = 28 / 4 = 7.

SJF is provably optimal for minimising average waiting time (shortest jobs first reduce the cumulative wait), cutting it from 10.25 to 7 here — a 32% improvement. Its drawback: it needs the burst lengths in advance (usually estimated) and can starve long jobs. FCFS is simple and starvation-free but suffers the convoy effect, where short jobs wait behind a long one (P4 waiting 21 units under FCFS).

Answer: FCFS average waiting time = 10.25; SJF average waiting time = 7. SJF is optimal for average waiting time but requires known burst times and risks starving long processes.