Synchronization in Linux

01 Introduction

The previous six lessons of this unit introduced the classical synchronization abstractions: race conditions, critical sections, locks, semaphores, monitors, and condition variables. Those abstractions are general — they appear in every operating system and every concurrent language. This final lesson examines the specific mechanisms that Linux provides to implement them.

Linux has two distinct worlds of synchronization. The user-space world is the one most programmers work in: the POSIX threading library (pthread) provides mutexes, condition variables, read-write locks, spinlocks, and barriers, and the POSIX semaphore library provides semaphores. These primitives are standardized and portable. A program written against them runs on Linux, macOS, the BSDs, and any other POSIX-conformant system.

The kernel-space world is the one the kernel uses internally. The kernel cannot use the POSIX library — it does not have an underlying library to call — so it provides its own primitives: spinlocks, mutexes, reader-writer locks, seqlocks, RCU, completion variables, and atomic operations. These primitives have different names, different semantics, and different constraints from their user-space counterparts, because they operate in a context where sleeping is forbidden in some places and preemption is disabled in others.

Between the two worlds sits the futex — the fast userspace mutex mechanism introduced in Lesson 6.3. The futex is the bridge: the user-space POSIX mutex is implemented on top of it, and it uses the kernel only when a thread must actually block. Understanding the futex completes the picture of how user-space synchronization works on Linux.

This lesson closes the unit. It surveys both worlds, places each primitive in its appropriate context, and provides the practical guidance for choosing among them. It also closes with a bridge to Unit 7, which examines the problem that arises when multiple locks are held simultaneously: deadlock.

02 Learning objectives

This lesson contributes to U6.5 and U6.6, and to course learning outcomes CLO2, CLO3, and CLO6.

03 Required reading

• Silberschatz et al. — Chapter 6, Section 6.9, Synchronization Examples. The POSIX synchronization primitives and the Java synchronization primitives, side by side.
• Love, R. — Linux Kernel Development, 3rd ed., Chapter 9, Kernel Synchronization Methods, and Chapter 10, Synchronization Methods, Part II. The authoritative treatment of the kernel's primitives. Read the chapters together; they cover atomics, spinlocks, mutexes, semaphores, completion variables, RCU, and the memory barriers.
• Love, R. — Linux System Programming, 2nd ed., Chapter 10, Concurrency. The user-space view of the same topic.
• Butenhof, D. R. — Programming with POSIX Threads, Chapters 7 and 8. The definitive reference for the POSIX primitives — mutexes, condition variables, read-write locks, spinlocks, and barriers.
• Drepper, U. — Futexes Are Tricky. Red Hat, 2004. The futex interface and its pitfalls.
• McKenney, P. E. — Is Parallel Programming Hard, And, If So, What Can You Do About It? The definitive reference for RCU and the parallel-programming techniques it enables.
• Linux man pages: man 7 pthreads, man 7 sem_overview, man 2 futex, man 3 pthread_mutex_init, man 3 pthread_cond_init, man 3 pthread_rwlock_init, man 3 pthread_spin_lock, man 3 pthread_barrier_init, man 3 pthread_mutexattr_setprotocol, man 3 pthread_mutexattr_setpshared.

04 Core content

4.1 The two worlds of Linux synchronization

Synchronization in Linux is divided between user space and kernel space. The division is not arbitrary; it follows from the different constraints of the two environments.

• User space is where applications run. The synchronization primitives here must be portable across POSIX systems, must be safe to use from many threads, and must not require privileges. They are provided by the C library (glibc on Linux), which implements them using the kernel only when necessary.
• Kernel space is where the kernel itself runs. The synchronization primitives here must work in contexts where the kernel cannot sleep (interrupt handlers, softirqs, some spinlock-protected regions), must be fast enough for the hot paths of the networking and file-system code, and must work on a wide range of hardware, including systems with hundreds of cores. They are provided by the kernel itself and cannot be called from user space.

The two worlds are linked by the futex, which is the only primitive that exists in both. A futex is a user-space integer that the kernel treats specially: user-space code manipulates it with atomic operations, and the kernel is involved only when a thread must wait or be woken. The user-space POSIX mutex is built on top of futexes; the futex is the mechanism by which the user-space world calls into the kernel world when it needs to.

4.2 The POSIX user-space primitives

The POSIX threading library provides six categories of synchronization primitive, and the POSIX semaphore library provides a seventh. The table below summarises them and the appropriate use of each.

