Search Knowledge

© 2026 LIBREUNI PROJECT

Page 16 of 29

Device I/O, Interrupts, and DMA

Derive the driver–device ownership protocol behind polling, interrupts, DMA, descriptor rings, memory ordering, and bounded recovery.

Lesson briefDevices and I/O · 6 h · 4 outcomes

Required knowledge

  • Privilege transitions, traps, locks, sleep/wakeup, and virtual memory
  • Caches, memory ordering, MMIO, and hexadecimal register-level reasoning
  • Rates, latency, utilization, and dimensional analysis

Learning outcomes

  • Specify a device contract in terms of registers, descriptor ownership, access widths, ordering, interrupts, and failure states.
  • Derive when polling, interrupt-driven programmed I/O, or DMA minimizes CPU occupancy under an explicit workload model.
  • Trace descriptor publication, device access, completion, synchronization, and reclamation without races or stale ownership.
  • Design failure-injection evidence for lost notification, duplicate completion, malformed status, timeout, and teardown during DMA.

Assessment target

Given an unfamiliar MMIO device, event rate, transfer-size distribution, ring snapshot, and injected failure, derive the I/O mechanism and ordering protocol, calculate CPU occupancy, trace ownership to completion, and reject any recovery that reuses a buffer while the device can still access it.

Scope boundary

  • PCIe transaction details, cache-coherence protocol internals, IOMMU programming, NAPI, MSI-X, and production power management are bounded extensions.
  • The numeric simulator is a single-operation teaching model; it does not model queueing, device parallelism, cache misses, or measured hardware constants.

A driver fills a descriptor with a buffer address and length, advances a producer index, and rings a device doorbell. The CPU reordered the producer-index store before the descriptor stores. The device observes new work, reads the old length and address, and transfers data into a frame that has already been reassigned.

The defect is not “DMA is unsafe.” The driver published ownership before the work description was complete. Device I/O is a concurrent protocol between agents with different clocks, caches, and failure modes. Correctness comes from explicit state transitions and ordering edges.

Buffer-ownership invariant. At every instant, the protocol identifies which agent may read or write each descriptor and data buffer. Ownership changes only after all prior writes required by the new owner are visible, and reclamation occurs only after the old owner can no longer access the object.

A device contract precedes driver code

A driver needs more than register addresses. Its contract must define:

Contract fieldQuestions that must have one answer
register semanticswidth, alignment, reset value, read/write side effects, reserved bits
command publicationwhich fields are written first; what store or I/O barrier orders them
device ownershipwhen the device may read descriptors or write buffers
completionstatus encoding, interrupt condition, acknowledgment sequence, batching
queue capacityfull/empty test, wrap rule, maximum outstanding work
failuremalformed status, timeout meaning, reset/quiescence, late completion
concurrencywhich locks protect software metadata; which fields the device changes independently

Memory-mapped I/O (MMIO) gives device registers addresses in a processor-visible range. Register access is not ordinary RAM access: reads and writes can have side effects, widths can be constrained, and the platform defines ordering and caching attributes. In C, volatile can stop the compiler from removing or merging an access, but it does not create a cross-CPU lock, a device memory barrier, or a DMA ownership protocol. Kernel code should use architecture/platform MMIO accessors and barriers whose contract matches the device.

Programmed I/O (PIO) has the CPU copy data through registers or memory. Direct memory access (DMA) lets a device transfer between device-visible memory and itself after the CPU supplies descriptors. DMA removes a CPU copy loop from the data path; it adds another memory-accessing agent whose authority and lifetime must be controlled.

Retrieval — separate three guarantees. For an MMIO command register, state what volatile, a spinlock, and a device write barrier each establish. None may be described as a substitute for the other two.

Reveal the diagnostic answerExpand
  • volatile constrains compiler treatment of the access according to the C implementation; it does not by itself order another core or device.
  • A spinlock serializes participating CPU threads and usually carries CPU memory-ordering semantics; the device does not acquire it.
  • The architecture/platform’s device barrier orders specified CPU memory operations with respect to device observation.

