Unit 6.2 · about 6 h
36 / 324Synchronization primitives and concurrency hazards
Correct shared-state code needs both safety and progress. A lucky stress run proves neither; force the interleaving that breaks the invariant.
- explain
- implement
You can now
- Protect a compound invariant with a lock and coordinate a bounded queue with condition predicates.
- Reproduce a lost update and a deadlock with controlled interleavings, then remove their causes.
- Distinguish deadlock, livelock, starvation and lost notification from slow useful work.
Covers
- Locks, semaphores, conditions, events and queues
- Race, deadlock, livelock, starvation and lost wakeups
Study, in this order
3 steps
- Locks, permits and progress failuresAlgoMaster Concurrency
Mutex; Semaphores; Condition Variables; Deadlock; Livelock; Starvation; Lost Signal
Depth · Read the mechanism and failure examples, not every language implementation. Use Python's
Conditioncontract for the implementation. - `Condition` predicates under one lockPython concurrency documentation
Conditionobjects: producer-consumer example,wait,wait_for,notifyandnotify_all;Semaphoreobjects - Design Thread-Safe Blocking QueueAlgoMaster Concurrency
Problem Statement, Required Operations, Concurrency Challenges and Approach 1: Single Lock with Conditions
Depth · Stop before Approach 2. Python locks do not promise the fair-lock starvation guarantee shown in the analysis table.
Focus on
- A lock protects an invariant across all its reads and writes. A semaphore counts admission permits; it does not by itself protect the buffer mutation.
- Check the predicate under the condition's lock and
waitin a loop.waitreleases that lock while sleeping and reacquires it before returning;notifydoes not release it. - Remove circular lock acquisition with a global lock order. Livelock changes state without useful progress; starvation denies one participant progress while others advance.
- Use barriers and events to control test schedules. A timeout detects a stuck test; it does not identify the underlying wait cycle.
Reproduce closed-book
Barrier(2) between read and write. After both join, assert 1 instead of the intended 2 on both default and free-threaded builds. Remove that barrier from the critical section, lock the full read-modify-write and assert 2. In a separate test, give two threads opposite first locks, synchronize them at a barrier and use timed second acquisitions to demonstrate the wait cycle without leaving hung threads. Then use one global lock order and assert both finish.Traps
- Waiting while holding an unrelated lock needed by the notifier.
Condition.waitreleases only its own lock. - Putting the test barrier inside the repaired critical section. The first thread then waits for a second thread that cannot enter.
- Assuming mutex or condition wakeups are FIFO. Python gives no general starvation-freedom guarantee.
Practice
AlgoMaster: Design Thread-Safe Blocking Queue
Problem Statement: put, take, offer, poll, peek and size; Approach 1: Single Lock with Conditions
Implement the single-lock design in Python. Test capacity one, blocked producer and consumer, FIFO order and unique item delivery with events rather than sleeps. Do not claim Java-style thread interruption or fair-lock guarantees for Python.
Self-test
-
Why use
whilerather thanifaroundCondition.wait?A wakeup does not reserve the resource. Another participant may consume it before this thread reacquires the lock. -
Does
notifypreserve a message for a future waiter?No. Persistent state is the predicate; check and update it under the same lock used bywait. -
When can
emptyandfullsemaphore counts sum to less than capacity?After a producer or consumer acquires a permit but before it releases the opposite permit. Reserved in-flight permits are missing from that sum. -
What does a fixed lock order prevent, and what does it not promise?
It prevents a circular wait among those locks if all paths obey it. It does not guarantee fairness, bounded latency or freedom from other waits.
Completion criterion
Stop when
Your controlled tests expose the lost update and wait cycle, the repairs pass, and the blocking queue preserves its capacity and delivery invariants with multiple producers and consumers.
Mark passed, then open 6.3 Only mark this when you can do it without notes.Leads to
- 6.4 Backpressure, load shedding and graceful shutdown Apply bounded coordination to admission and draining.
Comes after
- 6.1 Work types, threads, processes, async tasks and the GILProtect the state your chosen model shares.
- 7.7 Threads, data races, memory ordering and atomicsRelate native synchronization to the route's broader concurrency contracts.
Resources for this unit
- AlgoMaster Concurrency Study Concurrency 101; the Python units on threads, the GIL, multiprocessing, asyncio and concurrent.futures; synchronization primitives; concurrency challenges; locking strategies; and concurrency patterns. Then solve Bounded Buffer, Thread-Safe Blocking Queue, Thread-Safe Rate Limiter and Task Scheduler with Dependencies.
- Python concurrency documentation Use asyncio task groups, cancellation, queues and timeouts; concurrent.futures; multiprocessing; threading; and signal documentation to verify lifecycle and failure behavior.
Also in this section
- High Performance Python, 3rd edition Read Chapter 2 Profiling to Find Bottlenecks, Chapter 9 Asynchronous I/O, Chapter 10 The multiprocessing Module and Chapter 12 Using Less RAM, and use the companion code (https://github.com/mynameisfiber/high_performance_python_3e) as experiment starting points. Change the workloads and measure the regimes where concurrency helps, loses or only moves the bottleneck.
- Operating Systems: Three Easy Pieces - concurrency Read Chapters 26-33, from threads through event-based concurrency, for locks, condition variables, semaphores, concurrency bugs and event loops. Do selected homework only for a weak mechanism.
- Docker guides Use the Python container guide and build best practices to run as non-root, pin dependencies, handle signals and test CPU and memory limits.
- OpenTelemetry Python instrumentation Manually instrument one request so its structured logs, one low-cardinality metric and one trace share a correlation identity. Use the telemetry to locate one seeded fault.
- Algorithmica - Getting Accurate Results Use Measuring the Right Thing and Reducing Noise for benchmark design: input distribution, latency versus throughput, warm-up, frequency scaling and pinning. The examples are C++; the checks transfer to Python.
- Timeouts, retries, and backoff with jitter Read Timeouts, Retries and backoff, and Jitter for deadline scope, idempotency, one retry owner and bounded retry load. Interpret the five-layer example as three total attempts per layer, not three retries plus the initial attempt.
- Site Reliability Engineering - overload and troubleshooting Read Chapter 21, The Pitfalls of Queries per Second, Client-Side Throttling, Utilization Signals, Handling Overload Errors and Conclusions. Read Chapter 12, Triage, Examine, Diagnose, Test and Treat, and Making Troubleshooting Easier for a service runbook. Skip datacenter load-balancing implementation details.
- Liveness, Readiness, and Startup Probes Read Liveness probe, Readiness probe and Startup probe for the different health decisions and failure actions. Apply the contracts to a local service; do not install Kubernetes or configure a cluster.