Search Knowledge

© 2026 LIBREUNI PROJECT

Operating Systems Engineering/Crossing the kernel boundary
Page 1 of 29

The Operating-System Contract

Derive the operating system as a mediator that turns shared, failure-prone hardware into protected abstractions with explicit safety and progress conditions.

Lesson briefCrossing the kernel boundary · 5 h · 4 outcomes

Required knowledge

  • C pointers, object lifetime, and integer representations
  • CPU privilege modes, interrupts, address translation, and device registers
  • State machines, invariants, and asymptotic reasoning

Learning outcomes

  • Distinguish abstraction, virtualization, multiplexing, mechanism, policy, and protection without treating the terms as synonyms.
  • Model a kernel operation as a state transition and state the authority, safety invariant, and progress assumption at its boundary.
  • Trace CPU, memory, and device ownership through two concrete requests and identify where mediation can fail.
  • Evaluate an unfamiliar operating-system design claim by exposing its trusted base, workload assumptions, and omitted failure modes.

Assessment target

Produce and defend a mechanism map for an unfamiliar kernel service: define its abstract state, authority check, safety invariant, progress assumption, observable contract, and one adversarial failure trace.

Scope boundary

  • Historical surveys, command-line administration, package management, and operating-system installation are outside this mechanism course.
  • Formal noninterference proofs, real-time schedulability, distributed coordination, and physical fault tolerance require dedicated treatments.
  • xv6 is used as a compact implementation model; its policies, scale limits, and attack surface are not presented as production practice.

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:

  1. the state the attacker wants to change;
  2. the first component that can prevent the change;
  3. the authority evidence that component needs; and
  4. one assumption under which prevention still fails.
HintExpand

Separate the CPU's privilege check from the device's ability to access memory.

Worked solutionExpand

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.

IdeaPrecise questionExampleNon-example
AbstractionWhich 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.
VirtualizationHow 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.
MultiplexingWhich 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.
MechanismWhat 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.
PolicyWhich allowed outcome should the mechanism choose?Select the runnable thread with the earliest eligible virtual deadline.The context-switch assembly that saves registers.
ProtectionWhich 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 solutionExpand

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

0 / 4 answered

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.

1
Hardware timer interrupt delivery, trapframe register saving, and low-level context switching are mechanisms.
2
Choosing the exact numeric millisecond duration for a round-robin scheduling quantum is a hardware mechanism.
3
Selecting the runnable thread with the highest priority or smallest accumulated virtual runtime is policy.
4
Hardware MMU page-table translation and physical memory address calculation are software scheduler policies.

A kernel operation as a transition system

Let the machine state be

S=(H,K,P1,…,Pn,D),S = (H, K, P_1,\ldots,P_n, D),