Confusing these layers often produces code that passes on one machine because its memory model is stronger than the driver’s stated assumptions.

Device memory access and DMA ordering invariants

0 / 4 answered

Evaluate each statement regarding memory-mapped IO registers, volatile qualifiers, and DMA synchronization:

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

1
Hardware cache coherence eliminates the need for software memory barriers when publishing ring buffer entries.
2
When a DMA request times out, drivers can safely reallocate the buffer immediately without waiting for reset.
3
The C volatile qualifier prevents compiler reordering but does not issue hardware memory barriers to devices.
4
Drivers must execute a device write memory barrier before writing the doorbell to publish DMA descriptors.

Polling and interrupts trade work for notification latency

Polling repeatedly reads status. It can give bounded detection delay when a core polls at a controlled period, but consumes CPU work even when no event arrives. An interrupt transfers control when a device signals an event; it avoids idle polling but pays entry, dispatch, acknowledgment, and cache-disruption costs per notification.

For a periodic poll every PP seconds, uniformly distributed event arrival gives expected detection delay P/2P/2 and worst-case delay near PP If one poll costs CpC_p CPU seconds, polling occupancy is approximately

Up=CpP.U_p = \frac{C_p}{P}.

For event rate λ\lambda and interrupt-handling CPU time CiC_i per event,

Ui=λCi,U_i = \lambda C_i,

until queueing, coalescing, or saturation invalidates the independent-event model. Equating the two gives a first-order crossover λ∗=Cp/(PCi)\lambda^*=C_p/(P C_i) The result is meaningful only if the latency constraint permits period PP and the measured costs match the platform.

Worked example: sparse control events

A device produces 200 events/s. One status poll costs 120 ns. The deadline requires detection within 50 µs, so choose P=50P=50 µs for worst-case compliance. Polling consumes

120 ns50 μs=0.0024=0.24%\frac{120\,\mathrm{ns}}{50\,\mu\mathrm{s}}=0.0024=0.24\%

of one CPU. If one interrupt consumes 2.5 µs of CPU time, interrupts consume

200 s−1×2.5 μs=0.0005=0.05%.200\,\mathrm{s}^{-1}\times2.5\,\mu\mathrm{s}=0.0005=0.05\%.

Interrupts use less CPU under these assumptions. Polling may still be chosen if its tighter jitter matters, if a dedicated core is available, or if event bursts would produce interrupt storms. The model does not decide the objective.

Coalescing changes the event unit

If the device posts 64 completions and sends one interrupt, the fixed notification cost is amortized across the batch. Coalescing reduces interrupt rate but delays early completions. The control variable is a count or timer threshold; evaluate both CPU occupancy and tail completion latency.

Application — choose a coalescing bound. Events arrive at 80,000/s. One interrupt costs 1.5 µs of CPU time. Batching 16 completions per interrupt adds at most 200 µs by policy. Calculate notification CPU occupancy without and with full batches; state why the latency claim still needs a burst/idle analysis.

Reveal the calculationExpand

Without batching, occupancy is 80,000 × 1.5 µs = 0.12, or 12% of one CPU. With full batches of 16, interrupt rate is 5,000/s and occupancy is 0.75%. Full batches do not always form: after a sparse arrival, a timer must release a partial batch, and the first completion may wait near the timer limit. The 200 µs policy bound also excludes interrupt dispatch and scheduling delay unless those are included explicitly.

DMA changes who moves bytes

For a transfer of nn bytes, compare two CPU-busy models:

CPIO(n)=Csetup+Cinterrupt+nccopy,C_{PIO}(n)=C_{setup}+C_{interrupt}+n c_{copy}, CDMA(n)=Cdma_setup+Ccompletion.C_{DMA}(n)=C_{dma\_setup}+C_{completion}.

