A storage controller accepts physical addresses. A malicious process knows the controller’s register layout and submits a direct-memory-access descriptor targeting another process’s page. If the CPU permits the write, the controller faithfully corrupts the victim while the attacker remains in user mode. A filesystem API, process identifier, and graphical desktop can all exist on such a machine; none supplies protection unless access to the underlying mechanism is mediated.
The operating system is necessary because hardware resources are shared and because the requests presented to them are not intrinsically trustworthy. Its central contract is stronger than “provide convenient functions”:
Kernel mediation contract. Every transition that can affect protected state must be reached through a controlled entry, checked against the caller’s authority, executed while preserving global invariants, and reported through an interface whose failure semantics are explicit.
Boundary prediction — the hostile DMA descriptor
Before reading the model below, write four lines:
- the state the attacker wants to change;
- the first component that can prevent the change;
- the authority evidence that component needs; and
- one assumption under which prevention still fails.
HintExpandCollapse
Separate the CPU's privilege check from the device's ability to access memory.
Worked solutionExpandCollapse
The protected state is the victim’s physical page. The CPU can prevent user code from programming the controller by mapping its registers as supervisor-only; an IOMMU can separately constrain the device’s DMA addresses. The kernel needs both the caller’s right to use the device and ownership of the submitted buffers. Protection can still fail if the kernel validates the wrong length, retains a stale mapping, misprograms the IOMMU, or trusts malicious firmware. Naming only “permissions” misses the two distinct access paths: CPU loads/stores and device DMA.
Six ideas that must not collapse into one
The same implementation may serve several roles, but the roles answer different questions.
| Idea | Precise question | Example | Non-example |
|---|---|---|---|
| Abstraction | Which details does the interface hide while preserving useful operations? | A file exposes byte reads instead of disk-sector commands. | Renaming a sector number file_id without adding semantics. |
| Virtualization | How does one physical resource appear as multiple logical instances or as a different resource? | Each process observes a private virtual address space. | Merely serializing access to one global buffer. |
| Multiplexing | Which claimant receives a finite resource, when, and for how long? | A scheduler allocates CPU intervals among runnable threads. | Mapping two names to the same object without allocating time or capacity. |
| Mechanism | What operations make a policy enforceable? | Timer interrupts, saved contexts, and a ready queue permit preemption. | “Be fair” without a way to stop a running thread. |
| Policy | Which allowed outcome should the mechanism choose? | Select the runnable thread with the earliest eligible virtual deadline. | The context-switch assembly that saves registers. |
| Protection | Which subject may perform which operation on which object? | Page-table permissions reject a user-mode store to a kernel page. | Hiding an address while leaving it writable. |
An abstraction can exist without isolation: two processes may hold descriptors for the same open file description. Virtualization can be partial: CPU time is virtualized while cache capacity remains visibly shared. Protection can be correct yet unavailable: a kernel that denies every request preserves confidentiality but offers no useful progress.
Retrieval under changed names
A storage service assigns each tenant a “virtual disk,” queues all operations in one FIFO, and performs no access check because identifiers are 128-bit random values. Classify the design’s three claims: abstraction, multiplexing, and protection.
Worked solutionExpandCollapse
The block interface and tenant-specific names provide an abstraction. The FIFO multiplexes one physical service path. Protection is not established: identifier unpredictability is not an authorization proof, and accidental disclosure grants access. A correct answer that calls the random identifier a capability must also establish unforgeability, controlled transfer, revocation semantics, and complete mediation; length alone does none of those things.
Mechanism Versus Policy Classification Matrix
Evaluate each statement regarding how kernel mechanisms and scheduling policies are separated in operating systems architecture:
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
A kernel operation as a transition system
Let the machine state be
where is architecturally visible hardware state, is kernel-owned state, each is a protection domain, and is device-visible state. An event proposes a transition Events include explicit requests such as a system call, synchronous faults caused by the current instruction, and asynchronous interrupts raised by devices or timers.
The transition is acceptable only if three obligations hold:
- Authorization: the subject represented by has authority for the requested operation on the target object.
- Safety: an invariant implies Examples include “a physical frame has at most one mutable owner unless sharing is explicit” and “a runnable thread is not simultaneously linked into two run queues.”
- Progress under assumptions: if required resources and external events eventually become available, the request either completes or returns a documented error. This is conditional liveness, not a promise against broken hardware or infinite contention.
The diagram is a proof obligation, not a literal function-call graph. Some kernels fuse entry and validation; a device completion may awaken a different thread; and hardware may reject a request before kernel code runs. The invariant must survive every path, including errors and cancellation.
Application — define an invariant before code
A kernel exposes map_shared(frame_handle, va, writable). Two processes may map the same frame. Write one safety invariant that is strong enough to prevent unintended mutable aliasing but weak enough to permit deliberate shared memory. Then list the information the authorization check needs.
HintExpandCollapse
Ownership and writability need a relation; a count of mappings is insufficient.
Worked solutionExpandCollapse
One usable invariant is: “For every physical frame, either exactly one protection domain has a writable mapping, or every writable mapping belongs to a sharing group explicitly authorized by the frame owner; all other mappings are read-only.” The check needs the caller identity, the frame object denoted by the handle, the handle’s map and write rights, the requested virtual interval and permissions, the caller’s current address-space map, and the sharing-group policy. “At most one mapping” is too strong; “all handles may map” ignores rights encoded by the handle.
Worked trace: four bytes from a file
Assume one process calls read(fd, buf, 4). The descriptor already denotes a readable open file; buf is a user virtual address; the requested bytes are not cached.
| Cut | Controller | Relevant state | Obligation before advancing |
|---|---|---|---|
| 0 | user process | fd, buf, register state | User code may prepare a request but cannot issue disk DMA. |
| 1 | trap hardware | saved user PC, cause, privilege state | Entry must land at a kernel-configured vector without trusting a user target. |
| 2 | kernel dispatcher | call number and raw arguments | Reject unknown call numbers, invalid descriptors, overflowed ranges, and unwritable destinations. |
| 3 | filesystem/device path | file offset, cache state, request queue | Serialize updates to shared file state; bind DMA to kernel-owned buffers. |
| 4 | scheduler | caller is blocked; another thread runs | A blocked thread must not remain marked running on the same CPU. |
| 5 | interrupt path | device reports completion | Match the completion to a live request before waking a waiter. |
| 6 | return path | four bytes copied; result register is 4 | Restore the caller’s user state and no kernel-only register or mapping. |
This trace crosses abstraction layers but does not imply a copy at each boundary. A production kernel might satisfy the read from a page cache, perform readahead, or map data into user space. The contract remains: descriptor authority and user memory are checked, shared offsets change atomically according to the interface, and failure is reported without exposing unrelated state.
Transfer — a cancellation cut
At cut 4, another thread requests cancellation of the blocked operation. The disk later completes anyway. Give one safe ownership protocol for the request object and explain why “free it on cancellation” is wrong.
Worked solutionExpandCollapse
Use a request state machine such as QUEUED → IN_FLIGHT → COMPLETING → DONE, with cancellation recording CANCEL_REQUESTED rather than freeing an in-flight object. The completion path owns the final transition, detaches the DMA mapping, records either completion or cancellation, wakes waiters, and releases the last reference. Immediate free permits the later interrupt to dereference reused memory or to copy device data into a new owner’s buffer. The missing concept in that wrong answer is asynchronous lifetime, not merely locking.
Worked trace: one CPU, two processes, one page frame
Consider processes and on one CPU. is running; is runnable. No free physical frame exists. requests a page that may be supplied by evicting a clean page owned by
- A timer event transfers control to the kernel. The scheduler saves ‘s execution context, changes from running to runnable, chooses and restores
- Later, runs and faults on an unmapped virtual page. The fault is synchronous: the current instruction cannot retire with its requested effect.
- The kernel chooses a victim frame using a replacement policy. The unmap and TLB invalidation mechanisms make that policy enforceable.
- Before reassigning the frame, every mapping that could write it as ‘s page must cease to authorize access. The kernel records the new owner and mapping for
- The faulting instruction is retried. From ‘s perspective, a private page appeared; from the machine’s perspective, CPU time and a frame were multiplexed at different timescales.
The CPU scheduler and memory manager solve different allocation problems but share one structure: observable abstraction, protected metadata, revocable hardware mechanism, and policy under scarcity.
Quantitative check — capacity is not a policy
Suppose demands 8 ms of CPU every 20 ms and demands 15 ms every 25 ms. Compute average utilization demand and decide what the number proves.
HintExpandCollapse
Add demand rates, then separate a necessary capacity condition from a schedule proof.
Worked solutionExpandCollapse
demands CPU and demands so average demand is This establishes no scheduling guarantee. At exactly full utilization there is no slack for kernel work, release jitter, cache effects, or unfavorable alignment, and average feasibility does not prove every deadline. The diagnostic distinction is capacity versus policy plus timing assumptions.
Mechanism, policy, and evidence
“The kernel should be fair” is not implementable until fairness has an observable definition. Equal CPU time, weighted shares, bounded response time, and deadline satisfaction are different policies. A timer interrupt and context switch are mechanisms. A run queue is partly mechanism and partly policy because its ordering encodes a choice.
Use this claim decomposition for any operating-system feature:
| Claim layer | Required evidence |
|---|---|
| Interface | Inputs, outputs, error cases, concurrency semantics, and lifetime rules |
| Safety | Invariant plus an argument over all state transitions, including failure paths |
| Liveness | Workload and fairness assumptions; a bound or a counterexample when possible |
| Performance | Cost model, controlled measurements, uncertainty, and a competing explanation |
| Security | Threat model, authority path, trusted computing base, and revocation story |
A benchmark cannot prove isolation. A type signature cannot prove progress. A successful happy-path test cannot prove recovery. Evidence must match the claim.
Synthesis — audit a “zero-copy” service
A proposed service maps a network device’s receive ring into every client for “zero-copy performance.” Clients are mutually hostile. Produce a compact mechanism map with: abstract objects, protected state, authority checks, one safety invariant, one liveness risk, and one measurement needed before accepting the performance claim.
Worked solutionExpandCollapse
A defensible design exposes per-client receive buffers or immutable packet views, not the shared writable ring. Protected state includes descriptor ownership, producer/consumer indices, DMA mappings, and buffer lifetimes. Authority checks bind a client to its queue and map only buffers assigned to it. A useful invariant is: each writable descriptor and DMA target has exactly one current owner; clients cannot advance device-owned indices. A slow client can retain buffers and exhaust the ring, so liveness needs quotas, revocation, or copying under pressure. Measure end-to-end throughput and tail latency while accounting for IOMMU operations, cache-line contention, retained buffers, and fallback copies. A response that says only “use an IOMMU” omits ownership and denial-of-service.
Boundaries of the contract
The kernel cannot create guarantees absent from its assumptions.
- Hardware failure: a CPU that violates privilege checks or memory ordering invalidates the software proof.
- Trusted-code defect: a monolithic kernel bug may bypass every user/kernel boundary because the buggy code already has supervisor authority.
- Information leakage: page isolation does not automatically hide timing through shared caches or queues.
- Permanent overload: no scheduler can complete unbounded demand with finite capacity.
- Durability: a successful write to volatile cache is not a persistence guarantee unless the interface defines and enforces a durability point.
The trusted computing base (TCB) is the set of components whose correct behavior is necessary for a security property. Smaller is not automatically correct, but every additional trusted parser, driver, or privileged service enlarges what must be audited.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 1.1.1: The Hostile DMA Descriptor and Privilege Boundaries
A storage controller accepts physical addresses directly from software descriptors. Explain why CPU privilege mode checks alone cannot prevent a hostile user process from corrupting physical memory via the controller, and identify the hardware and software mediation mechanisms required to enforce isolation.
HintExpandCollapse
Separate the CPU privilege check from the peripheral device memory bus access path.
Worked solutionExpandCollapse
The CPU privilege mode check restricts CPU instructions (loads and stores) from writing peripheral device registers when mapped as supervisor-only. However, once a peripheral initiates a direct memory access (DMA) transaction across the system bus, the access originates from the controller rather than the CPU core. Without an I/O Memory Management Unit (IOMMU) translating and filtering peripheral bus requests, a rogue or untrusted device descriptor can target any physical memory frame. Complete mediation requires mapping device control registers as supervisor-only and routing all DMA through an IOMMU programmed strictly with validated kernel-owned physical frame buffers.
Exercise 1.1.2: Random Identifier Authorization vs Protection
A cloud storage service assigns each tenant a virtual disk, queues requests in a single FIFO queue, and uses 128-bit random tokens as handles without per-operation permission checks. Analyze whether this system achieves abstraction, multiplexing, and protection.
HintExpandCollapse
Evaluate whether unguessable handles establish unforgeability, revocation, and complete mediation.
Worked solutionExpandCollapse
The system achieves abstraction (presenting disk-block operations) and multiplexing (sharing the physical storage path via the FIFO queue). However, it does not achieve true protection. A 128-bit random token provides obscurity, but tokens can be leaked, intercepted, or replayed. A sound capability protection system requires unforgeability, controlled delegation, explicit revocation semantics, and complete mediation at every access point.
Exercise 1.1.4: Asynchronous Cancellation and Object Lifetime
A user process invokes an asynchronous block read. While the request is in flight in the storage controller, another thread issues a cancellation request. Detail the state machine and reference counting rules required to prevent a use-after-free or buffer corruption hazard upon completion.
HintExpandCollapse
Track request lifecycle explicitly through state transitions rather than deallocating on cancel.
Worked solutionExpandCollapse
The request must follow an explicit lifecycle such as QUEUED -> IN_FLIGHT -> COMPLETING -> DONE. When cancellation is requested while IN_FLIGHT, the kernel marks the state CANCEL_REQUESTED but retains all buffer allocations and DMA mappings. When the hardware interrupt fires, the completion handler observes CANCEL_REQUESTED, tears down the DMA mapping, records an aborted status, and releases the final reference. Deallocating memory immediately on cancellation allows the pending DMA write to corrupt reallocated memory.
Exercise 1.1.5: Capacity Limits vs Feasible Scheduling Guarantees
Two tasks run on a uniprocessor: Task requires 8 ms of CPU every 20 ms, and Task requires 15 ms of CPU every 25 ms. Compute the total utilization demand and evaluate whether satisfying the capacity bound guarantees that all deadlines are met.
HintExpandCollapse
Sum utilization fractions and evaluate whether nominal capacity implies schedulability without scheduling assumptions.
Worked solutionExpandCollapse
Utilization is While nominal demand equals total uniprocessor capacity, this does not guarantee deadline satisfaction. Zero slack exists for context switching overhead, timer interrupt latency, or cache refill penalties. Furthermore, under rate-monotonic or earliest-deadline-first scheduling, phase alignment and non-preemptive regions can cause immediate deadline misses. Capacity is a necessary precondition, not a proof of liveness.
Exercise 1.1.6: Complete Mechanism Map and Safety Invariant Defense
Construct a structured mechanism map for a microkernel IPC subsystem transferring messages between mutually untrusted processes. Specify the state tuple, controlled entry, authorization check, safety invariant, and a falsifiable performance measurement plan.
HintExpandCollapse
Decompose the IPC subsystem into abstract state, authority checks, invariants, and measurable tail latency metrics.
Worked solutionExpandCollapse
State tuple: where tracks channel endpoints, message queues, and capability tokens. Controlled entry: system call ipc_send(cap_endpoint, msg_ptr, len). Authority check: verifies caller owns the endpoint capability with send rights, validates and verifies that msg_ptr references valid user memory. Safety invariant: messages are delivered strictly to the intended recipient endpoint; unmapped physical frames are never exposed to peer address spaces; and failed deliveries leave endpoints consistent. Performance measurement: benchmark end-to-end round-trip latency and throughput under varying message sizes while controlling for cache warm-up, context-switch cycles, and CPU frequency pinning.
References & Further Reading
- RISC-V International, The RISC-V Instruction Set Manual, Volume II: Privileged Architecture, especially privilege modes and supervisor trap state.
- MIT PDOS, xv6: a simple, Unix-like teaching operating system, Chapters 1–2. The xv6 code and book are distributed under permissive notices retained by upstream.
- The Open Group, POSIX.1-2024
open()andread(), for the visible file-descriptor and I/O contracts used in the worked trace. - MIT PDOS, official xv6 RISC-V rev5 source, pinned at commit
7d7adbb1b0acbd67c9766a20d0f9900fef2789fafor the implementation spine.