Search Knowledge

© 2026 LIBREUNI PROJECT

Operating Systems Engineering/Processes and CPU time
Page 6 of 29

CPU Scheduling as Policy

Derive scheduling metrics and policy trade-offs from arrival/service traces, then falsify universal claims with adversarial workloads and context-switch cost.

Lesson briefProcesses and CPU time · 5 h 30 min · 4 outcomes

Required knowledge

  • Processes, runnable/running/blocked states, timer preemption, and context switching
  • Arithmetic means, ratios, inequalities, and exchange arguments
  • The distinction between mechanism, policy, and measured evidence

Learning outcomes

  • Compute response, turnaround, ready-waiting, throughput, and useful utilization from a preemptive schedule trace.
  • Derive FCFS, non-preemptive SJF, SRTF, and round-robin behavior under explicit arrival and burst assumptions.
  • Prove the simultaneous-arrival SJF interchange result and construct starvation and convoy counterexamples outside its assumptions.
  • Select and defend a scheduling policy for an unfamiliar workload using latency distributions, fairness constraints, overhead, and workload uncertainty.

Assessment target

Given an unseen arrival/service workload with a context-switch model and a fairness requirement, construct competing schedules, compute all metrics, expose one policy failure, and defend a policy or hybrid with falsifiable evidence.

Scope boundary

  • Hard real-time feasibility, multiprocessor load balancing, NUMA affinity, energy-aware scheduling, gang scheduling, and priority inheritance require separate models.
  • The interactive model uses one CPU, fixed CPU bursts, no I/O re-entry, and exact SJF burst knowledge; its numbers are not production forecasts.
  • Linux EEVDF is included as a current mechanism comparison, not reimplemented or reduced to the teaching policies.

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 A(0,8)A(0,8) B(0,2)B(0,2) C(1,1)C(1,1) and D(2,2)D(2,2) 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.

HintExpand

An objective about A is not an objective about the population.

Worked solutionExpand

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 ii define:

  • arrival aia_i
  • first dispatch fif_i
  • completion cic_i
  • total required CPU service bib_i and
  • total blocked time did_i during the observation.

Then

responsei=fi−ai,turnaroundi=ci−ai,ready-waiti=ci−ai−bi−di.\begin{aligned} \text{response}_i &= f_i-a_i,\\ \text{turnaround}_i &= c_i-a_i,\\ \text{ready-wait}_i &= c_i-a_i-b_i-d_i. \end{aligned}

In the teaching traces, di=0d_i=0 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 LL

throughput=completed jobsL,Uuseful=time executing job instructionsL.\text{throughput}=\frac{\text{completed jobs}}{L}, \qquad U_{useful}=\frac{\text{time executing job instructions}}{L}.

Scheduler and switch work may keep the CPU physically busy while reducing UusefulU_{useful} Report both if the distinction matters.

Worked trace — metric reconstruction for a preempted job

Job PP arrives at 2, runs on intervals [4,6)[4,6) and [10,13)[10,13) blocks on I/O during [6,8)[6,8) and completes at 13. Compute response, turnaround, service, blocked time, and ready-wait.

Worked solutionExpand

Response is 4−2=24-2=2 Turnaround is 13−2=1113-2=11 CPU service is 2+3=52+3=5 Blocked time is 2. Ready-wait is 11−5−2=411-5-2=4 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

0 / 4 answered

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.

1
Ready-waiting time is 5 units, computed directly by subtracting 6 CPU service units from 11 turnaround units.
2
The 2 units spent blocked on I/O must be charged directly to the CPU scheduler as processor scheduling delay.
3
Response time is 2 units, measured as the initial latency from arrival at time 3 until first CPU dispatch at time 5.
4
Ready-waiting time is 3 units, calculated by subtracting 6 service units and 2 blocked units from 11 turnaround units.

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 |
JobFirst runCompletionResponseTurnaroundWaiting
A08080
B8108108
C10119109
D11139119
mean——6.509.756.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 solutionExpand

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 nn non-preemptive jobs all arrive at time zero, service times are known exactly, and the objective is mean waiting time. Consider adjacent jobs ii then jj after prefix duration TT with bi>bjb_i>b_j Their contribution to total waiting is