DMA is advantageous for CPU occupancy when its fixed setup cost is less than the avoided CPU copy cost. It does not make the device latency or bus transfer disappear. Small transfers can favor PIO because DMA setup dominates.

Worked crossover under the simulator’s constants

The investigation below uses a 3 GHz CPU, 500 setup cycles for programmed I/O, 1,800 for DMA, 1,200 per interrupt, two CPU cycles per copied byte, and 100 MB/s transfer rate. Equating interrupt-driven PIO and DMA CPU work:

500+1200+2n=1800+1200⇒n=650 bytes.500+1200+2n=1800+1200 \quad\Rightarrow\quad n=650\text{ bytes}.

Under these invented constants, DMA has lower modeled CPU occupancy above 650 bytes; interrupt-driven PIO has lower fixed CPU work below it.

For 4 KiB, 1 ms latency, and 100 operations/s:

MechanismCPU busy per operationElapsed per operationCPU occupancy
busy polling + PIO1.0439 ms1.0439 ms10.44%
interrupt + CPU copy0.00330 ms1.0443 ms0.033%
DMA + completion interrupt0.00100 ms1.0420 ms0.010%

DMA has both the lowest CPU occupancy and, by a small margin, the lowest elapsed time for this 4 KiB state: its larger setup is outweighed by eliminating the modeled CPU copy. That elapsed-time result can reverse for transfers below the 650-byte crossover. Latency and CPU demand remain different objectives.

Experiment: change bytes, events, and device latency

The simulator assumes one independent operation, no queueing, a fixed 100 MB/s transfer rate, and the numeric constants listed above. Polling means continuous busy waiting for the modeled device latency, not periodic polling. CPU occupancy is capped at 100%; once offered work exceeds capacity, the widget does not model the resulting queue or latency growth.

Prediction — quantify before moving a slider. At 64 bytes, 0.1 ms device latency, and 2,000 operations/s, which has lower modeled CPU occupancy: interrupt-driven copying or DMA? Use the fixed-cycle equations, then set the widget to that state.

Interactive exploration

Choose polling, interrupts, or DMA from workload evidence

Change transfer size, device latency, and operation rate. The timeline separates elapsed device time from CPU occupancy and exposes when setup overhead or busy waiting dominates.

0.0% modeled CPU occupancy
devicelatency + transferCPU01.044 ms elapsedCPU available while device works
CPU busy / operation
0.0033 ms
Elapsed / operation
1.0443 ms
CPU occupancy
0.0%

Explicit model: 3 GHz CPU, 500 setup cycles for programmed I/O, 1,800 for DMA, 1,200 per interrupt, two CPU cycles per CPU-copied byte, and 100 MB/s device transfer. Polling occupies the CPU during both device latency and transfer. Very short CPU phases receive an eight-pixel minimum marker, so their drawn width is not a timing claim. Occupancy is capped at 100%; a larger offered load means the requested rate is unsustainable on one CPU. These are teaching assumptions—not hardware claims.

Choose polling, interrupts, or DMA from workload evidence
devicelatency + transferCPU01.044 ms elapsedCPU available while device works

Static state: 4 KiB transfers, 1 ms device latency, 100 operations/s, interrupt-driven CPU copying. The CPU is free during device latency but pays setup, interrupt, and copy work.

Interrupt-driven copying consumes (500 + 1200 + 128)/3 GHz = 0.609 µs per operation, or about 0.122% of a CPU at 2,000/s. DMA consumes 3,000/3 GHz = 1 µs per operation, or 0.200%. The small transfer favors CPU copy under this CPU-work model; device latency changes elapsed time but not these two modeled CPU-work equations.

Transfer — invalidate one assumption. Replace the constant 100 MB/s device with a device that sustains four transfers concurrently but slows each transfer by 30% at queue depth four. State what additional state the model needs before it can predict throughput and tail latency.

Reveal the modeling requirementsExpand

