Threads sharing memory is useful but dangerous. Without coordination, concurrent reads and writes produce unpredictable results. Synchronisation gives threads the tools to take turns.

The Critical Section Problem#

A critical section is code that accesses shared data. The rules:

  1. Mutual exclusion: at most one thread executes the critical section at a time
  2. Progress: if no thread is in the critical section, a waiting thread must eventually enter
  3. Bounded waiting: no thread should wait forever (no starvation)
Python

Mutex (Mutual Exclusion Lock)#

A mutex is a lock: only one thread holds it at a time. Any thread that tries to lock an already-locked mutex blocks until it's released.

Python

Watch the Race Happen#

Reading about a lost update is not the same as seeing one. Below, two threads each add 1 to a counter that starts at 0, run two ways on one shared clock.

The top two lanes are unsynchronised. Watch T2 read the counter before T1 has written its result back. Both threads then compute 1, both store 1, and one of the two increments simply vanishes. The counter ends at 1 when it should be 2.

The bottom two lanes run the same threads through a mutex. T2's long grey BLOCKED bar is the cost of correctness, and it is the whole trade: the lock makes the run take longer, and it makes the answer right.

The same race happens outside a CPU wherever two requests check a shared value and then act on it. Below, Asha and Ben tap the same great seat in a cinema, C3, at the same moment, first with no lock and then again with one. With no lock, both apps read "C3 free" before either has booked, both pay, both phones show a ticket for C3, and when the show starts, both of them are standing at the same seat. Then the hall resets and the race runs again with a lock: Asha's tap holds C3 in the same step that checks it, so Ben's request finds it held, his phone says it is taken, and he books C4 instead. Check and book have to be one step.

Semaphores#

A semaphore is a generalised synchronisation primitive: a counter with two atomic operations:

  • wait() (P): decrement; if counter < 0, block
  • signal() (V): increment; if any thread is waiting, unblock one

Binary semaphore (counter = 0 or 1): mutex-like, but not identical: a semaphore has no notion of ownership, so any thread can signal it, whereas a mutex can only be released by the thread that acquired it.

Counting semaphore: controls access to a pool of n identical resources.

Python

Producer-Consumer Problem#

The classic synchronisation problem: producers add items to a bounded buffer; consumers remove them. Need to prevent:

  • Producer adding to a full buffer
  • Consumer reading from an empty buffer
Python

Condition Variables#

A condition variable lets a thread wait until a condition becomes true, without busy-waiting. Used with a mutex.

Python

Read-Write Locks#

When many threads read shared data but writes are rare, a standard mutex serialises all reads unnecessarily. A read-write lock allows:

  • Multiple simultaneous readers
  • Exclusive access for a single writer
Python

Deadlock#

A deadlock occurs when a set of threads are each waiting for a resource held by another: circular waiting with no exit.

Coffman's four necessary conditions (all must hold simultaneously):

  1. Mutual exclusion: resources are non-shareable
  2. Hold and Wait: a thread holds one resource while waiting for another
  3. No preemption: resources cannot be forcibly taken
  4. Circular wait: T1 waits for T2's resource; T2 waits for T1's resource

Deadlock example:

Python

Prevention (break circular wait): always acquire locks in the same global order:

Python

Livelock & Starvation#

  • Livelock: threads keep changing state in response to each other but no progress is made (like two people in a corridor both stepping aside for each other).
  • Starvation: a thread repeatedly loses the CPU to higher-priority threads and never runs.

What to Remember#

  • Race conditions occur when concurrent threads access shared mutable state without synchronisation
  • Mutexes enforce mutual exclusion, the foundation of thread-safe code
  • Semaphores generalise mutexes: binary for mutual exclusion, counting for resource pools
  • Deadlock requires all four Coffman conditions; prevent any one to make it impossible
  • Always acquire multiple locks in a consistent global order to eliminate circular wait