where HH is architecturally visible hardware state, KK is kernel-owned state, each PiP_i is a protection domain, and DD is device-visible state. An event ee proposes a transition S→S′S \rightarrow S' 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:

  1. Authorization: the subject represented by PiP_i has authority for the requested operation on the target object.
  2. Safety: an invariant I(S)I(S) implies I(S′)I(S') 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.”
  3. 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.
Code
left to right direction
actor "untrusted process" as U
rectangle "controlled entry" as E
rectangle "authority check" as A
rectangle "kernel mechanism" as M
database "protected kernel state" as K
node "CPU / memory / device" as H

U --> E : request + arguments
E --> A : caller identity + handles
A --> M : validated operation
M --> K : preserve invariant
M --> H : privileged action
H --> M : completion / fault / interrupt
M --> U : result or explicit error

note bottom of A
User pointers, lengths, handles,
and state-dependent rights are untrusted.
end note
note bottom of M
Mechanism is not policy:
several legal outcomes may remain.
end note
untrusted processcontrolled entryauthority checkkernel mechanismprotected kernel stateCPU / memory / deviceUser pointers, lengths, handles,and state-dependent rights areuntrusted.Mechanism is not policy:several legal outcomes mayremain.request + argumentscaller identity + handlesvalidated operationpreserve invariantprivileged actioncompletion / fault /interruptresult or explicit error

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.

HintExpand

Ownership and writability need a relation; a count of mappings is insufficient.

Worked solutionExpand

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.

CutControllerRelevant stateObligation before advancing
0user processfd, buf, register stateUser code may prepare a request but cannot issue disk DMA.
1trap hardwaresaved user PC, cause, privilege stateEntry must land at a kernel-configured vector without trusting a user target.
2kernel dispatchercall number and raw argumentsReject unknown call numbers, invalid descriptors, overflowed ranges, and unwritable destinations.
3filesystem/device pathfile offset, cache state, request queueSerialize updates to shared file state; bind DMA to kernel-owned buffers.
4schedulercaller is blocked; another thread runsA blocked thread must not remain marked running on the same CPU.
5interrupt pathdevice reports completionMatch the completion to a live request before waking a waiter.
6return pathfour bytes copied; result register is 4Restore 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 solutionExpand

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 AA and BB on one CPU. AA is running; BB is runnable. No free physical frame exists. AA requests a page that may be supplied by evicting a clean page owned by BB

  1. A timer event transfers control to the kernel. The scheduler saves AA‘s execution context, changes AA from running to runnable, chooses BB and restores BB
  2. Later, AA runs and faults on an unmapped virtual page. The fault is synchronous: the current instruction cannot retire with its requested effect.
  3. The kernel chooses a victim frame using a replacement policy. The unmap and TLB invalidation mechanisms make that policy enforceable.
  4. Before reassigning the frame, every mapping that could write it as BB‘s page must cease to authorize access. The kernel records the new owner and mapping for AA
  5. The faulting instruction is retried. From AA‘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 AA demands 8 ms of CPU every 20 ms and BB demands 15 ms every 25 ms. Compute average utilization demand and decide what the number proves.

HintExpand

Add demand rates, then separate a necessary capacity condition from a schedule proof.

Worked solutionExpand

AA demands 8/20=0.48/20=0.4 CPU and BB demands 15/25=0.615/25=0.6 so average demand is 1.01.0 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 layerRequired evidence
InterfaceInputs, outputs, error cases, concurrency semantics, and lifetime rules
SafetyInvariant plus an argument over all state transitions, including failure paths
LivenessWorkload and fairness assumptions; a bound or a counterexample when possible
PerformanceCost model, controlled measurements, uncertainty, and a competing explanation
SecurityThreat 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 solutionExpand

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.

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 1.1.1: The Hostile DMA Descriptor and Privilege Boundaries

Descriptionapplication

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.

HintExpand

Separate the CPU privilege check from the peripheral device memory bus access path.

Worked solutionExpand

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

Verificationapplication

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.

HintExpand

Evaluate whether unguessable handles establish unforgeability, revocation, and complete mediation.

Worked solutionExpand

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.3: Shared Memory Invariants and Authority Verification

Formalisationtransfer

For a kernel system call map_shared(frame_handle, va, writable), formulate a mathematical safety invariant that permits intentional inter-process memory sharing while strictly preventing accidental or unauthorized mutable aliasing.

HintExpand

Formulate a condition relating physical frames to protection domains and authorized sharing groups.

Worked solutionExpand

A sound invariant is: For every physical frame FF either (1) at most one protection domain PiP_i holds a mapping with write permissions, or (2) all protection domains holding write permissions belong to an explicit sharing group GG authorized by the frame owner. The authorization check must verify the caller identity, validate that frame_handle conveys mapping and writing rights, ensure the requested virtual range [va,va+len)[va, va + \mathrm{len}) is unmapped, and check group authorization before modifying the page table.

Exercise 1.1.4: Asynchronous Cancellation and Object Lifetime

Constructiontransfer

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.

HintExpand

Track request lifecycle explicitly through state transitions rather than deallocating on cancel.

Worked solutionExpand

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

Verificationsynthesis

Two tasks run on a uniprocessor: Task AA requires 8 ms of CPU every 20 ms, and Task BB 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.

HintExpand

Sum utilization fractions and evaluate whether nominal capacity implies schedulability without scheduling assumptions.

Worked solutionExpand

Utilization is U=820+1525=0.40+0.60=1.00U = \frac{8}{20} + \frac{15}{25} = 0.40 + 0.60 = 1.00 100%100\% 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

Constructionsynthesis

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.

HintExpand

Decompose the IPC subsystem into abstract state, authority checks, invariants, and measurable tail latency metrics.

Worked solutionExpand

State tuple: S=(Kipc,Psender,Preceiver)S = (K_{\mathrm{ipc}}, P_{\mathrm{sender}}, P_{\mathrm{receiver}}) where KipcK_{\mathrm{ipc}} 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 len≤MAX_MSGlen \le \mathrm{MAX\_MSG} 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

  1. RISC-V International, The RISC-V Instruction Set Manual, Volume II: Privileged Architecture, especially privilege modes and supervisor trap state.
  2. 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.
  3. The Open Group, POSIX.1-2024 open() and read(), for the visible file-descriptor and I/O contracts used in the worked trace.
  4. MIT PDOS, official xv6 RISC-V rev5 source, pinned at commit 7d7adbb1b0acbd67c9766a20d0f9900fef2789fa for the implementation spine.