Unit 2.2 · about 4 h
241 / 324Mutexes, condition variables, semaphores and barriers
Programming's synchronization-hazards unit showed a lock-order deadlock and a blocking queue in Python. This unit rebuilds the same primitives from C pthreads down to the futex, so blocking, ownership and wakeup have a mechanism, not just an API. It assumes that unit as background and never reuses its TaskGroup demo.
- explain
- implement
You can now
- Explain mutex ownership, blocking against spinning, and how a futex keeps the uncontended path in user space.
- Implement a correct producer-consumer queue with one mutex and while-loop waits, and show the if version failing.
- Choose semaphores, barriers and read-write locks for ordering, rendezvous and read-mostly sharing.
Covers
- Mutex ownership, lock granularity and lock ordering
- Condition variables, predicates, waits and notifications
- Semaphores, barriers and read-write locks
Study, in this order
7 steps
- Locks: idea, pthread API and evaluationOperating Systems: Three Easy Pieces - concurrency
Sections 28.1, 28.2 and 28.4: the basic idea, pthread locks, and the mutual-exclusion, fairness and performance criteria
- Condition variables and the bounded bufferOperating Systems: Three Easy Pieces - concurrency
Sections 30.1 and 30.2 with Figure 30.9: Mesa semantics, the stolen signal, and why the woken thread re-checks
- Semaphores: definition, ordering and the bounded bufferOperating Systems: Three Easy Pieces - concurrency
Sections 31.1 to 31.5: binary against counting semaphores, ordering, the semaphore bounded buffer and reader-writer locks
- MutexAlgoMaster Concurrency lessons
How Mutex Works; Key Operations; Performance Considerations
Depth · Treat its 10 ns to 100 us cost table as trend only; measured numbers come from the contention unit.
- Condition VariablesAlgoMaster Concurrency lessons
What is a Condition Variable; How Condition Variables Work; Why use the Mutex
- Barriers and LatchesAlgoMaster Concurrency lessons
How Barriers Work; Implementing Barriers and Latches
- pthread and futex contractsLinux man-pages: pthreads and futex
pthread_mutex_lockpage for blocking acquire and ownership;pthread_cond_waitpage for atomic release-and-wait and spurious wakeups; futex(2) forFUTEX_WAIT_PRIVATEandFUTEX_WAKE_PRIVATE
Focus on
- A mutex has an owner: the thread that locks must unlock. A semaphore has no owner: any thread may post. Mixing the two disciplines causes lost wakeups and double releases.
pthread_cond_waitatomically releases the mutex and sleeps, and holds the mutex again on return. A signal is a hint, not a handoff: Mesa semantics plus spurious wakeups force the while loop.- Uncontended pthread mutexes stay in user space: 1000 lock and unlock pairs issue zero futex calls under
strace -f -c(glibc 2.43, Linux 7.0). A blocked lock issuesFUTEX_WAIT_PRIVATEand the unlock wakes it withFUTEX_WAKE_PRIVATE. - One condition variable per predicate: producers wait for not-full, consumers for not-empty. A single CV with if lets a stolen signal consume from an empty buffer, exactly Figure 30.9.
Reproduce closed-book
-O2 -pthread: signal with no waiter, then wait, and show the consumer blocks until a second signal and prints ready=2. Convert the wait to while (ready == 0) and show the consumer prints ready=1 with a -fsanitize=thread build reporting no races. State the compiler, flags and sanitizer with the result.Traps
- A signal with no waiter is not queued. If the predicate changed before the wait, the signal is gone; only the while loop over shared state is correct.
- Holding a lock across a slow call serializes every contender, but moving the check out of the lock reintroduces check-then-act. Keep exactly the state transition inside.
- Published cost tables are trends, not measurements. On an i9-12900K an uncontended lock plus increment cost about 10.5 ns per op and four threads on four cores about 41 to 48 ns; the contention unit shows how those were measured.
Practice
OSTEP condition-variable homework: break and repair the bounded buffer
threads-cv folder: build with make, run ./main-two-cvs-if -l 50 -m 1 -p 1 -c 2 (ten of ten reference runs stopped with error: tried to get an empty buffer), then ./main-two-cvs-while with the same flags, which drains all 50 items
gcc 15.2 builds the folder with warnings only. Use -v to watch the buffer while it fails.
OSTEP semaphore skeletons: rendezvous and barrier
threads-sema folder: fill rendezvous.c, then barrier.c; each child prints its before line before either prints its after line
Build each with gcc -pthread; common_threads.h in the folder wraps the calls with error checks.
Self-test
-
What does
pthread_cond_waitdo with the mutex, step by step?It atomically releases the mutex and sleeps. On wakeup it reacquires the mutex before returning, so the woken thread holds the mutex when wait returns. -
Two consumers share a buffer of one slot with if instead of while. Walk the failure.
Consumer Tc1 waits on empty. The producer fills the slot and signals Tc1. Before Tc1 runs, Tc2 consumes the item. Tc1 resumes past the if and gets from an empty buffer; the homework program prints error: tried to get an empty buffer. -
When does a pthread mutex enter the kernel?
Only on contention: to block inFUTEX_WAIT_PRIVATEor to wake a waiter withFUTEX_WAKE_PRIVATE. Uncontended acquire and release are user-space atomics; 1000 pairs showed zero futex calls. -
Why must the locker be the unlocker for a mutex, while any thread may post a semaphore?
Ownership lets the implementation track the holder for handoff and error checking. A semaphore is a counter with no holder, so release-by-other is the intended use, as in producer-posts while consumer-waits.
Completion criterion
Stop when
The if version fails on demand, the while version drains every configuration you try, and you can state the futex evidence for blocked against uncontended locking.
Mark passed, then open 2.3 Only mark this when you can do it without notes.Leads to
- 2.6 Bounded queues, admission and backpressure The two-condition-variable queue here gains close semantics and an admission policy.
- 2.3 Atomic operations, compare-and-swap and memory ordering Locks serialize contenders; compare-and-swap retries instead. Compare the costs.
Comes after
- 2.1 Threads, interleavings and memory consistencyMutexes turn the critical section identified here into an enforceable invariant.
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.