Each of the mutex-family types can be configured with attributes that change its behaviour. The most important attributes are:

• Type. A normal mutex (PTHREAD_MUTEX_NORMAL) does not check for errors: relocking a held mutex deadlocks the thread silently, and unlocking an unheld mutex is undefined. An error-checking mutex (PTHREAD_MUTEX_ERRORCHECK) returns EDEADLK on a relock and EPERM on an unlock of an unheld mutex — useful during development but slower in production. A recursive mutex (PTHREAD_MUTEX_RECURSIVE) allows a thread to relock a mutex it already holds, maintaining a lock count; each lock must be balanced by an unlock. A default mutex (PTHREAD_MUTEX_DEFAULT) has implementation-defined semantics for relock, but on Linux it behaves like a normal mutex.
• Process-shared. By default, a mutex is shared only between threads of the same process. Setting PTHREAD_PROCESS_SHARED allows it to be shared between processes that map the same memory region — useful for process-level cooperation but with higher overhead on every operation.
• Protocol. By default, a mutex does not implement any priority protocol. Setting PTHREAD_PRIO_INHERIT enables priority inheritance, so that a low-priority thread holding the mutex temporarily inherits the priority of a high-priority thread that blocks on it. Setting PTHREAD_PRIO_PROTECT enables the priority ceiling protocol. These are used in real-time systems to bound priority inversion (Lesson 5.4).
• Robustness. A robust mutex (PTHREAD_MUTEX_ROBUST) detects when the thread holding it has died, so that another thread can take over. This matters for process-shared mutexes in shared memory, where a crashed process would otherwise leave the mutex permanently locked.

4.3 The futex bridge

The futex (fast userspace mutex) is the mechanism that makes user-space locking fast on Linux. It was introduced in Lesson 6.3 and is worth revisiting here in its role as the bridge between the two worlds.

The futex's essential design is a division of labour. The common case — acquiring or releasing an uncontended lock, or acquiring a lightly contended one after a short spin — is handled entirely in user space, by atomic operations on a 32-bit integer. The rare case — blocking a thread that cannot acquire the lock, or waking one — is handled by the kernel, via two futex system calls: FUTEX_WAIT and FUTEX_WAKE.

/* User-space fast path of an uncontended lock acquire */
if (atomic_exchange(&lock->state, 1) == 0)
    return;                 /* we got it — no system call */

/* Slow path: another thread holds the lock */
while (atomic_exchange(&lock->state, 2) != 0) {
    syscall(SYS_futex, &lock->state, FUTEX_WAIT, 2, NULL, NULL, 0);
    /* returns when the kernel wakes us */
}

The user-space POSIX mutex, condition variable, read-write lock, and semaphore are all built on top of futexes. When you call pthread_mutex_lock, the library attempts the atomic fast path and, if it fails, enters the kernel through the futex system call. The result is that the kernel is involved only when it must be: an uncontended mutex is acquired and released with a couple of atomic instructions and no system call at all.

The futex interface is not part of POSIX. It is a Linux-specific mechanism, and the futex man page describes it as "not intended for direct use from applications". The interface is complex and its contract is easy to violate — the kernel checks a futex value before sleeping, and the check-then-wait sequence is racy if not done carefully. The recommendation is always to use the POSIX primitives rather than raw futexes, and to use raw futexes only when implementing a runtime or a lock library.

4.4 The kernel's synchronization primitives

The kernel cannot use the POSIX library. It provides its own primitives, with semantics that reflect the constraints of kernel code. The most important of these are listed below.

spinlock_t

A spinlock. The kernel version of the spinlock from Lesson 6.3. It busy-waits until the lock is free, and it must be used only in contexts where sleeping is forbidden — interrupt handlers, softirqs, and any code that holds a spinlock with interrupts disabled. The critical section must be short, and it must not block or sleep. The kernel provides many variants, including spin_lock_irqsave (disables local interrupts and saves their previous state) and spin_lock_bh (disables bottom halves), to protect against interrupt handlers that might try to acquire the same lock.

struct mutex

A sleeping lock. The kernel's mutex is a blocking lock: when a thread cannot acquire it, the thread sleeps, and the scheduler runs another thread. It is the right choice for critical sections that may be long, for code that may need to sleep (allocate memory, wait for I/O), and for any context where sleeping is permitted. The mutex cannot be used in an interrupt handler, because interrupt handlers cannot sleep.

rwlock_t and struct rw_semaphore

