Synchronisation: locks, mutexes and semaphores

The critical section problem, mutexes and semaphores compared, condition variables, atomic operations, and how reader-writer locks trade fairness for concurrency.

The critical section

Two threads that read, modify and write the same memory can interleave. The fix is to make the read-modify-write sequence atomic with respect to other threads, which is what a lock provides.

// broken: the increment is three operations, not one
counter++;

// roughly:
//   load   counter -> register
//   add    1, register
//   store  register -> counter
// two threads can interleave between the load and the store, losing one update

Primitive	Guarantee	Use when
Mutex	Only the owner may unlock	Protecting a critical section
Binary semaphore	Any thread may signal	Signalling between threads
Counting semaphore	Up to N holders	Limiting concurrency to a pool size
Condition variable	Wait until a predicate holds	Waiting for a state change
Read-write lock	Many readers or one writer	Read-heavy shared data
Spinlock	Busy-waits instead of sleeping	Very short critical sections in kernel or RT code
Atomic operation	Single indivisible instruction	Counters, flags, lock-free structures

Using them correctly

import threading

lock = threading.Lock()
condition = threading.Condition(lock)
queue = []

def producer(item):
    with condition:
        queue.append(item)
        condition.notify()          # wake one waiter

def consumer():
    with condition:
        while not queue:            # ALWAYS a while, never an if
            condition.wait()
        return queue.pop(0)

# a semaphore limits concurrency to a fixed number of slots
slots = threading.Semaphore(4)

def handle(req):
    with slots:
        process(req)

The while loop around wait is mandatory: a wake-up may not mean the condition is true, and spurious wake-ups happen.
Hold a lock for the shortest time possible; never do I/O, allocate heavily or call out to another service while holding one.
A recursive mutex lets the same thread lock twice; it hides design problems more often than it solves them.
A reader-writer lock improves concurrency only when reads dominate and the critical section is long enough to matter.
Default mutexes in Java and C++ are not fair, so a waiting thread can starve indefinitely under contention.

Atomics and lock-free code

#include <stdatomic.h>

atomic_int counter = 0;

void bump(void) {
    // single indivisible increment, no lock needed
    atomic_fetch_add_explicit(&counter, 1, memory_order_relaxed);
}

// compare-and-swap is the building block of lock-free algorithms
int expected = 0;
atomic_compare_exchange_strong(&counter, &expected, 42);

Memory order	Guarantee	When it is enough
relaxed	Atomicity only, no ordering	Standalone counters and statistics
acquire	Later reads cannot move before it	Reading a flag published by another thread
release	Earlier writes cannot move after it	Publishing data for another thread
acq_rel	Both directions	Read-modify-write on shared state
seq_cst	A single global order, the default	When in doubt; the slowest option

⚠️

Lock-free does not mean fast, and it does not mean simple. Getting the memory ordering wrong produces a bug that appears once a month on one machine and never reproduces under a debugger. Prefer a well-tested library over a hand-rolled lock-free structure.

FAQ

Mutex or semaphore?

A mutex is about ownership: one thread holds it and must release it. A semaphore is about signalling and counting: any thread may post, and it has no owner. Using a semaphore as a mutex works until a bug needs the ownership guarantee.

How long should a critical section be?

As short as correctness allows. If it contains a network call, a disk write or a large allocation, redesign so the shared state is updated under the lock and the slow work happens outside it.

Races, deadlocks and starvation Concurrency models: threads, async and processes

Last refreshed 2026-09-18.

Synchronisation: locks, mutexes and semaphores

The critical section

Using them correctly

Atomics and lock-free code

FAQ

Related