A driver appends a request to a queue, then sets ready = 1. Another core observes ready == 1 but follows an old queue tail and submits the wrong descriptor to hardware. No two cores wrote the same queue field at the same instant; the publication still failed because the consumer observed the flag without an ordering guarantee for the data it announced.
Mutual exclusion answers who may mutate an invariant now. Memory ordering answers which earlier effects another observer must see. An atomic instruction can contribute to both, but the words are not interchangeable.
Start from the invariant, not the lock variable
For a lock the protected invariant is a predicate over shared state that may be temporarily false only while one thread owns Every acquisition may assume every release must publish a state satisfying
For a lock the protected invariant is a predicate over shared state that may be temporarily false only while one thread owns Every acquisition may assume every release must publish a state satisfying
Consider a queue represented by head, tail, and count with capacity
The mutex is not part of the abstract queue. It is a protocol granting temporary exclusive authority to violate and restore those equations. A field is “protected by L” only if every access that depends on the invariant follows that protocol. Locking writers while readers inspect fields unlocked is not protection.
Retrieval. Why is “only one thread executes this function” weaker than a queue correctness proof?
AnswerExpandCollapse
The function may call another path that accesses the same fields under a different lock, readers may bypass the function, callbacks may re-enter it, and an early return may release before restoring the representation. The proof must identify all shared state covered by all access paths, acquisition and release boundaries, and preservation of the abstraction—not one function name.
Worked trace and preservation derivation for one enqueue
Assume the pre-state satisfies and tail == (head + count) mod N. Under exclusive ownership:
- write the item into slot
tail; - set
tail' = (tail + 1) mod N; - set
count' = count + 1; - release only after the item initialization and both metadata updates are complete.
Then and
The arithmetic proof is incomplete without an ownership clause: the new slot must contain a fully initialized item before another thread may observe the increased count. That publication obligation leads directly to memory ordering.
Memory Publication and Lock Ordering Matrix
A queue protects state with lock L. A producer initializes buffer[tail] and increments count while holding L. A consumer reads count without L. Evaluate each statement:
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
A spin lock needs one indivisible winner
Two threads cannot implement a lock with plain “check then set”:
while locked == true:
wait
locked = true
Both can read false before either store. A lock acquisition needs one atomic state transition that says, in effect, “change false to true and tell me whether I was the thread that changed it.” Compare-and-exchange, atomic exchange, load-reserved/store-conditional, and architecture-specific atomic memory operations can supply that transition.
#include <stdatomic.h>
#include <stdbool.h>
typedef struct {
atomic_flag held;
} spinlock;
void spin_lock(spinlock *lock) {
while (atomic_flag_test_and_set_explicit(
&lock->held, memory_order_acquire)) {
/* architecture-specific pause/backoff may reduce contention */
}
}
void spin_unlock(spinlock *lock) {
atomic_flag_clear_explicit(&lock->held, memory_order_release);
}
This fragment establishes one owner and acquire/release ordering under the C abstract machine when the flag is initialized correctly. It does not promise FIFO admission, bounded waiting, reentrancy, interrupt safety, adaptive backoff, or good performance. A production lock also needs an ownership policy, debug behavior, and architecture/runtime integration.
Application — kill a plausible wrong lock. Replace atomic_flag_test_and_set with an atomic load followed by an atomic store. Construct a schedule with two owners.
ScheduleExpandCollapse
The atomicity of each access is insufficient:
- A atomically loads
held == false. - B atomically loads
held == false. - A atomically stores true and enters.
- B atomically stores true and enters.
The winner election must itself be one read-modify-write operation, or a compare-and-exchange loop whose failed contender retries from a fresh observation.
Acquire and release publish a relation
Coherence normally gives each atomic location a consistent modification order. It does not, by itself, require a core that observes a new flag to observe earlier writes to other locations. The language and ISA memory models define the required cross-location order.
In ISO C, the standard publication idiom is:
#include <assert.h>
#include <stdatomic.h>
static int payload;
static atomic_int ready = 0;
void publish(void) {
payload = 42;
atomic_store_explicit(&ready, 1, memory_order_release);
}
void consume(void) {
if (atomic_load_explicit(&ready, memory_order_acquire) == 1) {
assert(payload == 42);
}
}
If the acquire load reads the value from the release sequence, the release synchronizes with it. The payload store is sequenced before the release; the payload load is sequenced after the acquire; transitivity places the store before the load in the happens-before relation. The plain payload accesses therefore do not form a data race in that successful branch.
Replacing both operations on ready with memory_order_relaxed preserves atomic accesses to ready but removes the publication edge for payload. Relaxed order is suitable for a counter whose numeric value is independent, not for announcing that an object graph is initialized.
Code Exercise
Establish an acquire/release publication edge in C11
Complete the memory-order specifiers so that whenever consume() observes ready == 1, the prior non-atomic store payload = 42 is guaranteed to be visible without a data race.
void publish(void) { payload = 42; atomic_store_explicit(&ready, 1, ); } void consume(void) { if (atomic_load_explicit(&ready, ) == 1) { assert(payload == 42); } }
Interrupt-context self-deadlock on a single hart
A kernel thread on hart 0 acquires spin lock rx_lock to dequeue a packet from a driver ring buffer. While rx_lock is held with local interrupts still enabled, the network interface raises an interrupt on hart 0. The interrupt handler runs on hart 0 and calls spin_lock(&rx_lock) to append the newly arrived descriptor.
What is the exact failure mode on hart 0, and which locking protocol prevents it?
Transfer. A statistics counter is incremented with relaxed atomics. A shutdown thread observes the expected count and then frees every worker’s result object. Is the count observation enough to publish those objects?
AnalysisExpandCollapse
No. A relaxed fetch-add makes the counter update atomic and gives that atomic object a modification order, but it does not make preceding ordinary writes to each result happen before the shutdown thread’s reads or frees. Use a joining operation, a release/acquire completion protocol, a mutex/condition predicate, or another mechanism with the required lifetime and visibility guarantees. The exact repair depends on who owns each object and whether workers can still access it.
RISC-V’s RVWMO permits observers on different harts to see memory operations in orders not implied by source order unless preserved-program-order rules, dependencies, acquire/release annotations, atomics, or fences constrain them. The A extension provides atomic read-modify-write and load-reserved/store-conditional instructions. Kernel code should use the kernel’s established primitives; hand-inserting fence instructions without connecting ISA semantics to compiler semantics is not a portable repair.
Spin, block, or redesign
Let be expected wait time, the cost to deschedule and later resume, the lock-hold time, and the number of runnable contenders. Spinning is plausible only when is reliably small, the owner can run, and consuming a CPU for does not violate a stronger objective. Blocking is plausible when may exceed or CPU time must be available to other work.
Let be expected wait time, the cost to deschedule and later resume, the lock-hold time, and the number of runnable contenders. Spinning is plausible only when is reliably small, the owner can run, and consuming a CPU for does not violate a stronger objective. Blocking is plausible when may exceed or CPU time must be available to other work.
| Context | Candidate | Reason | Failure boundary |
|---|---|---|---|
| short non-sleeping kernel section on another running core | spin lock | avoids scheduler path | collapses under long hold or oversubscription |
| user thread waiting on I/O-protected state | blocking mutex | yields CPU while owner/device progresses | sleep/wakeup and priority policy add cost |
| read-mostly immutable snapshot | versioning, RCU, or copy-on-write | readers avoid a global owner | reclamation and update publication become harder |
| high-contention counter | per-CPU/per-shard state | removes one shared cache line | aggregation may be approximate or delayed |
Worked cost comparison. A critical section normally holds a lock for 200 ns but once per 10,000 entries blocks for a 2 ms device operation. The mean hold time is roughly which looks small. A contender arriving during the rare device wait can still burn 2 ms of CPU. The bug is not the average; sleeping while holding a spin lock makes the tail unbounded relative to the intended mechanism. Move the blocking operation outside the section or change the synchronization design.
Spin locks also generate coherence traffic. A naïve exchange loop writes the lock line on every failed attempt, invalidating peer copies. Test-and-test-and-set first spins on read-only loads and attempts the write only when the lock appears free; queue locks arrange local spinning. These designs change traffic and fairness, not the protected invariant.
Kernel context is part of the lock type
If an interrupt handler on one hart can acquire L, ordinary code on that hart cannot hold L while the handler is allowed to preempt it. The handler would spin waiting for an owner that cannot resume. One design disables the relevant local interrupts before acquisition and restores the previous interrupt state after release. Another ensures the handler never takes that lock and defers work to a context that may block.
xv6’s spin-lock path tracks interrupt-disable nesting for this reason. That is an xv6 mechanism under its own assumptions, not evidence that every lock acquisition should globally disable interrupts. Scope, nesting, non-maskable events, preemption, and architecture rules matter.
Counterexample: “one CPU means no race.” A uniprocessor kernel can be preempted by an interrupt, fault, signal delivery path, or scheduler transition between shared-state operations. Disabling preemption may exclude thread interleavings on that CPU but not necessarily device DMA, non-maskable events, or another CPU. State exactly which actors the exclusion covers.
Granularity changes both proof and performance
Suppose a buffer cache has 1,024 buckets. One global lock gives a simple invariant but serializes independent buckets. One lock per bucket permits parallel lookups, but moving an entry from bucket 3 to bucket 8 now touches two protected regions.
Worked two-lock update. Impose the order min(bucket_id) before max(bucket_id). To move 8→3, acquire 3 then 8 despite the source being 8. Revalidate that the entry is still in bucket 8 after both locks are held; another thread may have changed it between the initial lookup and acquisition. Unlink, relink, restore both bucket invariants, then release in either documented order.
Fine-grained locks can introduce:
- a larger proof surface and lock-order graph;
- cross-region operations that need rollback or revalidation;
- false sharing when distinct lock words occupy one cache line;
- memory overhead and initialization/lifetime hazards; and
- starvation if a hot region repeatedly admits local contenders.
The right comparison measures throughput and tail latency against a named workload while retaining invariant checks. “More locks scales better” is not a theorem.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 3.2.1: Ring Buffer Invariant Derivation and Pointer Wraparound
Consider a bounded FIFO queue of capacity protected by mutex Formulate the mathematical invariants governing head, tail, and count modulo Show why updates to count and buffer entries require mutual exclusion.
HintExpandCollapse
Relate head, tail, and count with modulo arithmetic and state slot ownership boundaries.
Worked solutionExpandCollapse
The queue invariant requires:
- When buffer slots at indices for contain valid initialized elements; all other slots are available for allocation.
If a thread enqueues without holding concurrent readers can observe before the buffer slot is written, or concurrent writers can compute the same
tailoffset and overwrite each other’s data, corrupting the modulo relationship and lost elements.
Exercise 3.2.2: Test-and-Set Spinlock Implementation and Interrupt Disabling
Write the C/assembly implementation of acquire() and release() for a basic spinlock using the atomic exchange primitive __sync_lock_test_and_set. Explain why kernel spinlocks must disable local CPU interrupts before spinning.
HintExpandCollapse
Trace the deadlock that occurs if an interrupt handler on the same CPU attempts to acquire the lock.
Worked solutionExpandCollapse
void acquire(struct spinlock *lk) {
push_off(); // disable local CPU interrupts
if (holding(lk))
panic("acquire");
while (__sync_lock_test_and_set(&lk->locked, 1) != 0)
; // spin
__sync_synchronize(); // memory fence (acquire)
lk->cpu = mycpu();
}
void release(struct spinlock *lk) {
if (!holding(lk))
panic("release");
lk->cpu = 0;
__sync_synchronize(); // memory fence (release)
__sync_lock_release(&lk->locked);
pop_off(); // restore interrupt state
}If a CPU core acquires lock with interrupts enabled, a device or timer interrupt can fire on that same CPU. If the interrupt service routine attempts to acquire it will spin waiting for to be released. However, because the interrupted thread holding is frozen on the same CPU, the lock is never released, causing an instantaneous, unrecoverable deadlock.
Exercise 3.2.3: Message Passing Publication with Acquire-Release Fences
A producer thread initializes payload data in array data[0..1023] and sets flag = 1. A consumer thread spins waiting for flag == 1 and then reads data[0..1023]. Describe how modern relaxed hardware can violate correctness without memory barriers, and state the exact placement of release and acquire barriers.
HintExpandCollapse
Explain store buffering and speculative load reordering across memory locations.
Worked solutionExpandCollapse
On weakly-ordered architectures (such as ARM or RISC-V RVWMO), memory stores to independent addresses may drain from the CPU write buffer out of program order. Without barriers, the store flag = 1 may become globally visible in cache while stores to data are still buffered locally. Concurrently, the consumer CPU may speculatively load data before reading flag == 1.
Placement:
- Producer: Store payload into
data; execute a release barrier (atomic_store_explicit(..., memory_order_release)orfence rw, w); storeflag = 1. - Consumer: Load
flagwith an acquire barrier (atomic_load_explicit(..., memory_order_acquire)orfence r, rw); read payload fromdata. This guarantees that all stores preceding the release are visible to any thread that executes the matching acquire.
Exercise 3.2.4: Deadlock Hazard When Acquiring Held Spinlocks in Interrupt Handlers
Identify three independent kernel operations that are strictly prohibited while holding a spinlock in an operating system kernel.
HintExpandCollapse
Consider operations that yield the CPU, sleep, allocate unbounded memory, or cross privilege modes.
Worked solutionExpandCollapse
- Sleeping or blocking: A thread holding a spinlock must never call
sleep(), wait on a condition variable, or perform blocking disk I/O. If the thread sleeps, other CPU cores spinning on that lock waste processor cycles waiting for a sleeping thread, and if a waiting thread runs on the same CPU, deadlocks occur. - Dereferencing unpinned user-space pointers: Accessing unpinned user memory can trigger a demand-paging page fault. If the page fault handler sleeps waiting for disk reads, it violates the rule against sleeping with spinlocks held.
- Enabling interrupts without saving depth: Arbitrarily re-enabling interrupts while inside a nested spinlock critical section exposes the CPU to nested interrupt deadlocks.
Exercise 3.2.5: Replacing Contended Global Spinlocks with Sharded Table Structures
A multi-tenant database server runs on a 64-core system. A global process/connection lookup table protected by a single spinlock experiences severe cache-line bouncing and lock contention under high query rates. Propose a scalable architectural redesign.
HintExpandCollapse
Consider hash partitioning, fine-grained bucket locks, and read-copy-update mechanisms.
Worked solutionExpandCollapse
- Hash sharding: Partition the single global table into independent buckets (e.g., where Each bucket has its own dedicated spinlock and cache-aligned memory boundary to prevent false sharing.
- Read-dominated optimization: If lookups vastly outnumber insertions/deletions, employ a Read-Copy-Update (RCU) or versioned pointer architecture. Readers traverse pointers lock-free without atomic operations or write invalidations. Writers allocate a new node copy, update pointers atomically with release semantics, and defer memory reclamation until a grace period passes.
- Measurable validation: Benchmark throughput and -percentile latency under uniform and skewed zipfian lookup distributions, measuring L1/L2 cache-miss invalidation rates with hardware performance counters.
References & Further Reading
- ISO/IEC JTC1/SC22/WG14, N1570: ISO C11 committee draft, §§5.1.2.4 and 7.17.
- RISC-V International, RVWMO Memory Consistency Model, Version 2.0.
- The Open Group, POSIX.1-2024
pthread_mutex_lock,pthread_mutex_trylock, andpthread_mutex_unlock. - Linux kernel documentation, Linux kernel memory barriers.
- MIT PDOS, xv6: a simple, Unix-like teaching operating system, locking chapter.