T+(T+bi)=2T+bi.T+(T+b_i)=2T+b_i.

Swapping them contributes

T+(T+bj)=2T+bj,T+(T+b_j)=2T+b_j,

which is smaller by bi−bj>0b_i-b_j>0 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 (13+2+2+3)/4=5.00(13+2+2+3)/4=5.00 The improvement is large because exact service times were supplied by the exercise.

Proof boundary — construct starvation

Suppose a long job LL with service 100 is ready. Can an arrival stream of short jobs (service 1) starve LL indefinitely? Distinguish non-preemptive SJF from preemptive SRTF:

  1. Non-preemptive SJF with LL alone at time 0: If LL is the sole ready job at t=0t=0 non-preemptive SJF immediately dispatches LL Because the policy is non-preemptive, subsequent arrivals cannot displace LL it runs uninterrupted from t=0t=0 to t=100t=100 Starvation does not occur.
  2. True starvation under non-preemptive SJF: Requires that at t=0t=0 another job S0S_0 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 LL is never selected.
  3. Starvation under preemptive SRTF: If short jobs arrive with remaining service <remaining(L)< \text{remaining}(L) LL is repeatedly preempted or delayed, suffering unbounded waiting.
Worked solutionExpand

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 S0S_0 is dispatched, and before each SkS_k completes, Sk+1S_{k+1} 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 LL

The simultaneous-arrival batch theorem bi≤bjb_i \le b_j does not prevent starvation because its foundational assumption—a finite, closed batch arriving simultaneously at t=0t=0—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 (10+10)/2=10(10+10)/2=10
  • 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 solutionExpand

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 qq A job that blocks or finishes early gives up the CPU; an unfinished job returns to the tail. With mm continuously runnable jobs, zero switch cost, and no higher-priority interference, a job waits at most roughly (m−1)q(m-1)q between its quanta. That is a model bound, not a production latency guarantee.

For the motivating workload with q=2q=2 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 ss the saturated upper-bound overhead fraction is

sq+s.\frac{s}{q+s}.

As q→∞q\rightarrow\infty round robin approaches FCFS for finite jobs. As q→0q\rightarrow0 response opportunities become frequent while switching consumes the machine. A quantum is therefore a workload-timescale decision.

Round-Robin trade-off: context-switch overhead $\delta/q$ (decaying as $O(1/q)$) vs. interactive queue response latency (increasing linearly with quantum size $q$). Scheduling quantum trade-off showing context switch overhead percentage decaying inversely with quantum size while interactive latency scales linearly. q = 10 ms 2.0% 5.0 ms
Figure 2.3.1: Round-Robin trade-off: context-switch overhead δ/q\delta/q (decaying as O(1/q)O(1/q)) vs. interactive queue response latency (increasing linearly with quantum size qq).

Prediction before interaction

For the convoy workload, predict the direction—not exact magnitude—of these changes:

  1. FCFS → RR with zero switch cost: mean response and mean turnaround;
  2. RR quantum 8 → quantum 1 with switch cost 2: response opportunity and useful utilization;
  3. convoy → staggered workload: idle time.
Interactive exploration

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.

RR · mean response 2.0 · 100% useful CPU
Quantum = 2
Context-switch cost = 0
A0B2C4D5A7A9A1113CPU timeline · amber = context switch
JobArrivalBurstResponseWaitingTurnaround
A080513
B02224
C11334
D22335

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.

Schedule the same jobs under competing policies
A0B2C4D5A7A9A1113CPU timeline · amber = context switch
JobArrivalBurstResponseWaitingTurnaround
A080513
B02224
C11334
D22335

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.

HintExpand

Increase switch cost enough that extra boundaries become visible.

Worked solutionExpand

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

b^k+1=αbk+(1−α)b^k,0≤α≤1.\hat b_{k+1}=\alpha b_k+(1-\alpha)\hat b_k, \qquad 0\le\alpha\le1.

Large α\alpha reacts quickly and forgets history; small α\alpha 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 α=0.1\alpha=0.1 and α=0.9\alpha=0.9 at each phase boundary. Which is “better”?

