Operating systems and concurrency
Concurrency
Why shared state breaks when two threads touch it at once, and the tools that fix it, from locks and semaphores to atomics, message passing and database constraints.
Concurrency means several things making progress at once. It shows up as threads in one process, separate processes, or many machines. The trouble starts when two of them read and write the same data. The result then depends on the exact order of their steps, and that order changes from run to run.
Most concurrency bugs are not exotic. A counter drops increments, a check passes and then the action fails, or two services each wait for the other forever. Learning a small set of patterns handles most of them.
The big idea
Two ideas explain nearly every concurrency bug:
- Interleaving. Each thread runs a sequence of steps, and the operating system can pause one thread between any two steps. Read, modify and write look like one operation in your code. They are three steps to the machine.
- Visibility. On modern CPUs, one core's writes may not be visible to another in the order you expect. Caches and reordering mean that without synchronization, you can't assume what another thread sees.
Locks solve both by letting only one thread into a section at a time, and by publishing its writes when it leaves.
Concepts in this topic
| Step | Concept | What it answers |
|---|---|---|
| 1 | Race conditions | Why do two correct-looking threads lose an update? |
| 2 | Mutexes, semaphores and condition variables | Which primitive fits which waiting pattern? |
| 3 | Atomics and memory ordering | When can one word be updated without a lock? |
| 4 | Deadlock and livelock | How do threads wait forever, and how do you prevent it? |
| 5 | Shared state without locks | How do message passing, database constraints and fencing tokens help? |
The same bugs appear across machines. Two servers can both believe they hold a lock, which is why fencing tokens exist, covered in the last concept page. Async I/O has its own concurrency model, covered in async I/O.
Common mistakes
- Using a lock around one line of a multi-step update, and missing the step that reads the state.
- Holding a lock during a network call, so every other thread waits on a remote service.
- Assuming a test that passes once proves the code is correct. Race bugs often need a specific timing.
- Reaching for lock-free code before measuring whether a lock is the bottleneck.
Key takeaways
- A race is any result that depends on the order of steps, and it's often a read-modify-write.
- Pick the primitive by the pattern: a mutex for exclusive access, a condition variable for waiting, atomics for one word.
- Keep critical sections short, and never hold a lock across a slow call.
- Across machines, use database constraints or fencing tokens, because a local lock doesn't protect remote state.
Further learning
Next, read race conditions to see how a simple read-modify-write goes wrong.
Related
Processes, threads and the kernel
What the OS gives every program, and how to see it on a live Linux box. Start here for the process model.
The memory hierarchy
From registers to SSDs to the network, the latency numbers that dominate performance, and why the tier your data sits in matters more than the code you write.
Transactions, MVCC and isolation levels
What ACID guarantees on one database node, which concurrency bugs each isolation level still allows, how MVCC gives snapshots without blocking, and the code patterns that keep concurrent writes correct. Start here for transactions.
Async I/O
Why waiting on the network should not hold a thread, how event loops and async functions handle thousands of connections, and when goroutines or thread pools fit better.