Scheduling Performance Metrics

A CPU scheduler decides, among ready processes, which one runs next and for how long. To compare two scheduling policies objectively, we need quantities computable from the resulting execution timeline — the sequence of intervals in which each process holds the CPU, commonly drawn as a Gantt chart. Six metrics dominate the literature and practice.

CPU utilization is the fraction of wall-clock time the CPU is doing useful work rather than sitting idle. Throughput is the number of processes completed per unit time. Turnaround time for a process is the total time from its arrival in the system to its completion — it bundles waiting, I/O, and execution together. Waiting time isolates just the portion of turnaround spent in the ready queue, not running and not blocked on I/O. Response time measures how long an interactive user waits before seeing the first sign of progress, i.e., time until the process is first scheduled, not until it finishes. Fairness measures how evenly the CPU is shared among competing processes, often quantified by the variance or spread of waiting times, or by formal notions like max-min fairness. These six metrics are not independent choices a system architect can freely maximize together. They form genuine tradeoffs: a scheduler minimizing mean waiting time (like Shortest-Job-First Scheduling) systematically favors short jobs, which increases the variance of waiting times among long jobs and thus reduces fairness. A scheduler maximizing fairness (equal CPU shares, as in Round-Robin Scheduling) sacrifices some throughput to context-switch overhead. Understanding precisely how each metric is computed is the prerequisite for understanding why CPU Scheduling Fundamentals frames scheduling as a policy decision rather than a single "correct" algorithm.

The mechanism here is not an algorithm that produces a schedule — that is the job of FCFS, SJF, Round-Robin, etc. Rather, it is the algorithm for measuring any given schedule once it exists. Given a schedule (a Gantt chart) plus each process's arrival time and total CPU burst, we compute every metric in one linear pass.

Definitions, precisely, for process $P_i$:

where $\text{FirstRun}_i$ is the timestamp of the first CPU slice ever given to $P_i$ (relevant when preemption lets a process run in several disjoint slices).

System-wide aggregates:

where $n$ is the number of completed processes and makespan is the total elapsed wall-clock time from the first arrival to the last completion.