Worked solutionExpand

α=0.9\alpha=0.9 moves the estimate near the new phase within a few samples but follows individual noise; α=0.1\alpha=0.1 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 wiw_i a proportional-share target over a long interval is

share⁡i≈wi∑jwj.\operatorname{share}_i \approx \frac{w_i}{\sum_j w_j}.

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 solutionExpand

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.

Section Exercises

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

Descriptionapplication

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.

HintExpand

Contrast the FCFS schedule with an interleaved round-robin or shortest-job-first order.

Worked solutionExpand

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 80+82+⋯+9811≈80.9 ms\frac{80 + 82 + \dots + 98}{11} \approx 80.9\text{ ms} 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

Proofapplication

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.

HintExpand

Construct an adversarial workload where new short jobs arrive faster than they can be cleared.

Worked solutionExpand

Suppose a long job JlongJ_{\mathrm{long}} with burst length T=100T = 100 arrives at time 0. At every time interval t=5kt = 5k (for k=0,1,2,…k = 0, 1, 2, \dots a new short job JkJ_k with burst length 4 arrives. Because 4<1004 < 100 (and 4<remaining(Jlong)4 < \text{remaining}(J_{\mathrm{long}}) the SJF/SRTF dispatch rule perpetually prioritizes the newly arrived short job JkJ_k over JlongJ_{\mathrm{long}} Thus, JlongJ_{\mathrm{long}} is never scheduled and starves indefinitely. An aging mechanism dynamically decrements the effective burst estimate or increments an effective priority by α⋅waiting_time\alpha \cdot \text{waiting\_time} guaranteeing that JlongJ_{\mathrm{long}}‘s priority eventually dominates every fresh arrival.

Exercise 2.3.3: Round-Robin Quantum Sizing and Switch Overhead Trade-off

Verificationtransfer

In a Round-Robin scheduler with context switch cost δ=0.2 ms\delta = 0.2\text{ ms} evaluate the fractional CPU overhead δq+δ\frac{\delta}{q + \delta} and maximum interactive response latency (m−1)(q+δ)(m - 1)(q + \delta) across m=10m = 10 runnable tasks for quantum lengths q=1 msq = 1\text{ ms} q=10 msq = 10\text{ ms} and q=100 msq = 100\text{ ms}

HintExpand

Apply the saturation overhead formula and queue cycle bounds.

Worked solutionExpand
  1. q=1 msq = 1\text{ ms}
    • Overhead: 0.21.0+0.2=0.21.2≈16.67%\frac{0.2}{1.0 + 0.2} = \frac{0.2}{1.2} \approx 16.67\%
    • Max latency between quanta: (10−1)(1.0+0.2)=9×1.2=10.8 ms(10 - 1)(1.0 + 0.2) = 9 \times 1.2 = 10.8\text{ ms}
  2. q=10 msq = 10\text{ ms}
    • Overhead: 0.210.0+0.2=0.210.2≈1.96%\frac{0.2}{10.0 + 0.2} = \frac{0.2}{10.2} \approx 1.96\%
    • Max latency between quanta: 9×10.2=91.8 ms9 \times 10.2 = 91.8\text{ ms}
  3. q=100 msq = 100\text{ ms}
    • Overhead: 0.2100.0+0.2=0.2100.2≈0.20%\frac{0.2}{100.0 + 0.2} = \frac{0.2}{100.2} \approx 0.20\%
    • Max latency between quanta: 9×100.2=901.8 ms9 \times 100.2 = 901.8\text{ ms} Small quanta guarantee snappy interactive response 10.8 ms10.8\text{ ms} but waste 16.7%16.7\% of CPU cycles in switching overhead; large quanta minimize overhead 0.2%0.2\% but degrade interactive responsiveness toward FCFS.

Exercise 2.3.4: Exponential Moving Average CPU Burst Estimation

Verificationtransfer

A process exhibits measured CPU bursts t1=12t_1 = 12 t2=4t_2 = 4 t3=6t_3 = 6 t4=8t_4 = 8 Using an exponential moving average τn+1=αtn+(1−α)τn\tau_{n+1} = \alpha t_n + (1 - \alpha)\tau_n with weighting factor α=0.5\alpha = 0.5 and initial guess τ1=10\tau_1 = 10 compute the predicted bursts τ2,τ3,τ4,τ5\tau_2, \tau_3, \tau_4, \tau_5

HintExpand

Apply the recursive formula step by step.

Worked solutionExpand
  1. τ2=0.5⋅t1+0.5⋅τ1=0.5(12)+0.5(10)=6+5=11.0\tau_2 = 0.5 \cdot t_1 + 0.5 \cdot \tau_1 = 0.5(12) + 0.5(10) = 6 + 5 = 11.0
  2. τ3=0.5⋅t2+0.5⋅τ2=0.5(4)+0.5(11.0)=2+5.5=7.5\tau_3 = 0.5 \cdot t_2 + 0.5 \cdot \tau_2 = 0.5(4) + 0.5(11.0) = 2 + 5.5 = 7.5
  3. τ4=0.5⋅t3+0.5⋅τ3=0.5(6)+0.5(7.5)=3+3.75=6.75\tau_4 = 0.5 \cdot t_3 + 0.5 \cdot \tau_3 = 0.5(6) + 0.5(7.5) = 3 + 3.75 = 6.75
  4. τ5=0.5⋅t4+0.5⋅τ4=0.5(8)+0.5(6.75)=4+3.375=7.375\tau_5 = 0.5 \cdot t_4 + 0.5 \cdot \tau_4 = 0.5(8) + 0.5(6.75) = 4 + 3.375 = 7.375 The estimator dampens transient spikes while gradually tracking shifts in process behavior.

Exercise 2.3.5: Virtual Runtime, Lag, and Eligibility in EEVDF Scheduling

Descriptionsynthesis

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.

HintExpand

Contrast the eligibility check (lag >= 0) with the selection criterion (earliest virtual deadline).

Worked solutionExpand

In EEVDF, each entity has a weight wiw_i Fluid fair-share time advances at rate wi/∑wjw_i / \sum w_j 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: lagi=V−vi\mathrm{lag}_i = V - v_i An entity is defined as eligible if and only if lagi≥0\mathrm{lag}_i \ge 0 (it has not received more than its fair share). Among eligible tasks, EEVDF selects the task with the earliest virtual deadline di=vi+qi/wid_i = v_i + q_i / w_i where qiq_i is the task’s requested slice. An interactive task requests a small slice qiq_i 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

Constructionsynthesis

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.

HintExpand

Combine fixed-priority real-time scheduling with rate-monotonic analysis and round-robin background queues.

Worked solutionExpand
  1. Queue hierarchy:
    • Priority 1 (Highest, Real-Time FIFO): Control loop CC Admitted only after rate-monotonic feasibility check: UC=0.5/10=5%≤69.3%U_C = 0.5 / 10 = 5\% \le 69.3\% Preempts all lower queues immediately upon timer release.
    • Priority 2 (Interactive Round-Robin): Console daemon II Allocated a small quantum q=2 msq = 2\text{ ms} for low response latency.
    • Priority 3 (Lowest, Batch Background): Compression worker BB Runs with a large quantum q=20 msq = 20\text{ ms} to maximize L1/L2 cache locality and reduce switch overhead.
  2. Overload protection: If CC overruns its 0.5 ms budget (detected via hardware watchdog or CPU timer), it is quarantined and an alarm logged. If II floods the system, Priority 2 is throttled to at most 20%20\% CPU time, preserving residual bandwidth for BB

References & Further Reading

  1. The Open Group, POSIX.1-2024 General Information §2.8.4: Process Scheduling, FIFO/RR conceptual semantics.
  2. Linux kernel documentation, EEVDF Scheduler and CFS Scheduler, for current production virtual-time context.
  3. MIT PDOS, xv6 rev5 kernel/proc.c and kernel/trap.c, for the teaching scheduler and timer-yield mechanism.
  4. MIT PDOS, xv6: a simple, Unix-like teaching operating system, Chapter 7.