Locks, Semaphores & Condition Variables

We ended the previous chapter with a clear problem and no solution. Two threads incrementing a shared counter step on each other because counter++ is really three operations — load, add, store — and the scheduler can interleave them at the worst possible moment. We named the dangerous region a critical section and said only one thread may be inside it at a time. This chapter delivers the tools that make that guarantee real, so you never have to invent your own.

It matters that you do not roll your own. Correct mutual exclusion from plain reads and writes is one of the classic hard problems in computer science — Dekker’s and Peterson’s algorithms are elegant but subtle, work only for a fixed number of threads, and quietly break on modern CPUs that reorder memory operations. The primitives in this chapter are built on special hardware instructions and kernel support that ordinary code cannot express, which is exactly why they exist. Reach for them; do not reinvent them.

Mutex (lock)

The simplest tool: exactly one thread holds it at a time, protecting a critical section. Your default choice.

Semaphore

A counter with atomic wait/signal operations; lets up to N threads through, or signals events between threads.

Condition variable

A way for a thread to sleep until some condition on shared data becomes true, always paired with a mutex.

Higher-level tools

Read-write locks, barriers, and language features (Java synchronized, Go channels) built on top of the primitives above.

A mutex — short for "mutual exclusion" — is the most direct tool in the box. It has two operations, lock and unlock, and one rule: at most one thread can hold the lock at any instant. A thread calls lock before entering the critical section; if the lock is free it takes it and proceeds, and if another thread already holds it, the caller waits until it is released. When the thread is done it calls unlock, which lets exactly one waiting thread through. Wrap your critical section between lock and unlock and the race is gone.

Here is the broken counter from the race-condition chapter, now fixed. The only change is a lock around the increment — but that is the whole point: the fix is small, and knowing precisely where to put it is the skill.

#include <pthread.h>

static long counter = 0;
static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

void *worker(void *arg) {
    for (int i = 0; i < 1000000; i++) {
        pthread_mutex_lock(&lock);    /* enter critical section */
        counter++;                    /* now safe: sole occupant */
        pthread_mutex_unlock(&lock);  /* leave; wake one waiter */
    }
    return NULL;
}

With the lock in place, the load–add–store of counter++ can no longer be interrupted by another thread that is also inside the critical section, because there is no other thread inside it — the lock guarantees a single occupant. Run this with two threads and you now get exactly 2,000,000 every time, not the smaller, jittery numbers the unprotected version produced.

A mutex has an owner, and that ownership carries real obligations. The thread that locked it is the one that must unlock it — you cannot hand the lock to a different thread to release, and unlocking a mutex you do not hold is undefined behaviour. The most common bug is not a race at all but a forgotten unlock: return early from the middle of a critical section, or throw past the unlock, and every other thread waits on that lock forever. This is why higher-level languages wrap locks in scope guards — Java’s synchronized block, C++’s std::lock_guard, Python’s with lock — that unlock automatically no matter how control leaves the block.

When a thread calls lock and the lock is already taken, it has to wait — but there are two fundamentally different ways to wait, and the difference is not academic. A spinlock waits by spinning: it sits in a tight loop, repeatedly checking "is the lock free yet?" and burning CPU cycles the entire time. A blocking (or sleeping) lock waits by going to sleep: it tells the OS "put me on this lock’s wait queue and run someone else", giving up the CPU until the lock is released and the OS wakes it back up.

Neither is universally better; they trade the same resource in opposite directions. Spinning wastes CPU while waiting but wakes up instantly the moment the lock frees, with no scheduler involvement. Blocking wastes no CPU while waiting but pays for a context switch to sleep and another to wake — hundreds of nanoseconds to microseconds each way. So the right choice depends entirely on how long you expect to wait.

#include <pthread.h>

pthread_spinlock_t sl;
pthread_spin_init(&sl, PTHREAD_PROCESS_PRIVATE);

pthread_spin_lock(&sl);    /* burns CPU in a loop until acquired */
shared_state++;            /* keep this VERY short */
pthread_spin_unlock(&sl);

• ▸Spin when the critical section is tiny (a few instructions) AND you are on a multicore machine, so the holder can be finishing on another core while you spin.
• ▸Block when the critical section may be long, may do I/O, or may itself wait — you do not want to burn a core for milliseconds.
• ▸Never spin on a uniprocessor: the thread holding the lock cannot make progress while you monopolise the single CPU spinning, so you spin for your whole time slice accomplishing nothing.