Reader-writer locks. The rwlock_t is the spinning variant and is used in the same contexts as a spinlock; the rw_semaphore is the sleeping variant. Both allow multiple readers simultaneously but only one writer. They are used for data structures that are read much more often than they are written.

seqlock_t

A sequence lock, optimised for write-rarely, read-frequently data. Readers read the sequence number, read the data, then re-read the sequence number; if the number has changed, the read was concurrent with a write and must be retried. Readers never block, and readers do not block writers; the write path is very fast. The classic use is the system clock and other frequently-read, rarely-written values.

struct completion

A one-shot rendezvous. A completion variable lets one thread wait for another to finish some work. It is used throughout the kernel for the pattern "thread A does work, thread B waits for it to finish". The completion is initialised once, waited on once, and completed once. It is a lighter-weight mechanism than a full semaphore or mutex for this specific pattern.

struct rcu_head and the RCU API

Read-copy-update, the most distinctive of the kernel's synchronization mechanisms. RCU allows lock-free reads of a data structure that may be modified concurrently. Readers execute an rcu_read_lock/rcu_read_unlock pair around the read, but this does not actually lock anything — it merely marks the read as being in progress. Writers make a copy of the data structure, modify the copy, and atomically swap the new version in, then wait for all current readers to finish before freeing the old version. Readers never block; writers pay the cost of copying and of waiting for readers to quiesce. RCU is used throughout the kernel for read-mostly data structures: the routing table, the process table, the file descriptor table, and many others.

atomic_t, atomic_long_t, atomic64_t

Atomic integer types. The kernel provides functions for atomic increment, decrement, addition, subtraction, and compare-exchange on these types. They are used for reference counts, statistics counters, and any single-variable operation that must be atomic but does not warrant a full lock.

Memory barriers: smp_mb(), smp_rmb(), smp_wmb()

Full, read, and write memory barriers. These prevent the compiler and the CPU from reordering memory accesses across the barrier. They are needed when a synchronization protocol depends on the order of memory operations, and they are one of the most subtle aspects of kernel programming. A locking primitive that is used correctly provides the necessary barriers implicitly; barriers are needed only when building a primitive, not when using one.

4.5 Spinlock or mutex: the fundamental kernel choice

The most important decision in kernel synchronization is the choice between a spinlock and a mutex. The two are appropriate in different contexts, and choosing wrongly is a serious bug.

The rule of thumb is: use a spinlock when the critical section is short and you are certain the holder will not sleep; use a mutex in every other case. Most kernel code that touches user data, allocates memory, or waits for I/O uses a mutex. Spinlocks are used in the hottest paths — the scheduler, the interrupt handlers, the networking stack — where the cost of a context switch would be prohibitive.

4.6 Per-CPU variables

A theme that appears in both worlds — and especially in the kernel — is that the fastest way to synchronize is often to avoid sharing altogether. The kernel provides per-CPU variables: variables for which each CPU has its own copy, so that a thread running on a given CPU accesses only that CPU's copy and never contends with threads on other CPUs.

DEFINE_PER_CPU(int, my_counter);

/* On the current CPU, no lock needed */
this_cpu_inc(my_counter);

/* To read another CPU's value, use a per-CPU accessor */
int total = 0;
int cpu;
for_each_possible_cpu(cpu)
    total += per_cpu(my_counter, cpu);

Per-CPU variables are used for statistics counters, the scheduler's runqueues, and many other data structures where the natural scope of the data is per-CPU. The general principle — partition the state so that threads do not share it — is the same one we saw in Lesson 6.3 for the per-thread counter, and it is arguably the most important technique in scalable concurrent programming. A per-CPU variable requires no lock at all, because by construction no two threads can access the same copy concurrently.

The trade-off is that reading the aggregate value — the sum across all CPUs — is more expensive, because each CPU's copy must be read separately. Per-CPU variables are therefore appropriate when writes are frequent and reads are rare, or when the read can tolerate a slightly stale value.

4.7 RCU: read-copy-update

RCU is the most distinctive of the kernel's synchronization mechanisms, and it is worth understanding because it illustrates a general principle about read-mostly data structures.

The problem RCU solves is this: many kernel data structures are read extremely frequently and modified only rarely. The routing table, the process table, and the file descriptor table are examples. A conventional lock — even a reader-writer lock — imposes a cost on every read, because readers must acquire and release the lock. RCU removes that cost entirely by allowing readers to access the data without any lock at all.

