Source: Operating Systems: Three Easy Pieces (OSTEP) — Chapter 32, Arpaci-Dusseau & Arpaci-Dusseau

Common Concurrency Problems

Researchers have long studied concurrency bugs — early work on deadlock [C+71], later work on the everyday bugs that dominate real code bases. Knowing the common patterns is the first step to writing robust concurrent code.

Crux: how to recognize and handle common concurrency bugs?

What types of bugs exist?

Lu et al. [L+08] studied fixed concurrency bugs in MySQL, Apache, Mozilla, and OpenOffice (~105 bugs). Most were non-deadlock (74); 31 were deadlock. Mozilla alone contributed nearly 60.

Non-deadlock bugs

About 97% of the non-deadlock bugs were atomicity violations or order violations.

Atomicity violation

A region that should execute atomically does not — e.g. MySQL’s check-then-use of proc_info:

T1: if (thd->proc_info) { fputs(thd->proc_info, ...); }
T2: thd->proc_info = NULL;

If T2 runs between the check and fputs, T1 dereferences NULL.

Fix: one lock around check+use and around the write that clears the field.

Order violation

Required order A-before-B is not enforced — e.g. child thread reads mThread before init finishes assigning it.

Fix: condition variable (or semaphore): state flag + while (!ready) wait / signal after init.

Deadlock

Classic: T1 holds L1 waits for L2; T2 holds L2 waits for L1. A cycle in the wait-for graph means deadlock. It is timing-dependent — the buggy lock order may run many times before it hangs.

Quiz

Rank the sequence

1 / 1

Order the interleaved events that lead T1 and T2 into the classic two-lock deadlock.

OrderDrag the handle to rearrange — top should be first.

1T1 locks L1
2T2 locks L2
3T2 tries to lock L1 and blocks (T1 holds it)
4T1 tries to lock L2 and blocks (T2 holds it)

Drag items into the correct order (or use ↑↓), then check.

Why do deadlocks happen?

Large systems (VM ↔ FS) create natural circular dependencies. Encapsulation hides locks: Java v1.AddAll(v2) vs v2.AddAll(v1) can deadlock inside the library [J+08].

Four Coffman conditions [C+71]

Deadlock needs all four:

Mutual exclusion — exclusive ownership of resources
Hold-and-wait — hold one lock while waiting for another
No preemption — cannot forcibly take a lock away
Circular wait — a cycle in the wait-for graph

Break any one → no deadlock.

Prevention

Break	Technique
Circular wait	Total/partial lock order; sort by lock address when acquiring two mutexes
Hold-and-wait	Acquire all locks under a global “prevention” lock (hurts concurrency / encapsulation)
No preemption	`trylock`; on failure unlock and retry (watch livelock — add random backoff)
Mutual exclusion	Lock-free / wait-free with CAS [H91,H93] — e.g. atomic increment, lock-free list insert

Enforce order by lock address

If do_something(m1, m2) might be called with swapped args, lock in high-to-low (or low-to-high) address order so every call acquires in the same global order.

Avoidance, detect & recover

Avoidance (e.g. Banker’s Algorithm [D64]): schedule threads knowing which locks they need so conflicting pairs never run together — useful mainly in embedded / fully known workloads; often too conservative.

Detect & recover: allow rare deadlocks; reboot or abort a DB transaction. Tom West: not everything worth doing is worth doing well — if failure is rare and cheap, pragmatic recovery beats perfect prevention.

Interactive

Try: bug taxonomy · atomicity · order · deadlock / prevention · lock-free CAS.

Check your understanding

Quiz