Real systems blend the two. The Linux kernel uses spinlocks heavily for the short critical sections deep inside itself, where sleeping is impossible or too slow. User-space mutexes on Linux are built on a mechanism called a futex that does the smart thing: it spins briefly in the hope the lock frees almost immediately, and only falls back to a real sleep in the kernel if the wait drags on. That "spin a little, then block" hybrid is called an adaptive mutex, and it is what you usually get from pthread_mutex_lock in practice.

A semaphore, invented by Edsger Dijkstra, generalises the lock. At its heart it is just a non-negative integer with two atomic operations. wait (historically called P, from a Dutch word) tries to decrement the count: if the count is above zero it decrements and proceeds; if it is zero the caller blocks until someone raises it. signal (called V) increments the count and wakes one waiting thread if any are blocked. The magic is that both operations are atomic — the check-and-decrement in wait cannot be split by another thread, so no race sneaks in.

The cleanest way to picture a counting semaphore is as a pool of identical permits. Initialise it to N and it hands out N permits; each wait takes one, each signal returns one, and when all N are out the next taker waits. This is exactly the shape of a connection pool, a rate limiter, or a bounded set of worker slots: "at most N of you inside at once".

#include <semaphore.h>

sem_t slots;
sem_init(&slots, 0, 3);      /* 0 = shared between threads; start with 3 permits */

void *use_connection(void *arg) {
    sem_wait(&slots);        /* P: take a permit, or block if none free */
    /* ... use one of 3 identical DB connections ... */
    sem_post(&slots);        /* V: return the permit, wake a waiter */
    return NULL;
}

A binary semaphore is simply one initialised to 1: the count is only ever 0 or 1, so it acts like a lock — one thread in, everyone else waits. But a semaphore has a second, distinct use that a lock cannot serve: signalling. Start a semaphore at 0 and it becomes a way for one thread to wake another. The waiter calls wait and blocks (count is 0); when the other thread finishes some work it calls signal (count goes to 1) and the waiter proceeds. Here the semaphore carries no notion of a critical section at all — it is a one-way "go ahead" between threads.

wait / P / sem_wait

Atomically: if count > 0 decrement and continue, else block until count becomes positive.

signal / V / sem_post

Atomically increment the count and wake one blocked waiter, if any.

Counting semaphore

Initialised to N; models a pool of N interchangeable permits (connections, slots, buffers).

Binary semaphore

Initialised to 1 (acts like a lock) or to 0 (used to signal an event from one thread to another).

Beginners often treat a binary semaphore and a mutex as interchangeable — both let one thread in at a time, after all. They are not the same tool, and the differences are exactly the ones that bite you in production. The three that matter are ownership, counting, and intended purpose.

Ownership

A mutex is owned: the thread that locks it must be the one to unlock it. A semaphore has no owner — any thread can call signal, including one that never called wait.

Counting

A mutex is strictly binary (held or free). A semaphore holds an integer and can admit up to N threads, which a mutex simply cannot express.

Purpose

A mutex exists for mutual exclusion. A semaphore is equally at home signalling an event between threads, where there is no critical section at all.

Ownership is the practical dividing line. Because a mutex knows who holds it, the runtime can catch a whole class of bugs (unlocking a lock you never took) and can implement priority-inheritance to fight priority inversion — a trick we meet two sections from now. A semaphore, having no owner, cannot do either. That freedom is also its power: because anyone can post, a semaphore can signal across a producer/consumer boundary where the signaller is not the waiter. That is the one thing a mutex genuinely cannot do.

So the rule of thumb is: if you are guarding shared data — protecting a critical section — use a mutex. It is clearer, it is checkable, and it says exactly what you mean. Reach for a semaphore when you are counting a resource (a pool of N of something) or signalling between threads (one thread waits, another releases). The classic misuse is using a plain binary semaphore where a mutex belongs: you lose the ownership check, and a stray post from the wrong thread silently corrupts your mutual exclusion with no error at all.

Mutexes answer "may I enter?" but not "has the thing I am waiting for happened yet?". Suppose a consumer thread needs an item from a shared buffer, but the buffer is empty. It cannot just hold the mutex and loop — that would spin forever while holding the very lock the producer needs to add an item. What it needs is a way to release the lock and sleep until a producer says "there is an item now", then wake and re-check. That is exactly what a condition variable provides.

A condition variable is always paired with a mutex, and it has three operations. wait atomically releases the mutex and puts the thread to sleep — the atomicity is crucial, because it closes the window in which a signal could slip past between releasing the lock and going to sleep. When woken, wait re-acquires the mutex before returning, so the thread is safely back inside the critical section. signal wakes one waiting thread; broadcast wakes all of them. Together a mutex plus its condition variables form what the literature calls a monitor: shared data, the lock that guards it, and the conditions threads wait on.

