Concurrency, Locks & Deadlocks — Sharing Without Breaking

What you'll learn

• What a race condition is and why counter++ is not one step
• How a mutex protects a critical section, and which hardware instructions make locks possible
• How condition variables let a thread sleep until something becomes true, and why you always wait in a while loop
• How semaphores count resources, as in the classic producer-consumer problem
• How deadlocks arise (the four Coffman conditions) and how a consistent lock order prevents them

You will build a real bounded buffer with POSIX threads in C, a semaphore simulator in Python and a lock-order checker in JavaScript.

A race on one line of code 🏁

Two threads share a global counter and both run counter++. It looks like one step, but the CPU executes it as three instructions: load the value into a register, add 1, store it back. The scheduler may switch threads between any two of them:

thread A                 thread B                 counter
load  rA = counter                                5
                         load  rB = counter       5
add   rA = rA + 1  (6)                            5
                         add   rB = rB + 1  (6)   5
store counter = rA                                6
                         store counter = rB       6   <- one increment lost

Both threads did their work, yet the counter went from 5 to 6. This is a race condition: the result depends on the timing of the threads. Races are nasty because they are rare: a program passes a thousand tests and then fails on a busy production server. In C and C++ an unsynchronised data race is even undefined behaviour (C11), so the compiler may assume it never happens.

The code that touches shared data is a critical section. A correct solution must give:

• Mutual exclusion: at most one thread inside the critical section at a time
• Progress: if nobody is inside, a thread that wants to enter eventually can
• Bounded waiting: no thread waits forever while others keep entering

Count how often the race bites if every interleaving is equally likely:

Locks: one thread at a time 🔒

A mutex (mutual exclusion lock) has two operations: lock waits until the mutex is free and takes it; unlock releases it. With POSIX threads (pthreads(7)):

pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;

void increment(void) {
    pthread_mutex_lock(&m);     /* enter the critical section */
    counter++;                  /* only one thread can be here */
    pthread_mutex_unlock(&m);   /* leave it */
}

Building a lock out of ordinary loads and stores is fragile on modern CPUs, which reorder memory accesses, so the hardware provides atomic instructions that read and modify memory in one indivisible step: test-and-set, compare-and-swap (lock cmpxchg on x86) or load-linked/store-conditional pairs (ARM). A spinlock loops on such an instruction until it wins; that wastes CPU time but suits very short sections inside the kernel. A blocking mutex puts the waiter to sleep instead. On Linux, glibc's mutex is built on the futex system call: without contention, lock and unlock are a single atomic instruction in user space, and the kernel is involved only to put a thread to sleep or wake it.

Rules of thumb:

• A lock protects data, not code: every access to that data, reads included, must hold the same lock
• Keep critical sections short; do not do slow I/O while holding a lock
• Unlock on every path, including early returns and errors

Waiting for a condition: condition variables ⏳

Often a thread must wait until something becomes true: a queue is no longer empty, a buffer has room. Spinning on while (count == 0) {} burns a CPU and still races. A condition variable lets a thread sleep until another thread signals it:

pthread_mutex_lock(&m);
while (count == 0)                       /* WHILE, not if */
    pthread_cond_wait(&not_empty, &m);   /* unlocks m, sleeps, relocks m on wake-up */
item = take_one();
pthread_cond_signal(&not_full);          /* someone may be waiting for room */
pthread_mutex_unlock(&m);

pthread_cond_wait releases the mutex and goes to sleep atomically, so a signal cannot slip in between the check and the sleep. Always re-check the condition in a while loop: POSIX allows spurious wake-ups, and another thread may have taken the item between the signal and the moment you run again.

This is the heart of the producer-consumer (bounded buffer) problem: a producer adds items to a buffer with a fixed number of slots and a consumer removes them; the producer must wait while the buffer is full and the consumer while it is empty. The pipes from the shell lesson work exactly like this inside the kernel. Build one:

Semaphores: counting permits 🎫

A semaphore (introduced by Dijkstra in the 1960s) is an integer with two atomic operations:

• wait (P, sem_wait): if the value is above 0, decrement it and continue; otherwise sleep until that becomes possible
• signal (V, sem_post): increment the value, or hand the unit directly to one sleeping thread

Initialised to 1, a semaphore works as a lock (a binary semaphore). Initialised to N, it counts N identical resources: database connections, buffer slots, parking spaces. Unlike a mutex, a semaphore has no owner: any thread may signal it. The bounded buffer written with semaphores uses three of them:

slots = N  (free slots)     items = 0  (filled slots)     mutex = 1

producer:  wait(slots); wait(mutex); put(x);     signal(mutex); signal(items)
consumer:  wait(items); wait(mutex); x = take(); signal(mutex); signal(slots)

Order matters here too: if the consumer did wait(mutex) before wait(items) on an empty buffer, it would sleep while holding the mutex, and the producer could never get in to add an item. That is a deadlock, the topic after the next lab.

Deadlocks: everyone waits for everyone 🔁

A deadlock is a set of threads in which each one waits for a resource that another thread of the set holds, so none of them can ever continue. Coffman, Elphick and Shoshani (1971) showed that a deadlock needs all four of these conditions at once:

1. Mutual exclusion: a resource is held by one thread at a time
2. Hold and wait: a thread holds one resource while waiting for another
3. No preemption: a resource cannot be taken away; only its holder releases it
4. Circular wait: there is a cycle T1 → T2 → ... → T1 of threads waiting for each other

Break any one and deadlock becomes impossible. In practice the most useful target is circular wait: give every lock a place in one global order and always acquire locks in that order. If every thread that needs both accounts and audit takes accounts first, no cycle can form. Other tools:

• Try and back off (breaks no preemption: a thread that cannot get its next lock gives up the one it holds): pthread_mutex_trylock the second lock; if that fails, release the first and retry later. (Hold and wait is broken differently: take every lock you will need at once, before you start.) Beware of livelock, where threads keep retrying in lockstep and nobody progresses
• Avoidance: grant a request only if the system stays in a safe state (the Banker's algorithm). General-purpose OSes rarely do this because it needs to know every future request
• Detection and recovery: build the wait-for graph, look for a cycle and abort one victim; databases do this with transactions

The Linux kernel checks its own locks this way: lockdep records which lock was taken while holding which, and warns about a possible deadlock the first time it sees two locks taken in inverted order, even if the bad interleaving never actually happened. Watch a deadlock happen, then disappear with a consistent order:

Summary

• A race condition happens when the result depends on thread timing; counter++ is three instructions, so updates get lost. Code touching shared data is a critical section and needs mutual exclusion, progress and bounded waiting
• A mutex gives mutual exclusion; it is built on atomic instructions (test-and-set, compare-and-swap), and on Linux on futex so the uncontended case stays in user space
• A condition variable lets a thread sleep until a condition holds; pthread_cond_wait releases the mutex atomically, and you always wait in a while loop
• A semaphore counts permits: value 1 is a lock, value N guards N resources; the bounded buffer uses slots, items and mutex
• A deadlock needs all four Coffman conditions; a global lock order removes circular wait, and tools like lockdep check that order automatically
• You built a real pthread bounded buffer, a semaphore simulator and a lock-order checker

Practice: read pthreads(7) and sem_overview(7), then compile the race from this lesson with real threads and gcc -fsanitize=thread on a Linux machine to watch ThreadSanitizer report it. Next: file systems, where a crash between two writes causes the same kind of inconsistency a race does.