Search Knowledge

© 2026 LIBREUNI PROJECT

Operating Systems Engineering/Concurrency and liveness
Page 8 of 29

Interleavings and Atomicity

Execution histories, races, invariants, linearization points, and systematic reasoning about concurrent state.

Lesson briefConcurrency and liveness · 5 h 30 min · 3 outcomes

Required knowledge

  • Processes, threads, and context switches
  • C expressions, pointers, and object lifetime
  • State-machine invariants

Learning outcomes

  • Represent a concurrent execution as events constrained by program order and enumerate its legal sequentially consistent interleavings.
  • Distinguish an atomicity violation, a logical race, and an ISO C data race by the evidence each claim requires.
  • State a shared-state invariant, locate a valid linearization point, and construct a schedule that kills an incorrect implementation.

Assessment target

Given an unseen two- or three-thread implementation, state the invariant, derive the event constraints, enumerate or bound reachable outcomes, identify the first violating event, and defend one repair with a schedule that distinguishes it from a named wrong repair.

Scope boundary

  • Weak-memory executions, lock implementations, and acquire/release ordering are developed in the next lesson.
  • Distributed consistency and failure are outside this shared-memory model.

Two workers dequeue jobs from a shared ring. The queue contains one job. Each worker reads count == 1, each reads the same head slot, and each decrements count. Both return the same job; one real job is executed twice. No instruction failed. The failure exists only in the order formed by individually ordinary instructions.

Concurrency turns time into program input. Correctness must therefore quantify over every execution the scheduler and hardware may permit, not only the order seen in one debugger run.

Freeze the execution model before tracing

Definition 3.1.1History and program order

A history is a finite sequence of invocation, internal, and response events from one or more threads. For each thread TT program order ≺T\prec_T orders that thread’s events as the abstract machine requires. An interleaving is a total order of events that preserves every ≺T\prec_T

This lesson begins with a deliberately strong machine model:

  • one processor instruction completes before the next event in the history;
  • every load sees the most recent preceding store to that location in the total order;
  • a context switch may occur between the primitive events shown in the trace; and
  • no compiler or processor reorders those events.

That is a sequentially consistent trace model, not a claim about C or RISC-V execution. It isolates the scheduling problem. The next lesson adds language-level data-race rules and weak hardware ordering.

Code
hide footbox
participant "thread A" as A
participant "shared counter" as M
participant "thread B" as B
A -> M : load counter → rA = 0
M -> B : load counter → rB = 0
A -> A : rA = rA + 1
B -> B : rB = rB + 1
A -> M : store rA → counter = 1
B -> M : store rB → counter = 1
note over A,B
Program order is preserved inside each lifeline.
The cross-thread order loses one update.
end note
thread Ashared counterthread Bthread Ashared counterthread Bload counter → rA = 0load counter → rB = 0rA = rA + 1rB = rB + 1store rA → counter = 1store rB → counter = 1Program order is preservedinside each lifeline.The cross-thread order loses oneupdate.

Retrieval — answer before expanding. If thread A has three ordered events and thread B has three ordered events, how many six-event interleavings preserve both threads’ program order?

DerivationExpand

Choose which three of the six positions belong to A; B occupies the rest. The count is

(63)=6!3!3!=20.\binom{6}{3}=\frac{6!}{3!3!}=20.

This counts schedules, not distinct final states. Several schedules may produce the same state, and synchronization can make many schedules observationally equivalent.

For event sequences of lengths mm and nn the same argument gives (m+nm)\binom{m+n}{m} With three threads, the multinomial coefficient grows quickly. Exhaustive reasoning is still practical for a reduced state machine; it is not practical if every source statement is treated as one indivisible event without justification.

An increment is a protocol, not a glyph

Suppose counter initially equals 0 and each thread evaluates counter++. In the trace model, expand the expression into load, local add, and store:

EventThread A stateThread B stateShared counter
initialrA = —rB = —0
A loadsrA = 0rB = —0
B loadsrA = 0rB = 00
A addsrA = 1rB = 00
B addsrA = 1rB = 10
A storesrA = 1rB = 11
B storesrA = 1rB = 11

The intended postcondition is counter == 2. The first five events leave a recoverable state: a remaining store might still produce 2 only if it were derived from 1. The final store commits a stale value and makes the intended postcondition unreachable in this history. That store is the first event at which the completed-operation count and shared counter cannot be reconciled.

Prediction — do not move the slider yet. In the lost-update schedule, after both loads and both local additions but before either store, is the invariant already false? State which invariant you are using.

Interactive exploration

