Skip to main content
Be Bitwise

Synchronisation Primitives

Concurrency & Race Conditions · VR Foundations track

7 min read

Part ofSystems Programming Companion, week 12

In this module

Controlling the Chaos

The previous lesson showed how unsynchronised concurrent access corrupts data. Synchronisation primitives are the tools that impose order on the chaos. They let programmers carve out critical sections — slices of code where only one thread may run at a time.

Mutexes

A mutex (mutual exclusion lock) is the bread-and-butter synchronisation primitive. A thread has to acquire (lock) the mutex before entering the critical section and release (unlock) it on the way out. If another thread tries to grab a locked mutex, it blocks — the OS puts it to sleep until the lock frees up.

Mutexes fix the counter problem from the last lesson. Wrap the load-add-store sequence in a mutex, and only one thread runs through it at a time. The increment becomes atomic at the application level, even though the underlying machine instructions are anything but.

A mutex has a second job that's easy to miss: it makes writes visible. Unlocking has release semantics and locking has acquire semantics, so everything a thread wrote before pthread_mutex_unlock is guaranteed to be seen by the next thread that locks the same mutex. Without that, another core could still be looking at a stale value even though the threads took turns.

Deadlock

Mutexes bring their own failure mode: deadlock. Thread A holds Mutex 1 and waits for Mutex 2. Thread B holds Mutex 2 and waits for Mutex 1. Neither can move. Both threads are wedged forever. The usual fix is disciplined lock ordering: every thread must acquire mutexes in the same global sequence. When a fixed order isn't possible, a thread can use pthread_mutex_trylock (or pthread_mutex_timedlock) for the second lock, and on failure release what it holds, back off and try again.

Draw who holds what and who's waiting for what, and a deadlock is a cycle you can point at. Lock checkers such as Linux's lockdep look for exactly this shape:

Follow the arrows from Thread A: it waits for Mutex 2, held by B, which waits for Mutex 1, held by A. Lock ordering works because if everyone takes Mutex 1 first, B can never be holding 2 while waiting for 1, and the loop can't close.

Semaphores

A semaphore is the mutex idea, generalised. Rather than admitting one thread, it maintains a count. Each acquire decrements the count; each release puts one back. When the count hits zero, the next acquire blocks. A semaphore initialised to 1 acts much like a mutex. Set it to 10, and up to ten threads can occupy the critical section at once. Handy for connection pools, rate limiting, and bounded buffers.

c
#include <semaphore.h>
sem_t slots;
sem_init(&slots, 0, 10); /* 0: shared between threads, not processes */
sem_wait(&slots); /* take a slot, blocking if all ten are in use */
use_connection();
sem_post(&slots); /* give it back */

Condition Variables

A mutex stops threads colliding, but it can't make a thread wait until something becomes true, such as "the queue isn't empty". A condition variable does that. The waiting thread holds the mutex, checks the condition, and calls pthread_cond_wait, which releases the mutex and sleeps in one step. Another thread changes the state under the same mutex and calls pthread_cond_signal to wake a waiter. Always re-check the condition in a while loop after waking, because wake-ups can be spurious and another thread may have got there first.

c
pthread_mutex_lock(&m);
while (queue_empty(&q))
pthread_cond_wait(&not_empty, &m); /* unlocks m while asleep */
item = queue_pop(&q);
pthread_mutex_unlock(&m);

Spinlocks and Reader-Writer Locks

A spinlock never sleeps. A thread that finds it held just loops, re-checking until it's free. That wastes CPU, but for a critical section a few instructions long it beats the cost of putting a thread to sleep and waking it again, which is why kernels use spinlocks heavily. In user space it's risky: if the holder gets descheduled, every waiter spins uselessly for a whole time slice.

A reader-writer lock (pthread_rwlock_t) lets any number of readers in at once but gives a writer exclusive access. It pays off for data that's read far more often than it's written, such as a configuration table or a routing cache.

Atomic Operations

