Search Knowledge

© 2026 LIBREUNI PROJECT

Operating Systems Engineering/Protection, isolation, and synthesis
Page 28 of 29

Operating Systems Capstone

An evidence-backed operating-system change with explicit invariants, adversarial tests, reproducible measurement, failure analysis, and an independently usable handoff.

Lab briefProtection, isolation, and synthesis · 19 h · 4 outcomes

Required knowledge

  • System-call boundaries, scheduling, synchronization, virtual memory, device I/O, filesystems, protection, and multicore observability
  • C systems programming, Git, Make, GDB, QEMU, and official xv6-riscv-rev5 course root 7d7adbb1b0acbd67c9766a20d0f9900fef2789fa
  • Ability to distinguish a mechanism model, a test observation, and a measured performance result

Learning outcomes

  • Bound an operating-system change by contract, failure model, invariants, workload, and explicit exclusions before implementation.
  • Implement one substantial kernel mechanism while preserving the approved start-point contract and killing named incorrect designs with adversarial tests.
  • Evaluate the change against a pinned baseline using reproducible trials, raw evidence, uncertainty, and threats to validity.
  • Defend engineering judgment against adversarial edge cases, then deliver a handoff another engineer can build, test, inspect, and extend.

Assessment target

An explicit engineering proposal, bounded kernel change, invariant-driven public tests, disclosed hidden-test categories, reproducible baseline comparison, design memo, and maintainable handoff; automated checks are evidence rather than proof of mastery.

Scope boundary

  • A production kernel, formal verification, novel systems research, real-time certification, and universal performance claims are outside the required scope.
  • The course publishes project contracts, evidence requirements, diagnostic examples, and verification checklists—not complete capstone patches or hidden-test inputs.

A patch passes the upstream tests and reports “18% faster.” The claim still fails review. The author changed the benchmark while changing the scheduler, retained only five favorable runs, did not record the baseline commit, and never tested a blocking workload. Under memory pressure, one error path leaves a process runnable on two queues. The benchmark result is neither reproducible nor relevant to the broken invariant.

The capstone is a bounded engineering argument:

Under a stated workload and failure model, this mechanism preserves these invariants and changes this observable relative to this pinned baseline; these tests and measurements support the claim, subject to these limitations.

Every noun in that sentence must resolve to an artifact. A build log is not a correctness argument. A passing test is not proof that no bug exists. A simulation is not a measurement. A fast median does not excuse corruption, deadlock, authority expansion, or an unexplained tail.

The project contract

Select exactly one option from the bounded set below. A project may extend an earlier checkpoint only when it introduces a new mechanism, invariant, adversarial failure, and evaluation question. Repackaging a lab patch with more prose does not satisfy the contract.

All work descends from official xv6 RISC-V tag xv6-riscv-rev5, commit 7d7adbb1b0acbd67c9766a20d0f9900fef2789fa. Use either a clean rev5 tree or the course’s ordered cumulative checkpoint patch stack rooted at rev5. Record the chosen start point and keep the capstone treatment separable from every earlier patch. The project must remain small enough that one engineer can explain and trace every changed control path.

Definitions that make the claim testable

termoperational meaning
course rootofficial xv6-riscv-rev5 commit 7d7adbb1b0acbd67c9766a20d0f9900fef2789fa; every allowed project history descends from this object
start pointeither the clean course root or a reproducible, ordered cumulative checkpoint stack applied to that root
baselinethe immutable chosen start point plus configuration, toolchain, emulator or hardware target, and command sequence against which the capstone treatment is compared
treatmentthe baseline plus only the isolated capstone change; earlier checkpoints, upgrades, and unrelated refactors are not treatment
contractexternally visible allowed behavior, error behavior, and explicitly unsupported behavior
invarianta property required after every relevant transition, not merely at function return
failure modelthe faults, interleavings, resource limits, crashes, and adversarial inputs the design claims to handle
oraclea rule that maps an observation to pass, fail, or inconclusive without consulting the implementation’s intended answer
workloadoperations, input distribution, concurrency, machine state, duration, and units that generate an observation
trialone independently identified execution with recorded configuration, seed, order, and raw result
claima falsifiable relation among mechanism, workload, observable, and baseline
threata plausible reason the evidence could support the claim even though the claim is false, or reject it even though it is true

Assume failures can occur at any documented injection point, CPUs can interleave at every synchronization boundary, allocations can fail where the kernel permits failure, and user inputs can take every contract-valid boundary value. Do not assume sequential consistency for unsynchronized shared memory, a particular disk write order without an enforced persistence mechanism, or FIFO device completion unless the device contract provides it.

Retrieval checkpoint: what is missing?

The statement “the new lock-free table is correct because it completed one million lookups without crashing” contains an observation. Name four missing parts of an engineering claim.

Reveal the diagnosisExpand

At minimum it lacks:

  1. a contract defining which lookup results are legal under concurrent insert or delete;
  2. invariants covering publication, object lifetime, and reclamation;
  3. a pinned baseline and treatment boundary;
  4. a workload and failure model, including CPU count and interleavings;
  5. an independent result oracle; and
  6. adversarial evidence capable of exposing stale references or forbidden results.

Completion without a crash demonstrates only that one execution reached its end. It cannot establish linearizability, memory safety, progress, or superiority to a baseline.

Capstone evaluation rigor and treatment boundaries

0 / 4 answered

Evaluate each statement regarding experimental controls, treatment isolation, and invariant testing in the capstone project:

Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.

1
Achieving a faster median throughput in a microbenchmark compensates for unhandled race conditions on kernel exit paths.
2
The treatment diff must contain solely the isolated mechanism change applied directly on top of the pinned baseline.
3
A rigorous evaluation requires adversarial stress tests capable of failing if core invariants are deliberately violated.
4
Importing unrelated bug fixes from modern branches into the treatment branch does not confound paired causal comparisons.

Choose one bounded option

The hard exclusions are part of each option. A proposal that silently absorbs an excluded production feature is too broad.