Find the lost update in an interleaving

Both threads execute counter++. Scrub one memory-relevant operation at a time; then compare an unsafe schedule, serialized critical sections, and an atomic read-modify-write.

Step 0 of 6 · counter = 0

Thread A

rA = counter;
rA = rA + 1;
counter = rA;
atomic_fetch_add(&counter, 1);

Register rA: not loaded

Thread B

rB = counter;
rB = rB + 1;
counter = rB;
atomic_fetch_add(&counter, 1);

Register rB: not loaded

Shared memory
0
counter

No instruction has executed.

Find the lost update in an interleaving

Thread A

rA = counter;
rA = rA + 1;
counter = rA;
atomic_fetch_add(&counter, 1);

Register rA: 1

Thread B

rB = counter;
rB = rB + 1;
counter = rB;
atomic_fetch_add(&counter, 1);

Register rB: 1

Shared memory
1
counter
Invariant fails: one increment was lost

The unsafe schedule finishes both increments with counter = 1 because each thread stores a value derived from the same stale read.

Transfer. Change the initial counter to 9 and replace A’s increment with counter += 2 while B still adds 1. Construct a legal six-event history ending in 10, one ending in 11, and the serialized history ending in 12.

Transfer traceExpand
  • Final 10: A and B both load 9; A computes 11; B computes 10; A stores 11; B stores 10.
  • Final 11: use the same stale reads but let B store 10 before A stores 11.
  • Final 12: A completes load/add/store first, then B loads 11 and stores 12; or B completes first and A subsequently loads 10 and stores 12.

The first answer to the prediction depends on the invariant. counter == completed increments still holds before either operation responds because neither increment has completed. A stronger implementation invariant such as “each local pending update was derived from a distinct logical version” is already violated when both loads observe version 0. State which layer of correctness the invariant describes.

Name the failure precisely

TermRequired evidenceWhat it does not imply
race conditioncorrectness depends on relative timing or orderingthat two accesses target the same byte
atomicity violationa multi-event operation is observed in a state inconsistent with its required indivisible effectthat the implementation language declares undefined behavior
ISO C data raceconflicting actions in different threads, at least one non-atomic, without a happens-before relationthat the only possible symptom is a lost update
determinism failurethe specified observable result varies across allowed executionsthat the result is incorrect; nondeterminism may be intentional

In ISO C, a data race has undefined behavior. The sequentially consistent lost-update table is therefore a useful abstract diagnosis, not a list of the only outcomes a real racy C program may exhibit. The compiler is not required to preserve an intuitive interleaving for a program outside the language contract.

volatile does not repair the program. In C it constrains accesses to volatile objects for implementation-defined observable behavior such as device registers; it neither combines load/add/store into one atomic action nor creates inter-thread synchronization. A volatile int counter can still lose updates, and a C data race on it still has undefined behavior.

Application. Classify each case and justify the minimum claim:

  1. Two threads use an atomic fetch-add; the final count is correct, but which thread receives ticket 0 varies.
  2. Two C threads write a plain int flag without synchronization, even though both write 1.
  3. A thread checks access(path, W_OK) and later opens the pathname after another process replaces the directory entry.
ClassificationExpand
  1. The result may be nondeterministic without an atomicity violation or data race. Each fetch-add can still have one indivisible place in the order.
  2. The writes conflict, are non-atomic, and lack happens-before; this is an ISO C data race even if a particular machine appears to store the same value twice.
  3. This is a time-of-check/time-of-use race. The pathname can name a different object at use time. The relevant repair is an interface that binds checking and use to one kernel object or directory-relative handle—not a mutex private to one process.

Concurrent Access Classification Matrix

0 / 4 answered

Thread T loads a shared counter with atomic_load while Thread U concurrently executes atomic_fetch_add on the same variable. Evaluate each classification:

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

1
An atomicity violation occurs because the read access can observe a torn intermediate half-written integer value.
2
Reading either the pre-increment or post-increment value reflects valid concurrency nondeterminism, not an error.
3
Concurrent execution constitutes an ISO C data race because two threads access one memory location without mutexes.
4
Each atomic access executes indivisibly at a single linearization point, producing a legally serialized history.

Invariants turn schedules into proof obligations

An invariant is a predicate that must hold at designated observable states. It is stronger than “the test passed” and more useful than “the code is thread-safe.”

For a bounded queue with capacity NN useful clauses include:

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

plus ownership clauses stating which slots contain initialized jobs and when a returned job stops belonging to the queue. The arithmetic catches overflow and duplicate removal; the ownership clause catches returning a pointer whose slot another producer may overwrite.

