Part 3 · 2 chapters · ~12 min

Synchronisation

Race conditions and critical sections, atomic instructions, spinlocks and mutexes, semaphores, condition variables and monitors, readers-writer locks, deadlock and its four conditions, prevention by lock ordering, livelock and starvation, and the same problems in databases and distributed systems.

Races and critical sections

code

// a condition variable: a bounded queue where consumers sleep until items arrive (pseudocode, pthread-style)
lock(m);
while (queue.empty()) wait(not_empty, m);   // releases m while sleeping; re-acquires on wake; loop for spurious wakeups
item = queue.pop();
signal(not_full);
unlock(m);

A RACE CONDITION, STEP BY STEP

two threads increment a shared balance; one update is lost

swipe the figure sideways, or tap expand for full screen

1/4

the read

Both threads read the same balance before either writes. Each believes it is working from the current value.

both read 100nothing is wrong yet

Deadlock

Coffman condition	break it by
mutual exclusion	lock-free structures, or sharing less
hold and wait	acquire all locks at once, or none
no preemption	timeouts (tryLock, lock_timeout) and retry
circular wait	a global lock order: always lock accounts in id order (Ledgers part 1 does this)

All four must hold for deadlock; removing any one prevents it. Databases detect deadlocks with a wait-for graph and abort a victim (MySQL course part 5); distributed locks need leases and fencing tokens (Distributed Systems part 6). Livelock (everyone retrying in lockstep) is fixed with randomised backoff; starvation with fair queues.