optionrequired mechanism and contractmandatory adversarial evidencehard exclusions
A — scheduler policy and accountingadd one policy or one bounded accounting mechanism; define runnable-state ownership, queue membership, wakeup, migration, and idle behaviorCPU-bound plus sleeping tasks, multicore migration, repeated wakeups, starvation probe, and accounting conservationhard real-time guarantees, energy policy, full priority inheritance, and claims about every workload
B — virtual-memory state transitionimplement either copy-on-write fork or a bounded anonymous/file-backed mapping subset; define PTE permissions, frame reference counts, fault outcomes, and teardownparent/child writes, fork trees, memory exhaustion, concurrent exit, invalid addresses, and stale-translation probecomplete POSIX mmap, swapping, NUMA placement, huge pages, and production-grade overcommit
C — interrupt-driven device queueimplement a bounded queue for one emulated device or teaching device; define descriptor ownership, publication, completion, retry, and shutdownwraparound, full and empty queues, duplicate/spurious completion, delayed interrupt, malformed length, and injected allocation failureuniversal driver framework, real-device certification, DMA isolation proof, and unmodeled hardware claims
D — recoverable filesystem mutationadd one persistent operation distinct from the rename lab, such as atomic temporary-file publication or a bounded durability call; define namespace and recovery semanticstransaction exhaustion, allocation failure, every named crash cut, recovery idempotence, and concurrent conflicting operationsfull POSIX durability, directory trees, cross-filesystem operations, ACLs, and storage-device firmware guarantees
E — multicore kernel-state redesignshard or redesign one contended kernel table while preserving its lookup/update contract; define lock order, object lifetime, and progressskewed keys, CPU-count sweep, create/delete races, exhaustion, hotplug exclusion, and contention tracinga general RCU library, universal scalability, lock-freedom claims without proof, and production NUMA tuning

Combining two options usually weakens the evidence. A queue plus a new scheduler creates two treatments and makes a causal result difficult to interpret. Focus on a single bounded mechanism to preserve clear causal attribution.

Scope budget: 1,140 minutes

phaseminutesexit evidence
specification, source audit, invariants, and threat model120falsifiable specification, invariant inventory, and threat model
pinned baseline and experimental harness180reproducible clean build, upstream tests, calibration data
mechanism implementation and design record360reviewable commits or patch series, transition traces, invariant assertions
adversarial, concurrency, and fault tests240test suite, wrong-implementation kill matrix, minimized failures
evaluation and threats-to-validity analysis120raw trials, analysis script, figures/tables, bounded interpretation
design memo, verification trace, and handoff120reproducible package verifiable from a fresh checkout
total1,14019 hours

The time box bounds scope, not rigor. If the chosen mechanism cannot be made safe within it, preserve the failing evidence, reduce the contract, and document the residual gap. Do not hide an unsafe path to make the project appear complete.

Specification and verification gate

Implementation begins only after establishing a precise specification. Verify that the specification defines explicit invariants, an observable baseline, and an adversary. A disposable feasibility probe is allowed when declared, but none of its code enters the treatment until the specification is verified and its provenance is clear.

Code
top to bottom direction
rectangle "specification\nclaim + contract + invariants" as P
rectangle "specification gate\ninvariants verified?" as G
rectangle "refine scope or evidence plan" as R
rectangle "pin and measure baseline" as B
rectangle "implement one mechanism" as I
rectangle "adversarial correctness gate" as C
rectangle "repair mechanism; retain failure" as F
rectangle "measure treatment" as M
rectangle "analyze threats and limits" as T
rectangle "synthesis analysis\nverification trace" as D
rectangle "reproducible handoff" as H
P --> G
G --> R : no / conditional gap
R --> P : refine specification
G --> B : verified
B --> I
I --> C
C --> F : invariant or oracle fails
F --> C : rerun all correctness tests
C --> M : passes stated contract
M --> T
T --> D
D --> H : invariants hold; trace verified
D --> F : unresolved mechanism defect
specificationclaim + contract + invariantsspecification gateinvariants verified?refine scope or evidence planpin and measure baselineimplement one mechanismadversarial correctness gaterepair mechanism; retain failuremeasure treatmentanalyze threats and limitssynthesis analysisverification tracereproducible handoffno / conditional gaprefine specificationverifiedinvariant or oracle failsrerun all correctnesstestspasses stated contractinvariants hold; traceverifiedunresolved mechanismdefect

The gate rejects proposals that promise “better performance,” “more security,” or “POSIX support” without an observable, adversary, and boundary.

Proposal packet

Keep the packet short enough to review but precise enough to falsify. It must contain:

  1. Claim. One sentence naming workload, treatment, baseline, preserved contract, observable, expected direction, mechanism, and limitation.
  2. Pinned object. Course-root tag/hash, clean or cumulative start mode, ordered checkpoint patch checksums, resulting start-point identity, license, configuration, compiler, emulator or hardware, host facts, and commands.
  3. Contract and exclusions. Inputs, outputs, error behavior, concurrency semantics, persistence point if relevant, and non-goals.
  4. State model. State variables, initial state, legal transitions, invariant after each transition, and ownership or authority.
  5. Failure model. Relevant crashes, races, exhaustion, malformed inputs, interrupt behavior, and explicitly unhandled faults.
  6. Mechanism sketch. A control-path diagram plus a lock/authority/resource-order table. No implementation listing is required.
  7. Evidence map. At least four named wrong implementations and a test or observation that should kill each one.
  8. Evaluation plan. Baseline, workloads, units, trial order, repetitions, raw-data format, analysis rule, and stop conditions.
  9. Threat preview. One plausible construct, internal, external, and conclusion-validity threat.
  10. Provenance plan. Primary sources, borrowed interfaces or code, licenses, collaborators, tools, and assistance-disclosure method.

Use this claim grammar when the scope drifts:

Under [workload W and failure model F], treatment [T] relative to pinned
baseline [B] preserves [contract/invariants C] and changes [observable M]
in [direction or bounded relation D] because [mechanism Z]. Evidence [E]
can reject the claim; the result does not cover [limitation L].

Worked trace 1: repair an unreviewable scheduler proposal

Initial proposal:

Make xv6 scheduling fairer and faster.

The terms “fairer” and “faster” have no units; the workload is absent; simultaneous improvement may be impossible; no invariant prevents a lost runnable process; and the claim could not be rejected by a specific result.

