Section 2 of 7 · Systems Foundations

Concurrency, Scheduling & Bounded Work

Concurrency is useful only when safety, liveness, ownership and capacity remain explicit. This section makes timing failures reproducible and overload behavior finite before those problems cross a network.

9 units 20 topics 0/9

Units

9 in this section

2.1 Threads, interleavings and memory consistency
explain
3 h
2.2 Mutexes, condition variables, semaphores and barriers
explain · implement
4 h
2.3 Atomic operations, compare-and-swap and memory ordering
explain
3 h
2.4 Data races, lost updates and lost wakeups
explain · measure
3 h
2.5 Deadlock, livelock, starvation and priority inversion
derive · explain
3 h
2.6 Bounded queues, admission and backpressure
implement
4 h
2.7 Cancellation, deadlines and shutdown state machines
implement
3 h
2.8 Deterministic schedules, stress tests and contention
implement · measure
4 h
2.9 Event loops, work stealing and structured concurrency
explain
2 h

Before moving on

Checkpoint

Force a safety failure and a liveness failure with a deterministic schedule, repair both, then drive a bounded worker queue through saturation while preserving cancellation, finite memory and predictable recovery.

Deliberately out of scope

Leave for later

Production lock-free data structures
Formal verification of concurrent algorithms
Distributed coordination and collective communication

Resources for this section

Shared by every unit above

Operating Systems: Three Easy Pieces - concurrency
Remzi and Andrea Arpaci-Dusseautheory

primary

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.
OSTEP concurrency homework and code
OSTEP authorspractice

required

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
AlgoMasterpractice

required

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
MIT PDOScourse

depth

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
AlgoMastercourse

support

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
Linux man-pages projectreference

reference

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
cppreferencereference

reference

Read atomic_compare_exchange for success and failure semantics and the expected-pointer update rule, and memory_order for the six orderings and what relaxed permits. Stop before lock-free-property macros.
GCC __atomic builtins
GNU Compiler Collectionreference

reference

Read __atomic_compare_exchange, __atomic_load and __atomic_store for the expected-pointer update rule and the __ATOMIC_RELAXED constant used by the CAS reproduce step.
The Little Book of Semaphores
Green Tea Pressbook

support

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.

Apply the section

Mini-project · Bounded admission and clean shutdown for the service slice, with forced schedules (10 to 14 h)

Port a closable bounded queue and drain states into the Python worker pool that will serve later requests. Force schedule-driven safety and liveness failures, repair them, then prove admission stays bounded and shutdown stays clean under overload.

Steps

Keep the C programs from the units in lab/concurrency: racy and clean counters, lost wakeup, deadlock and repair, closable queue and drain demo, rebuilt and asserted by make check with and without ThreadSanitizer.
Write kv/pool.py with ClosableQueue and a WorkerPool owning OPEN, CLOSING and CLOSED, where close stops admission, drains admitted jobs within a deadline, then cancels and reports the remainder, tested against the ported C queue cases.
Give every job a request identity and an absolute deadline on time.monotonic(), drop expired jobs before their effect while counting them, and let running jobs observe cancellation between steps, with tests for both.
Force a double-apply failure by interleaving duplicate requests through check-then-act with a schedule shim, then claim each identity under a lock before its effect and keep the shim as a regression test.
Force a lock-order deadlock with a shim that stages opposite acquisitions, repair it with one global order, and add a randomized stress test that compares final state against an exact oracle.
Predict capacity from workers over service time, drive the pool past it across rising offered rates, and show held work stays bounded, offered work is accounted for, and latency recovers after the flood.
Close the pool mid-flood so admission stops and admitted jobs finish or cancel within the deadline, wire close() to SIGTERM through lab/supervise.py, and compare one lock-granularity choice with pinned repeats, naming what the interpreter lock permits the test to show.

Deliverables

kv/pool.py with bounded admission, deadline cancellation and drain accounting, plus tests ported from the C queue cases.
The two forced-schedule regressions with their repairs, plus a randomized stress test against an exact oracle.
Saturation, shutdown and contention reports with predictions, raw samples and recovery evidence, and the C programs under make check.

Checks

rubric · Self-grade with the rubric below

Rubric

Criterion	Pass	Strong
Forced failures	Each shim reproduces its failure before the repair and passes after, with the shim kept as a regression test.	The write-up explains why randomized stress alone could miss each failure, and kept runs show the miss.
Bounded work	Held work stays bounded at every offered rate, every offered job is accounted for, and expired jobs never start.	The capacity prediction precedes the sweep, and the measured knee is explained against it.
Shutdown and evidence	Close stops admission at once with admitted work finished or counted, and the signal path works end to end.	The contention comparison states what the interpreter lock can show, and raw times with pinning are kept.

Feeds into: Capstone service slice: the pool gives bounded admission, cancellation and shutdown. The C queue and forced schedules join the mechanisms laboratory.