Search Knowledge

© 2026 LIBREUNI PROJECT

Operating Systems Engineering/Concurrency and liveness
Page 9 of 29

Locks, Atomics, and Memory Ordering

Mutual exclusion, acquire/release visibility, spin and blocking locks, interrupt context, and lock-invariant proofs.

Lesson briefConcurrency and liveness · 6 h · 4 outcomes

Required knowledge

  • Interleavings and atomicity
  • C object and pointer semantics
  • Caches and multicore coherence

Learning outcomes

  • Derive a lock's safety obligation from a protected invariant and prove that acquire/use/release preserves it.
  • Explain the distinct roles of atomicity, coherence, and acquire/release ordering in a publication protocol.
  • Choose between spinning, blocking, and finer-grained locking under explicit wait-time, context, fairness, and contention assumptions.
  • Diagnose interrupt, preemption, lock-order, and false-sharing failures from an execution trace.

Assessment target

Given an unfamiliar kernel critical section and a weak-memory execution, state the protected invariant, identify missing atomicity or ordering edges, select a context-safe lock design, and give both a preservation argument and a contention counterexample.

Scope boundary

  • Lock-free memory reclamation, full ISO C memory-model formalism, and architecture-specific litmus tooling require later specialist study.
  • Condition variables, semaphores, and deadlock protocols are developed in the following lessons.

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

Definition 3.2.1Protected invariant

For a lock LL the protected invariant ILI_L is a predicate over shared state that may be temporarily false only while one thread owns LL Every acquisition may assume ILI_L every release must publish a state satisfying ILI_L

Consider a queue represented by head, tail, and count with capacity NN

0≤count≤N,tail≡head+count(modN).0 \le count \le N, \qquad tail \equiv head + count \pmod N.

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.

Code
state "outside critical section\nI_L must hold" as Outside
state "L acquired\nexclusive authority" as Owned
state "representation update\nI_L may be transiently false" as Updating
state "restored representation\nI_L holds" as Restored
Outside --> Owned : acquire(L)
Owned --> Updating : first dependent mutation
Updating --> Restored : final invariant-restoring mutation
Restored --> Outside : release(L) publishes writes
Updating --> Outside : release too early / exception
note on link
invalid transition:
other acquirer observes broken state
end note
outside critical sectionI_L must holdL acquiredexclusive authorityrepresentation updateI_L may be transiently falserestored representationI_L holdsacquire(L)first dependentmutationfinal invariant-restoringmutationrelease(L) publisheswritesrelease too early /exceptioninvalid transition:other acquirer observes brokenstate

Retrieval. Why is “only one thread executes this function” weaker than a queue correctness proof?

AnswerExpand

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 ILI_L 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 0≤count<N0 \le count < N and tail == (head + count) mod N. Under exclusive ownership:

  1. write the item into slot tail;
  2. set tail' = (tail + 1) mod N;
  3. set count' = count + 1;
  4. release only after the item initialization and both metadata updates are complete.

Then 0<count′≤N0 < count' \le N and

tail′≡tail+1≡head+count+1≡head+count′(modN).tail' \equiv tail+1 \equiv head+count+1 \equiv head+count' \pmod N.

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

0 / 4 answered

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.

1
Acquire and release memory semantics establish visibility edges only between threads synchronizing on the same lock.
2
Reading an integer memory location without holding a mutual exclusion lock triggers a CPU hardware machine check.
3
Without acquiring lock L, the consumer can observe updated count > 0 before buffer initialization stores arrive.
4
A concurrent unsynchronized read of count causes the producer thread release operation to deadlock permanently.

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.

ScheduleExpand

The atomicity of each access is insufficient:

  1. A atomically loads held == false.
  2. B atomically loads held == false.
  3. A atomically stores true and enters.
  4. 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.

Code
hide footbox
participant "producer core" as P
participant "payload cache line" as D
participant "ready atomic" as F
participant "consumer core" as C
P -> D : ordinary store payload = 42
P -> F : release-store ready = 1
F -> C : acquire-load reads 1
D -> C : subsequent load must observe\npayload publication under C rules
note over P,C
The release/acquire pair supplies an ordering edge.
Atomicity of ready alone does not publish payload.
end note
producer corepayload cache lineready atomicconsumer coreproducer corepayload cache lineready atomicconsumer coreordinary store payload= 42release-store ready = 1acquire-load reads 1subsequent load mustobservepayload publicationunder C rulesThe release/acquire pair suppliesan ordering edge.Atomicity of ready alone doesnot publish payload.

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