A bounded replacement:

Under a two-CPU QEMU workload containing three CPU-bound processes and one
process that sleeps for 10 ms after each 1 ms burst, weighted round-robin T
relative to rev5-rooted start point B preserves single-queue membership and eventual
dispatch for continuously runnable positive-weight processes. T is expected
to reduce the interactive process's p99 runnable-to-running delay, while
reporting aggregate completed bursts and CPU time as possible trade-offs.
Queue-transition assertions, deterministic wakeup tests, randomized stress,
and paired trials E can reject the claim. The result does not establish a
hard latency bound or superiority for other workload mixes.

The revised proposal names a fairness proxy instead of treating fairness as a mood. It permits throughput to fall and makes that trade-off visible rather than defining success as “every metric improved.”

Application checkpoint: gate two claims

Classify each claim as approve, revise, or reject, and give the smallest repair.

  1. “COW fork uses less memory than eager copying.” The plan pins a commit, measures resident frames after a 64-page fork tree, tests write faults and OOM, records raw trials, and excludes page cache effects. It does not define when a shared frame may be freed.
  2. “My driver works on all VirtIO devices.” The implementation targets xv6’s emulated block device, tests one QEMU version, and assumes completions arrive in descriptor order although the proposed contract does not guarantee that order.
Reveal the gate decisionsExpand
  1. Revise. The performance/memory observable is bounded, but correctness lacks a frame-lifetime invariant. Add: the frame reference count includes mapping references and temporary pins; at least one such reference remains while any valid or stale translation, copy, or in-flight fault can access the frame. The allocator may reclaim the frame only when the final reference is dropped after PTE removal and required TLB invalidation complete. Define atomicity/locking for those transitions and add a concurrent exit/write test that can expose premature reuse.
  2. Reject as written. Evidence from one emulated device cannot support “all VirtIO devices,” and the completion-order assumption can corrupt descriptor ownership. Repair the claim to the pinned QEMU device/configuration, identify the normative queue contract, key completions by descriptor identity rather than assumed order, and inject reordered completions if the model permits them.

Freeze a reproducible baseline

The baseline is experimental data, not a nostalgic description of upstream behavior.

Create REPRODUCE.md with values rather than placeholders:

course-root URL, tag, hash, and license:
start mode (`clean-rev5` or `cumulative-stack`):
ordered checkpoint patch IDs/checksums (`none` for clean mode):
baseline start-point commit or tree checksum:
treatment commit or patch checksum:
submodules/dependencies and checksums:
compiler, assembler, linker, and make versions:
QEMU or hardware model and version:
host OS, architecture, CPU allocation, and memory allocation:
kernel/build configuration:
build command:
upstream test command:
project correctness-test command:
measurement command:
trial seeds and randomized execution order:
raw-data path and schema:
analysis command and expected output checksums:
known nondeterminism and unsupported environments:

Baseline procedure

  1. Verify that tag xv6-riscv-rev5 resolves to the exact course-root hash; never substitute a moving branch.
  2. Choose clean mode or reconstruct the cumulative checkpoint stack in course order, recording every patch/checksum and conflict resolution.
  3. Record license and notices before importing or adapting any code.
  4. Build the clean course root, then build the chosen start point with the exact documented commands from fresh trees.
  5. Run the upstream suite on both; run every applicable checkpoint regression on a cumulative start point; preserve complete output plus exit status.
  6. Run the proposed harness against the unchanged start point. A harness that fails only because the capstone feature is absent must distinguish “unsupported” from “baseline defect.”
  7. Execute a no-change calibration: baseline A versus an independently rebuilt baseline A. Large apparent differences expose harness or host noise before they are mistaken for a treatment effect.
  8. Save the machine-readable environment, raw data, and checksums in the implementation package.

The clean mode isolates the capstone mechanism. The cumulative mode tests integration with accepted checkpoint work. Results from the two modes are not interchangeable: an earlier scheduler, VM, driver, or filesystem patch can change both correctness paths and performance. If the capstone applies only to one mode, state that boundary rather than merging results.

Integration incompatibilities

Any cumulative patch conflict, changed syscall number, altered disk format, different lock order, expanded log bound, test-hook collision, or failed checkpoint regression is an incompatibility requiring a recorded resolution and reviewer review. Preserve the conflicting patch and explain which invariant or measurement it affects. Do not replace a cumulative file with its clean rev5 version or fold earlier changes into the capstone diff.

Rev5 does not already implement most option mechanisms: it has no COW fork, production mapping interface, general device framework, or scalable shared-table abstraction. Those absences define implementation work, not permission to import a later branch. A later upstream fix may be evaluated only as a separately labeled sensitivity comparison.

A container image can help but is not sufficient by itself. Record its source definition and immutable digest; otherwise the opaque image merely packages the missing provenance.

Transfer checkpoint: the baseline moved

Upstream fixes a wakeup bug after proposal approval. The fix seems relevant to the scheduler project. Should the treatment silently rebase?

Reveal the controlled responseExpand

No. Preserve the rev5-rooted approved baseline so the course comparison remains interpretable. If the fix matters, create a separate sensitivity branch, document the source delta, and rerun both its no-capstone and capstone variants as a new labeled pair. It cannot replace the course root or be mixed with rev5 measurements: source change and proposed mechanism would be confounded.

Derive the mechanism from invariants

Do not organize the design memo around files changed. Organize it around state and transitions.

For every mutable object, provide a table with this shape:

state or resourceowner / protecting mechanismlegal writersinvariant after publicationreclamation or persistence rule
example: run-queue nodeone queue lockenqueue, dequeue, migrationrunnable process appears in exactly one queueremove under source lock before reuse

Then trace each operation through five questions:

  1. What state is read before validation?
  2. Which transition establishes ownership?
  3. At what point can another CPU, interrupt, process, or recovery pass observe it?
  4. Which failure can occur after each visible transition?
  5. What restores or completes the invariant on every exit path?

Assertions should encode cheap local consequences of invariants. They supplement adversarial tests; an assertion that repeats the same mistaken model as the implementation is not an independent oracle.

Worked trace 2: copy-on-write frame lifetime