The model needs at least queue depth, arrival process, number of service lanes, service-time dependence on concurrency, completion order, and a latency distribution rather than one constant. CPU occupancy can still be computed per submission/completion, but end-to-end latency requires waiting time plus concurrency-dependent service. A single-operation bar cannot support a queueing claim.

Descriptor rings encode ownership

High-throughput devices use shared-memory descriptors. A descriptor typically contains a device-visible address, length, direction, command, and status. A split ring such as Virtio has driver-written available state and device-written used state.

Code
title "One DMA request from construction to reclamation"
participant "driver thread" as CPU
participant "descriptor memory" as RING
participant "device" as DEV
participant "interrupt path" as IRQ
CPU -> CPU : map/pin data buffer
CPU -> RING : write command, address, length, direction
CPU -> CPU : write barrier
CPU -> RING : publish available index
CPU -> DEV : MMIO doorbell / notification
DEV -> RING : read descriptor and buffer
DEV -> RING : DMA data and write completion status
DEV -> IRQ : raise completion interrupt
IRQ -> DEV : acknowledge according to device contract
IRQ -> IRQ : read barrier / DMA synchronization
IRQ -> RING : consume used entry and status
IRQ -> CPU : mark complete and wake waiter
CPU -> CPU : unmap, release buffer, recycle descriptor
One DMA request from construction to reclamationOne DMA request from construction to reclamationdriver threaddescriptor memorydeviceinterrupt pathdriver threaddriver threaddescriptor memorydescriptor memorydevicedeviceinterrupt pathinterrupt pathmap/pin data bufferwrite command,address, length,directionwrite barrierpublish available indexMMIO doorbell /notificationread descriptor andbufferDMA data and writecompletion statusraise completioninterruptacknowledge accordingto device contractread barrier / DMAsynchronizationconsume used entry andstatusmark complete andwake waiterunmap, release buffer,recycle descriptor

For ring capacity NN and monotonic producer/consumer counters, the software invariant is

0≤producer−consumer≤N.0\le producer-consumer\le N.

Slots are indexed modulo NN but counters should retain enough generation information to distinguish full from empty after wrap. Publication follows a release pattern:

write descriptor fields
write barrier for device visibility
write ring slot containing descriptor head
write barrier required by transport
advance published producer index
notify device if required

The device may access the descriptor immediately after the publication point. Editing a submitted descriptor before completion violates ownership even if the CPU still has a pointer to it.

Worked wrap trace

An eight-entry ring has monotonic producer=14, consumer=10, so occupancy is four. Published requests occupy logical sequence numbers 10–13 and physical slots 2–5. The producer’s next physical slot is 14 mod 8 = 6.

Publishing three requests uses slots 6, 7, and 0, then advances producer to 17. Occupancy becomes seven. One slot remains. Comparing only producer mod 8 = 1 with consumer mod 8 = 2 does not directly reveal occupancy; generation-bearing counters do.

Application — kill publish-first. A mutation advances producer before writing the descriptor’s length. Construct an interleaving in which the device reads a valid old address and old length. State which single happens-before edge is missing.

Reveal the failing interleavingExpand

CPU publishes producer 15; device observes the new index and reads slot 6; slot 6 still contains the previous generation’s descriptor; device begins DMA; CPU writes the new address and length too late. The missing edge is “all descriptor and ring-slot stores happen before the publication-index store as observed by the device.” A CPU-only lock does not create that edge unless the device participates in its memory-ordering protocol, which it does not.

Coherence, synchronization, and IOMMU authority

A coherent DMA allocation lets CPU and device observe each other’s writes without explicit cache-line cleaning for coherence, but coherent memory still needs barriers to order fields. A streaming DMA mapping may require explicit synchronization when ownership passes between CPU and device. Linux’s DMA API documents separate dma_sync_*_for_device and dma_sync_*_for_cpu operations for reused streaming mappings.

An IOMMU translates a device-visible I/O virtual address and enforces device permissions. It can restrict a device to the pages assigned to its DMA context, but it cannot repair a driver that reuses a still-owned buffer. Teardown requires both:

  1. stop or quiesce old device transactions; and
  2. revoke/invalidate device translations before the physical pages enter a new ownership domain.

