Unit 2.4 · about 3 h
243 / 324Data races, lost updates and lost wakeups
Programming's synchronization-hazards unit showed a lost update behind a barrier and a lock-order deadlock in Python. Here the same defects move to C pthreads, where a data race is undefined behavior and only the sanitizer or a controlled schedule counts as evidence. It assumes that unit as background and never reuses its barrier demo.
- explain
- measure
You can now
- Separate a data race (unsynchronized access, undefined behavior in C) from a race condition (order-dependent wrong result) with an example of each.
- Reproduce a lost update and a lost wakeup on demand, and show the sanitizer report that convicts the first.
- Measure a racy counter across repeated runs and explain why no single run states the rule.
Covers
- Data races, race conditions and lost updates
- Lost wakeups and condition synchronization defects
Study, in this order
5 steps
- Non-deadlock bugsOperating Systems: Three Easy Pieces - concurrency
Sections 32.1 and 32.2: atomicity violations and order violations with the before and after code
- Race Conditions and Critical SectionsAlgoMaster Concurrency lessons
Common Race Condition Patterns (read-modify-write, check-then-act, combining thread-safe operations); Race Condition vs Data Race
- Lost Signal / WakeupAlgoMaster Concurrency lessons
What is a Lost Signal; Common Scenarios That Cause Lost Signals; How to Prevent Lost Signals
Depth · Read the scenarios; the while-loop proof is the locks unit.
- Spurious WakeupAlgoMaster Concurrency lessons
What is a Spurious Wakeup; Why Spurious Wakeups Exist; Correct Handling Patterns
- Spurious wakeups in the cond contractLinux man-pages: pthreads and futex
pthread_cond_waitpage: spurious wakeups and why the predicate must be re-checked
Focus on
- A data race is a property of two accesses; a race condition is a property of an outcome. The synchronized-map get-then-put has no data race and still loses updates.
- gcc 15.2
-O2compiles a plain-global increment loop into oneaddq $2000000per thread, so the classic demo printed the exact total of 4000000 in five of five runs on an i9-12900K with Linux 7.0. The race is still there: TSan reports a read and write on globalcountin the same build. volatilerestores per-iteration accesses, so the demo loses updates again (twelve runs landed between 2.0 and 2.32 million, never 4000000), butvolatileadds no atomicity or ordering. It is a measurement harness, not a fix.- A condition signal with no waiter is lost, and a wait may return spuriously. Both force the same discipline: wait in a while loop over shared state.
Reproduce closed-book
-O2 -pthread: record five runs printing 4000000, then rebuild with -fsanitize=thread and keep the data-race report naming global count. Then build the volatile variant and record six runs, none reaching 4000000. State CPU, kernel, compiler, flags, repeat counts and warm caches with every number.Traps
- An exact total is not a proof. Optimization level, core placement and timing move the number; only TSan or a forced schedule settles existence.
- Removing the data race does not remove the race condition. Locking each map access still loses the get-then-put update; the sequence needs one critical section.
- Sleep-timed reproduction is not deterministic. A passing sleep-timed run can miss the schedule; barriers and sleep-string shims force it.
Practice
OSTEP thread API homework: `main-race` under ThreadSanitizer, plus signal ordering
threads-api folder: build main-race.c with gcc -g -pthread -fsanitize=thread and keep the race report; then compare main-signal.c with main-signal-cv.c
The README uses valgrind's helgrind; ThreadSanitizer, built into gcc and clang, reports the same race. Answer the README questions with whichever detector you have.
Self-test
-
The plain counter prints 4000000 five times and TSan reports a race. Which result is the finding?
The TSan report. The total is one schedule plus one optimization; the race exists on every run regardless of the printed number. -
Can a TSan-clean program still have a race condition? Give the example.
Yes. Individually locked get and put on a shared map compose a lost update with no unsynchronized access. Zero data races do not imply a correct sequence. -
Why is
volatilethe wrong fix for the racy counter?It restores per-iteration memory traffic so updates interleave visibly, but concurrent read-modify-write stays a data race: still undefined behavior and still lost updates, now merely observable. -
A signal sent before any waiter is lost. Which two mechanisms prevent the loss?
A predicate re-checked in a while loop, so a thread sleeps only while the state says so; and designs where the state change itself is observable, such as sequence counters or close flags, rather than the bare signal.
Completion criterion
Stop when
You can produce a wrong total, a TSan report and a lost signal on demand, and explain why each proves something different.
Mark passed, then open 2.5 Only mark this when you can do it without notes.Leads to
- 2.5 Deadlock, livelock, starvation and priority inversion Races break safety one access at a time; deadlock breaks liveness for the whole program.
- 2.8 Deterministic schedules, stress tests and contention Randomized stress turns one observed schedule into quantified flakiness.
Comes after
- 2.1 Threads, interleavings and memory consistencyLost updates are the first race this vocabulary predicts.
- 2.3 Atomic operations, compare-and-swap and memory orderingA failed CAS is a detected race; an unsynchronized read-modify-write is a silent one.
Resources for this unit
- Operating Systems: Three Easy Pieces - concurrency Read Chapters 26-33 in order: threads, thread API, locks, locked data structures, condition variables, semaphores, bugs and event-based concurrency. Write the safety and liveness invariant before reading each worked pattern.
- AlgoMaster Concurrency lessons Use the named lessons only: Processes vs Threads, Race Conditions and Critical Sections, Mutex, Condition Variables, Compare-And-Swap, Atomic Operations, Semaphores, Producer-Consumer Pattern, Bounded Buffer, Design Thread-Safe Blocking Queue, Barriers and Latches, Read-Write Locks, Coarse-grained vs Fine-grained Locking, Deadlock, Livelock, Starvation, Priority Inversion, Lost Signal/Wakeup, Spurious Wakeup, Concurrency Models and Thread Pool Pattern. Each unit names its lessons; read no other chapter for this section.
- Linux man-pages: pthreads and futex Look up the exact pthread mutex, condition variable, barrier, cancellation and timed-wait contracts plus futex(2) and pthreads(7). Read the stated pages; do not browse the whole manual.
Also in this section
- OSTEP concurrency homework and code Use x86.py and the main, vector, condition-variable and semaphore exercises to enumerate schedules. Preserve one lost update, one deadlock and one lost wakeup as minimized tests, then repair each invariant.
- AlgoMaster Concurrency - four bounded contracts Attempt Design a Closable Bounded Queue, Design Thread-Safe Rate Limiter, Design a Deadlock-Free Two-Key Executor, Design an Atomic Maximum With Compare-and-Swap, Design Deferred Callback Executor and Design Task Scheduler with Dependencies. For each, add a changed input, a deterministic failure schedule and an independent stress test outside the platform.
- MIT 6.1810 - locks and parallelism Use Lectures 12-14 and one lock-lab exercise only after the user-space bounded queue passes. Measure the contention change and explain the invariant preserved by the revised locking scheme.
- cppreference: C atomic operations Read
atomic_compare_exchangefor success and failure semantics and the expected-pointer update rule, andmemory_orderfor the six orderings and what relaxed permits. Stop before lock-free-property macros. - GCC __atomic builtins Read
__atomic_compare_exchange,__atomic_loadand__atomic_storefor the expected-pointer update rule and the__ATOMIC_RELAXEDconstant used by the CAS reproduce step. - The Little Book of Semaphores Use the rendezvous, barrier and reader-writer puzzles as extra semaphore practice after OSTEP Chapter 31. Skip the Python event material; this section works in C with pthreads.