Assume parent P maps virtual page v to frame F, and fork creates child C. Both PTEs become read-only COW mappings. The reference count is protected by ref_lock.

Initial post-fork state:

objectstate
P[v]F, valid, user, read-only, COW
C[v]F, valid, user, read-only, COW
ref[F]2 mapping references, no temporary pin

P writes v while C exits on another CPU:

stepCPU 0: parent faultCPU 1: child exitrequired invariant
1under page-table/ref synchronization, revalidate P[v] = F and acquire a temporary pin; ref[F]: 2 → 3read C[v] = Fmapping references plus temporary pins keep every accessible frame non-allocatable
2allocate private frame G with one fault-owned temporary reference, ref[G]=1clear C[v]; complete the required child TLB invalidation; drop C’s mapping reference, ref[F]: 3 → 2P’s mapping reference and the fault pin still protect F; G cannot return to the allocator during the copy
3copy bytes F → G while holding the temporary pinfinish child teardownan in-flight copy owns a counted reference even if another mapping disappears
4under page-table/ref synchronization, replace P[v] with writable G, convert G’s temporary reference into its mapping reference (ref[G] remains 1), and drop P’s old mapping reference; ref[F]: 2 → 1—the F pin substitutes for the removed mapping while a stale P translation may remain; G has exactly one published owner
5complete P’s local invalidation and any required remote shootdown; then drop the temporary pin, ref[F]: 1 → 0, and return F to the allocator—transition to zero occurs only after no PTE, stale translation, or in-flight copy can access F

A wrong implementation omits the temporary pin and drops P’s mapping reference before copying. Child exit can then reduce ref[F] to zero, the allocator fills F with another page, and the parent copies unrelated bytes into G. A second wrong implementation takes the pin but drops it immediately after PTE replacement, before P’s stale TLB entry is invalidated; a stale write can then target allocator-owned F. Killing tests pause at each boundary, force reuse with a known poison page, and check both copied bytes and post-shootdown allocator ownership. A loop that merely forks and exits may never schedule either dangerous interleaving.

This trace does not prove a complete COW implementation. It requires the selected rev5-rooted design to define whether invalidation is local or requires remote shootdown, how fault retry and page-table locks interact, and how a temporary pin is represented without holding a global reference lock across the copy.

Build evidence that can kill the design

Correctness testing precedes performance measurement. If an invariant fails, treatment timing is a measurement of a different or invalid contract.

Public test contract

Publish tests and oracles for all of these applicable categories:

categoryminimum evidence
upstream regressionunchanged upstream suite, complete output, and exit status
happy pathone smallest valid operation with exact post-state
boundaryzero, one, maximum supported value, wraparound, and just-over-limit behavior
invalid inputmalformed identifiers, addresses, lengths, states, or permissions rejected without partial effect
exhaustionallocator, queue, log, descriptor, or process limit reached at each fallible stage
concurrencybarriers or hooks force a named interleaving; stress is additional evidence, not the only method
failure injectionevery documented injection point maps to an allowed recovered state or explicit unsupported outcome
observabilitycounters conserve events and do not alter the contract they measure
repeatabilityfixed seeds reproduce each deterministic failure; randomized seeds are recorded on failure

Tests must inspect externally visible state or independently reconstructed invariants. Do not call a private helper solely to ask whether that helper believes its own update succeeded.

Wrong-implementation kill matrix

Name at least four plausible defects specific to the chosen mechanism. The generic examples below are prompts, not a substitute for project-specific analysis.

defect IDwrong designobservation that can kill it
W1publishes an object before all fields are initializedreader barrier at publication; validate every field and authority bit
W2assumes FIFO completion or wakeupreorder two distinguishable operations and check identity-based completion
W3drops a lifetime reference before the last copy, stale translation, or shootdown completespause at the release boundary, force reclamation, and detect poison/reuse or stale access
W4updates two persistent locations outside one recovery unitcrash at each write boundary; accept only enumerated recovered states
W5retries after partial effect without idempotenceinject duplicate completion or recovery replay; count effect exactly once
W6improves a counter by omitting expensive workcompare end-state and independent conserved-event totals, not the reported counter alone
W7acquires two resources in caller-dependent orderrun opposite operations behind a barrier; detect cycle with bounded timeout and trace
W8treats allocation failure as impossiblefail the nth allocation at every site; compare pre/post ownership and leak counts

For each row selected, record the test identifier, forced schedule or fault, oracle, result on the wrong implementation, result on the treatment, and residual blind spot. A test that passes both versions does not kill that defect.

Hidden tests and human review

An adversarial test suite may withhold exact inputs so an implementation cannot specialize to a finite public test suite. The categories are explicit:

  • contract boundaries and just-over-limit values;
  • resource exhaustion and cleanup;
  • forced races and alternate CPU counts;
  • crash or interrupt cuts at declared publication points;
  • malformed user-controlled state;
  • repeated operation, replay, and teardown;
  • independent invariant reconstruction.

Hidden tests contribute evidence; they do not create secret requirements. A failure outside the published contract triggers clarification, not retroactive scope. A pass does not establish absence of bugs or authorship.

Human review examines the state model, control paths, lock/authority order, error cleanup, source provenance, meaningful test oracles, interpretation of results, and whether the author can derive an unfamiliar trace. The site and harness must not claim to automate that judgment.

Diagnostic checkpoint: a test that rewards the bug

A scheduler test passes when a new dispatches counter is at least 20% lower. The treatment increments the counter only on CPU 0, so it passes on two CPUs. Repair the oracle.

Reveal the independent oracleExpand

First define the intended claim. If the goal is fewer context switches for the same completed work, independently count dispatch events from a trace point common to baseline and treatment, and verify conservation per CPU. Hold workload completion constant, record CPU count, and compare trace-derived dispatches per completed operation. Also assert that every actual transition to running has exactly one event and that the sum of per-CPU events equals the global total. A treatment-owned counter can remain an observability output, but it cannot be its own sole oracle.

Measure after correctness gates pass

Performance evidence must identify what changed, where the expected event reduction occurs, and which cost may have moved elsewhere.

Prediction before measurement

Write a causal prediction before collecting treatment results:

mechanism change
  -> event expected to decrease/increase
  -> counter or trace that observes that event
  -> end-to-end metric affected
  -> competing cost or trade-off
  -> result that would reject the mechanism explanation

Examples of rejecting evidence include unchanged lock wait despite a claimed lock redesign, lower reported allocations with unchanged allocator traces, or throughput improvement that disappears in no-change calibration.

Trial protocol

  • Preserve every valid trial, including slow and failed runs. Mark invalid trials by a rule written before seeing treatment results.
  • Randomize or counterbalance baseline/treatment order so thermal drift and host load do not always favor one side.
  • Use identical workload generation, build mode, CPU/memory allocation, cache-state policy, and measurement interval.
  • Separate warmup from measured intervals and justify both.
  • Report the raw distribution, not only a mean. Include units, trial count, central tendency, dispersion or interval, and tail metric when latency matters.
  • Use paired comparisons when each treatment run has a matching baseline run under the same block/seed.
  • Repeat across the independent variable the claim names, such as CPU count or queue depth. One favorable point cannot support a scaling claim.
  • Record observation overhead. Tracing can serialize or perturb the path it measures.

Illustrative result trace: throughput rises, tail latency fails

The numbers below are a modeled review example, not measurements from xv6 or any real scheduler. Each row pairs equal workload seeds; throughput is completed bursts per second.

pairbaseline throughputtreatment throughputbaseline p99 delay (ms)treatment p99 delay (ms)
11011184.110.9
2991174.311.4
31001204.211.8
41021194.012.1
598454.597.0
61001184.211.6
71001194.111.9

The median throughput changes from 100 to 118 bursts/s, an 18% increase in this modeled sample. That does not justify “the scheduler is 18% faster”:

  • every treatment p99 delay is worse;
  • pair 5 is a severe collapse and cannot be discarded merely because it is inconvenient;
  • seven pairs provide weak information about rare stalls;
  • a burst/s result does not establish CPU efficiency, fairness, or behavior under another mix.

The next action is causal diagnosis of pair 5 using preserved seed, runnable-queue trace, lock wait, and host metadata—not editing the chart. A defensible claim might eventually be “higher median throughput for this fixed CPU-bound-heavy workload, with substantially worse interactive tail latency,” if repeated evidence supports it. The proposal’s latency goal would still be rejected.

Application checkpoint: separate model, observation, and claim

Classify each statement.

  1. “Splitting one lock into four shards permits at most four independent critical sections in the simplified lock model.”
  2. “Across 30 recorded trials at eight virtual CPUs, the treatment median was 1.31 times the baseline median.”
  3. “Sharding makes the kernel scalable.”
Reveal the classificationsExpand
  1. Model result. It follows from a simplified structural model and omits key skew, cache, and remaining-lock costs.
  2. Measurement statement, provided the raw trials, units, pairing, and configurations are available. It reports the sample without generalizing beyond it.
  3. Unsupported broad claim. “Scalable” needs an independent variable, range, workload, metric, correctness contract, and comparison. Repair it by naming the tested CPU range and key distribution, reporting the observed curve, and limiting the conclusion to that configuration.

Analyze threats to validity

Do not append a ceremonial “more testing is needed.” Connect each threat to a claim and mitigation.

threat classcapstone questionexamplemitigation or bounded interpretation
constructdoes the observable represent the concept named?dispatch count is called fairnessreport wait distribution or defined fairness index; narrow the claim
internalcould another difference cause the result?treatment uses a different compiler or benchmark seedfreeze treatment boundary; pair/randomize trials; no-change calibration
externalwhere may the result fail to transfer?one QEMU model stands for physical multicore hardwarestate emulation boundary; test an approved second setting or restrict conclusion
conclusionis the sample/analysis strong enough for the relation?median reported from three unstable runspreserve raw data, increase independent trials, report uncertainty and instability

Also audit instrumentation validity: event loss, counter overflow, timestamp source, tracing perturbation, sampling period, CPU migration, and whether the observer shares the lock it is diagnosing.

Counterexample: a clean graph with no valid comparison

Suppose the treatment benchmark is run after the filesystem cache is warmed, while the baseline begins after a fresh image boot. Thirty perfectly formatted repetitions can yield narrow intervals around a confounded difference. Repetition reduces random uncertainty; it does not remove systematic bias. The correct response is to repair the protocol and rerun both sides, not to attach a more sophisticated statistical test.

Transfer checkpoint: negative result

The mechanism preserves all tested invariants, but paired trials show no meaningful throughput change and lock traces show that contention moved to the allocator. Is the project a failure?

Reveal the engineering valueExpand

The performance hypothesis is rejected, but the project can still be rigorous. Preserve the result; show that the intended lock wait fell while allocator wait rose; bound the workloads and instrumentation; explain the causal bottleneck migration; and avoid claiming improvement. Correct mechanism work plus a reproducible negative evaluation and credible diagnosis can score strongly. Fabricating a win or silently changing the metric cannot.

Design memo

Structure a concise memo whose structure follows the argument rather than the chronology of coding:

  1. Claim and scope: approved claim, option, contract, exclusions, and reviewer conditions.
  2. Baseline and provenance: immutable source/configuration, license, dependencies, assistance, and treatment boundary.
  3. State and invariants: state variables, legal transitions, ownership, authority, lifetime, persistence, and error states.
  4. Mechanism: control path, synchronization or transaction order, resource bounds, and alternatives rejected.
  5. Failure analysis: one concrete race/crash/exhaustion trace, cleanup path, and residual unsupported fault.
  6. Tests: independent oracles, public categories, wrong-implementation kill matrix, hidden-category expectations, and coverage limits.
  7. Evaluation: pre-registered prediction, workloads, raw-data schema, analysis, observed distributions, and modeled-versus-measured labels.
  8. Threats and interpretation: construct/internal/external/conclusion threats, mitigations, negative evidence, and bounded conclusion.
  9. Handoff: build/test/measurement commands, patch organization, known issues, and safe extension points.

Include diagrams or state tables where they replace ambiguous prose. A screenshot of passing output without the command, exit status, and artifact identity is not useful evidence.

Verification trace and changed assumptions