Counterexample: timeout is not cancellation

A request exceeds its deadline. The driver returns an error, unmaps the DMA address, and allocates the frame to another process. The device completes late and writes into the new process’s memory. The timeout proved only that completion was not observed by a deadline. Safe recovery must retain the buffer or complete a documented cancel/reset/quiesce protocol before reuse.

Interrupt handling closes the protocol

An interrupt handler must drain enough device state that the interrupt condition is understood and acknowledged according to the device contract. It must also preserve concurrency invariants:

  • validate completion IDs before indexing software arrays;
  • synchronize before reading device-written status or data;
  • transition each request to completed at most once;
  • detach ownership before waking a waiter that may free resources;
  • avoid blocking work that cannot run in interrupt context; and
  • handle more than one completion per interrupt when the device batches.

Worked race: wake before state

Waiter code uses while (req.state != DONE) sleep(req, lock). The interrupt handler calls wakeup(req) and then writes req.state = DONE. A waiter can wake, reacquire the lock before the state store, observe IN_FLIGHT, and sleep again after the one wakeup has passed. The fix is to update completion state while holding the protocol lock and wake after the state transition is visible. The loop remains necessary because wakeups can be spurious or another event can change scheduling.

Duplicate and malformed completions

A duplicate completion must not decrement a reference twice or recycle a descriptor already assigned to another generation. Track request identity and lifecycle, validate id < ring_size, require state == IN_FLIGHT, and pair a reusable slot with a generation or sequence number when delayed events can cross reuse. A malformed status is a device/transport failure to report; treating every completion as success converts device error into silent data corruption.

Transfer — teardown defense. A hot-unplug event arrives with four requests in flight. Write a state sequence that permits their buffers to be reused. “Wait 100 ms” is not an admissible transition.

Reveal a valid boundary sequenceExpand

Stop admitting new submissions; mark the device stopping; mask or route interrupts according to the platform contract; request and verify device/queue reset or another specified quiescence mechanism; drain or fail completions while keeping buffers pinned; revoke DMA mappings and invalidate IOMMU state after quiescence; transition every request exactly once to completed/failed; wake waiters; then release descriptors and buffers. If the platform cannot prove quiescence, retaining/quarantining the memory is safer than reuse.

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 5.1.1: Calculating the Polling versus Interrupt CPU Occupancy Crossover

Verificationapplication

A peripheral device produces I/O events at mean rate λ\lambda events per second.

  • Polling implementation: The CPU polls every P=20 μsP = 20\ \mu\text{s} with each poll requiring Cp=100 nsC_p = 100\text{ ns} of CPU execution time.
  • Interrupt-driven implementation: Each event triggers a hardware interrupt requiring Ci=4 μsC_i = 4\ \mu\text{s} of CPU service time (entry, context save, driver handler, EOI acknowledgment, context restore).
  1. Calculate the steady-state CPU occupancy of the polling driver UpollU_{\text{poll}}
  2. Compute the event arrival rate λ∗\lambda^* at which the interrupt-driven driver consumes identical CPU occupancy Uintr=UpollU_{\text{intr}} = U_{\text{poll}}
  3. If the actual arrival rate is λ=2500 events/s\lambda = 2500\text{ events/s} determine which notification strategy minimizes CPU overhead.
HintExpand

Occupancy for polling is C_p / P; occupancy for interrupts is lambda * C_i.

