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

4.2.10 · Coding › Operating Systems

Core vocabulary (har metric derive karo, memorize mat karo)

Do axes jo in algorithms ko classify karte hain

Preemptive vs Non-preemptive: Kya OS kisi running process se CPU chheen sakta hai? Non-preemptive = completion tak run karo; Preemptive = interrupt kiya ja sakta hai.
Selection criterion: aane ka order? shortest burst? priority number? ek 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 |

Yeh order kyun? P1 pehle aaya (t=0), poora run kiya; phir P2; phir 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$
Dekho tiny P3 ne 6s wait kiya bade P1 ke peeche → convoy effect ne avg WT bada kar diya.

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

Worked example SJF (same jobs, sab t=2 tak aa gaye)

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

t=0 par sirf P1 present hai → use start karna hi padega. Gantt: | P1 0-5 | P3 5-6 | P2 6-9 |

t=5 par P3 pehle P2 se kyun? Dono aa gaye; 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$ — FCFS ke 3.33 se better.

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: sirf P1 → P1 run karo.
t=1: P2 aaya (3). P1 remaining = 4. 3 < 4 → preempt, P2 run karo.
t=2: P3 aaya (1). P2 remaining = 2. 1 < 2 → preempt, P3 run karo.
t=3: P3 done. Remaining: P2=2, P1=4 → P2 run karo.
t=5: P2 done. P1 run karo (4 left) t=9 tak.

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$ — abhi tak ka lowest, kyunki tiny P3 instantly khatam hua.

4. Round Robin (RR)

Worked example RR with q = 2

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

Queue evolve hoti hai (naye arrivals preempted process ke re-join se pehle enqueue hote hain):

t0-2: P1 (rem 3). Queue ab: 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$ . Avg zyada hai, lekin response time great hai & koi starvation nahi.

Flashcards

CT aur AT ke terms mein Turnaround Time kya hota hai?

T A T = C T - A T

(system mein present rehne ka total time).

TAT aur BT se Waiting Time derive karo.

Time present = running + waiting, isliye

W T = T A T - B T

Non-preemptive SJF average waiting time ke liye optimal kyun hai?

Total WT mein earliest jobs par sabse bada multiplier

(n - i)

lagta hai; minimize karna matlab smallest bursts ko largest multipliers do ⇒ ascending sort ⇒ shortest first.

Convoy effect kya hai?

FCFS mein, front par ek lamba job bahut saari chhoti jobs ko wait karwaata hai, average waiting time badha deta hai.

SRTF kab preempt karta hai?

Jab naya aaya process ka remaining burst currently running process ke remaining burst se chhota ho.

Round Robin q → ∞ hone par kaisa behave karta hai?

FCFS ki tarah (koi preemption trigger nahi hoti).

Round Robin q → 0 hone par kya problem hai?

Bahut zyada context-switch overhead; CPU thoda useful kaam karta hai.

Round Robin kaunsa metric best optimize karta hai?

Response time / fairness (koi starvation nahi).

Priority scheduling mein starvation kya hai aur uska fix kya hai?

Low-priority jobs kabhi nahi run hoti kyunki higher ones aate rehte hain; fix hai aging (waiting time ke saath priority badhao).

Kaun sa scheduler minimum average waiting time deta hai (no preemption)?

SJF (Shortest Job First).

Gantt chart se metrics compute karne ka order kya hai?

Pehle CT, phir TAT = CT−AT, phir WT = TAT−BT.

Recall Feynman: 12-saal ke bachche ko samjhao

Ek jhula socho aur bachhon ki line. FCFS = jo pehle line mein laga woh jab tak chaahe jhulta rahe — unfair hai agar pehla bachcha forever ruka rahe. SJF = jo sirf ek chhoti si push chahte hain unhe pehle jaane do, taaki line jaldi choti ho. SRTF = beech jhule ke bhi, agar ek bachcha sirf ek tiny push ke liye aaye, toh use turat jaane do. Round Robin = sabko exactly 2 minute, phir line ke peeche — super fair, koi baad nahi rehta. Priority = teacher ke chahite pehle jaate hain, lekin agar tum kaafi der wait karo toh dheere-dheere tum bhi chahite ban jaate ho (yahi "aging" hai). Har rule ek hi sawaal ka jawaab deta hai — aage kaun? — alag tarike se.