Worked trace: duplicate dequeue. Let head = 4, count = 1, and slot 4 contain job J. Workers A and B each perform if (count > 0) { j = ring[head]; head++; count--; } without synchronization.

  1. A and B both test count > 0.
  2. Both read slot 4 and obtain J.
  3. A updates head = 5, count = 0.
  4. B uses stale local values and also publishes head = 5, count = 0.

The numeric invariant still holds. The abstraction invariant fails because one abstract queue element produced two successful dequeue responses. A correct invariant must connect representation state to operation history, not merely bound integers.

Definition 3.1.2Linearizability

A concurrent history is linearizable when each completed operation can be assigned one point between its invocation and response so that the resulting sequential order (1) obeys the object’s sequential specification and (2) preserves real-time order for non-overlapping operations.

The assigned point is a linearization point. For an atomic fetch-add, it is the successful atomic read-modify-write. For a lock-protected enqueue, it may be the pointer or count update that makes the new item reachable while the lock excludes observers. “Somewhere inside the function” is not enough: name an event and prove every allowed observer sees a history consistent with it.

Counterexample: the response is not always the point. A queue operation may link a node, then spend time reclaiming metadata before returning. A concurrent dequeue can observe the node during that interval. Linearizing enqueue at its response would put dequeue before enqueue in the sequential order even though dequeue returned the new node. The publication store—not the later return—is the candidate point.

Reduce the state space without deleting behavior

Code
start
:Write the sequential specification;
:Choose one shared-state invariant;
:Split each operation at shared-memory or blocking events;
:Add program-order constraints;
if (Synchronization orders two events?) then (yes)
:Add the happens-before edge;
else (no)
:Explore both legal relative orders;
endif
:Merge states only when future observations are equivalent;
:Check invariant and operation responses;
stop
Write the sequentialspecificationChoose one shared-stateinvariantSplit each operation atshared-memory or blockingeventsAdd program-order constraintsSynchronization orders twoevents?yesnoAdd the happens-before edgeExplore both legal relativeordersMerge states only when futureobservations are equivalentCheck invariant and operationresponses

Treat local arithmetic with no shared observation as one event. Split at loads, stores, atomic operations, lock operations, waits, wakeups, and externally visible responses. This reduction is valid only when the merged local steps cannot block, fault in a relevant way, call unknown code, or expose state through a signal or callback.

Worked search. Two one-slot exchanger operations each execute publish(value) then take(peer). If publish and take are atomic abstract events, there are six interleavings of two two-event threads. Four schedules let both publish before either take and can succeed. Two schedules attempt a take before the peer publication. Whether those block, fail, or read “empty” is part of the sequential specification; deleting that choice from the model would assume the result.

Random stress can discover a violating schedule but cannot establish that no schedule exists. A useful concurrency test harness controls one uncertainty at a time:

  • barriers place threads at a chosen boundary;
  • a deterministic scheduler selects the next event;
  • an invariant checker runs after every event in the reduced model;
  • a history recorder captures invocation and response order; and
  • a test oracle checks whether the observed history admits a legal sequentialization.

Dynamic race detectors answer a different question: whether an execution contains unsynchronized conflicting memory accesses under their model. They can miss unexecuted races and cannot prove a higher-level queue or filesystem protocol correct.

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.1.1: Counting Legal Interleavings for Concurrent Instructions

Verificationapplication

Two threads each execute an instruction sequence: Thread 1 executes mm sequential instructions, and Thread 2 executes nn sequential instructions. Derive the total number of distinct interleaved instruction execution histories, and evaluate this count for m=3m = 3 and n=3n = 3

HintExpand

Recall combinations of m steps chosen from m + n total positions.

Worked solutionExpand

Any valid interleaving is a sequence of length m+nm + n where mm steps belong to Thread 1 and nn steps belong to Thread 2, preserving their respective intra-thread program orders. The total number of distinct interleavings is given by the binomial coefficient:

(m+nm)=(m+n)!m! n!.\binom{m + n}{m} = \frac{(m + n)!}{m! \, n!}.

For m=3m = 3 and n=3n = 3

(63)=6×5×43×2×1=20 distinct interleavings.\binom{6}{3} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20 \text{ distinct interleavings.}

Even for very short code sequences, testing a few arbitrary thread orders explores only a small fraction of the possible interleaving space.

Exercise 3.1.2: Lost-Update History for Non-Atomic Fetch-Add

Constructionapplication

