Scheduling algorithms — FCFS, SJF (preemptive = SRTF), Round Robin, Priority

Core vocabulary (derive every metric, don't memorize)

Two axes that classify these algorithms

Preemptive vs Non-preemptive: Can the OS snatch the CPU from a running process? Non-preemptive = run to completion; Preemptive = can be interrupted.
Selection criterion: order of arrival? shortest burst? priority number? a fixed time slice?

Algorithm	Criterion	Preemptive?
FCFS	arrival order	No
SJF	shortest burst	No
SRTF	shortest remaining burst	Yes
Round Robin	time slice (quantum)	Yes
Priority	priority number	either

1. FCFS — First Come First Served

Worked example FCFS worked example

P	AT	BT
P1	0	5
P2	1	3
P3	2	1

Gantt: | P1 0-5 | P2 5-8 | P3 8-9 |

Why this order? P1 arrived first (t=0), runs fully; then P2; then P3.
CT: P1=5, P2=8, P3=9
TAT = CT−AT: P1=5, P2=7, P3=7
WT = TAT−BT: P1=0, P2=4, P3=6
Avg WT $= (0+4+6)/3 = 10/3 \approx 3.33$
Notice the tiny P3 waited 6s behind big P1 → convoy effect made avg WT large.

2. SJF — Shortest Job First (non-preemptive)

Worked example SJF (same jobs, all arrived by t=2)

P	AT	BT
P1	0	5
P2	1	3
P3	2	1

At t=0 only P1 is present → it must start. Gantt: | P1 0-5 | P3 5-6 | P2 6-9 |

Why P3 before P2 at t=5? Both arrived; P3 burst(1) < P2 burst(3).
CT: P1=5, P3=6, P2=9 → TAT: 5,4,8 → WT: 0,3,5
Avg WT $=(0+3+5)/3 \approx 2.67$ — better than FCFS's 3.33.

3. SRTF — Shortest Remaining Time First (preemptive SJF)

Worked example SRTF worked example

P	AT	BT
P1	0	5
P2	1	3
P3	2	1

t=0: only P1 → run P1.
t=1: P2 arrives (3). P1 remaining = 4. 3 < 4 → preempt, run P2.
t=2: P3 arrives (1). P2 remaining = 2. 1 < 2 → preempt, run P3.
t=3: P3 done. Remaining: P2=2, P1=4 → run P2.
t=5: P2 done. Run P1 (4 left) to t=9.

Gantt: | P1 0-1 | P2 1-2 | P3 2-3 | P2 3-5 | P1 5-9 |

CT: P1=9, P2=5, P3=3
TAT: P1=9, P2=4, P3=1 → WT: P1=4, P2=1, P3=0
Avg WT $=(4+1+0)/3 \approx 1.67$ — lowest yet, because tiny P3 finished instantly.

4. Round Robin (RR)

Worked example RR with q = 2

P	AT	BT
P1	0	5
P2	1	3
P3	2	1

Queue evolves (new arrivals enter before the preempted process re-joins):

t0-2: P1 (rem 3). Queue now: P2,P3,P1
t2-4: P2 (rem 1). Queue: P3,P1,P2
t4-5: P3 (rem 0, done). Queue: P1,P2
t5-7: P1 (rem 1). Queue: P2,P1
t7-8: P2 (rem 0, done). Queue: P1
t8-9: P1 (done).

Gantt: | P1 0-2 | P2 2-4 | P3 4-5 | P1 5-7 | P2 7-8 | P1 8-9 |

CT: P1=9, P2=8, P3=5 → TAT: 9,7,3 → WT: 4,4,2
Avg WT $=(4+4+2)/3 \approx 3.33$ . Higher avg, but great response time & no starvation.

Flashcards

What is Turnaround Time in terms of CT and AT?

TAT = CT - AT

(total time present in system).

Derive Waiting Time from TAT and BT.

Time present = running + waiting, so

WT = TAT - BT

Why is non-preemptive SJF optimal for average waiting time?

Total WT weights earliest jobs by largest multiplier

(n-i)

; minimizing means smallest bursts get largest multipliers ⇒ sort ascending ⇒ shortest first.

What is the convoy effect?

In FCFS, one long job at the front forces many short jobs to wait, inflating average waiting time.

SRTF preempts when?

When a newly arrived process has remaining burst smaller than the currently running process's remaining burst.

Round Robin with q → ∞ behaves like?

FCFS (no preemption ever triggers).

Round Robin with q → 0 problem?

Excessive context-switch overhead; CPU does little useful work.

What metric does Round Robin optimize best?

Response time / fairness (no starvation).

What is starvation in Priority scheduling and its fix?

Low-priority jobs never run because higher ones keep arriving; fix is aging (raise priority with waiting time).

Which scheduler gives minimum average waiting time (no preemption)?

SJF (Shortest Job First).

Order of metrics computed from a Gantt chart?

CT first, then TAT = CT−AT, then WT = TAT−BT.

Recall Feynman: explain to a 12-year-old

Imagine one swing and a line of kids. FCFS = whoever lined up first swings until they're bored — unfair if the first kid stays forever. SJF = let kids who only want a quick push go first, so the line shrinks fast. SRTF = even mid-push, if a kid wanting just one tiny push shows up, you let them in instantly. Round Robin = everyone gets exactly 2 minutes, then back of the line — super fair, nobody's left out. Priority = teacher's pets go first, but if you wait long enough you slowly become a pet too (that's "aging"). Each rule answers the same question — who goes next? — differently.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, CPU ek hi worker hai jo ek time par ek hi kaam (process) kar sakta hai, par line mein bahut saare processes khade hain. Scheduling algorithm bas ye rule hai ki "agla number kiska?". Yahi decide karta hai ki average mein sab kitna wait karenge. Mast baat ye hai ki sirf order badal ke hi average waiting time half ho sakta hai — koi naya hardware nahi chahiye!

FCFS mein jo pehle aaya wo pehle, pura kaam khatam karke hi hatega — par agar bada job aage khada ho to peeche ke chhote jobs phass jaate hain (ye convoy effect hai). SJF bolta hai jo present hain unme se sabse chhota burst wala pehle bhejo — mathematically ye sabse kam average waiting deta hai. SRTF SJF ka preemptive version hai: beech mein bhi agar koi chhota job aa gaya, to running job se CPU cheen lo.

Round Robin sabse fair hai — har process ko ek fixed time quantum (jaise 2 unit) milta hai, phir wapas line ke peeche. Isse response time accha rehta hai aur koi starve nahi hota. Priority mein number ke hisaab se CPU milta hai, par yahan khatra hai starvation ka — low priority wala kabhi chance hi na mile. Iska ilaaj aging hai: jitna zyada wait, utni priority badhao.

Exam ke liye yaad rakho: pehle Gantt chart banao, usse CT nikalo, phir $TAT=CT-AT$ , phir $WT=TAT-BT$ . SJF/SRTF mein hamesha check karo "abhi tak kaun-kaun aa chuka hai" — sirf wahi choose kar sakte ho. Bas yahi 20% concept 80% questions cover kar dega!