Unit 2.8 · about 4 h
247 / 324Deterministic schedules, stress tests and contention
Passing once is not passing. This unit makes timing failures reproducible on a hybrid CPU with performance and efficiency cores: deterministic shims for the schedule you fear, stress for the ones you did not imagine, and pinned measurements that survive review.
- implement
- measure
You can now
- Build a barrier-forced schedule shim that turns an intermittent interleaving deterministic.
- Stress a mutex-protected structure with randomized threads and report throughput, correctness and retry counts.
- Compare lock strategies under matched contention with per-op costs, stating pinning, repeats and cache state.
Covers
- Deterministic schedule shims and randomized stress tests
- Contention, locality, throughput, tail latency and fairness
Study, in this order
5 steps
- Concurrent counters, queues and tablesOperating Systems: Three Easy Pieces - concurrency
Section 29.1: single, fine-grained and approximate counters with the throughput figure; Section 29.3 for the queue
- Evaluating locks and two-phase blockingOperating Systems: Three Easy Pieces - concurrency
Section 28.4: the no-contention against contended performance cases and fairness; Section 28.16: two-phase spin-then-block
- Locking lecture: the allocator contention storyMIT 6.1810 - locks and parallelism
Locking lecture notes: the
kfreelost-page case study without locks and the per-CPU freelist remedy - Lock lab contention countersMIT 6.1810 - locks and parallelism
Memory allocator half:
kalloctest#test-and-set tables before and after per-CPU freelistsDepth · Read the printed counter tables only. Building xv6 needs a RISC-V toolchain and QEMU, which this unit does not use.
- Coarse-grained vs Fine-grained LockingAlgoMaster Concurrency lessons
What is Lock Granularity; Trade-offs Comparison; When to Use Each Approach
Focus on
- Deterministic shims (barriers, sleep strings, condition gates) choose the schedule; stress (many threads, many iterations, varied seeds) samples it. Shim to reproduce, stress to discover.
- Pin with
tasksetand name the cores: unpinned runs migrate across performance and efficiency cores and smear the numbers. On the i9-12900K reference, logical CPUs 0 and 1 are one physical core (lscpu -e), so four threads pin to0,2,4,6;taskset -c 0-3would put them on two cores. - Report per-op cost, not just totals: 8M mutex increments take 0.084 s solo (10.5 ns per op) and 0.33 to 0.38 s with 4 threads on four P-cores (41 to 48 ns per op) on an i9-12900K with Linux 7.0 and gcc 15.2
-O2 -pthread, three invocations of 1 warm-up plus 5 timed runs, warm caches. Same work, about 4 to 4.5 times the per-op cost. - Fairness is a separate axis from throughput: OSTEP 28.4 names it, plain spin locks lack it, and try-back-off buys progress at 0.8 to 3.1 million retries per
vector-try-waitrun.
Reproduce closed-book
-O2 -pthread: 8M increments in four configs (1 thread; 4 threads unpinned; 4 threads on four physical cores; 8 threads on eight physical cores; find the core map with lscpu -e, on the reference CPU taskset -c 0,2,4,6 and 0,2,4,6,8,10,12,14), 1 warm-up plus 5 timed runs each, repeated in three invocations. The reference shape: solo mutex 0.084 s, solo atomic 0.029 s, 4-thread mutex 0.33 to 0.38 s, exact totals every run. State CPU, kernel, compiler, flags, pinning, repeats and cache state.Traps
- Averages hide the spread. Report the range across repeats (six try-wait runs took 0.11 to 0.28 s); a single mean claims a precision the runs do not support.
- Oversubscription measures the scheduler, not the lock. Keep threads at or below the pinned cores when comparing strategies.
- Stress without an oracle proves nothing. Assert exact totals (mutex, CAS) or exact retry accounting (the try-wait
Retriesline) on every run.
Practice
OSTEP deadlock homework: timing three lock strategies
threads-bugs folder: run ./vector-global-order, ./vector-try-wait and ./vector-avoid-hold-and-wait with -d -l 200000 -n 2 -t, three runs each; reference on an i9-12900K with Linux 7.0: about 0.04 s, 0.11 to 0.28 s with 0.8 to 3.1 million retries, and 0.07 to 0.09 s
Quote ranges, not means. If kernel.perf_event_paranoid is 2 on your machine, count user-space events of your own processes only.
Self-test
-
What is the difference between a schedule shim and a stress test?
A shim forces one chosen interleaving (barrier, sleep string) to reproduce a known failure deterministically. Stress samples many unknown interleavings to discover new failures, and needs an independent correctness oracle. -
Your unpinned 4-thread mutex numbers move by 10% between invocations. What does pinning fix, and what not?
Pinning fixes placement: which cores, performance or efficiency, and whether two threads share one core through SMT. It does not remove frequency scaling or background load, so report the spread across invocations. The reference machine has one NUMA node, so no remote-memory effect is claimed. -
Try-wait is correct but retries about a million times or more per run. What does that number tell you?
Each retry is a failed acquisition plus another attempt: livelock-shaped waste that ordering avoids. Correctness passed; efficiency did not. -
Why 1 warmup plus 5 timed runs instead of a single run?
Warmup faults pages and warms caches and branch predictors. Repeats expose run-to-run spread from scheduling and frequency scaling.
Completion criterion
Stop when
Your counter table matches the stated shape, the three vector timings reproduce in range, and every number you quote carries its setup.
Mark passed, then open 2.9 Only mark this when you can do it without notes.Leads to
- 2.9 Event loops, work stealing and structured concurrency A pool that survives stress here earns its place in the scheduler design.
- 6.2 Latency distributions, throughput and saturation Throughput and tail latency get their full treatment there.
Comes after
- 1.2 Caches, working sets, bandwidth and NUMAMeasure cache-line ownership traffic under actual multicore contention.
- 2.3 Atomic operations, compare-and-swap and memory orderingCompare the CAS counter against the mutex counter under matched contention.
- 2.4 Data races, lost updates and lost wakeupsRandomized stress turns one observed schedule into quantified flakiness.
- 2.6 Bounded queues, admission and backpressureDrive this queue to saturation and measure the tail.
- 2.7 Cancellation, deadlines and shutdown state machinesA shutdown that passes idle must also pass under load and saturation.
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.
- 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.
- 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.
- 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.