The canonical use is the bounded-buffer producer/consumer — a fixed-size queue that producers fill and consumers drain. It is worth studying line by line, because this one pattern underlies thread pools, logging pipelines, message queues, and the internals of Go channels and Java’s BlockingQueue.

#include <pthread.h>
#define N 16

static int buf[N];
static int count = 0, head = 0, tail = 0;

static pthread_mutex_t m         = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t  not_full  = PTHREAD_COND_INITIALIZER;
static pthread_cond_t  not_empty = PTHREAD_COND_INITIALIZER;

void produce(int item) {
    pthread_mutex_lock(&m);
    while (count == N)                      /* WHILE, never if */
        pthread_cond_wait(&not_full, &m);   /* unlock + sleep, then re-lock */
    buf[tail] = item;
    tail = (tail + 1) % N;
    count++;
    pthread_cond_signal(&not_empty);        /* a consumer may now proceed */
    pthread_mutex_unlock(&m);
}

int consume(void) {
    pthread_mutex_lock(&m);
    while (count == 0)                       /* WHILE, never if */
        pthread_cond_wait(&not_empty, &m);
    int item = buf[head];
    head = (head + 1) % N;
    count--;
    pthread_cond_signal(&not_full);         /* a producer may now proceed */
    pthread_mutex_unlock(&m);
    return item;
}

The single most important detail is that both waits sit inside a while loop, never an if. There are two reasons. First, spurious wakeups: pthread_cond_wait is permitted to return even when no one signalled, and correct code must simply re-check its condition and go back to sleep. Second, and more common, is the stolen wakeup: by the time a woken consumer re-acquires the mutex, a different consumer may already have grabbed the only item. Re-testing count == 0 in the loop catches both cases for free. Rewrite while as if and you have planted a race that passes every test until the day it corrupts data in production.

pthread_cond_wait(&c, &m)

Atomically unlock m and sleep on c; on wakeup, re-acquire m before returning. Must be called with m held.

pthread_cond_signal

Wake one thread waiting on the condition variable (if any).

pthread_cond_broadcast

Wake all waiting threads — use it when more than one waiter could now make progress.

Monitor

The bundle of shared data + its mutex + condition variables; the structured way to build safe blocking coordination.

Locks solve races, but they introduce hazards of their own. These deserve full chapters later — deadlock especially — but you should recognise the shapes now, because the moment you use more than one lock you can trip over them.

The headline hazard is deadlock. If thread 1 holds lock A and wants B, while thread 2 holds B and wants A, neither can proceed and neither will let go: a circular wait, frozen forever. Nothing crashes, nothing errors — the threads simply stop, which is what makes deadlock so maddening to diagnose.

/* Thread 1 */                       /* Thread 2 */
pthread_mutex_lock(&A);             pthread_mutex_lock(&B);
pthread_mutex_lock(&B);  /* waits */ pthread_mutex_lock(&A);  /* waits */
/*   ... never reached ...   */     /*   ... never reached ...   */

The cheap, powerful defence is lock ordering: pick one global order for all your locks and always acquire them in that order. If every thread takes A before B, the circular wait above is impossible by construction. This one discipline prevents the overwhelming majority of real deadlocks, and we will formalise why in the deadlock chapters ahead.

Priority inversion is subtler. A low-priority thread grabs a lock; a high-priority thread then needs the same lock and blocks; and a medium-priority thread, needing no lock at all, hogs the CPU and prevents the low-priority holder from ever finishing and releasing. The high-priority thread is now effectively stuck behind a lower-priority one. This is not a textbook curiosity: in 1997 NASA’s Mars Pathfinder lander kept resetting itself on the Martian surface for exactly this reason, and was rescued by remotely enabling priority inheritance — a scheme where the lock temporarily boosts its holder to the priority of the highest waiter so it can finish and get out of the way.

Deadlock

A circular wait where each thread holds a lock another needs; all involved threads freeze permanently.

Lock ordering

The simplest deadlock defence: always acquire multiple locks in one fixed global order.

Priority inversion

A high-priority thread stuck behind a low-priority lock holder that a medium-priority thread keeps off the CPU.

Convoying

Threads pile up behind one slow lock holder and then release in lockstep, destroying throughput and cache locality.

The three primitives so far are the foundation, but you will rarely write raw pthread code in application work. Above them sits a layer of higher-level tools that encode common patterns so you do not re-derive them each time. Knowing which to reach for is a real part of engineering judgement.

