Synchronisation & Deadlocks

Threads sharing memory is powerful — 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)

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.

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) — equivalent to a mutex.

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

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

Condition Variables

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

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

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:

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

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.

Key Takeaways

• 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