Concurrency & Deadlocks
Concurrency cheat sheet: race conditions, a deadlock in one picture, the four conditions it needs, mutexes, semaphores, condition variables and atomics compared, the ways out of a deadlock, producer / consumer, and a checklist before you add a lock.
Cheat sheet · Offered as a template
In this diagram
- Concurrency & Deadlocks
- ① The problem
- Two threads read, change and write the same data
- The interleaving is different on every run
- Race condition: the result depends on timing
- Critical section: code that must not interleave
- ② A deadlock in one picture
- Thread A
- Lock 1
- Lock 2
- Thread B
- A cycle in the wait-for graph means nobody can move. Break any one of the four conditions and the cycle cannot form.
- ③ All four must hold
- Mutual exclusion: one holder at a time
- Hold and wait: keep what you have while asking for more
- No preemption: nothing can be taken away
- Circular wait: a ring of threads, each waiting on the next
- ④ Synchronisation tools
- ⑤ The classic bug
- race.c
- ⑥ Ways out of deadlock
- Prevent
- Give every lock a rank; always take them in order
- Or take all the locks at once, or none
- Avoid
- Grant a request only if a safe state remains
- Banker’s algorithm; rare outside textbooks
- Detect and recover
- Look for cycles, then kill or roll back a victim
- What databases do
- Ignore
- Assume it is rare and restart when it happens
- What most operating systems do
- ⑦ Producer / consumer
- Producer
- bounded buffer
- Consumer
- The producer waits when the buffer is full, the consumer when it is empty: one mutex and two condition variables.
- ⑧ Other hazards
- Starvation: a thread never gets its turn