A read-write lock (rwlock) recognises that reading shared data is safe to do concurrently — only writing needs exclusivity. It grants either many simultaneous readers or one exclusive writer. For data that is read far more often than written — a configuration table, a routing map, a cache — this can dramatically outperform a plain mutex that would needlessly serialise readers against each other.

#include <pthread.h>
static pthread_rwlock_t rw = PTHREAD_RWLOCK_INITIALIZER;

const char *lookup(int key) {         /* readers run in parallel */
    pthread_rwlock_rdlock(&rw);
    const char *v = table_get(key);
    pthread_rwlock_unlock(&rw);
    return v;
}

void update(int key, const char *v) { /* writer runs alone */
    pthread_rwlock_wrlock(&rw);
    table_put(key, v);
    pthread_rwlock_unlock(&rw);
}

A barrier solves a different problem: making a group of threads meet at a line before any of them may pass. Each thread calls the barrier’s wait when it reaches the checkpoint and blocks until all N have arrived, at which point they are all released together. This is the bread-and-butter of parallel numerical code — finish phase one on every thread, sync at the barrier, then all start phase two — where reading half-finished results from the previous phase would be a bug.

Higher-level languages wrap all of this in friendlier forms. Java’s synchronized keyword is a mutex bolted to an object, with the unlock done automatically when the block exits. Go takes a deliberately different stance — "do not communicate by sharing memory; share memory by communicating" — and offers channels, which are essentially a thread-safe bounded buffer (the very producer/consumer monitor from earlier) dressed up as a language feature. And beneath everything sit atomics: single hardware instructions like compare-and-swap that update a variable indivisibly with no lock at all, the seed of the lock-free structures we tease in the next chapter.

Read-write lock

Many concurrent readers or one exclusive writer; a win for read-mostly data.

Barrier

A rendezvous point: all N threads must arrive before any may continue. Core to phased parallel algorithms.

Language locks

Java synchronized, C++ lock_guard, Python with lock — mutexes with automatic, scope-based release.

Channels & atomics

Go channels package producer/consumer as a language feature; atomics update a value indivisibly with no lock at all.

Everything in this chapter is about correctness first — without these tools your concurrent code is simply wrong. But once it is correct, locks become the number-one thing standing between you and scalability, and that is where senior engineers spend real effort. The reason is lock contention: whenever a critical section is held, every other thread that wants it waits, so the locked region is a stretch of your program that runs strictly one-at-a-time no matter how many cores you own. Add cores and the serial part does not speed up — a direct, painful instance of Amdahl’s law.

The lever is lock granularity. A coarse-grained lock — one big lock around an entire data structure — is trivial to reason about but becomes a bottleneck the moment traffic climbs; throughput rises with threads, then flattens, then can actually fall as threads spend their time fighting over the lock. Fine-grained locking splits that into many small locks (one per hash bucket, one per row) so unrelated operations proceed in parallel. It scales far better, but multiplies the risk of deadlock and is much harder to get right — the eternal trade-off between simple-and-slow and fast-and-subtle.

• ▸Hold locks for as short a time as possible — do slow work (I/O, allocation, formatting) before you take the lock, not while holding it.
• ▸Shrink the critical section, not just the lock’s lifetime: less code under the lock means more parallelism.
• ▸Prefer read-write locks or per-shard locks when contention shows up in profiling — but measure first; fine-grained locking you did not need is just extra deadlock risk.
• ▸Know that lock-free data structures exist: built directly on atomic compare-and-swap, they let threads make progress with no lock at all — powerful, and notoriously hard to write correctly (the subject waiting in the next chapter).

Databases are the clearest real-world showcase of everything here. A database uses two-phase locking on rows and tables to keep transactions isolated — the same mutual-exclusion idea, scaled up to protect your data’s consistency. Internally it also uses short-lived locks it calls latches to guard in-memory structures like the buffer pool and B-tree pages, chosen to be held for the briefest possible moment precisely because contention on them would throttle the whole engine. When you tune a database and hit "lock wait" or "latch contention", you are looking at this chapter, live, under production load.

Lock contention

Threads stalling while they wait for a held lock; the critical section becomes a serial bottleneck that extra cores cannot relieve.

Coarse vs fine-grained

One big lock (simple, low-scaling) versus many small locks (scalable, deadlock-prone). Choose by measured contention.

Lock-free

Structures built on atomic compare-and-swap that avoid locks entirely — fast and scalable, but very hard to write correctly.

Locks vs latches (DB)

Databases use logical locks for transaction isolation and short physical latches for internal structures like the buffer pool.