The verification demonstration is a controlled falsification attempt, not a feature tour. In your verification demonstration:

  1. identify the exact baseline and treatment;
  2. state the contract and one non-goal;
  3. draw or trace the hardest state transition;
  4. run one ordinary case and one adversarial case;
  5. inject one fault or forced interleaving and explain the oracle before revealing the result;
  6. show raw baseline/treatment evidence and one threat that limits interpretation;
  7. reproduce from a fresh checkout or clean build state.

To audit robustness, evaluate system behavior under an altered assumption: CPU count, queue order, allocation outcome, crash cut, authority, or workload skew. Reason from invariants rather than recall a memorized execution sequence.

Representative analysis prompt:

Your queue test assumes the interrupt cannot arrive between publishing the descriptor and recording the request as in flight. Move the interrupt to that boundary. Which state can the handler observe, which invariant applies, and what code or contract change is required?

A strong answer enumerates the concrete states, identifies the publication edge and synchronization, predicts the observable failure, and either derives why the state is safe or acknowledges a defect and proposes a discriminating test. Confidence without a trace is invalid.

Reproducible handoff

The final archive or repository state must contain:

README.md                 project purpose, contract, exclusions
REPRODUCE.md              pinned environment and exact commands
DESIGN.md or report.pdf   design memo and diagrams
PATCHES/ or named commits reviewable treatment boundary
tests/                    public tests, fixtures, fault hooks, oracles
results/raw/              immutable machine-readable trial outputs
results/analysis/         scripts/notebook plus generated tables
results/manifest.json     checksums, seeds, configurations, status
LICENSES/ or notices      upstream and imported-code obligations
KNOWN_ISSUES.md           residual defects, unsupported states, next probes
ASSISTANCE.md             people, tools, models, sources, and adapted material

Do not include generated binaries as the only way to reproduce a result. Do not require credentials, an undisclosed local path, or an environment-specific script. An independent engineer or automated runner should be able to determine within ten minutes how to build and start the public tests, even if a full measurement campaign takes longer.

The handoff must explain where a future engineer can safely add a state, where lock or transaction order is defined, and which tests must change with the contract. “Read the code” is not a maintenance boundary.

Handoff checkpoint: checksum mismatch

The analysis script produces the published table, but one raw file’s checksum differs from manifest.json. May the table remain in the final memo?

Reveal the dispositionExpand

Not as verified evidence. Determine whether the raw file, manifest, or table came from a different run; preserve all versions with provenance; regenerate the table only from a clearly identified immutable dataset; and update the manifest through the documented process. If provenance cannot be recovered, label the result unverifiable and exclude it from the supported claim. A visually identical table does not repair a broken evidence chain.

Provenance and assistance policy

Architectural mastery means being able to explain and verify every mechanism, test oracle, result, and source decision. It does not mean working without tools or feedback.

Sample ASSISTANCE.md disclosure record:

Tool / external sourcePurpose of consultationArtifact affectedWhat was accepted vs rejectedIndependent verification method
LLM code assistantDrafted initial Virtio descriptor chainkernel/virtio_disk.cKept descriptor struct; rejected unbarried ring writeVerified memory fence ordering against Virtio v1.2 spec §2.7
xv6 commit logClarified same-inode rename semanticskernel/sysfile.cAdopted no-op return with link count 2Wrote adversarial test asserting nlink unchanged

Allowed when disclosed:

  • reading and citing primary documentation and licensed source;
  • discussing mechanisms and experimental design without exchanging project patches;
  • using debuggers, tracers, static analysis, fuzzers, code completion, and generative systems;
  • adapting licensed code when the option permits it, attribution is explicit, and you can defend the adaptation;
  • receiving review comments and recording which changes they caused.

Not allowed:

  • incorporating unverified third-party patches, tests, memo, or results as original work;
  • asking for, reconstructing, probing, or special-casing hidden-test inputs;
  • fabricating, deleting, or relabeling trials to improve a conclusion;
  • concealing assistance, copied interfaces, incompatible licenses, or known failing states;
  • using generated text without verifying the underlying mechanism.

ASSISTANCE.md records source/tool, purpose, affected artifact, what was accepted or rejected, and how it was verified. A long undifferentiated tool transcript is not a provenance record. You should be able to rederive any assisted portion under a changed assumption.

Provenance requires falsifiable evidence. Token overlap, style, or an automated detector alone is not a finding. Conversely, passing automated checks cannot certify understanding.

Invariant and quality checklist

Verify evidence against objective engineering standards, not patch size or presentation polish alone.

dimensioninvariant criteriaverification evidence
baseline, scope, and provenanceimmutable baseline; licensed treatment boundary; bounded claim and exclusionsclean diff, verified git ancestry, explicit exclusions
contract, state model, and invariantsprecise transitions, ownership/lifetime/persistence rules, and error statesformal state machine, invariant table covering all transitions
mechanism correctnesscontrol paths preserve stated invariants across normal, boundary, and cleanup pathszero contract-breaking defects, clean failure logs
adversarial tests and oraclesdeterministic races/faults/exhaustion plus regression teststest suite and wrong-implementation kill matrix
design qualitysynchronization/transaction/authority order is justifiedlock/interrupt ordering graph, bounded resources
reproducible evaluationprediction, calibrated baseline, raw paired or randomized trials, units, uncertaintyautomated scripts, machine-readable trial outputs
failure analysis and validityminimized failure trace, negative evidence, four threat classesdocumented failure injected and minimized
handoff qualityfresh-build path, organized patch, tests/data/checksums, known issuessingle-command fresh checkout build and test
synthesis analysisconcise causal argument; adversarial verification; reasoning under changed assumptionstrace-backed analysis under altered parameters

The following are critical failure conditions that invalidate verification:

  • the chosen start point does not descend reproducibly from rev5, or the capstone treatment does not build as a separable change from it;
  • the start-point regression suite or contract fails without a documented scope change;
  • a test exposes corruption, authority escape, use-after-free, deadlock, or recovery violation within scope;
  • claimed measurements cannot be tied to raw data and configuration;
  • required license/provenance is missing;
  • the central implementation control path or oracle cannot be derived or explained;
  • the evidence contains fabricated data or unattributed work.