Worked solutionExpand
  1. Polling occupancy: Upoll=CpP=100 ns20 μs=0.1 μs20 μs=0.005=0.5%.U_{\text{poll}} = \frac{C_p}{P} = \frac{100\text{ ns}}{20\ \mu\text{s}} = \frac{0.1\ \mu\text{s}}{20\ \mu\text{s}} = 0.005 = 0.5\%.
  2. Crossover arrival rate λ∗\lambda^* Set Uintr=λ∗Ci=UpollU_{\text{intr}} = \lambda^* C_i = U_{\text{poll}} λ∗×4 μs=0.005  ⟹  λ∗=0.0054×10−6 s=1250 events/s.\lambda^* \times 4\ \mu\text{s} = 0.005 \implies \lambda^* = \frac{0.005}{4 \times 10^{-6}\text{ s}} = 1250\text{ events/s}.
  3. Evaluation at λ=2500 events/s\lambda = 2500\text{ events/s} Uintr=2500×(4×10−6 s)=0.010=1.0%.U_{\text{intr}} = 2500 \times (4 \times 10^{-6}\text{ s}) = 0.010 = 1.0\%. Because λ=2500>λ∗=1250\lambda = 2500 > \lambda^* = 1250 polling consumes 0.5%0.5\% CPU whereas interrupts consume 1.0%1.0\% Polling minimizes CPU occupancy at this arrival rate.

Exercise 5.1.2: Memory Barrier Placement in Producer-Consumer Descriptor Rings

Constructionapplication

A driver submits a DMA packet by populating a ring descriptor desc[idx] in host RAM (fields: buffer_pa, length, flags) and subsequently ringing an MMIO doorbell register DOORBELL = idx to notify the network device.

  1. Explain the race condition that occurs if the CPU or compiler reorders the doorbell store before the descriptor field stores.
  2. Specify the exact memory barrier or fence required between the descriptor initialization and the MMIO doorbell write on weakly ordered architectures.
HintExpand

The device starts fetching memory immediately upon receiving the doorbell write.

Worked solutionExpand
  1. Reordering race condition: If the MMIO store to DOORBELL reaches the peripheral before the writes to desc[idx] retire to coherent RAM or cache, the device immediately reads desc[idx]. The device observes uninitialized or stale descriptor values (e.g., an old buffer address or invalid length), causing the device to read or overwrite unauthorized host memory.
  2. Barrier specification: The driver must place a release memory barrier or write memory barrier (smp_wmb() or atomic_thread_fence(memory_order_release)) immediately before the doorbell store:
    desc[idx].buffer_pa = dma_addr;
    desc[idx].length = packet_len;
    desc[idx].flags = DESC_VALID;
    dma_wmb(); /* guarantees memory writes precede MMIO writes */
    mmio_write32(&dev->doorbell, idx);
    This enforces the happens-before relationship: Write(Descriptor Fields)≺Write(MMIO Doorbell).\text{Write}(\text{Descriptor Fields}) \prec \text{Write}(\text{MMIO Doorbell}).

Exercise 5.1.3: Deriving Transfer-Size Thresholds for DMA versus Programmed I/O

Constructiontransfer

A 2 GHz CPU executes programmed I/O (PIO) or direct memory access (DMA):

  • PIO setup is negligible, but copying requires 3 CPU cycles per transferred byte.
  • DMA setup requires pinning pages, setting up descriptors, and cache flushing/invalidation, costing a fixed Tsetup=1800 cyclesT_{\text{setup}} = 1800\text{ cycles} The DMA engine transfers data without CPU intervention.
  • Both schemes pay a fixed Tintr=1200 cyclesT_{\text{intr}} = 1200\text{ cycles} for completion interrupt processing.
  1. Write the CPU cycle cost functions CPIO(B)C_{\text{PIO}}(B) and CDMA(B)C_{\text{DMA}}(B) for a transfer of BB bytes.
  2. Find the breakeven transfer size B∗B^* where DMA becomes strictly more efficient for CPU occupancy than PIO.
HintExpand

Set C_PIO(B) = C_DMA(B) and solve for B.

