Concurrency Mind Map
Algorithm & Systems VisualizationsEvery concurrency visualization on this site on one map. The branches are the main ideas. Each leaf is a page; the grey line under it is the one thing to remember about it. Click a branch to focus on it, click a page to open it.
1. How the map is organized
Ask what a thread does while it cannot go on, and you know the branch:
- It keeps the CPU and retries with one atomic instruction: atomics and spinning.
- It sleeps until the lock is free: locks that sleep. It sleeps until some state changes (an item, a permit): waiting for a condition.
- It is not an OS thread at all but a task, coroutine or goroutine that a runtime parks: many tasks, few threads.
- The classic problems combine these tools; basics explains why any of it is needed.
2. The branches side by side
| Branch | A waiting thread... | Main tool | Classic bug |
|---|---|---|---|
| Concurrency basics | takes turns on a core | time slicing, cores | counter++ race |
| Atomics and spinning | spins on the CPU | xchg, cmpxchg | wasted CPU, ABA |
| Locks that sleep | sleeps in the kernel | futex | deadlock |
| Waiting for a condition | sleeps until signalled | semaphore, condition variable | lost wake-up |
| Classic problems | depends on the solution | all of the above | deadlock, starvation |
| Many tasks, few threads | is parked by a runtime | run queues, work stealing | blocking call stalls a thread |
3. Five facts to remember
- A data race needs shared data, at least one writer and nothing ordering the accesses.
counter++is a read, an add and a write, so two threads can lose an update.- Deadlock needs all four Coffman conditions; break one, for example with a fixed lock order, and it cannot happen.
- Always wait on a condition variable in a
whileloop: a wake-up can be spurious or already stale. - Spinning pays only when the wait is shorter than the cost of sleeping and waking up.
See all concurrency pages in the index, or the other mind maps.