CPU Scheduling: Metrics & Algorithms — کارت مفهوم کنکور ارشد مهندسی کامپیوتر

What CPU scheduling decides

When several processes are ready but only some cores are free, the OS short-term scheduler chooses which ready process runs next. A program is a stream of CPU bursts separated by I/O bursts; the scheduler only ever schedules the CPU bursts. A scheduler is non-preemptive if a process keeps the CPU until it finishes or voluntarily blocks (I/O or exit), and preemptive if the OS can forcibly take the CPU away (on a timer interrupt or the arrival of a higher-priority job).

The four time metrics

For a process with arrival time $a_i$ , first time it gets the CPU $s_i$ , completion time $c_i$ , and total CPU burst $b_i$ :

Metric	Definition	Formula
Turnaround time	total time in the system	$T_i = c_i - a_i$
Waiting time	time spent ready but not running	$W_i = T_i - b_i$
Response time	until first CPU service	$R_i = s_i - a_i$
Throughput	jobs finished per unit time	$\dfrac{\#\text{ completed}}{\text{elapsed time}}$

Averages are taken over all processes, e.g. $\overline{W} = \tfrac{1}{n}\sum_i W_i$ . Throughput and CPU utilization are system-wide; the rest are per-process.

The classic algorithms

Algorithm	Preemptive?	Picks	Note
FCFS / FIFO	no	earliest arrival	simple; suffers the convoy effect
SJF	no	shortest next burst	optimal $\overline{W}$ ; needs burst length
SRTF	yes	shortest remaining time	preemptive SJF
Priority	either	highest priority	risk of starvation (fix: aging)
Round Robin	yes	next in queue, quantum $q$	fair; good response time
Rate Monotonic	yes	shortest period (real-time, fixed priority)	preempts lower-rate tasks

SJF minimizes average waiting time among non-preemptive schedulers, but it requires knowing burst lengths in advance, so it is mostly a theoretical bound. Round Robin trades a little throughput for bounded response time: small $q$ improves responsiveness but adds context-switch overhead.

Mini-example (non-preemptive FCFS)

Three jobs arrive at $t=0$ in order $P_1,P_2,P_3$ with bursts $24, 3, 3$ .

FCFS runs $P_1[0\text{-}24],\ P_2[24\text{-}27],\ P_3[27\text{-}30]$ , so waiting times are $0, 24, 27$ and $\overline{W} = \tfrac{0+24+27}{3} = 17$ . Reordering shortest-first (SJF) as $P_2,P_3,P_1$ gives waits $0,3,6$ and $\overline{W}=3$ — the convoy effect that a long job at the front inflates everyone's wait.

Multicore throughput

With $k$ identical cores and total CPU work $\sum_i b_i$ , the makespan (time to finish a batch) is bounded below by $\sum_i b_i / k$ . This bound is achievable when each process's I/O wait can be perfectly overlapped by another process's CPU burst, keeping every core $100\%$ busy — then I/O time hides completely behind computation.

Exam trick: Watch the preemption word. "Strict-priority and non-preemptive" points to FCFS — Rate Monotonic is strict fixed-priority but preemptive, and SJF has a preemptive variant (SRTF), so both fail. For a multicore batch with a matched CPU/I/O ratio, the answer is just (total CPU work) / (number of cores), not the naive sum of all burst-plus-wait times.

فرمول‌های کلیدی

Turnaround & waiting time

T_i = c_i - a_i, \qquad W_i = T_i - b_i

Turnaround is completion minus arrival; waiting subtracts the actual CPU burst from turnaround.

Average waiting time

\overline{W} = \frac{1}{n}\sum_{i=1}^{n} W_i

Mean over all n processes; minimized by SJF among non-preemptive schedulers.

Multicore makespan lower bound

M \ge \frac{1}{k}\sum_{i=1}^{n} b_i

With k identical cores, the batch finish time is at least total CPU work over k; tight when I/O waits overlap others' CPU bursts.