The mechanism is as follows. Readers execute an rcu_read_lock that does not acquire any lock at all — it merely informs the kernel that the current thread is in an RCU read-side critical section. The reader then accesses the data structure normally and executes rcu_read_unlock. Writers do not modify the existing data structure; they make a copy, modify the copy, and atomically install the copy as the new version of the data structure. The old version is not freed immediately, because existing readers may still be reading it. Instead, the writer registers the old version with the kernel, which frees it only after all current RCU readers have finished (after a "grace period"). Readers never block; writers block briefly while installing the new version, and the freeing is deferred.

The result is a data structure that can be read without any synchronization overhead at all — the reader does not even touch shared state to enter or leave the critical section. This is a substantial advantage on a many-core system, where lock contention would otherwise dominate the cost of a read.

RCU is not a general-purpose replacement for locks. It requires a workload where reads dominate writes (typically by a factor of ten or more), where readers can tolerate seeing an old version of the data for a short period, and where the update operation can be expressed as "replace the whole structure" rather than "modify in place". Where these conditions hold, RCU is dramatically faster than any lock. Where they do not, a lock is the right choice.

4.8 Choosing the right primitive

The following decision procedure is a useful guide for choosing the right synchronization primitive in Linux.

1. Can the operation be expressed as a single atomic instruction? If so, use an atomic operation — atomic_fetch_add in user space, this_cpu_inc or atomic_inc in the kernel. No lock needed.
2. Can the state be partitioned? If so, give each thread or CPU its own copy — a per-thread counter, a per-CPU variable — and combine the values only when necessary. No lock needed in the common case.
3. Is the critical section short and free of any operation that might block? In user space, use a spinlock or a mutex; in the kernel, use a spinlock. The choice between spinlock and mutex depends on the expected contention and on whether sleeping is allowed.
4. Is the critical section long, or does it contain operations that may block? Use a mutex (user space or kernel). The mutex blocks rather than spinning, so it does not waste CPU.
5. Is the data read much more often than it is written? Use a reader-writer lock (user space or kernel). If the read-mostly property is extremely strong and the workload is in the kernel, use RCU.
6. Is the problem one of signalling rather than mutual exclusion? Use a condition variable (user space) or a completion (kernel). A one-shot wait is cheaper than a full semaphore or mutex.
7. Is the problem a count of available resources? Use a semaphore. The counting semaphore is the right tool when multiple threads share a pool of N identical units.
8. Is the problem specific to a monitor-style pattern? Use a mutex and one or more condition variables (user space) or the equivalent kernel pattern. The monitor is a programming discipline, not a single primitive.

The general guidance is to start with the simplest primitive that solves the problem, and to add complexity only when measurement shows that the simplest choice is too slow. Most synchronization needs are met by a mutex and, occasionally, a condition variable. The more elaborate primitives — reader-writer locks, RCU, per-CPU variables — are optimisation tools that should be reserved for the hot paths where they make a measurable difference.

4.9 Common misconceptions

05 Worked example

The following example implements the same synchronization problem — a bounded buffer — with three of the Linux primitives and compares their behaviour and performance.

typedef struct {
    pthread_mutex_t mutex;
    pthread_cond_t  not_full;
    pthread_cond_t  not_empty;
    int buffer[100];
    int in, out, count;
} buffer_t;

void buffer_insert(buffer_t *b, int item) {
    pthread_mutex_lock(&b->mutex);
    while (b->count == 100)
        pthread_cond_wait(&b->not_full, &b->mutex);
    b->buffer[b->in] = item;
    b->in = (b->in + 1) % 100;
    b->count++;
    pthread_cond_signal(&b->not_empty);
    pthread_mutex_unlock(&b->mutex);
}

sem_t empty, full, mutex;

void buffer_insert(int item) {
    sem_wait(&empty);
    sem_wait(&mutex);
    buffer[in] = item;
    in = (in + 1) % 100;
    sem_post(&mutex);
    sem_post(&full);
}

typedef struct {
    int      buffer[100];
    atomic_int in;
    atomic_int out;
} spsc_buffer_t;

bool spsc_try_insert(spsc_buffer_t *b, int item) {
    int in  = atomic_load_explicit(&b->in,  memory_order_relaxed);
    int out = atomic_load_explicit(&b->out, memory_order_acquire);
    int next = (in + 1) % 100;
    if (next == out)
        return false;           /* buffer full */
    b->buffer[in] = item;
    atomic_store_explicit(&b->in, next, memory_order_release);
    return true;
}