Two threads concurrently execute counter++ on a shared integer initialized to 0. In assembly, each increment consists of: L: load r, [counter]; A: add r, r, 1; S: store [counter], r. Construct an interleaving schedule of these 6 operations that produces a final counter value of 1 instead of 2.

HintExpand

Interleave the loads so both threads read the initial value 0 before either stores.

Worked solutionExpand

Schedule:

  1. T1T_1 L   ⟹  r1=0\implies r_1 = 0
  2. T2T_2 L   ⟹  r2=0\implies r_2 = 0
  3. T1T_1 A   ⟹  r1=1\implies r_1 = 1
  4. T1T_1 S   ⟹  counter=1\implies \text{counter} = 1
  5. T2T_2 A   ⟹  r2=1\implies r_2 = 1
  6. T2T_2 S   ⟹  counter=1\implies \text{counter} = 1 Both threads read the initial value 0. T2T_2‘s store overwrites T1T_1‘s update with the identical value 1, resulting in a classic lost update anomaly.

Exercise 3.1.3: Check-Then-Act Race Condition in Naive Lock-Free Allocator

Descriptiontransfer

An engineer replaces a mutex-protected free list with atomic operations: if (atomic_load(&head) != NULL) { block = atomic_load(&head); atomic_store(&head, block->next); return block; }. Demonstrate an interleaving where two concurrent threads allocate and return the exact same memory block.

HintExpand

Trace two threads executing the atomic loads concurrently before either performs the atomic store.

Worked solutionExpand

Assume the free list contains two blocks: X→Y→NULLX \to Y \to \mathrm{NULL}

  1. Thread AA executes atomic_load(&head): observes X≠NULLX \ne \mathrm{NULL}
  2. Thread BB executes atomic_load(&head): observes X≠NULLX \ne \mathrm{NULL}
  3. Thread AA executes block_A = atomic_load(&head): receives pointer to XX
  4. Thread BB executes block_B = atomic_load(&head): receives pointer to XX
  5. Thread AA executes atomic_store(&head, block_A->next): updates head to YY and returns XX
  6. Thread BB executes atomic_store(&head, block_B->next): updates head to YY and returns XX Both threads return block XX simultaneously, violating allocator uniqueness and corrupting application memory. Making individual loads and stores atomic does not make the compound multi-step protocol atomic.

Exercise 3.1.4: Time-of-Check to Time-of-Use Pathname Races

Verificationtransfer

A setuid root utility checks file permissions: if (access(path, W_OK) == 0) { fd = open(path, O_WRONLY); write(fd, data, len); }. Construct an adversarial race condition that allows an unprivileged user to overwrite /etc/passwd.

HintExpand

Exploit the time gap between access() and open() by substituting a symlink.

Worked solutionExpand

The time gap between access() (check) and open() (act) creates a Time-of-Check to Time-of-Use (TOCTOU) vulnerability.

  1. The unprivileged user creates a harmless temporary file /tmp/target that they own.
  2. The user runs the privileged program passing path = "/tmp/target".
  3. The kernel executes access("/tmp/target", W_OK). Because the user owns the file, access() returns 0 (permission granted).
  4. Before open() executes, the user process rapidly replaces /tmp/target with a symbolic link: unlink("/tmp/target"); symlink("/etc/passwd", "/tmp/target");.
  5. The privileged utility calls open("/tmp/target", O_WRONLY). The kernel follows the symlink with root privileges, opening /etc/passwd and truncating or overwriting critical system data. Repair: Avoid path-based check-then-act sequences; use file descriptor handles and open(..., O_NOFOLLOW | O_CREAT) with dropped privileges.

Exercise 3.1.5: Designing Compare-and-Swap Loops with Linearization Points

Constructionsynthesis

Design a correct concurrent stack push() operation using an atomic compare-and-swap primitive (atomic_compare_exchange_weak). Identify the exact linearization point of the operation and explain how failure retries preserve safety.

HintExpand

Snapshot the current top pointer and retry if another thread modified it before the swap.

Worked solutionExpand
struct Node {
    void *data;
    struct Node *next;
};

void push(atomic_ptr *top, struct Node *new_node) {
    struct Node *old_top = atomic_load(top);
    do {
        new_node->next = old_top;
    } while (!atomic_compare_exchange_weak(top, &old_top, new_node));
}

Linearization point: The single clock cycle where atomic_compare_exchange_weak succeeds. At that precise instant, top transitions from old_top to new_node, making new_node atomically visible to all concurrent push and pop operations. If another thread prepends a node in the interim, the CAS returns false, updates old_top with the new value, and repeats the loop without modifying shared memory, guaranteeing safety.

References & Further Reading