Scheduling goals — CPU utilization, throughput, turnaround, waiting, response

4.2.9 · Coding › Operating Systems

WHY hume metrics ki zaroorat hi kyun hai?

WHAT hain ye paanch core quantities?

Inhe define karne ke liye hume har process $P_{i}$ ke timestamps chahiye:

Baaki sab inhi se derive hota hai.

HOW karte hain har formula derive first principles se

1. Turnaround time

"Poora safar kitna lamba tha, door se door tak?" Jis pal arrive kiya uss pal se jis pal gaya uss pal tak:

$T A T_{i} = C T_{i} - A T_{i}$

2. Waiting time

Safar ka time do parts mein banta hai: CPU par actually run hone ka time ( $B T_{i}$ ) aur nahi run hone ka time (queue mein wait karna). Toh:

$T A T_{i} = B T_{i} + W T_{i} \Rightarrow W T_{i} = T A T_{i} - B T_{i}$

(Preemptive schedulers ke liye $W T$ phir bhi "system mein time minus CPU par bitaya gaya time" ke barabar hota hai; agar process preempt ho jaata hai, toh queued gaps $W T$ ke andar add ho jaate hain.)

3. Response time

Users ko pehli reaction ki parwah hoti hai, finish hone ki nahi.

$R T_{i} = S T_{i} - A T_{i}$

4. CPU Utilization

Hum chahte hain CPU kabhi idle na ho. $T_{t o t a l}$ length ki observation window mein $T_{i d l e}$ idle time ke saath:

$U = \frac{T _{t o t a l} - T _{i d l e}}{T _{t o t a l}} \times 100%$

5. Throughput

Ek window mein finished jobs count karo:

$Throughput = \frac{number of completed processes}{T _{t o t a l}}$

Figure — Scheduling goals — CPU utilization, throughput, turnaround, waiting, response

Worked Example 1 — FCFS, teen processes

Process	AT	BT
P1	0	5
P2	0	3
P3	0	8

Order = P1, P2, P3 (FCFS, sab 0 par arrive karte hain).

Timeline banao (Gantt): | P1 0–5 | P2 5–8 | P3 8–16 |

CT: $C T_{1} = 5, C T_{2} = 8, C T_{3} = 16$ . Ye step kyun? Har process completion tak run karta hai, toh completion = uske slice ka end.
TAT $= C T - A T$ : $T A T_{1} = 5, T A T_{2} = 8, T A T_{3} = 16$ . Kyun? Sab 0 par aaye, toh TAT = CT.
WT $= T A T - B T$ : $W T_{1} = 0, W T_{2} = 5, W T_{3} = 8$ . Kyun? P2 ne P1 ke 5 units wait kiye; P3 ne 5+3 wait kiye.
RT $= S T - A T$ : $0, 5, 8$ (yahaan WT ke barabar, non-preemptive, koi baad ke gaps nahi).

Averages: $\overline{T A T} = \frac{5 + 8 + 16}{3} = 9.67$ , $\overline{W T} = \frac{0 + 5 + 8}{3} = 4.33$ . Throughput $= 3/16 = 0.1875$ proc/unit. Utilization = 100% (CPU kabhi idle nahi).

Worked Example 2 — Alag arrivals (idle CPU)

Process	AT	BT
P1	0	4
P2	6	2

Gantt: | P1 0–4 | idle 4–6 | P2 6–8 |

$C T_{1} = 4, C T_{2} = 8$ .
$T A T_{1} = 4 - 0 = 4, T A T_{2} = 8 - 6 = 2$ .
$W T_{1} = 4 - 4 = 0, W T_{2} = 2 - 2 = 0$ . Dono 0 kyun? Koi bhi kisi doosre job ke peeche wait nahi kiya.
Utilization $= \frac{6}{8} \times 100% = 75%$ . Kyun? CPU 4→6 idle raha, 8 units mein se 6 busy.
Throughput $= 2/8 = 0.25$ proc/unit.

Common Mistakes (Steel-manned)

Flashcards

CT aur AT ke terms mein turnaround time kya hai?

T A T_{i} = C T_{i} - A T_{i}

(completion minus arrival).

Turnaround se waiting time derive karo.

System mein time = burst + waiting, toh

W T_{i} = T A T_{i} - B T_{i}

Response time define karo.

R T_{i} = S T_{i} - A T_{i}

: arrival se pehli baar process ko CPU milne tak.

RT, WT se alag kyun ho sakta hai?

Preemption ke saath process jaldi start hota hai (low RT) lekin interrupt hokar baad mein aur wait karta hai, isliye generally

R T \leq W T

CPU utilization ka formula?

U = T_{b u sy} / T_{t o t a l} \times 100%

= useful kaam mein bitaye wall-clock time ka fraction.

Throughput ka formula?

N_{co m pl e t e d} / T_{t o t a l}

— per unit time mein complete hue processes.

Kaun sa scheduler provably average waiting time minimize karta hai?

Shortest Job First (SJF) given set of jobs ke liye.

CPU 10 units mein se 2 units idle raha — utilization?

8/10 = 80%

100% utilization automatically achhi kyun nahi hai?

Ye backlog/thrashing hide kar sakti hai jisme users ke liye response aur turnaround bahut buri hoti hain.

User ke liye aur system owner ke liye kaunse metrics matter karte hain?

User: response & turnaround; System owner: utilization & throughput.

Recall Feynman: 12-saal ke bache ko samjhao

Socho ek akela checkout counter (CPU) hai aur customers (processes) hain. Turnaround = tum dukaan mein kitne der the, door se door tak. Waiting = line mein khade rehne ka time, serve nahi ho rahe. Response = cashier ne pehli baar tumhe "hi" bolne mein kitna time liya. Utilization = din mein cashier kitni der actually items scan karta raha, idle nahi tha. Throughput = ghante mein kitne customers serve hue. Ek achha manager chahta hai cashier hamesha busy rahe AND customers khush rahe — lekin kuch customers ko rush karne se doosre wait karte hain. Tumhe choose karna padta hai ki "fair" ka kya matlab hai.

Connections

First-Come First-Served (FCFS) — baseline; achha throughput, bura waiting.
Shortest Job First (SJF) — optimal average waiting time.
Round Robin Scheduling — response optimize karta hai, context-switch overhead deta hai.
Context Switching — wo overhead jo bahut fine slicing se throughput hurt karta hai.
Gantt Chart — wo tool jisse ye sab metrics compute hoti hain.
Process States — ready/running/waiting queue feed karte hain jise ye metrics measure karti hain.
Priority Scheduling — fairness ko chosen-goal optimization ke liye trade karta hai.