Four jobs arrive at a single CPU. A long batch job arrives first; three short interactive jobs arrive immediately after it. First-come, first-served keeps the CPU busy and completes every job, yet users wait behind work that is irrelevant to their requests. “100% utilization” has concealed a latency failure.
A scheduling policy chooses among runnable execution contexts. Timer interrupts, context save/restore, and run-queue operations are mechanisms. The choice is defensible only relative to a workload and objective.
Prediction — one trace, three objectives
Jobs and are written as (arrival, CPU service). With no preemption or switch cost, predict which first job minimizes each objective: completion time of A, mean response time, and maximum waiting time. One choice need not optimize all three.
HintExpandCollapse
An objective about A is not an objective about the population.
Worked solutionExpandCollapse
Running A first minimizes A’s completion time. Choosing a short ready job such as B improves mean response relative to A-first. Maximum waiting depends on the full order; among simultaneous known jobs, short-first tends to delay A substantially, while long-first delays every short job. The point is not a unique answer before constructing complete schedules: the objectives are different functions and cannot be replaced by “fast.”
Workload model and metrics
For job define:
- arrival
- first dispatch
- completion
- total required CPU service and
- total blocked time during the observation.
Then
In the teaching traces, so waiting is turnaround minus service. Under preemption, response counts only until the first dispatch; later ready intervals contribute waiting but not response.
For an interval of length
Scheduler and switch work may keep the CPU physically busy while reducing Report both if the distinction matters.
Worked trace — metric reconstruction for a preempted job
Job arrives at 2, runs on intervals and blocks on I/O during and completes at 13. Compute response, turnaround, service, blocked time, and ready-wait.
Worked solutionExpandCollapse
Response is Turnaround is CPU service is Blocked time is 2. Ready-wait is two units before first dispatch and two from wakeup at 8 until redispatch at 10. Using turnaround minus service alone would report 6 and incorrectly charge blocked time to the CPU scheduler.
CPU Scheduling Metrics Classification Matrix
Job Q arrives at 3, is first dispatched at 5, blocks on I/O during [7,9), resumes at 10, and completes at 14 with 6 units of CPU service. Evaluate each statement:
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
FCFS and the convoy effect
First-come, first-served orders ready work by arrival, with an explicit tie rule. Under non-preemptive FCFS and tie order A, B, C, D, the motivating workload becomes:
time 0 8 10 11 13
CPU | A | B |C| D |
| Job | First run | Completion | Response | Turnaround | Waiting |
|---|---|---|---|---|---|
| A | 0 | 8 | 0 | 8 | 0 |
| B | 8 | 10 | 8 | 10 | 8 |
| C | 10 | 11 | 9 | 10 | 9 |
| D | 11 | 13 | 9 | 11 | 9 |
| mean | — | — | 6.50 | 9.75 | 6.50 |
The CPU is usefully busy for all 13 units, but short jobs inherit the long job’s service time. This is the convoy effect. FCFS remains valuable when order itself is the contract, overhead must be minimal, or jobs have similar service demands. A counterexample is not a universal rejection.
Transfer — arrival order versus queue order
At time 5, a running FCFS job blocks. Two jobs already wait; a third arrives while the CPU is selecting. What must the policy specify to remain deterministic, and why is “earliest PID” not FCFS?
Worked solutionExpandCollapse
Specify the linearization of runnable insertion and the tie rule for equal logical arrival times. Existing waiters should precede the newly runnable/arriving job under FIFO semantics. PID is identity, not arrival order; reuse and allocation patterns can reorder service. A real concurrent queue needs synchronization around insertion/selection, but the policy contract must exist before implementation.
SJF: an optimum inside a narrow theorem
Assume non-preemptive jobs all arrive at time zero, service times are known exactly, and the objective is mean waiting time. Consider adjacent jobs then after prefix duration with Their contribution to total waiting is
Swapping them contributes
which is smaller by Repeatedly removing every inversion yields nondecreasing service order. Therefore shortest-job-first minimizes total—and hence mean—waiting under these assumptions.
This proof says nothing about unknown bursts, unequal arrivals, preemption, deadlines, weights, or maximum waiting.
For the motivating workload, non-preemptive SJF can choose B at time 0; by time 2 C and D have arrived:
time 0 2 3 5 13
CPU | B|C| D | A |
Responses are A=5, B=0, C=1, D=1; mean response and waiting are 1.75. Mean turnaround is The improvement is large because exact service times were supplied by the exercise.
Proof boundary — construct starvation
Suppose a long job with service 100 is ready. Can an arrival stream of short jobs (service 1) starve indefinitely? Distinguish non-preemptive SJF from preemptive SRTF:
- Non-preemptive SJF with alone at time 0: If is the sole ready job at non-preemptive SJF immediately dispatches Because the policy is non-preemptive, subsequent arrivals cannot displace it runs uninterrupted from to Starvation does not occur.
- True starvation under non-preemptive SJF: Requires that at another job is already running or ready, and before each short job finishes, a new short job arrives. At every scheduling decision boundary, the scheduler sees at least one shorter job ready, so is never selected.
- Starvation under preemptive SRTF: If short jobs arrive with remaining service is repeatedly preempted or delayed, suffering unbounded waiting.
Worked solutionExpandCollapse
Under non-preemptive SJF, a long job ready at time 0 cannot starve if it is selected first; once running, non-preemption protects it. Unbounded starvation requires either: (a) under non-preemptive SJF: at time 0, a short job is dispatched, and before each completes, arrives so the ready queue is never empty of shorter jobs at any decision point; or (b) under preemptive SRTF: frequent short arrivals repeatedly preempt
The simultaneous-arrival batch theorem does not prevent starvation because its foundational assumption—a finite, closed batch arriving simultaneously at —is violated by continuous dynamic arrivals. Real systems prevent this via dynamic priority aging.
SRTF and the value of preemption
Shortest-remaining-time-first re-evaluates the runnable job with least remaining service whenever the eligible set changes. Let A arrive at 0 with service 10 and B arrive at 1 with service 1.
- Non-preemptive SJF starts A because it is the only job at time 0: A runs 0–10, B 10–11. Mean turnaround is
- SRTF runs A 0–1, B 1–2, then A 2–11. Turnarounds are 11 and 1; mean is 6.
Preemption improves this trace because new information arrives. It also adds context-switch cost and can starve large jobs under sustained short arrivals. Exact remaining time is usually unavailable; systems infer behavior from history or use application-provided classes under an authority policy.
Application — preemption is not free
In the A/B trace, each change between jobs costs 0.75 time units and no useful work occurs during a switch. Recompute both completion times for SRTF if the scheduler charges A→B and B→A, but not initial dispatch.
Worked solutionExpandCollapse
A runs 0–1; switch to B takes 1–1.75; B runs 1.75–2.75; switch to A takes 2.75–3.5; A’s remaining 9 units finish at 12.5. Turnarounds are A=12.5 and B=1.75, mean 7.125. This still beats the modeled non-preemptive mean 10, but the benefit shrinks. If switch cost exceeded the latency saved, preemption would lose. The scheduler must charge overhead to the schedule rather than treating it as an annotation.
Round robin: bound service gaps, choose a quantum
Round robin places runnable jobs in FIFO order and runs each for at most quantum A job that blocks or finishes early gives up the CPU; an unfinished job returns to the tail. With continuously runnable jobs, zero switch cost, and no higher-priority interference, a job waits at most roughly between its quanta. That is a model bound, not a production latency guarantee.
For the motivating workload with and zero switch cost:
time 0 2 4 5 7 9 11 13
CPU | A| B|C| D| A| A | A |
The queue after A’s first quantum is B, C, D, A. Responses are A=0, B=2, C=3, D=3; mean response is 2.00. Turnarounds are A=13, B=4, C=4, D=5; mean turnaround is 6.50. Mean waiting is 3.25.
If every quantum causes a switch costing the saturated upper-bound overhead fraction is
As round robin approaches FCFS for finite jobs. As response opportunities become frequent while switching consumes the machine. A quantum is therefore a workload-timescale decision.
Prediction before interaction
For the convoy workload, predict the direction—not exact magnitude—of these changes:
- FCFS → RR with zero switch cost: mean response and mean turnaround;
- RR quantum 8 → quantum 1 with switch cost 2: response opportunity and useful utilization;
- convoy → staggered workload: idle time.
Schedule the same jobs under competing policies
Change the policy, workload, round-robin quantum, and context-switch cost. Compare response, waiting, turnaround, and useful CPU time rather than declaring one scheduler universally best.
| Job | Arrival | Burst | Response | Waiting | Turnaround |
|---|---|---|---|---|---|
| A | 0 | 8 | 0 | 5 | 13 |
| B | 0 | 2 | 2 | 2 | 4 |
| C | 1 | 1 | 3 | 3 | 4 |
| D | 2 | 2 | 3 | 3 | 5 |
Means: response 2.0, waiting 3.3, turnaround 6.5. Model assumptions: one CPU, known bursts for SJF, no I/O re-entry, selection committed before any switch interval, and switch cost charged only when the CPU changes jobs.
| Job | Arrival | Burst | Response | Waiting | Turnaround |
|---|---|---|---|---|---|
| A | 0 | 8 | 0 | 5 | 13 |
| B | 0 | 2 | 2 | 2 | 4 |
| C | 1 | 1 | 3 | 3 | 4 |
| D | 2 | 2 | 3 | 3 | 5 |
Static state: convoy workload, round robin, quantum 2, zero switch cost. Response improves over FCFS, but real systems must account for switch overhead and workload uncertainty.
The simulator charges switch cost only when the CPU changes jobs, assumes one CPU and CPU-only jobs, and gives SJF exact burst knowledge. It is a trace calculator for those assumptions. It does not model cache warming, I/O wakeups, priority, multicore migration, or production Linux.
Simulator investigation — falsify “smaller quantum is better”
Use the convoy workload and RR. Record mean response, turnaround, and useful utilization for at least four (quantum, switch cost) pairs. Find one pair where a smaller quantum improves response but makes turnaround and utilization worse. Explain the causal sequence.
HintExpandCollapse
Increase switch cost enough that extra boundaries become visible.
Worked solutionExpandCollapse
One valid investigation compares zero cost with cost 1 or 2 while lowering the quantum. Exact displayed means are the evidence. The causal claim must mention that more preemption points let short jobs begin earlier, while each inter-job boundary inserts non-service time and delays every completion. If the selected run has only one job remaining, consecutive quanta of that job do not incur inter-job switch cost in this model; count actual amber segments rather than multiplying all quanta blindly.
Unknown bursts and feedback policies
Exact SJF is an oracle policy. A practical scheduler can estimate the next CPU burst using an exponentially weighted history
Large reacts quickly and forgets history; small smooths noise and adapts slowly. This is a predictor, not a guarantee. Adversarial or phase-changing workloads defeat it.
A multilevel feedback queue (MLFQ) can favor tasks that yield quickly and demote tasks consuming full quanta. To be a complete policy it must specify:
- number of queues and quantum per queue;
- insertion on creation and wakeup;
- demotion/accounting across voluntary yields;
- priority boost or aging rule;
- preemption between queues; and
- treatment of multiple threads or process weights.
Without cumulative accounting, a CPU-bound job can yield just before each quantum expires and avoid demotion. Without aging, lower queues can starve.
Transfer — predictor phase change
A task alternates 100 bursts of length 1 with 100 bursts of length 20. Compare qualitatively and at each phase boundary. Which is “better”?
Worked solutionExpandCollapse
moves the estimate near the new phase within a few samples but follows individual noise; retains the old phase for many bursts and is stable within a stationary phase. Neither is universally better. If misclassifying a newly interactive phase causes severe response harm, rapid adaptation may matter; if burst measurements are noisy and classes drive costly migration, smoothing may win. Report prediction error by phase rather than one global mean.
Fairness, tails, and overload
Mean latency can hide one victim. A policy evaluation should include:
- median and high-percentile response/turnaround;
- maximum or bounded waiting under stated admission assumptions;
- per-class service share versus assigned weight;
- deadline-miss or service-level violation rate when relevant;
- useful utilization and switch/migration overhead; and
- starvation and gaming traces.
For continuously runnable tasks with positive weights a proportional-share target over a long interval is
Short intervals, wakeups, minimum granularity, and hierarchy create deviation. Fairness is always measured over a window and subject set.
Counterexample — the mean approves starvation
One policy completes 99 one-unit jobs immediately and delays one 100-unit job for 10,000 units. Another delays every short job by 5 but begins the long job promptly. Why can mean response alone select the first policy, and what constraint repairs the objective?
Worked solutionExpandCollapse
The 99 near-zero responses dominate the average, so one extreme victim contributes only 1% of samples. Add a maximum-wait or starvation-freedom constraint, report tail distribution, or optimize a weighted objective that reflects the long job’s class. The repair is not to discard means; it is to prevent aggregation from erasing a required per-job guarantee.
Production comparison: virtual time and EEVDF
Current Linux scheduler documentation describes a transition from the older CFS design toward Earliest Eligible Virtual Deadline First (EEVDF). The documented model tracks virtual runtime and lag: a task with nonnegative lag is eligible, and the eligible task with earliest virtual deadline is selected. Shorter requested slices can improve latency while lag accounts for fair service.
This is not SJF: a virtual deadline is not an oracle for total job length. It is not the fixed-quantum RR simulator either: eligibility, weights, lag, wakeup behavior, and scheduler hierarchy matter. Production comparison should preserve those distinctions and cite the running kernel/version measured.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 2.3.1: Convoy Effect and Head-of-Line Blocking in FCFS
Analyze the convoy effect under First-Come, First-Served (FCFS) scheduling when one CPU-bound task with an 80 ms burst arrives immediately ahead of ten interactive I/O-bound tasks with 2 ms bursts. Compute the average waiting time and describe the utilization of the CPU and I/O devices over time.
HintExpandCollapse
Contrast the FCFS schedule with an interleaved round-robin or shortest-job-first order.
Worked solutionExpandCollapse
Under FCFS, the 80 ms CPU job blocks all ten 2 ms interactive jobs. The first interactive job waits 80 ms, the second waits 82 ms, and the tenth waits 98 ms, yielding a mean waiting time of During this initial 80 ms window, the I/O devices sit completely idle. Once the CPU job finishes, all ten interactive jobs quickly execute for 2 ms and issue I/O, leaving the CPU idle while disk or network transfers complete concurrently. FCFS creates head-of-line blocking that penalizes interactive response and degrades device concurrency.
Exercise 2.3.2: Starvation in Shortest Job First Under Continuous Short Job Arrival
Prove that non-preemptive Shortest Job First (SJF) and preemptive Shortest Remaining Time First (SRTF) can cause indefinite starvation for a long job, and formulate an aging mechanism that restores bounded turnaround.
HintExpandCollapse
Construct an adversarial workload where new short jobs arrive faster than they can be cleared.
Worked solutionExpandCollapse
Suppose a long job with burst length arrives at time 0. At every time interval (for a new short job with burst length 4 arrives. Because (and the SJF/SRTF dispatch rule perpetually prioritizes the newly arrived short job over Thus, is never scheduled and starves indefinitely. An aging mechanism dynamically decrements the effective burst estimate or increments an effective priority by guaranteeing that ‘s priority eventually dominates every fresh arrival.
Exercise 2.3.3: Round-Robin Quantum Sizing and Switch Overhead Trade-off
In a Round-Robin scheduler with context switch cost evaluate the fractional CPU overhead and maximum interactive response latency across runnable tasks for quantum lengths and
HintExpandCollapse
Apply the saturation overhead formula and queue cycle bounds.
Worked solutionExpandCollapse
-
- Overhead:
- Max latency between quanta:
-
- Overhead:
- Max latency between quanta:
-
- Overhead:
- Max latency between quanta: Small quanta guarantee snappy interactive response but waste of CPU cycles in switching overhead; large quanta minimize overhead but degrade interactive responsiveness toward FCFS.
Exercise 2.3.4: Exponential Moving Average CPU Burst Estimation
A process exhibits measured CPU bursts Using an exponential moving average with weighting factor and initial guess compute the predicted bursts
HintExpandCollapse
Apply the recursive formula step by step.
Worked solutionExpandCollapse
- The estimator dampens transient spikes while gradually tracking shifts in process behavior.
Exercise 2.3.5: Virtual Runtime, Lag, and Eligibility in EEVDF Scheduling
Explain the concepts of virtual runtime, lag, and virtual deadlines in Linux Earliest Eligible Virtual Deadline First (EEVDF) scheduling. Describe how EEVDF prevents a short interactive task from being starved by compute-heavy threads while preserving weighted proportional-share fairness.
HintExpandCollapse
Contrast the eligibility check (lag >= 0) with the selection criterion (earliest virtual deadline).
Worked solutionExpandCollapse
In EEVDF, each entity has a weight Fluid fair-share time advances at rate An entity’s lag is the difference between the service it should have received in an ideal fluid model and the service it actually received: An entity is defined as eligible if and only if (it has not received more than its fair share). Among eligible tasks, EEVDF selects the task with the earliest virtual deadline where is the task’s requested slice. An interactive task requests a small slice yielding an early virtual deadline that grants it immediate preemption upon becoming eligible, while compute threads with large slices are bounded to their proportional share without starving the interactive task.
Exercise 2.3.6: Scheduling Mixed Real-Time, Interactive, and Batch Workloads
Design a multi-queue scheduling policy for a single-core embedded controller running a hard real-time control loop (0.5 ms CPU every 10 ms), an interactive console daemon, and a background batch data compression worker. Specify admission checks, preemption triggers, quantum budgets, and overload shed policies.
HintExpandCollapse
Combine fixed-priority real-time scheduling with rate-monotonic analysis and round-robin background queues.
Worked solutionExpandCollapse
- Queue hierarchy:
- Priority 1 (Highest, Real-Time FIFO): Control loop Admitted only after rate-monotonic feasibility check: Preempts all lower queues immediately upon timer release.
- Priority 2 (Interactive Round-Robin): Console daemon Allocated a small quantum for low response latency.
- Priority 3 (Lowest, Batch Background): Compression worker Runs with a large quantum to maximize L1/L2 cache locality and reduce switch overhead.
- Overload protection: If overruns its 0.5 ms budget (detected via hardware watchdog or CPU timer), it is quarantined and an alarm logged. If floods the system, Priority 2 is throttled to at most CPU time, preserving residual bandwidth for
References & Further Reading
- The Open Group, POSIX.1-2024 General Information §2.8.4: Process Scheduling, FIFO/RR conceptual semantics.
- Linux kernel documentation, EEVDF Scheduler and CFS Scheduler, for current production virtual-time context.
- MIT PDOS, xv6 rev5
kernel/proc.candkernel/trap.c, for the teaching scheduler and timer-yield mechanism. - MIT PDOS, xv6: a simple, Unix-like teaching operating system, Chapter 7.