Worked solutionExpand
  1. Cost functions:
    • For Programmed I/O: CPIO(B)=Tintr+3⋅B=1200+3B cyclesC_{\text{PIO}}(B) = T_{\text{intr}} + 3 \cdot B = 1200 + 3B\text{ cycles}
    • For DMA: CDMA(B)=Tsetup+Tintr=1800+1200=3000 cyclesC_{\text{DMA}}(B) = T_{\text{setup}} + T_{\text{intr}} = 1800 + 1200 = 3000\text{ cycles}
  2. Breakeven size B∗B^* 1200+3B∗=3000  ⟹  3B∗=1800  ⟹  B∗=600 bytes.1200 + 3B^* = 3000 \implies 3B^* = 1800 \implies B^* = 600\text{ bytes}. For transfers strictly greater than 600 bytes, DMA is more CPU-efficient; for transfers smaller than 600 bytes (e.g., 64-byte control packets), PIO avoids the setup tax and reduces total CPU load.

Exercise 5.1.4: Proving Buffer Invariant Violations on Premature Timeout Reclamation

Proofsynthesis

Suppose a disk driver submits a DMA read request for physical buffer BB After 5 seconds, the request has not completed, and a software timeout fires. Prove that unmapping BB and immediately reallocating it to an unrelated process violates the buffer-ownership invariant unless the device is proven quiesced.

HintExpand

A timeout measures only software wait time, not device bus state; the device may commit transfer cycles later.

Worked solutionExpand

Assume for contradiction that the driver frees and reallocates buffer BB to Process P2P_2 immediately upon timeout expiration without issuing a hardware reset or awaiting device quiescence:

  1. The expiration of a software timer proves only that no completion interrupt was processed; it does not prove the peripheral hardware aborted its bus mastering activity.
  2. The device controller may be delayed due to internal queueing, bus contention, or high controller latency.
  3. Once buffer BB is reassigned to Process P2P_2 Process P2P_2 begins writing sensitive data into BB
  4. At t=5.2 secondst = 5.2\text{ seconds} the delayed device DMA engine initiates or finishes writing its delayed disk block into physical address BB
  5. The device overwrites P2P_2‘s active data, destroying memory contents and violating the buffer-ownership invariant: ∀t,Owner⁡(B,t)∈{CPU}⊕{Device}.\forall t, \quad \operatorname{Owner}(B, t) \in \{\text{CPU}\} \oplus \{\text{Device}\}.

Therefore, buffer BB cannot be freed or reused until the driver executes a verified hardware reset, aborts the in-flight command on the controller, and confirms bus quiescence.

Exercise 5.1.5: Eliminating Lost Wakeup Races in Asynchronous Driver Waiters

Descriptionsynthesis

Analyze the following buggy driver completion sequence between an interrupt handler and a sleeping process:

  • Waiter: while (req->status == PENDING) { sleep_on(&req->wq); }
  • Handler: wake_up(&req->wq); req->status = DONE;

Show how this order can cause an indefinite deadlock, and formulate the correct synchronized sequence.

HintExpand

Show that the waiter can evaluate the condition right before the handler executes both lines.

Worked solutionExpand
  • Failure schedule:
    1. Waiter reads req->status, observes PENDING.
    2. Before the waiter enters the sleep queue, a hardware interrupt fires on the CPU.
    3. The interrupt handler executes: calls wake_up(&req->wq), but the wait queue is currently empty.
    4. The interrupt handler then sets req->status = DONE and returns from interrupt.
    5. The preempted waiter resumes and executes sleep_on(&req->wq).
    6. The waiter is now suspended indefinitely because the wakeup occurred in the past, causing a lost wakeup and indefinite thread hang.
  • Correct synchronization protocol: The status transition must happen before the wakeup, and both operations must be protected by the queue lock:
    • In handler:
      acquire(&req->lock);
      req->status = DONE;
      wake_up_locked(&req->wq);
      release(&req->lock);
    • In waiter:
      acquire(&req->lock);
      while (req->status == PENDING) {
          sleep_locked(&req->wq, &req->lock);
      }
      release(&req->lock);
    Holding req->lock ensures that checking the condition and sleeping is atomic with respect to the state modification and wakeup.

References & Further Reading