📘 Synchronization and Deadlocks

When threads or processes share data, the order of their operations becomes unpredictable. This page covers the tools that make shared data safe, the classic problems used to teach them, and deadlock, the most common way those tools go wrong. For language-level APIs see Java Concurrency and JVM and Concurrency in LLD.

Table of Contents

1. Race Conditions
2. The Critical Section Problem
3. Hardware Support
4. Spinlocks and Mutexes
5. Semaphores
6. Monitors and Condition Variables
7. Read-Write Locks and Other Tools
8. Classic Problems
9. Memory Ordering
10. Deadlock
11. Handling Deadlock
12. The Banker's Algorithm
13. Livelock and Starvation
14. Questions

1. Race Conditions

A race condition is when the result depends on the timing of threads.

int counter = 0;          // shared
void *work(void *arg) {
    for (int i = 0; i < 1000000; i++)
        counter++;        // not atomic
    return NULL;
}
// Two threads: expected 2000000, typical results like 1134582

counter++ is three machine steps: load into a register, add 1, store back.

A data race specifically means two threads access the same memory concurrently, at least one writes, and there is no synchronization. In C, C++, and Rust (unsafe) it is undefined behavior; in Java and Go it gives unpredictable results.

Race detectors: ThreadSanitizer (-fsanitize=thread), go test -race, Helgrind.

2. The Critical Section Problem

A critical section is code that accesses shared state and must not run in two threads at once.

A correct solution guarantees:

Peterson's algorithm solves it for two threads with only loads and stores:

bool flag[2] = {false, false};
int turn;

void lock(int i) {          // i is 0 or 1
    int j = 1 - i;
    flag[i] = true;         // I want in
    turn = j;               // but you go first if you want
    while (flag[j] && turn == j) { /* spin */ }
}
void unlock(int i) { flag[i] = false; }

It is a great teaching example but fails on modern CPUs without memory barriers, because hardware and compilers reorder the stores and loads (see Memory Ordering). Real locks use atomic instructions.

3. Hardware Support

Modern CPUs provide atomic read-modify-write instructions.

// Lock-free increment with CAS
void increment(atomic_int *c) {
    int old = atomic_load(c);
    while (!atomic_compare_exchange_weak(c, &old, old + 1)) {
        // old now holds the current value; retry
    }
}

Lock-free algorithms built on CAS never block, but must handle the ABA problem: a value changes from A to B and back to A, so CAS wrongly succeeds. Fixes: version counters (tagged pointers), hazard pointers, or garbage-collected languages.

4. Spinlocks and Mutexes

// A minimal test-and-set spinlock
atomic_flag lock = ATOMIC_FLAG_INIT;
void acquire(void) { while (atomic_flag_test_and_set(&lock)) { /* spin, maybe pause */ } }
void release(void) { atomic_flag_clear(&lock); }

Real mutexes are hybrid: spin briefly, then sleep. On Linux they use a futex (fast userspace mutex): the uncontended path is a single atomic instruction in user space, and the kernel is involved only when a thread actually needs to sleep or wake another.

Mutex rules:

• The thread that locks must unlock (ownership), unlike a semaphore.
• A recursive (reentrant) mutex lets the owner lock again; Java's synchronized and ReentrantLock are reentrant.
• Keep critical sections short; never do I/O or call unknown code while holding a lock.

5. Semaphores

A semaphore (Dijkstra, 1965) is an integer with two atomic operations.

Mutex vs binary semaphore: a mutex has an owner and only the owner may unlock; a semaphore can be signaled by any thread, which makes it suitable for signaling between threads but easier to misuse for locking. Mutexes also support priority inheritance; semaphores usually do not.

6. Monitors and Condition Variables

A monitor bundles shared data with the lock that protects it, so only one thread is active inside at a time. Java objects with synchronized methods are monitors.

A condition variable lets a thread wait inside a monitor until some condition becomes true.