A correct but negative performance result is fully valid engineering evidence. A fast implementation that violates its contract cannot trade benchmark throughput for correctness.

Synthesis analysis

Analyze system behavior under this changed requirement:

The accepted design was evaluated on two CPUs with uniform keys. Deployment now uses eight CPUs and 90% of operations target one key. Which part of the claim survives, what new bottleneck or race becomes plausible, and what evidence would you gather before recommending deployment?

Reveal the evaluation standardExpand

A complete answer separates correctness from performance. Contract and invariants may survive if they are independent of CPU count and skew, but that must be traced through all shared state; uniform-key performance does not transfer. The hot key can collapse sharding onto one lock/cache line, increase queueing, expose lifetime races at higher concurrency, or move contention to allocation/reclamation. Gather an eight-CPU correctness stress run with forced create/delete interleavings, per-shard operation and wait distributions, cache/coherence indicators available in the environment, end-to-end latency/throughput across a skew sweep, no-change calibration, and raw paired trials. Recommend deployment only within the resulting evidence boundary.

The chosen change must connect at least three mechanism layers without expanding into three projects:

local mechanismconnection to trace explicitly
syscall or fault boundaryvalidation, privilege transition, user-visible error, and restart behavior
synchronizationpublication edge, lock/interrupt order, sleep/wakeup, lifetime, and progress
virtual memorytranslation, permission, frame ownership, TLB state, copy/pin behavior
device pathdescriptor ownership, interrupt ordering, DMA/model assumptions, and completion identity
persistencetransaction boundary, write ordering, crash cut, replay, and recovered invariant
protectionprincipal, authority conveyed by handle, confused-deputy risk, and revocation/lifetime
observabilityevent definition, collection overhead, conservation, and causal link to metric
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 7.6.1: Synthesizing Privilege, Memory, and File System Subsystems

Verificationapplication

A process executes mmap to map an 8 KiB file into its address space with PROT_READ | PROT_WRITE and MAP_SHARED. It then modifies the first byte of the second page (offset 4096) and calls msync(MS_SYNC). Trace how the operating system coordinates privilege transitions, virtual memory faults, the buffer cache/page cache, and disk write transactions to guarantee durability.

HintExpand

Trace: initial VMA creation (unmapped page table entry), first access triggering page fault, allocation of physical frame and disk block read, PTE update with dirty bit, user-mode write, and msync dirty-page flush through journal transaction.

Worked solutionExpand
  1. VMA registration: During mmap, the kernel validates arguments and allocates a Virtual Memory Area (VMA) recording range [addr, addr + 8192), permissions (PROT_READ | PROT_WRITE), flag MAP_SHARED, and backing file/inode reference. The page table entries (PTEs) remain invalid (demand paging).
  2. Page fault and cache lookup: Accessing offset 4096 triggers a hardware page fault trap (scause = 13 or 15). The kernel trap handler searches the process VMA list, discovers a valid shared mapping, and checks the page cache for file offset 4096.
  3. PTE population: If not in page cache, a frame is allocated and populated via device driver DMA. The kernel constructs a leaf PTE pointing to this frame with R=1, W=1, U=1, V=1 and installs it in the process page table, followed by sfence.vma.
  4. User-mode write: The faulting instruction restarts in user mode, successfully modifying byte 4096 in memory. The hardware or OS tracks the dirty state on the page.
  5. Durability via msync: When the application calls msync(..., MS_SYNC), the kernel traverses the VMA page table entries, identifies dirty pages, begins a file system log/journal transaction, copies the modified block into the buffer cache, issues barrier-ordered disk writes to persistent storage, and commits the transaction before returning to user space.

Exercise 7.6.2: Tracing Cross-Subsystem Invariant Races Between VM and VFS

Constructionapplication

Consider an asynchronous Direct I/O write (aio_write or io_uring) reading from a user memory buffer B and writing to disk, while another thread in the same process concurrently invokes munmap(B, len) or fork().

  1. Identify the race condition if the kernel merely validates the user virtual address B at submission time without pinning the underlying physical pages.
  2. Describe the synchronization mechanism used by modern kernels (get_user_pages / page pinning and refcounting) to maintain memory safety throughout the asynchronous I/O lifecycle.
HintExpand

Without page pinning, munmap can free physical frames back to the page allocator, allowing disk controllers to DMA stale or reassigned physical memory.

Worked solutionExpand
  1. The unpinned race condition: If the kernel validates virtual address B at submission and starts an asynchronous DMA transfer, but does not pin the physical frames:
    • Thread 2 executes munmap(B, len). The kernel tears down the PTEs and returns the physical frames to the global page allocator.
    • The allocator reassigns those frames to an unrelated sensitive process (e.g., storing cryptographic keys or kernel stacks).
    • The storage controller executes DMA from the reassigned physical frames into the target file on disk, leaking sensitive foreign memory to persistent storage.
  2. Resolution via page pinning (GUP):
    • At asynchronous I/O submission, the kernel calls get_user_pages(), which walks the page table, increments the reference count (struct page->_refcount) on each physical frame, and locks the pages against eviction.
    • Even if munmap destroys the user page table mappings, the physical frames cannot be reclaimed by the page allocator because their reference count remains greater than zero.
    • Once the storage controller signals DMA completion via hardware interrupt, the kernel decrements the frame reference counts (put_page()), allowing normal deallocation only after the hardware transfer completes.

Exercise 7.6.3: Proving End-to-End File Durability from Page Fault to Disk Platter

Proofsynthesis

Let a persistent storage subsystem guarantee durability under Write-Ahead Logging (WAL) with storage cache flush commands.

  1. Formulate the two write-ordering invariants required to prevent corruption across sudden power loss:
    • Invariant 1 (Log Record Order): Log descriptor and block writes must reach non-volatile media before the commit block.
    • Invariant 2 (Checkpoint Order): The commit block must reach non-volatile media before in-place data blocks are overwritten.
  2. Prove that if the disk controller reorders writes across the commit block boundary (violating Invariant 1), a crash during checkpointing can leave the file system in an unrecoverable corrupted state.
HintExpand

