Unit 2.1 · about 3 h
240 / 324Threads, interleavings and memory consistency
Programming's asyncio queues and TaskGroup assume threads and tasks already exist. This unit goes one level down to the mechanism they rest on: preemptive scheduling of threads over shared memory. It assumes programming/concurrency-profiling-operations concurrency-models-gil as background and does not re-teach async tasks.
- explain
You can now
- Explain how threads share an address space while processes isolate state, and what that sharing exposes to scheduling.
- Enumerate the legal interleavings of a two-thread increment and name the schedules that lose an update.
- Define atomicity, visibility and ordering, and state which guarantees a lock supplies beyond mutual exclusion.
Covers
- Threads versus processes and shared versus isolated state
- Scheduling, interleavings, preemption and critical sections
- Atomicity, visibility, ordering and memory consistency vocabulary
Study, in this order
4 steps
- Threads: shared state and uncontrolled schedulingOperating Systems: Three Easy Pieces - concurrency
Sections 26.1 to 26.5: why threads share state, the shared-data example, uncontrolled scheduling and the wish for atomicity
- Thread API: creation, joining and build flagsOperating Systems: Three Easy Pieces - concurrency
Sections 27.1, 27.2 and 27.5, including the build line
gcc -o main main.c -Wall -pthread - Processes vs ThreadsAlgoMaster Concurrency lessons
What is a Process? and What is a Thread?: shared address space against isolated state
- Race Conditions and Critical SectionsAlgoMaster Concurrency lessons
The Shared Counter Problem; Why
count++Is Not One Step; What is a Race Condition; Race Condition vs Data Race
Focus on
- Threads of one process share code, heap, globals and file descriptors; each thread keeps its own registers, stack and program counter. A process boundary isolates memory, a thread boundary does not.
count++compiles to load, add and store. Any preemption or parallel execution between those steps can discard one thread's update. The compiler may also collapse the whole loop at-O2; the races unit measures that case.- Atomicity means no visible intermediate state. Visibility means a write becomes observable to another thread. Ordering constrains which orders are observable. A mutex supplies all three for its critical section; a bare flag supplies none.
Reproduce closed-book
Traps
- One run's exact total proves nothing. Optimization level, core placement and timing decide what you see; ThreadSanitizer decides whether a race exists.
- Threads and processes do not differ only in creation cost. The defining difference is shared against isolated address space and what must be synchronized as a result.
- Atomicity, visibility and ordering are three distinct guarantees. Making a flag visible does not make a read-modify-write atomic.
Practice
OSTEP Chapter 26 simulation: `loop.s`, `looping-race-nolock.s` and `wait-for-me.s`
threads-intro folder: run x86.py on loop.s, looping-race-nolock.s and wait-for-me.s and answer the chapter's homework questions 1 to 10, including the critical-section question 6
Predict each trace on paper first, then check it with the -c flag.
Self-test
-
Two threads each run read, add, write on a counter holding 5. Which final values are possible, and how do the 20 legal orders split?
6 or 7. 18 orders end at 6: every order where both threads read 5 before either writes 6. Only the 2 fully serial orders end at 7. Count verified by enumerating all linear extensions of the two read-add-write chains. -
What state do threads share after
pthread_create, and what stays private?Shared: the address space (code, heap, globals) and file descriptors. Private: registers, stack, program counter and thread-local storage. -
Why does OSTEP Section 27.5 put
-pthreadon the build line?It sets the compiler defines for threaded code and links the threads library. Since glibc 2.34 the pthread functions live in libc, so a build without it often links anyway;-pthreadremains the portable form. -
A learner says visibility follows from atomicity. What is the counterexample?
An aligned int flag never tears, yet a loop reading it with a plain load may be compiled to read it once and spin forever. A relaxed atomic flag does become visible, but does not carry the data written before it; that needs release on the writer and acquire on the reader.
Completion criterion
Stop when
You can write the 5-to-6 table from memory, explain the 18-to-2 split, and predict the simulator traces for all ten chapter questions before checking them.
Mark passed, then open 2.2 Only mark this when you can do it without notes.Leads to
- 2.2 Mutexes, condition variables, semaphores and barriers Mutexes turn the critical section identified here into an enforceable invariant.
- 2.4 Data races, lost updates and lost wakeups Lost updates are the first race this vocabulary predicts.
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.
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.
- 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.
- 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.