pthread_mutex_lock(&m);
while (queue_is_empty(&q))          // always a loop, never an if
    pthread_cond_wait(&not_empty, &m);   // atomically releases m and sleeps; reacquires on wake
item = dequeue(&q);
pthread_mutex_unlock(&m);

Why while and not if:

1. Spurious wakeups are allowed by the spec.
2. Another thread may take the item between the signal and this thread reacquiring the lock (Mesa semantics, which almost all real systems use; Hoare semantics hand the lock directly but are rare).

signal wakes one waiter, broadcast (Java notifyAll) wakes all.

7. Read-Write Locks and Other Tools

The best synchronization is none: immutable data, message passing (Go channels, actors), or partitioning data so each thread owns its own part.

8. Classic Problems

Producer-consumer (bounded buffer)

semaphore empty = N;   // free slots
semaphore full  = 0;   // filled slots
mutex     m;

void producer(item x) {
    wait(empty);        // wait for a free slot
    lock(m);  put(x);  unlock(m);
    signal(full);       // one more item
}

item consumer(void) {
    wait(full);         // wait for an item
    lock(m);  item x = take();  unlock(m);
    signal(empty);      // one more free slot
    return x;
}

Order matters: calling lock(m) before wait(empty) in the producer deadlocks when the buffer is full, because the consumer can never get the mutex to free a slot.

This is the pattern behind every blocking queue, pipe, and thread pool work queue.

Readers-writers

Many readers may read at once; a writer needs exclusive access.

Dining philosophers

Five philosophers, five forks, each needs both neighbors' forks to eat. If everyone picks up the left fork at once, everyone waits forever for the right one: deadlock.

Solutions:

• Resource ordering: number the forks and always pick up the lower number first (breaks circular wait); this is the general fix for lock ordering in real code.
• Allow at most four philosophers to sit at once (a counting semaphore of 4).
• Pick up both forks atomically, or only if both are free.
• An asymmetric rule: odd philosophers pick left first, even pick right first.

9. Memory Ordering

Compilers and CPUs reorder memory operations for speed, as long as a single thread cannot tell the difference. Other threads can.

// Thread 1                 // Thread 2
data = 42;                  while (!ready) {}
ready = true;               print(data);   // may print 0 without proper ordering

Locks, atomics, volatile in Java, and channels all include the right barriers. The happens-before relationship in the Java and C++ memory models defines when one thread's write is guaranteed visible to another. Rule for application code: always use proper synchronization primitives and never invent your own flags without atomics.

10. Deadlock

A deadlock is a set of tasks each waiting for a resource held by another in the set, so none can proceed.

Coffman conditions, all four must hold at once:

A resource allocation graph shows tasks and resources; with one instance per resource, a cycle means deadlock. With multiple instances, a cycle means deadlock is possible but not certain.

11. Handling Deadlock

Practical checklist for application code:

• Always acquire locks in a documented global order (for example by account ID when transferring between accounts).
• Hold locks for as short a time as possible and never across network calls.
• Use tryLock with a timeout where ordering is impossible.
• Prefer higher-level constructs (concurrent collections, queues, actors).
• Diagnose with thread dumps: jstack, kill -3 on the JVM, gdb thread apply all bt, or Go's SIGQUIT goroutine dump.

12. The Banker's Algorithm

Five processes and three resource types (A, B, C), with 10, 5, and 7 total instances.

Available = (3, 3, 2).

Safety check: repeatedly find a process whose Need fits in Work, pretend it finishes, and return its allocation.

Safe sequence: P1, P3, P0, P2, P4 (other safe orders exist). A request is granted only if, after pretending to grant it, the state is still safe.

Safe vs unsafe: an unsafe state is not necessarily deadlocked, but the OS can no longer guarantee avoiding one.

13. Livelock and Starvation

Ethernet's randomized exponential backoff after collisions is a textbook livelock prevention.

14. Questions

Next: Memory Management.