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
A history is a finite sequence of invocation, internal, and response events from one or more threads. For each thread program order orders that thread’s events as the abstract machine requires. An interleaving is a total order of events that preserves every
A history is a finite sequence of invocation, internal, and response events from one or more threads. For each thread program order orders that thread’s events as the abstract machine requires. An interleaving is a total order of events that preserves every
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.
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?
DerivationExpandCollapse
Choose which three of the six positions belong to A; B occupies the rest. The count is
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 and the same argument gives 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:
| Event | Thread A state | Thread B state | Shared counter |
|---|---|---|---|
| initial | rA = — | rB = — | 0 |
| A loads | rA = 0 | rB = — | 0 |
| B loads | rA = 0 | rB = 0 | 0 |
| A adds | rA = 1 | rB = 0 | 0 |
| B adds | rA = 1 | rB = 1 | 0 |
| A stores | rA = 1 | rB = 1 | 1 |
| B stores | rA = 1 | rB = 1 | 1 |
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.
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.
Thread A
Register rA: not loaded
Thread B
Register rB: not loaded
No instruction has executed.
Thread A
Register rA: 1
Thread B
Register rB: 1
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 traceExpandCollapse
- 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
| Term | Required evidence | What it does not imply |
|---|---|---|
| race condition | correctness depends on relative timing or ordering | that two accesses target the same byte |
| atomicity violation | a multi-event operation is observed in a state inconsistent with its required indivisible effect | that the implementation language declares undefined behavior |
| ISO C data race | conflicting actions in different threads, at least one non-atomic, without a happens-before relation | that the only possible symptom is a lost update |
| determinism failure | the specified observable result varies across allowed executions | that 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:
- Two threads use an atomic fetch-add; the final count is correct, but which thread receives ticket 0 varies.
- Two C threads write a plain
int flagwithout synchronization, even though both write 1. - A thread checks
access(path, W_OK)and later opens the pathname after another process replaces the directory entry.
ClassificationExpandCollapse
- The result may be nondeterministic without an atomicity violation or data race. Each fetch-add can still have one indivisible place in the order.
- 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.
- 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
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.
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 useful clauses include:
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.
- A and B both test
count > 0. - Both read slot 4 and obtain J.
- A updates
head = 5,count = 0. - 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.
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.
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
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.
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
Two threads each execute an instruction sequence: Thread 1 executes sequential instructions, and Thread 2 executes sequential instructions. Derive the total number of distinct interleaved instruction execution histories, and evaluate this count for and
HintExpandCollapse
Recall combinations of m steps chosen from m + n total positions.
Worked solutionExpandCollapse
Any valid interleaving is a sequence of length where steps belong to Thread 1 and steps belong to Thread 2, preserving their respective intra-thread program orders. The total number of distinct interleavings is given by the binomial coefficient:
For and
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
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.
HintExpandCollapse
Interleave the loads so both threads read the initial value 0 before either stores.
Worked solutionExpandCollapse
Schedule:
-
L -
L -
A -
S -
A -
SBoth threads read the initial value 0. ‘s store overwrites ‘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
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.
HintExpandCollapse
Trace two threads executing the atomic loads concurrently before either performs the atomic store.
Worked solutionExpandCollapse
Assume the free list contains two blocks:
- Thread executes
atomic_load(&head): observes - Thread executes
atomic_load(&head): observes - Thread executes
block_A = atomic_load(&head): receives pointer to - Thread executes
block_B = atomic_load(&head): receives pointer to - Thread executes
atomic_store(&head, block_A->next): updatesheadto and returns - Thread executes
atomic_store(&head, block_B->next): updatesheadto and returns Both threads return block 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
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.
HintExpandCollapse
Exploit the time gap between access() and open() by substituting a symlink.
Worked solutionExpandCollapse
The time gap between access() (check) and open() (act) creates a Time-of-Check to Time-of-Use (TOCTOU) vulnerability.
- The unprivileged user creates a harmless temporary file
/tmp/targetthat they own. - The user runs the privileged program passing
path = "/tmp/target". - The kernel executes
access("/tmp/target", W_OK). Because the user owns the file,access()returns 0 (permission granted). - Before
open()executes, the user process rapidly replaces/tmp/targetwith a symbolic link:unlink("/tmp/target"); symlink("/etc/passwd", "/tmp/target");. - The privileged utility calls
open("/tmp/target", O_WRONLY). The kernel follows the symlink with root privileges, opening/etc/passwdand truncating or overwriting critical system data. Repair: Avoid path-based check-then-act sequences; use file descriptor handles andopen(..., O_NOFOLLOW | O_CREAT)with dropped privileges.
Exercise 3.1.5: Designing Compare-and-Swap Loops with Linearization Points
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.
HintExpandCollapse
Snapshot the current top pointer and retry if another thread modified it before the swap.
Worked solutionExpandCollapse
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
- Maurice Herlihy and Jeannette Wing, “Linearizability: A Correctness Condition for Concurrent Objects”, ACM Transactions on Programming Languages and Systems, 1990.
- ISO/IEC JTC1/SC22/WG14, N1570: ISO C11 committee draft, especially §§5.1.2.4 and 6.7.3.
- Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces, concurrency chapters.
- MIT PDOS, xv6: a simple, Unix-like teaching operating system, Chapter 6/7 “Locking” in the linked revision.