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

WHAT are the five core quantities?

To define them we need timestamps for each process $P_i$ :

Everything else is derived from these.

HOW to derive each formula from first principles

1. Turnaround time

"How long did the whole journey take, door to door?" From the instant it arrives to the instant it leaves:

$TAT_i = CT_i - AT_i$

2. Waiting time

The journey time is split into two parts: time actually running on the CPU ( $BT_i$ ) and time not running (waiting in queue). So:

$TAT_i = BT_i + WT_i \quad\Rightarrow\quad WT_i = TAT_i - BT_i$

(For preemptive schedulers $WT$ still equals "time in system minus time spent on CPU"; if the process is preempted, the queued gaps just add up inside $WT$ .)

3. Response time

Users care about the first reaction, not the finish.

$RT_i = ST_i - AT_i$

4. CPU Utilization

We want the CPU never idle. Over an observation window of length $T_{total}$ with $T_{idle}$ time idle:

$U = \frac{T_{total} - T_{idle}}{T_{total}} \times 100\%$

5. Throughput

Count finished jobs over a window:

$\text{Throughput} = \frac{\text{number of completed processes}}{T_{total}}$

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

Worked Example 1 — FCFS, three processes

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

Order = P1, P2, P3 (FCFS, all arrive at 0).

Build the timeline (Gantt): | P1 0–5 | P2 5–8 | P3 8–16 |

CT: $CT_1=5,\ CT_2=8,\ CT_3=16$ . Why this step? Each process runs to completion, so completion = end of its slice.
TAT $=CT-AT$ : $TAT_1=5,\ TAT_2=8,\ TAT_3=16$ . Why? All arrived at 0, so TAT = CT.
WT $=TAT-BT$ : $WT_1=0,\ WT_2=5,\ WT_3=8$ . Why? P2 waited the 5 of P1; P3 waited 5+3.
RT $=ST-AT$ : $0, 5, 8$ (same as WT here, non-preemptive, no later gaps).

Averages: $\overline{TAT}=\frac{5+8+16}{3}=9.67$ , $\overline{WT}=\frac{0+5+8}{3}=4.33$ . Throughput $=3/16=0.1875$ proc/unit. Utilization = 100% (CPU never idle).

Worked Example 2 — Different arrivals (idle CPU)

Process	AT	BT
P1	0	4
P2	6	2

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

$CT_1=4,\ CT_2=8$ .
$TAT_1=4-0=4,\ TAT_2=8-6=2$ .
$WT_1=4-4=0,\ WT_2=2-2=0$ . Why both 0? Neither waited behind another job.
Utilization $=\frac{6}{8}\times100\%=75\%$ . Why? CPU idle 4→6, busy 6 of 8 units.
Throughput $=2/8=0.25$ proc/unit.

Common Mistakes (Steel-manned)

Flashcards

What is turnaround time in terms of CT and AT?

TAT_i = CT_i - AT_i

(completion minus arrival).

Derive waiting time from turnaround.

Time in system = burst + waiting, so

WT_i = TAT_i - BT_i

Define response time.

RT_i = ST_i - AT_i

: arrival to first time the process gets the CPU.

Why can RT differ from WT?

With preemption a process starts early (low RT) but is interrupted and waits more later, so

RT \le WT

in general.

Formula for CPU utilization?

U = T_{busy}/T_{total}\times100\%

= fraction of wall-clock time doing useful work.

Formula for throughput?

N_{completed}/T_{total}

— completed processes per unit time.

Which scheduler provably minimizes average waiting time?

Shortest Job First (SJF) for a given set of jobs.

A CPU idle 2 of 10 units — utilization?

8/10 = 80\%

Why isn't 100% utilization automatically good?

It can hide backlog/thrashing with awful response and turnaround for users.

Which metrics matter to the user vs the system owner?

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

Recall Feynman: explain to a 12-year-old

Imagine a single checkout counter (the CPU) and customers (processes). Turnaround = how long you were in the shop, door to door. Waiting = time standing in line, not being served. Response = how long until the cashier first says "hi" to you. Utilization = how much of the day the cashier was actually scanning items instead of idle. Throughput = how many customers got served per hour. A good manager wants the cashier always busy AND customers happy — but rushing some customers makes others wait. You have to choose what "fair" means.

Connections

First-Come First-Served (FCFS) — baseline; good throughput, bad waiting.
Shortest Job First (SJF) — optimal average waiting time.
Round Robin Scheduling — optimizes response, costs context-switch overhead.
Context Switching — the overhead that hurts throughput when slicing too fine.
Gantt Chart — the tool used to compute all these metrics.
Process States — ready/running/waiting feed the queue these metrics measure.
Priority Scheduling — trades fairness for chosen-goal optimization.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, CPU scheduler ek referee jaisa hai jo decide karta hai ki ready queue me se kaunsa process ab CPU lega. Lekin "achha scheduling" har kisi ke liye alag matlab rakhta hai. System ka owner chahta hai CPU hamesha busy rahe (utilization) aur zyada se zyada kaam khatam ho (throughput). User chahta hai uska kaam jaldi ho (turnaround) aur screen turant react kare (response). Yeh sab cheezein hum numbers me measure karte hain, taaki do schedulers ko compare kar saken.

Sabse important relation yaad rakho: TAT = WT + BT. Yaani total time jo process system me bitata hai = uska actual CPU kaam (burst) + line me wait. Isi se WT = TAT − BT nikalta hai. TAT = CT − AT (jab process khatam hua minus jab aaya). RT = Start − AT yaani pehli baar CPU milne tak ka time. In char timestamps (AT, BT, ST, CT) se baaki sab derive ho jaata hai — Gantt chart bana ke nikaal lo.

Ek important baat: aap saari cheezein ek saath maximize nahi kar sakte. Agar response time kam karna hai to Round Robin se baar-baar switch karna padta hai, jisse context-switch overhead badhta hai aur average turnaround badh sakta hai. Yeh trade-off hi pura chapter ka dil hai. Aur 100% utilization hamesha achhi baat nahi — andar backlog ho sakta hai jisme users ko bura response mil raha ho.

Exam tip (80/20): bas yeh 5 metrics aur unke formula clear kar lo, ek Gantt chart practice kar lo (FCFS, SJF, Round Robin), aur common galti — WT ko TAT samajhna — avoid karo. Itne me hi 80% questions aaram se nikal jaayenge.