Rules of Thumb for Concurrency
Adapted from: Jason Gregory, Game Engine Architecture, 3rd ed. (CRC Press, 2018), Chapter 4, Section 4.8 — rewritten and condensed for teaching.
The dining-philosophers solutions from Problems with Lock-Based Concurrency — global chopstick ordering, a central arbiter, the N−1 trick — aren't just puzzle-specific tricks. Squint at them and a handful of genuinely general principles fall out, ones that apply to almost any concurrent programming problem you'll actually face. This lesson collects four of the most useful.
Global Ordering Rules
In a single-threaded program, the order instructions appear in your source is the order they execute in — full stop. Concurrency breaks that assumption completely: if your program needs a guaranteed order across threads, that order has to be imposed globally, across every thread that touches the data — nothing about "program order" within any one thread gets you there for free anymore.
This is exactly why a doubly linked list is a poor fit for concurrent access. Its whole design — O(1) insertion and deletion anywhere in the list — rests on an unstated assumption: program order equals data order. Given the ordered list { A, B, C }, if one thread inserts D before C and then another inserts E before C, a single-threaded program guarantees the result is { A, B, D, E, C }. Concurrently, program order says nothing about data order anymore — the same two operations racing against each other can legitimately produce { A, B, D, E, C }, { A, B, E, D, C }, or — if the operations aren't properly protected by critical sections — outright corruption, such as both D's and E's next pointers ending up pointing at C simultaneously.
The fix isn't a cleverer locking scheme bolted onto a doubly linked list — it's asking a more basic question first: does order even matter here? If not, a singly linked list with append-only inserts can be implemented reliably, with locks or even lock-free. If order genuinely does matter, you need a stable, deterministic ordering criterion that doesn't depend on the accident of which thread's instructions happened to run first — alphabetical, by priority, by timestamp, whatever fits the problem — and that criterion, not incidental program order, is what should actually drive the choice of data structure. Forcing a doubly linked list into concurrent, multi-writer use without solving this first is — in the memorable phrase — like hammering a square peg into a round hole.
Check: global ordering
Global ordering rules
1 / 2Why does a doubly linked list make a poor concurrent data structure when multiple threads insert into it simultaneously?
Pick an answer to see if you are right.
Transaction-Based Algorithms
The central-arbiter solution to dining philosophers hands out chopsticks in pairs — a philosopher gets everything they need, or nothing at all. That's a transaction: an indivisible bundle of resources and/or operations. Threads submit transaction requests to some central arbiter; each transaction either succeeds completely, or fails completely (typically because another thread's transaction was mid-flight when the request arrived) — and on failure, the requesting thread simply resubmits until it succeeds, possibly with a short wait between attempts.
This pattern shows up constantly in concurrent and distributed systems programming, and — as covered in the next few lessons — it's also the conceptual foundation underneath essentially every lock-free data structure and algorithm: prepare your change locally, then attempt to commit it as one atomic, all-or-nothing step, retrying on failure.
Minimizing Contention
The theoretical best-case concurrent system is one where no thread ever waits on a lock at all — an ideal that's never fully achievable in practice, but one worth actively designing toward. Take a group of threads all producing data into one shared, central repository: every single write contends with every other thread's write for that one resource. A simple, often-effective fix: give each thread its own private repository to write into, so production happens with zero contention, and have one thread collate all the results only once everyone's finished producing.
The dining-philosophers analog: if every philosopher simply started with their own two chopsticks, all contention (and, not coincidentally, all concurrency) vanishes instantly — no sharing, no problem. Real systems can't eliminate sharing entirely like that, but the underlying lesson generalizes cleanly: actively look for ways to shrink what's actually shared, since less sharing directly means less contention.
Thread Safety
A class or API is thread-safe when any thread can safely call its functions without external synchronization — typically implemented by having each function enter a critical section on entry and leave it just before returning. A class whose functions are all thread-safe this way is sometimes called a monitor.
Thread safety is genuinely convenient — but it isn't free, and blanket-applying it has two real costs:
- Wasted overhead. Locking machinery you don't need is pure cost when the interface is only ever used single-threaded, or exclusively by one thread even inside an otherwise multithreaded program.
- Broken reentrancy. If a thread-safe class exposes functions
A()andB(), andB()'s implementation needs to callA()internally, you get an instant self-deadlock —B()already holds the lock when it tries to enterA()'s own critical section. Two real fixes: reentrant locks (covered in a later lesson, letting the same thread re-enter a lock it already holds), or splitting the interface into "unsafe" internal functions plus thin, thread-safe public wrappers that just enter a critical section, call the unsafe version, and leave.
Reflexively making everything 100% thread-safe is usually the wrong instinct. It produces needlessly heavyweight interfaces, and — worse — it quietly encourages programmers to write code as if concurrency weren't even happening, since the class "handles it for them." The better goal: explicitly design data structures and algorithms around the concurrency that's actually present, deliberately minimizing both contention and outright lock usage. Getting all the way to fully lock-free is a lot of genuinely hard work (the subject of the next several lessons) — but striving toward fewer locks beats reflexively over-locking everything in a doomed attempt to let programmers pretend concurrency isn't there.
Check: transactions, contention, and thread safety
Transactions, contention, and thread safety
1 / 4What defines a "transaction" in the sense used by the central-arbiter dining philosophers solution?
Pick an answer to see if you are right.
- Program order is not data order in a concurrent system — any ordering requirement has to be imposed globally, which is exactly why unarbitrated concurrent access to a doubly linked list is a design smell, not just a locking inconvenience.
- Transaction-based algorithms (all-or-nothing, retry-on-failure) are the conceptual seed of essentially every lock-free technique covered in the lessons ahead.
- Minimizing contention — even by something as simple as giving each thread its own private workspace — is often more effective than any clever locking scheme applied to a fully shared resource.
- Thread safety is a tool, not a default. Blanket-applying it adds needless overhead, can break reentrancy, and can encourage programmers to stop thinking about concurrency altogether — deliberately designing for the concurrency that's actually present is the better goal.
Further Reading
- Jason Gregory — Game Engine Architecture, 3rd ed. (CRC Press, 2018), Chapter 4, Section 4.8
- Problems with Lock-Based Concurrency — this series' previous lesson, including the dining philosophers solutions these rules of thumb generalize from
- Causes of Data Races and Atomic Instructions — this series' next lesson, where transaction-based thinking becomes the foundation of lock-free programming