Unit 2.9 · about 2 h
248 / 324Event loops, work stealing and structured concurrency
Not every concurrent system needs a thread per connection. This unit closes the section with the alternative the later networking and server designs assume: structure work so completion, not preemption, drives progress.
- explain
You can now
- Explain the event loop: one thread, nonblocking event sources,
select, and handlers that must never block. - Contrast event loops, thread pools and work stealing, and state when each fits.
Covers
- Event loops, work stealing and structured concurrency
Study, in this order
3 steps
- Event-based concurrencyOperating Systems: Three Easy Pieces - concurrency
Sections 33.1 to 33.3: the event loop and select; Sections 33.5 to 33.8: blocking calls, async I/O and state management
- Concurrency ModelsAlgoMaster Concurrency lessons
Model 2: The Event Loop; Comparing the Models; Choosing a Model
Depth · Read the event-loop model against OSTEP 33; skim the actor and channel models as vocabulary only.
Focus on
- An event loop removes preemption inside handlers, not concurrency from the system: a blocking call stalls every connection, so Sections 33.5 and 33.6 demand nonblocking or async I/O.
- State moves from stacks to explicit records (Section 33.7): harder to write, easier to bound. No locks does not mean no state machine.
- Thread pools bound threads and queue the rest; work stealing balances queues across workers. All three still need this section's admission, deadline and shutdown contracts.
Reproduce closed-book
With CPython 3.14.4, register one end of
socket.socketpair() with selectors.DefaultSelector, send b"one" then b"two" from the other end, and read with recv(2) in the handler: the loop receives [b"on", b"et", b"wo"] and joins them to b"onetwo" with no threads. Then state, closed-book, the two OSTEP problems with events (blocking system calls, state management) and the remedy for the first.Traps
- Event-driven does not mean faster. It removes lock overhead and per-connection thread stacks but adds state-machine complexity; throughput still depends on handler cost.
- Readiness is not admission.
select()reports ready file descriptors; the loop must still bound handler time and queue growth, or one ready source starves the rest. - Structured concurrency (tasks with a defined lifetime and a join) is not fire-and-forget threads. A pool whose workers outlive their owner leaks the shutdown this section just built.
Practice
AlgoMaster: Design Task Scheduler with Dependencies
workerCount fixed workers with independent tasks running concurrently; cycle check returns false with no callback run; ready queue plus indegree accounting; the judge runs up to 10000 tasks and 100000 edges
Reuse your drain discipline: every worker must exit and execute() must join them.
Self-test
-
Why can one blocking read stall a thousand connections on an event loop?
One thread runs all handlers. A handler that blocks keeps the loop from polling, so ready events for every other connection wait. -
What replaces the call stack for tracking progress across events?
Explicit per-connection state records updated by each handler. OSTEP 33.7 names state management as the hard part of events. -
When does this section prefer a bounded thread pool over an event loop?
When handlers do CPU work or call blocking APIs that cannot be made async. The pool bounds threads while the queue bounds waiting work.
Completion criterion
Stop when
You can run the selector demo, name the two OSTEP event problems from memory, and place event loops, pools and work stealing on one trade-off map.
Mark passed, then open 3.1 Only mark this when you can do it without notes.Leads to
- 3.4 Sockets, partial reads and writes, and message framing Framing over partial reads is the event loop's day job.
- 2.7 Cancellation, deadlines and shutdown state machines Loop shutdown needs the same drain discipline.
Comes after
- 2.8 Deterministic schedules, stress tests and contentionA pool that survives stress here earns its place in the scheduler design.
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.