Unit 2.7 · about 3 h
246 / 324Cancellation, deadlines and shutdown state machines
Programming's cancellation unit built TaskGroup deadlines and full-jitter retries in Python. This unit implements the lower half: pthread cancellation points, timed waits as deadlines, and the OPEN, CLOSING, CLOSED machine the service slice shuts down with. It assumes that unit as background; no asyncio is reused.
- implement
You can now
- Separate cancellation (a request), deadlines (a bound) and shutdown (a state machine), and say which primitive serves each.
- Implement drain-or-abort shutdown with a timed wait, a close broadcast and a join, with no leaked thread.
- Propagate the first error to the joiner without losing admitted work in drain mode.
Covers
- Cancellation, deadlines, timeouts and error propagation
- Drain, abort and graceful shutdown state machines
Study, in this order
3 steps
- End-of-stream shutdown in the producer and consumer codeOSTEP concurrency homework and code
threads-cvfolder,main-common.c:main()inserts end-of-stream markers after producers finish and consumers exit onEND_OF_STREAM; watch the drain with-vDepth · Use the EOS pattern only. The sleep-string schedule forcing is the locks unit; do not repeat that practice here.
- pthread cancellation and deadline waitsLinux man-pages: pthreads and futex
pthread_cancelpage: deferred cancellation and cancellation points;pthread_cond_timedwaitpage: absolute deadlines andETIMEDOUTwith predicate re-check - Thread Pool PatternAlgoMaster Concurrency lessons
Core Components; Implementation; When to Use / When Not to Use
Focus on
- Cancellation is a request the target observes at defined points. A deadline is a bound the waiter enforces with a timed wait plus re-check. Shutdown is a state machine all threads observe. One primitive cannot serve all three.
- Timed waits take absolute time and return
ETIMEDOUTwithout changing state. Recompute the predicate and the remaining budget after every return; repeated relative sleeps drift. - Drain keeps admitted work and refuses new work; abort discards and reports. Set the
CLOSINGflag under the mutex first, then broadcast, then join to prove no thread was left behind. pthread_cancelacts only at cancellation points and skips cleanup without handlers. Prefer a close flag plus broadcast; reserve cancel for threads blocked where no flag is checked.
Reproduce closed-book
OPEN, CLOSING, CLOSED drain demo in C with gcc 15.2 -O2 -pthread: one worker, 3 admitted items, close-while-working, 200 ms timed waits. Three runs must print done=3 pending=0 state=2 with admit-after-close=0, and the -fsanitize=thread build must be clean.Traps
- Double close, double join and post-close admission must each be defined, not merely unlikely. Test all three.
- Broadcast before setting the flag wakes threads that re-sleep. Set the flag first, then broadcast, with both under the mutex.
- A bare sleep is not a deadline. Without the predicate loop, an early wakeup exits shutdown while work remains, and a late one reports a drain that never happened.
Practice
AlgoMaster: Design Deferred Callback Executor
schedule() plus runNext() with deadline ordering; a waiter for a future task wakes when an earlier deadline arrives; callbacks run outside the lock; waits use blocking primitives, never busy-waiting
The judge covers deadlines; your C drain demo covers close and join.
Self-test
-
What is the difference between cancelling a thread and shutting down a queue?
Cancellation asks one thread to stop at its next cancellation point. Shutdown moves shared state throughCLOSINGtoCLOSEDso every thread drains or aborts and the joiner observes completion. -
Why does the timed wait use an absolute deadline, and what must follow
ETIMEDOUT?Absolute time does not drift across repeated waits. AfterETIMEDOUT, re-check the predicate and the state: the timeout alone changes nothing. -
Close sets
CLOSINGand broadcasts. Why must a woken worker re-check instead of exiting?Drain mode still owns admitted items; only an empty queue inCLOSINGmoves toCLOSED. Exiting on wakeup abandons work. -
Where does the first worker error go?
Into shared state under the mutex or a joined return value, read by the joiner after all threads exit. Printing from the worker is not propagation.
Completion criterion
Stop when
Your drain demo passes three runs under TSan, the deferred-executor judge passes, and you can place every primitive on the cancel, deadline and shutdown map.
Mark passed, then open 2.8 Only mark this when you can do it without notes.Leads to
- 2.8 Deterministic schedules, stress tests and contention A shutdown that passes idle must also pass under load and saturation.
- 3.6 Deadlines, retries and idempotency across RPC RPC deadlines are this unit's timed wait across a network.
Comes after
- 2.5 Deadlock, livelock, starvation and priority inversionShutdown is the planned requested wait; deadlock is the unplanned one.
- 2.6 Bounded queues, admission and backpressureClose is half of shutdown; deadlines and drain complete it.
- 2.9 Event loops, work stealing and structured concurrencyLoop shutdown needs the same drain discipline.
Resources for this unit
- 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 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
- 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 - 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.