For something as small as bumping a counter, a full mutex is overkill. Modern CPUs ship atomic instructions that perform read-modify-write as one indivisible hardware operation. The workhorse is compare-and-swap (CAS): read a memory location, compare it against an expected value, and write a new value only if the comparison holds. All in a single instruction.

At the hardware level (connecting to Multi-Core & Coherence), x86 marks these instructions with a lock prefix. On a modern CPU the core grabs exclusive ownership of the cache line holding the variable and refuses to hand it to any other core until the instruction finishes. A true bus lock, which stalls every core at once, only happens in awkward cases such as a variable split across two cache lines.

Worked Example: Three Ways to Fix the Counter

Here's the racy loop from last lesson again: two threads, a million counter++ each. Three fixes, all correct, with very different costs.

1. A mutex around every increment.

c
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
for (int i = 0; i < 1000000; i++) {
pthread_mutex_lock(&lock);
counter++;
pthread_mutex_unlock(&lock);
}

Correct every time. But two threads now fight over the lock two million times, and every handover drags the lock's cache line from one core to the other.

2. An atomic increment.

c
#include <stdatomic.h>
atomic_int counter = 0;
for (int i = 0; i < 1000000; i++)
atomic_fetch_add(&counter, 1);

With gcc on x86-64, that call compiles down to a single lock add instruction. No lock object and no sleeping, though the cache line still bounces between cores on every increment.

3. Count locally, combine once.

c
int local = 0;
for (int i = 0; i < 1000000; i++)
local++;
atomic_fetch_add(&counter, local);

Each thread counts in its own variable, which nobody else can see, and touches shared memory exactly once at the end. Two synchronised operations in total instead of two million.

Predict: which of the three is fastest, and which is slowest?

Version 3 wins by a mile, and version 1 is usually slowest. The mutex version pays for lock and unlock calls plus contention on every iteration. The atomic version is far cheaper per operation but still forces the cores to pass one cache line back and forth two million times. Version 3 shares almost nothing, so the cores barely talk to each other. The best synchronisation is often the synchronisation you design away.

Try to break the two fixes. With the mutex, a thread that reaches a held lock simply can't step. With fetch_add, the read-modify-write is one indivisible step, so there's nothing to interleave.

Counter protected by a mutex

The same counter++, now inside lock(&m) and unlock(&m). A thread that reaches lock while the other holds m has to wait.

T1
  1. 0lock(&m);
  2. 1r1 = counter;// counter++ reads
  3. 2r1 = r1 + 1;// adds
  4. 3counter = r1;// writes back
  5. 4unlock(&m);
Registers
  • r1 = 0
T2
  1. 0lock(&m);
  2. 1r1 = counter;// counter++ reads
  3. 2r1 = r1 + 1;// adds
  4. 3counter = r1;// writes back
  5. 4unlock(&m);
Registers
  • r1 = 0
Shared memory
  • counter = 0
  • m: free
0 steps
Every possible schedule

0 of 2 possible schedules lose an update.

Final resultSchedules
counter = 22

Counter with an atomic fetch_add

atomic_fetch_add reads, adds and writes in one indivisible step (lock xadd on x86), so there is nothing to interleave inside it.

T1
  1. 0r1 = fetch_add(&counter, 1);
Registers
  • r1 = 0
T2
  1. 0r1 = fetch_add(&counter, 1);
Registers
  • r1 = 0
Shared memory
  • counter = 0
0 steps
Every possible schedule

0 of 2 possible schedules lose an update.

Final resultSchedules
counter = 22

Choosing the Right Tool

Reach for atomics on simple counters, flags, and lock-free data structures. Use mutexes when a critical section straddles several variables, because an atomic can only protect one value at a time. Semaphores fit when you want to cap concurrency at N threads, condition variables when a thread has to wait for some state to change, and reader-writer locks when reads vastly outnumber writes. Each rung up the ladder costs more overhead and buys stronger guarantees. The craft of concurrent programming is finding the lightest tool that still keeps correctness intact, and then asking whether the threads needed to share that data at all.