bool spsc_try_remove(spsc_buffer_t *b, int *item) {
    int out = atomic_load_explicit(&b->out, memory_order_relaxed);
    int in  = atomic_load_explicit(&b->in,  memory_order_acquire);
    if (out == in)
        return false;           /* buffer empty */
    *item = b->buffer[out];
    atomic_store_explicit(&b->out, (out + 1) % 100,
                         memory_order_release);
    return true;
}

06 Interactive activity

07 Knowledge check

08 Unit discussion

09 Practice exercise

10 Summary

• Linux provides synchronization in two worlds: the POSIX primitives available to user-space programs, and the kernel's own primitives. They are linked by the futex, which is the mechanism by which user-space locks call into the kernel when a thread must block or be woken.
• The POSIX primitives are pthread_mutex_t (mutual exclusion), pthread_cond_t (waiting for a condition), pthread_rwlock_t (reader-writer), pthread_spinlock_t (busy-wait), pthread_barrier_t (rendezvous), and sem_t (counting semaphore). C11 provides <stdatomic.h> for lock-free operations.
• The futex divides the work: the uncontended fast path is handled entirely in user space by atomic operations, and the kernel is entered only when a thread must block or be woken. This makes an uncontended POSIX mutex a couple of atomic instructions, with no system call at all.
• The kernel's primitives include spinlock_t (busy-wait, safe in interrupt context), struct mutex (sleeping), rwlock_t and rw_semaphore (reader-writer), seqlock_t (optimistic readers), struct completion (one-shot rendezvous), RCU (lock-free reads with deferred reclamation), atomic_t (single-instruction operations), and the memory barriers.
• The fundamental choice in the kernel is between a spinlock and a mutex. The rule is: use a spinlock when the critical section is short and the holder cannot sleep; use a mutex in every other case. Never sleep while holding a spinlock.
• Per-CPU variables give each CPU its own copy of a variable, so that accesses do not contend. This is the kernel's version of the per-thread counter principle — the fastest synchronization is the synchronization you do not need.
• RCU allows lock-free reads of read-mostly data. Readers enter and leave a critical section without acquiring any lock; writers make a copy, install it atomically, and defer freeing the old version until all readers have finished.
• Choosing the right primitive follows a decision procedure: atomic if the operation can be a single instruction; partitioned if the state can be split; spinlock or mutex for short or long critical sections; reader-writer lock or RCU for read-mostly data; condition variable or completion for signalling; semaphore for resource counts.
• The general guidance is to use the simplest primitive that solves the problem, and to add complexity only when measurement shows that it is needed. Most synchronization needs are met by a mutex and, occasionally, a condition variable.

11 References

• Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 6, Section 6.9, and Chapter 2, Section 2.5.
• Love, R. Linux Kernel Development, 3rd ed., Chapters 9 and 10. The authoritative treatment of the kernel's synchronization methods.
• Love, R. Linux System Programming, 2nd ed., Chapter 10.
• Butenhof, D. R. Programming with POSIX Threads, Chapters 7 and 8. The definitive reference for the POSIX primitives.
• Drepper, U. Futexes Are Tricky. Red Hat, 2004.
• Franke, H., Russell, R., & Kirkwood, M. Fuss, Futexes and Furwocks: Fast Userlevel Locking in Linux. Proceedings of the Ottawa Linux Symposium, 2002.
• McKenney, P. E., & Slingwine, J. D. Read-Copy Update: Using Execution History to Solve Concurrency Problems. Parallel and Distributed Computing and Systems, 1998. The original RCU paper.
• McKenney, P. E. Is Parallel Programming Hard, And, If So, What Can You Do About It? Available online at kernel.org. The definitive reference for RCU and parallel programming in the Linux kernel.
• Herlihy, M., & Shavit, N. The Art of Multiprocessor Programming, 2nd ed. The definitive treatment of lock-free data structures and the memory model.
• Linux man-pages: man 7 pthreads, man 7 sem_overview, man 2 futex, man 3 pthread_mutex_init, man 3 pthread_cond_init, man 3 pthread_rwlock_init, man 3 pthread_spin_lock, man 3 pthread_barrier_init, man 3 pthread_mutexattr_setprotocol, man 3 pthread_mutexattr_setpshared.
• The Linux kernel source tree, Documentation/locking/. The kernel's own documentation for its locking primitives.