Unit 2.6 · about 4 h
245 / 324Bounded queues, admission and backpressure
Programming's backpressure unit built admission with asyncio.Queue. This unit rebuilds it in C with explicit invariants, close states and a measured drain, which is the piece the fault-tested service slice reuses. It assumes that unit as background and never reuses its queue demo.
- implement
You can now
- Implement a bounded producer-consumer queue with two condition variables and state its full and empty invariants.
- Add close semantics that drain admitted items, reject late puts and wake every waiter.
- Derive queued-memory and worst-wait bounds from capacity, item size, service rate and worker count.
Covers
- Bounded queues and producer-consumer invariants
- Admission, backpressure, load shedding and overload propagation
Study, in this order
6 steps
- Producer and consumer with condition variablesOperating Systems: Three Easy Pieces - concurrency
Section 30.2 with the two-condition-variable while version as the reference implementation
- Bounded buffer with semaphores, plus throttlingOperating Systems: Three Easy Pieces - concurrency
Sections 31.4 and 31.7: counting semaphores as fill and empty counts, and thread throttling as admission
- Concurrent queuesOperating Systems: Three Easy Pieces - concurrency
Section 29.3: the concurrent queue structure and where the locks live
- Producer-Consumer PatternAlgoMaster Concurrency lessons
Core Components; Implementation; When to Use / When Not to Use
- Bounded BufferAlgoMaster Concurrency lessons
Solution 2: Semaphore-Based Solution; Solution 3: Monitor-Based Solution; Solution Comparison
Depth · Compare the two solutions; skip the naive busy-waiting variant except as a failure example.
- Design Thread-Safe Blocking QueueAlgoMaster Concurrency lessons
Approach 1: Single Lock with Conditions; Approach 2: Two-Lock Queue; Solution Comparison
Focus on
- Two predicates, two condition variables: not-full for producers, not-empty for consumers. One CV forces broadcast-on-every-op or risks a stolen signal.
- Capacity bounds memory and wait: max queued bytes equal capacity times item size, and a newly admitted item waits at most capacity divided by aggregate service rate, plus one service time. State units with every bound.
- Close is a state, not a signal:
CLOSEDrejects puts, preserves admitted items in FIFO order and wakes all waiters. A bare broadcast without the flag re-sleeps or loses items. - Admission control turns overload into explicit rejection: the rate limiter allows at most
limitpermits per aligned window, with lookup, reset, check and increment as one atomic operation.
Reproduce closed-book
-O2 -pthread (capacity 4): 2 producers times 5000 items with 2 consumers must drain exactly 10000 over three runs, post-close put must return -1, take on the drained closed queue must return -1, and the -fsanitize=thread build must be clean. State CPU, kernel, compiler, flags and repeats.Traps
notify_oneagainstnotify_allis a correctness choice under close: waking one consumer while producers also wait can stall shutdown. Broadcast on close.- Window edges admit bursts: a fixed-window limiter allows
limitpermits at the end of one window andlimitmore at the start of the next. Name the factor of 2 before claiming smoothness. - An unbounded queue plus a slow consumer is a memory leak with a polite name. Bound the queue or bound the wait; bound both when the slice demands it.
Practice
AlgoMaster: Design a Closable Bounded Queue
put, take and close with the five stated rules (drain in FIFO order, blocked puts fail, takes report no-item when drained); the judge runs concurrent producers, consumers and closers
Your C queue is the reference; now satisfy the judge's in-browser contract.
AlgoMaster: Design Thread-Safe Rate Limiter
Fixed aligned windows with at most limit permits per client per window; window lookup, reset, check and increment as one atomic operation under the judge's logical clock
Use the supplied logical clock, never the system clock.
Self-test
-
Why two condition variables instead of one?
Producers and consumers wait for different predicates. With one CV a producer signal can wake another producer, which re-sleeps while consumers stay asleep. At close, broadcast wakes everyone and each re-checks its own predicate. -
Capacity 1000, 8-byte items, 2 workers each serving 50000 items/s. Bound the queued memory and the worst wait of an admitted item.
Memory: 1000 times 8 = 8000 bytes plus bookkeeping. Wait: at most 1000 items ahead drain at 100000/s, about 10 ms, plus one 20 us service time. -
Close arrives with 3 items queued and 1 producer blocked in
put. What must happen?The blockedputwakes and fails without adding. The 3 items drain in FIFO order. Takes after drain report closed, and later puts fail immediately. -
Why must the window check, reset,
limitcheck and increment be one atomic operation?Otherwise two threads in the same window both observe a count belowlimitand both consume the last permit, admittinglimitplus 1.
Completion criterion
Stop when
Your C queue drains 10000 of 10000 under TSan, both judges pass, and you can derive the memory and wait bounds for a new capacity.
Mark passed, then open 2.7 Only mark this when you can do it without notes.Leads to
- 2.7 Cancellation, deadlines and shutdown state machines Close is half of shutdown; deadlines and drain complete it.
- 2.8 Deterministic schedules, stress tests and contention Drive this queue to saturation and measure the tail.
Comes after
- 2.2 Mutexes, condition variables, semaphores and barriersThe two-condition-variable queue here gains close semantics and an admission policy.
- 2.5 Deadlock, livelock, starvation and priority inversionLock ordering keeps the queue's two conditions live under many producers.
- 6.6 Retry budgets, circuit breaking and load sheddingReuse the user-space queue bounds behind the admission decision.
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.
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.
- 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.