Show that an out-of-order write of the commit block followed by a power cut leaves an incomplete transaction marked as committed, causing replay of corrupt or partial blocks.

Worked solutionExpand
  1. Formal ordering invariants:

    • Invariant 1 Wlog≺WcommitW_{\text{log}} \prec W_{\text{commit}} For any transaction TiT_i all journal log block writes Li,1,…,Li,kL_{i,1}, \dots, L_{i,k} must be completely flushed to persistent media before the commit record CiC_i is persisted: ∀k,  flushed(Li,k)≺flushed(Ci)\forall k, \; \text{flushed}(L_{i,k}) \prec \text{flushed}(C_i)
    • Invariant 2 Wcommit≺WcheckpointW_{\text{commit}} \prec W_{\text{checkpoint}} The commit record CiC_i must be completely flushed before any dirty metadata or data block is written in-place to its permanent location Pi,jP_{i,j} flushed(Ci)≺flushed(Pi,j)\text{flushed}(C_i) \prec \text{flushed}(P_{i,j})
  2. Proof of failure under Invariant 1 violation:

    • Suppose the disk controller reorders writes due to write-back volatile caching, writing CiC_i to persistent media while log payload block Li,1L_{i,1} is still volatile in controller RAM.
    • Power fails immediately.
    • Upon reboot, crash recovery scans the journal log. It inspects transaction TiT_i and detects a valid CiC_i on disk, concluding that TiT_i was successfully committed.
    • The recovery routine replays the transaction, copying the contents of Li,1L_{i,1} into permanent location Pi,1P_{i,1}
    • However, because Li,1L_{i,1} was never persisted, the sector on disk contains random garbage or stale data from an earlier epoch.
    • The file system overwrites valid in-place file system metadata (such as the root inode or allocation bitmap) with garbage, resulting in catastrophic metadata corruption that journal replay cannot rectify.

Exercise 7.6.4: Evaluating End-to-End Scalability Across Kernel Boundaries

Constructiontransfer

An engineer optimizes an operating system kernel by replacing a coarse-grained central spinlock on the virtual memory subsystem with fine-grained per-VMA range locks. In a single-threaded benchmark, throughput drops by 4%. In a 64-core multi-threaded benchmark with disjoint memory mappings, throughput scales 38× higher.

  1. Account for the 4% single-threaded throughput regression in terms of instruction count, memory barriers, and lock acquisition overhead.
  2. Explain why the multi-threaded benchmark achieves near-linear speedup, identifying the hardware cache coherence mechanisms involved.
  3. Formulate the decision rule for when this kernel redesign should be accepted into production.
HintExpand

Contrast lock instruction overhead on uncontended paths against cache-line bouncing (MESI invalidation) on contended global locks.

Worked solutionExpand
  1. Single-threaded overhead: Acquiring and releasing multiple fine-grained locks requires executing atomic instructions (e.g., lr/sc or cmpxchg) and memory fence instructions for each individual VMA accessed, whereas a single coarse lock executed those atomic instructions once. On an uncontended single-core execution path, these extra instructions and pipeline flushes increase execution cycles, manifesting as a 4% latency overhead.
  2. Multicore scaling mechanism: With a global lock, all 64 cores compete for the identical 64-byte cache line containing the lock state. Under the MESI coherence protocol, every lock acquire issues a Read-For-Ownership (RFO) bus transaction, invalidating the cache line across all 63 other cores and stalling them on interconnect latency. With fine-grained per-VMA locks accessed by disjoint threads, each core modifies disjoint memory addresses residing in distinct cache lines in local Exclusive or Modified state, eliminating cross-core cache invalidations and allowing parallel progress.
  3. Production decision rule: Accept the redesign if the targeted deployment environments are predominantly concurrent multi-threaded workloads on multicore hardware where the throughput gains (up to 38×) vastly outweigh the modest 4% single-thread penalty, and where memory consumption overhead from per-VMA lock structures remains within bounded system limits.

Exercise 7.6.5: Auditing the Final Operating System Trusted Computing Base

Descriptionsynthesis

At the completion of an operating system design, an architectural audit evaluates the Trusted Computing Base (TCB).

  1. Define the TCB of a computer system.
  2. For an xv6-based kernel running user processes, enumerate every hardware and software component included in the TCB.
  3. If an attacker discovers a vulnerability in the xv6 virtio disk driver, state the maximum privilege the attacker can achieve and explain how architectural redesign (such as driver privilege separation) could restrict that blast radius.
HintExpand

The TCB includes all hardware, firmware, and software elements whose misbehavior can break the system security policy. In monolithic xv6, all kernel code executes in supervisor mode.

Worked solutionExpand
  1. TCB definition: The Trusted Computing Base comprises the complete set of hardware, firmware, and software components that are critical to system security. If any component within the TCB contains a vulnerability or behaves maliciously, the security policy (confidentiality, integrity, availability) of the entire system can be compromised.
  2. xv6 TCB components:
    • Hardware: Physical CPU core and MMU translation hardware, physical RAM, system bus, interrupt controllers (PLIC/CLINT), timer, and storage devices.
    • Firmware: RISC-V machine-mode bootloader (OpenSBI / BIOS) executing at M-mode.
    • Software: The entire xv6 kernel binary executing in supervisor mode (S-mode)—including the trap handler, scheduler, physical memory allocator, page table manager, system call dispatcher, VFS and file system, and device drivers (UART, VirtIO disk).
  3. Driver exploit blast radius and containment:
    • In xv6, device drivers execute directly within supervisor mode with full access to kernel address space and page tables. A vulnerability in the virtio driver allows arbitrary code execution in S-mode, granting complete authority to alter kernel code, disable page protection, inspect arbitrary process memory, or bypass authentication entirely.
    • To contain this blast radius, the architecture can isolate device drivers in unprivileged user-mode address spaces (as in microkernels) mediated by an IOMMU. Under this redesign, a compromised driver can corrupt only its own user space and device buffers; it cannot access kernel memory or other processes without passing through capability-checked IPC endpoints.

References & Further Reading

These sources define baselines and methods, not a capstone solution. Cite the exact primary source beside any imported interface, code fragment, hardware contract, filesystem guarantee, or measurement method that materially shapes the verified design.