2 tokens to supply

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?

AnalysisExpand

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

Definition 3.2.2Lock acquisition cost model

Let WW be expected wait time, SS the cost to deschedule and later resume, HH the lock-hold time, and PP the number of runnable contenders. Spinning is plausible only when WW is reliably small, the owner can run, and consuming a CPU for WW does not violate a stronger objective. Blocking is plausible when WW may exceed SS or CPU time must be available to other work.

ContextCandidateReasonFailure boundary
short non-sleeping kernel section on another running corespin lockavoids scheduler pathcollapses under long hold or oversubscription
user thread waiting on I/O-protected stateblocking mutexyields CPU while owner/device progressessleep/wakeup and priority policy add cost
read-mostly immutable snapshotversioning, RCU, or copy-on-writereaders avoid a global ownerreclamation and update publication become harder
high-contention counterper-CPU/per-shard stateremoves one shared cache lineaggregation 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 0.9999(200 ns)+0.0001(2 ms)≈400 ns0.9999(200\text{ ns})+0.0001(2\text{ ms}) \approx 400\text{ ns} 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

Code
hide footbox
participant "thread on hart 0" as T
participant "interrupt controller" as C
participant "handler on hart 0" as I
T -> T : acquire L; enter critical section
C -> I : preempt thread with interrupt
I -> T : attempt acquire L
T --> I : owner cannot resume to release L
I -> I : spins forever on the same hart
note over T,I
Self-deadlock unless the interrupt is masked,
deferred, or forbidden from acquiring L.
end note
thread on hart 0interrupt controllerhandler on hart 0thread on hart 0interrupt controllerhandler on hart 0acquire L; enter criticalsectionpreempt thread withinterruptattempt acquire Lowner cannot resume torelease Lspins forever on thesame hartSelf-deadlock unless theinterrupt is masked,deferred, or forbidden fromacquiring L.

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.

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 3.2.1: Ring Buffer Invariant Derivation and Pointer Wraparound

Formalisationapplication

Consider a bounded FIFO queue of capacity NN protected by mutex LL Formulate the mathematical invariants governing head, tail, and count modulo NN Show why updates to count and buffer entries require mutual exclusion.

HintExpand

Relate head, tail, and count with modulo arithmetic and state slot ownership boundaries.

Worked solutionExpand

The queue invariant ILI_L requires:

  1. 0≤count≤N0 \le count \le N
  2. tail≡(head+count)(modN)tail \equiv (head + count) \pmod N
  3. When count>0count > 0 buffer slots at indices (head+i)(modN)(head + i) \pmod N for 0≤i<count0 \le i < count contain valid initialized elements; all other N−countN - count slots are available for allocation. If a thread enqueues without holding LL concurrent readers can observe count>0count > 0 before the buffer slot is written, or concurrent writers can compute the same tail offset 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

Constructionapplication

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.

HintExpand

Trace the deadlock that occurs if an interrupt handler on the same CPU attempts to acquire the lock.

Worked solutionExpand
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 LL with interrupts enabled, a device or timer interrupt can fire on that same CPU. If the interrupt service routine attempts to acquire LL it will spin waiting for LL to be released. However, because the interrupted thread holding LL 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

Descriptiontransfer

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.

HintExpand

Explain store buffering and speculative load reordering across memory locations.

Worked solutionExpand

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) or fence rw, w); store flag = 1.
  • Consumer: Load flag with an acquire barrier (atomic_load_explicit(..., memory_order_acquire) or fence r, rw); read payload from data. 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

Verificationtransfer

Identify three independent kernel operations that are strictly prohibited while holding a spinlock in an operating system kernel.

HintExpand

Consider operations that yield the CPU, sleep, allocate unbounded memory, or cross privilege modes.

Worked solutionExpand
  1. 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.
  2. 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.
  3. 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

Constructionsynthesis

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.

HintExpand

Consider hash partitioning, fine-grained bucket locks, and read-copy-update mechanisms.

Worked solutionExpand
  1. Hash sharding: Partition the single global table into KK independent buckets (e.g., K=256K = 256 where K≥number of coresK \ge \text{number of cores} Each bucket has its own dedicated spinlock and cache-aligned memory boundary to prevent false sharing.
  2. 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.
  3. Measurable validation: Benchmark throughput and 99th99\text{th}-percentile latency under uniform and skewed zipfian lookup distributions, measuring L1/L2 cache-miss invalidation rates with hardware performance counters.

References & Further Reading