Fairness (one common quantitative form, Jain's fairness index) applied to waiting times $w_1, \dots, w_n$:

$J = 1$ means every process waited exactly the same amount; $J \to 1/n$ means one process absorbed almost all the waiting.

Step-by-step algorithm

``` ALGORITHM ComputeSchedulingMetrics INPUT: processes[1..n] // each with arrival_time, burst_time schedule // list of (pid, start_time, end_time) slices, // in chronological order, possibly several // slices per pid if preemptive OUTPUT: utilization, throughput, avg_turnaround, avg_waiting, avg_response, fairness // Pass 1: scan the schedule once to find, per process, // first_run time and completion (last end) time, and total busy time. first_run[1..n] <- +infinity completion[1..n] <- -infinity total_busy <- 0 earliest_arrival <- min(arrival_time[i] for all i) last_completion <- -infinity for each slice (pid, start, end) in schedule: first_run[pid] <- min(first_run[pid], start) completion[pid] <- max(completion[pid], end) total_busy <- total_busy + (end - start) last_completion <- max(last_completion, end) // Pass 2: derive per-process metrics sum_turnaround <- 0 sum_waiting <- 0 sum_response <- 0 for i in 1..n: turnaround[i] <- completion[i] - arrival_time[i] waiting[i] <- turnaround[i] - burst_time[i] response[i] <- first_run[i] - arrival_time[i] sum_turnaround <- sum_turnaround + turnaround[i] sum_waiting <- sum_waiting + waiting[i] sum_response <- sum_response + response[i] makespan <- last_completion - earliest_arrival avg_turnaround <- sum_turnaround / n avg_waiting <- sum_waiting / n avg_response <- sum_response / n throughput <- n / makespan utilization <- total_busy / makespan // Fairness: Jain's index over the waiting-time vector sum_w <- sum_waiting sum_w2 <- sum(waiting[i]^2 for i in 1..n) fairness <- (sum_w sum_w) / (n sum_w2) // guard sum_w2 = 0 -> fairness = 1 return (utilization, throughput, avg_turnaround, avg_waiting, avg_response, fairness) ``` Two passes over a schedule of $m$ slices and $n$ processes: the first pass is $O(m)$, aggregating per-process extremes and busy time; the second is $O(n)$, deriving the per-process metrics and sums. This is exactly why the metrics are cheap to instrument in a real kernel or simulator — they require only counters updated at each context switch, not any re-derivation of the schedule itself.

Time complexity. Given a schedule already expressed as $m$ context-switch slices over $n$ processes, computing all six metrics takes $O(m + n)$ time: one linear scan of the slice list to find each process's first-run time, completion time, and busy total, followed by one linear scan over the $n$ processes to derive turnaround, waiting, and response, plus $O(n)$ work for the fairness index. There is no hidden superlinear step — every quantity is a running min, max, or sum. Space complexity is $O(n)$ for the per-process accumulator arrays; the slice list itself can be streamed rather than stored, so working memory need not grow with the length of the timeline.

Correctness argument. The definitions are not heuristics; they are direct bookkeeping identities that follow from what "waiting" and "turnaround" mean. Fix a process $P_i$ with arrival time $a_i$ and total CPU demand (burst) $b_i$. Over its lifetime it is always in exactly one of three states: waiting in the ready queue, running on the CPU, or blocked on I/O (ignored here since classic burst models assume CPU-only accounting between arrival and completion, or I/O is folded into separate bursts). Hence the time from arrival to completion decomposes as

which is the definition $\text{Waiting}_i = \text{Turnaround}_i - b_i$ — it is a conservation law over disjoint states, so the algorithm's Pass 2 formula is exact by construction, not an approximation. Similarly, response time is exact because $\text{FirstRun}_i$ is tracked as the minimum start time over all of $P_i$'s slices in Pass 1, and by definition no CPU time can be delivered to $P_i$ before that timestamp. Throughput and utilization are ratios over the makespan, itself computed as $\max_i \text{completion}_i - \min_i \text{arrival}_i$; both are well-defined as long as at least one process completes, and the busy-time sum in the numerator of utilization can never exceed the makespan because slices are non-overlapping on a single CPU, guaranteeing $0 \le \text{Utilization} \le 1$ as a sanity invariant. Jain's fairness index is bounded in $[1/n, 1]$ by the Cauchy–Schwarz inequality applied to the vector of waiting times: $(\sum w_i)^2 \le n \sum w_i^2$ gives the upper bound $J \le 1$ (equality iff all $w_i$ equal), and the lower bound follows because a single dominant outlier maximizes $\sum w_i^2$ relative to $(\sum w_i)^2$.

Honest tradeoffs. These metrics are descriptive, not prescriptive — computing them tells you how a given schedule performed, but optimizing one metric in isolation is a distinct, harder combinatorial problem (e.g., minimizing average waiting time non-preemptively is solved optimally by SJF, but minimizing maximum waiting time, or achieving fairness, requires different objectives entirely, and no single-queue scheduler can simultaneously minimize mean waiting time, maximize fairness, and maximize utilization under bursty arrivals — these are provably competing objectives, as later algorithms illustrate).

Consider four processes arriving over time, non-preemptively scheduled in arrival order (FCFS), to make the arithmetic concrete and traceable.

FCFS runs each process to completion in arrival order without preemption. The resulting Gantt chart:

Now apply the algorithm's formulas directly.

Averages:

(Response equals waiting here only because FCFS is non-preemptive and every process runs exactly once — once it starts, it never waits again; this equality vanishes under preemptive schedulers.)

Makespan $= 18 - 0 = 18$. Utilization $= \frac{5+3+8+2}{18} = \frac{18}{18} = 1.0$ (the CPU is never idle here because arrivals overlap the running process). Throughput $= 4/18 \approx 0.222$ processes per unit time.

Fairness (Jain's index) on waiting times $\{0, 4, 6, 13\}$:

A value noticeably below 1 confirms the intuition visible in the table: P4, unlucky enough to arrive after the long P3, absorbs a disproportionate share of waiting (13 units) compared to P1 (0 units) — precisely the "convoy effect" that motivates Shortest-Job-First Scheduling as an alternative policy, which would reorder execution to reduce average waiting at the cost of even more unfairness to P3.

The formal study of scheduling metrics emerged from operations research and early time-sharing systems, where measuring "goodness" of a schedule was as urgent as designing algorithms to improve it.

Every modern operating system scheduler — the Linux Completely Fair Scheduler, Windows' priority-based scheduler, and real-time schedulers in embedded systems — is tuned and benchmarked using exactly these metrics. Cloud platforms report throughput and utilization as service-level objectives; interactive systems (desktop UIs, mobile OSes, game engines) are engineered around response time because users perceive delay in milliseconds, not job completion. Data-center batch schedulers (Hadoop's YARN, Kubernetes' scheduler) optimize throughput and fair-share allocation across tenants, directly applying Jain's fairness index or similar measures to enforce multi-tenant SLAs. Understanding these metrics is the prerequisite for reading any scheduling research paper or systems benchmark, and for evaluating the tradeoffs made by First-Come First-Served Scheduling, Shortest-Job-First Scheduling, and Round-Robin Scheduling on their own terms.

Ask the tutor: Can you show how these same metrics change if P3 is preempted partway through by a shorter arriving process?