Synchronization: Locks, Mutexes, Semaphores

A critical section is any region of code that accesses shared mutable state. The critical section problem asks: how do we ensure that at most one thread executes a given critical section at a time?

To see why this matters concretely, imagine two threads both incrementing a shared counter:

// Thread A and Thread B both run:
counter++;

This one-liner compiles to three machine instructions:

1. LOAD: read counter from memory into a register
2. ADD: increment the register
3. STORE: write the register back to memory

If Thread A loads (gets 5), then Thread B loads (also gets 5), then both increment and both store 6 — the counter ends at 6 instead of 7. One increment was silently lost. This is a race condition — the result depends on the precise timing (the "race") between threads.

A correct solution to the critical section problem must satisfy three properties (Dijkstra, 1965):

1. Mutual exclusion: at most one thread is in the critical section at any time.
2. Progress: if no thread is in the critical section and some thread wants to enter, a decision about who enters must be made in finite time — we cannot stall forever.
3. Bounded waiting: after a thread requests entry, there is a bound on how many times other threads can enter before it does. No thread should starve.

Every synchronization primitive we study is just a different way to enforce these three properties with different performance and fairness tradeoffs.

#include <stdio.h>
#include <pthread.h>

static long counter = 0;

void *increment(void *arg) {
    for (int i = 0; i < 1000000; i++)
        counter++;  /* UNSAFE: race condition */
    return NULL;
}

int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, increment, NULL);
    pthread_create(&t2, NULL, increment, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    /* Expected: 2000000. Actual: varies, often ~1100000 */
    printf("counter = %ld\n", counter);
    return 0;
}

Software alone cannot solve the critical section problem without hardware support. Here is why: any software "locking" mechanism that uses regular loads and stores has a gap — the check and the act of locking are separate memory operations, and another thread can slip in between them.

Modern CPUs solve this with atomic read-modify-write instructions that are indivisible — the hardware guarantees no other CPU can observe or interfere with the operation mid-flight.

The most powerful of these is Compare-And-Swap (CAS). In pseudocode:

atomic CAS(addr, expected, new_value):
    if *addr == expected:
        *addr = new_value
        return true
    return false

The whole check-and-update happens as one uninterruptible unit at the hardware level. On x86 this is the CMPXCHG instruction (with a LOCK prefix to extend the guarantee across CPU cores via the cache coherence protocol). On ARM/RISC-V it is implemented with Load-Linked / Store-Conditional (LL/SC) pairs: the load marks the cache line as "monitored" and the store fails if anything else touched it.

Other useful atomics: XCHG (atomic swap), LOCK ADD (atomic increment), LOCK XADD (atomic fetch-and-add). In C11 and later these are exposed via <stdatomic.h> (atomic_fetch_add, atomic_compare_exchange_strong, etc.).

A critical but subtle point: atomic operations prevent data races on a single variable, but they do not on their own prevent higher-level races across multiple variables. Protecting a linked list requires locking around the multi-step pointer manipulation, not just atomic increments of a counter.

/* POSIX: atomic increment using C11 atomics */
#include <stdatomic.h>
#include <stdio.h>
#include <pthread.h>

static atomic_long counter = 0;

void *increment(void *arg) {
    for (int i = 0; i < 1000000; i++)
        atomic_fetch_add_explicit(&counter, 1, memory_order_relaxed);
    return NULL;
}

int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, increment, NULL);
    pthread_create(&t2, NULL, increment, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("counter = %ld\n", atomic_load(&counter)); /* Always 2000000 */
    return 0;
}

A spinlock is the simplest possible lock: a thread that cannot acquire the lock simply loops ("spins") in a tight loop checking the lock variable until it becomes free. Think of it as a revolving door where you stand and push repeatedly until you get through.

A minimal spinlock can be built from CAS:

typedef atomic_flag spinlock_t;
#define SPINLOCK_INIT ATOMIC_FLAG_INIT

void spin_lock(spinlock_t *lock) {
    while (atomic_flag_test_and_set_explicit(lock, memory_order_acquire))
        ; /* spin */
}
void spin_unlock(spinlock_t *lock) {
    atomic_flag_clear_explicit(lock, memory_order_release);
}

The atomic_flag_test_and_set sets the flag and returns its old value atomically. If the old value was false (unlocked), we got the lock. If it was true (locked), we spin.

When spinlocks shine: when the critical section is very short (microseconds) and the system has multiple CPUs. In this regime, the overhead of a full context switch to sleep and wake up would take longer than just spinning for a few hundred nanoseconds. This is exactly why the Linux kernel uses spinlocks in interrupt handlers and other low-latency contexts.

When spinlocks hurt: on a single CPU, spinning is always wasteful — the thread holding the lock cannot run because the spinner is burning the only CPU. Even on multicore systems, if the lock holder is preempted or the critical section is long, spinning wastes entire CPU cores doing nothing useful.

Real-world spinlocks also add a PAUSE instruction (x86) or YIELD hint (ARM) inside the spin loop. This tells the CPU to pipeline-reduce itself for a few cycles, reducing power consumption and improving performance of the hyper-threaded sibling core that might be running the lock holder.

A subtle bug: spinlocks are not reentrant. If a thread tries to acquire a spinlock it already holds, it will spin forever. The Linux kernel tracks this with lock debugging infrastructure (CONFIG_LOCKDEP).

#include <stdatomic.h>

typedef atomic_flag spinlock_t;

void spin_lock(spinlock_t *lock) {
    while (atomic_flag_test_and_set_explicit(lock, memory_order_acquire)) {
#if defined(__x86_64__)
        __asm__ volatile("pause" ::: "memory"); /* pipeline hint */
#elif defined(__aarch64__)
        __asm__ volatile("yield" ::: "memory");
#endif
    }
}

void spin_unlock(spinlock_t *lock) {
    atomic_flag_clear_explicit(lock, memory_order_release);
}

/* Usage */
static spinlock_t g_lock = ATOMIC_FLAG_INIT;
static int shared = 0;

void safe_increment(void) {
    spin_lock(&g_lock);
    shared++;          /* critical section */
    spin_unlock(&g_lock);
}

A mutex (mutual exclusion lock) solves the main problem with spinlocks: instead of burning CPU cycles spinning, a thread that cannot acquire the lock goes to sleep and is woken up by the OS when the lock is released. Think of a mutex as a numbered ticket at the DMV — you take your number and sit down, and they call you when it is your turn.

The conceptual implementation:

1. Try to atomically acquire the lock (CAS: locked = 0 → 1).
2. If that fails, add yourself to a wait queue and call schedule() to yield the CPU.
3. When the lock is released, the releaser picks the next waiter from the queue and marks it runnable.
4. The woken thread retries the acquisition.

POSIX provides pthread_mutex_t. The Linux kernel provides struct mutex (in include/linux/mutex.h). Both have the same semantics but wildly different internals — the kernel mutex is highly optimized with a "fast path" (a single atomic instruction for the uncontended case) and a "slow path" (the full queue-based sleep mechanism) triggered only under contention.

Mutex vs Spinlock — choosing between them:

• Spinlock: lock held for nanoseconds, cannot sleep while holding it (interrupt context), multicore system.
• Mutex: lock held for microseconds to milliseconds, thread may sleep while holding it, any context.
• In the kernel: spin_lock in IRQ handlers, mutex_lock in process context (e.g., open(), ioctl() handlers).

A recursive mutex (POSIX: PTHREAD_MUTEX_RECURSIVE) can be locked by the same thread multiple times, but must be unlocked the same number of times. Useful for libraries with internal locking that call each other, but often a sign of design issues.

Priority inversion is a famous mutex hazard: a high-priority thread waits for a lock held by a low-priority thread, but a medium-priority thread keeps running and starving the low-priority holder, indirectly starving the high-priority thread too. The Mars Pathfinder spacecraft suffered this exact bug in 1997. Solutions include priority inheritance (temporarily boost the lock holder's priority to the waiter's level) and priority ceiling protocols.

#include <pthread.h>
#include <stdio.h>

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

void *increment(void *arg) {
    for (int i = 0; i < 1000000; i++) {
        pthread_mutex_lock(&lock);   /* sleep if contended */
        counter++;
        pthread_mutex_unlock(&lock);
    }
    return NULL;
}

int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, increment, NULL);
    pthread_create(&t2, NULL, increment, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("counter = %ld\n", counter); /* Always 2000000 */
    pthread_mutex_destroy(&lock);
    return 0;
}

A semaphore is a generalization of a mutex invented by Dijkstra in 1965. Where a mutex is binary (locked/unlocked), a semaphore holds an integer count and supports two atomic operations:

• wait (P, down, sem_wait): decrement the count. If the result would be negative, block until another thread signals.
• signal (V, up, sem_post): increment the count. If there are blocked threads, wake one up.

A binary semaphore (count initialized to 1) behaves like a mutex with one crucial difference: any thread can signal it, not just the one that waited. This makes semaphores useful for signaling between threads, not just mutual exclusion.

A counting semaphore (count initialized to N) represents N available resources. Classic use: a connection pool of 10 database connections. Initialize the semaphore to 10. Each thread calls wait before using a connection (decrementing the count) and signal after releasing it. When all 10 are in use, additional threads block until one is returned.

Resource pool (N=3):  [####] count=3
Thread A wait():      [###_] count=2
Thread B wait():      [##__] count=1
Thread C wait():      [#___] count=0
Thread D wait():      BLOCKS (count would go to -1)
Thread A signal():    [##__] count=1 → Thread D unblocks

Semaphore vs Mutex:

• Mutex has ownership: only the locker can unlock. Semaphores have no ownership.
• Use a mutex for mutual exclusion (protecting shared data).
• Use a semaphore for signaling ("event happened") or resource counting.
• Using a semaphore as a mutex is legal but fragile — no ownership means accidental unlocking from the wrong thread compiles fine but is a bug.

On Linux: sem_init / sem_wait / sem_post (POSIX, <semaphore.h>). Kernel: struct semaphore with down() / up() (but rarely used in modern kernel code — mutex and completion are preferred).

#include <semaphore.h>
#include <pthread.h>
#include <stdio.h>
#define POOL_SIZE 3

sem_t pool;

void use_resource(int thread_id) {
    sem_wait(&pool);            /* acquire one resource slot */
    printf("Thread %d: using resource\n", thread_id);
    /* ... work ... */
    printf("Thread %d: releasing resource\n", thread_id);
    sem_post(&pool);            /* release the slot */
}

void *worker(void *arg) {
    use_resource((int)(long)arg);
    return NULL;
}

int main(void) {
    sem_init(&pool, 0, POOL_SIZE); /* 3 concurrent users */
    pthread_t threads[10];
    for (int i = 0; i < 10; i++)
        pthread_create(&threads[i], NULL, worker, (void*)(long)i);
    for (int i = 0; i < 10; i++)
        pthread_join(threads[i], NULL);
    sem_destroy(&pool);
    return 0;
}

A condition variable lets a thread sleep until some specific condition becomes true, without wasting CPU spinning. Think of it as a pub/sub system built into your synchronization primitives.

Condition variables always pair with a mutex. The pattern is:

// Waiter:
pthread_mutex_lock(&mutex);
while (!condition_is_true)       // ALWAYS use while, not if
    pthread_cond_wait(&cond, &mutex); // atomically: unlock mutex + sleep
// ... use shared state ...
pthread_mutex_unlock(&mutex);

// Signaler:
pthread_mutex_lock(&mutex);
set_condition_true();
pthread_cond_signal(&cond);     // or broadcast() to wake all
pthread_mutex_unlock(&mutex);

The atomic unlock-and-sleep in pthread_cond_wait is critical. If those were two separate operations, another thread could signal between the unlock and the sleep, and the signal would be lost (the waiter would sleep forever). This is called a lost wakeup bug.

Why while not if: condition variables can suffer spurious wakeups — the thread wakes up even though nobody called signal (this is permitted by POSIX, and real implementations on Linux using futexes can have this). Also, by the time the woken thread re-acquires the mutex, another thread may have consumed the resource, making the condition false again. The while loop handles both cases correctly.

signal vs broadcast:

• pthread_cond_signal: wakes one sleeping thread. Efficient if only one can make progress.
• pthread_cond_broadcast: wakes all sleeping threads. They will each re-check the condition; all but one (or a few) will go back to sleep. Use when the condition change might allow multiple waiters to proceed.

Condition variables are the foundation of more complex patterns: bounded buffers, thread pools, barriers, and event queues.

#include <pthread.h>
#include <stdio.h>
#include <stdbool.h>

static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t  ready = PTHREAD_COND_INITIALIZER;
static bool data_available = false;
static int  data_value = 0;

void *producer(void *arg) {
    pthread_mutex_lock(&lock);
    data_value = 42;
    data_available = true;
    pthread_cond_signal(&ready);    /* wake the consumer */
    pthread_mutex_unlock(&lock);
    return NULL;
}

void *consumer(void *arg) {
    pthread_mutex_lock(&lock);
    while (!data_available)          /* MUST be while loop */
        pthread_cond_wait(&ready, &lock);
    printf("consumed: %d\n", data_value);
    pthread_mutex_unlock(&lock);
    return NULL;
}

int main(void) {
    pthread_t p, c;
    pthread_create(&c, NULL, consumer, NULL);
    pthread_create(&p, NULL, producer, NULL);
    pthread_join(p, NULL);
    pthread_join(c, NULL);
    return 0;
}

The producer-consumer problem (also called the bounded-buffer problem) is one of the canonical synchronization problems and appears constantly in real systems: ring buffers in the kernel, work queues in web servers, message queues, audio subsystems, disk caches.

Setup: a fixed-size buffer shared between one or more producers (who add items) and one or more consumers (who remove items). The constraints:

• A producer must not add to a full buffer.
• A consumer must not remove from an empty buffer.
• Producers and consumers must not access the buffer simultaneously.

The elegant solution uses two semaphores plus a mutex:

• empty: counting semaphore initialized to N (buffer capacity). A producer waits on empty before inserting — waits until there is at least one empty slot.
• full: counting semaphore initialized to 0. A consumer waits on full before removing — waits until there is at least one filled slot.
• mutex: binary semaphore (or mutex) protecting the actual buffer access.

Producer:                  Consumer:
  wait(empty)               wait(full)
  wait(mutex)               wait(mutex)
  [add item to buffer]      [remove item from buffer]
  signal(mutex)             signal(mutex)
  signal(full)              signal(empty)

The ordering matters: always wait on the counting semaphore BEFORE acquiring the mutex. If you do it the other way, a producer holding the mutex might block on empty while a consumer that could signal empty is blocked waiting for the mutex — deadlock.

The same problem can be solved with a mutex + two condition variables (not_full and not_empty), which is the idiomatic C/POSIX style. The semaphore solution is elegant; the condition variable solution is more flexible and commonly preferred in practice.

In the Linux kernel, this pattern appears as kfifo (a lock-free ring buffer for single producer/consumer) and as work queues with wait_event / wake_up pairs.

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#define BUFFER_SIZE 5
#define ITEMS       20

static int  buffer[BUFFER_SIZE];
static int  in = 0, out = 0;
static sem_t empty_slots, filled_slots;
static pthread_mutex_t buf_lock = PTHREAD_MUTEX_INITIALIZER;

void *producer(void *arg) {
    for (int i = 0; i < ITEMS; i++) {
        sem_wait(&empty_slots);       /* wait for space */
        pthread_mutex_lock(&buf_lock);
        buffer[in] = i;
        in = (in + 1) % BUFFER_SIZE;
        printf("produced %d\n", i);
        pthread_mutex_unlock(&buf_lock);
        sem_post(&filled_slots);      /* signal item available */
    }
    return NULL;
}

void *consumer(void *arg) {
    for (int i = 0; i < ITEMS; i++) {
        sem_wait(&filled_slots);      /* wait for item */
        pthread_mutex_lock(&buf_lock);
        int item = buffer[out];
        out = (out + 1) % BUFFER_SIZE;
        printf("consumed %d\n", item);
        pthread_mutex_unlock(&buf_lock);
        sem_post(&empty_slots);       /* signal space available */
    }
    return NULL;
}

int main(void) {
    sem_init(&empty_slots, 0, BUFFER_SIZE);
    sem_init(&filled_slots, 0, 0);
    pthread_t p, c;
    pthread_create(&p, NULL, producer, NULL);
    pthread_create(&c, NULL, consumer, NULL);
    pthread_join(p, NULL);
    pthread_join(c, NULL);
    sem_destroy(&empty_slots);
    sem_destroy(&filled_slots);
    return 0;
}

Deadlock is a state where a set of threads are all blocked, each waiting for a resource held by another thread in the set. The most famous illustration: two threads, each holding one lock, each waiting for the other.

Coffman (1971) identified four necessary and sufficient conditions for deadlock. All four must hold simultaneously:

1. Mutual exclusion: at least one resource is held non-shareably.
2. Hold and wait: a thread holds at least one resource while waiting for additional resources.
3. No preemption: resources cannot be forcibly taken — only the holder can release them.
4. Circular wait: a cycle exists in the "waits-for" graph (Thread A waits for Thread B's resource, B waits for C's, C waits for A's).

To prevent deadlock, break any one condition:

• Break circular wait (most practical): establish a global lock ordering. Always acquire locks in the same order throughout the entire codebase. If every thread acquires lock_A before lock_B, a circular wait between A and B is impossible. The Linux kernel enforces this with lockdep, which at runtime builds a directed graph of lock acquisition orders and detects cycles.
• Break hold-and-wait: try to acquire all needed locks atomically (pthread_mutex_trylock), and release all if any fails. Wasteful but sometimes useful.
• Break no-preemption: not usually applicable to mutexes.
• Break mutual exclusion: use lock-free algorithms. Powerful but extremely difficult to get right.

Livelock is a cousin of deadlock: threads are not blocked but are too busy responding to each other to make progress. Two people in a hallway repeatedly stepping the same way to avoid each other. Avoid with randomized backoff or designated priority.

Starvation: a thread perpetually denied access because others keep acquiring the lock first. Use fair locks (ticket locks, or locks with FIFO queues) in latency-sensitive code.

/* Deadlock example — run at your own risk!
   Thread A: lock(&a) then lock(&b)
   Thread B: lock(&b) then lock(&a)  <-- opposite order! */

#include <pthread.h>
static pthread_mutex_t a = PTHREAD_MUTEX_INITIALIZER;
static pthread_mutex_t b = PTHREAD_MUTEX_INITIALIZER;

/* FIX: impose a global order. Both threads must lock a, then b. */
void safe_thread_A(void) {
    pthread_mutex_lock(&a);   /* always a first */
    pthread_mutex_lock(&b);
    /* ... work ... */
    pthread_mutex_unlock(&b);
    pthread_mutex_unlock(&a);
}

void safe_thread_B(void) {
    pthread_mutex_lock(&a);   /* same order */
    pthread_mutex_lock(&b);
    /* ... work ... */
    pthread_mutex_unlock(&b);
    pthread_mutex_unlock(&a);
}

Lock granularity refers to how much data a single lock protects. This is one of the most important performance decisions in systems programming.

Coarse-grained locking: one big lock protects everything. Simple to reason about, easy to get correct. But threads serialise on the single lock even when they are working on completely independent data. The Linux kernel's original "Big Kernel Lock" (BKL) was exactly this — a single global spinlock around almost all kernel code. It worked correctly but was a performance disaster on multicore systems and was finally removed in kernel 2.6.39.

Fine-grained locking: one lock per data structure instance, or even per sub-field of a data structure. This maximizes parallelism — threads operating on different objects proceed independently. But it significantly increases code complexity, increases the risk of deadlock (more locks → more opportunities for lock ordering violations), and increases memory overhead.

The sweet spot depends on the access pattern:

• If two operations almost always touch different data: go fine-grained.
• If two operations almost always touch the same data: fine-grained locking just adds overhead with no concurrency benefit.

A common progression for, say, a hash table:

1. One lock for the whole table: simple, high contention under load.
2. One lock per bucket: threads hashing to different buckets proceed in parallel. Usually 10-100x improvement.
3. Lock-free with CAS: maximum concurrency, complex implementation.

In the Linux kernel, you see this everywhere: struct inode has its own spinlock, each struct page has a page lock bit, the networking stack has per-socket locks, and so on. Reading the kernel's locking annotations (comments like /* protected by rq->lock */) reveals the granularity decisions made by the subsystem authors.

A useful metric: lock hold time vs lock acquisition rate. If you hold a lock for 1 microsecond and another thread needs it 1000 times per second, contention is mild. If you hold it for 1 millisecond and it is needed 10,000 times per second, you have a serialization bottleneck.

/* Fine-grained hash table: one lock per bucket */
#include <pthread.h>
#include <stdlib.h>
#define BUCKETS 64

struct entry { int key, val; struct entry *next; };

struct htable {
    struct entry        *bucket[BUCKETS];
    pthread_mutex_t      lock[BUCKETS];   /* one lock per bucket */
};

void htable_init(struct htable *h) {
    for (int i = 0; i < BUCKETS; i++) {
        h->bucket[i] = NULL;
        pthread_mutex_init(&h->lock[i], NULL);
    }
}

void htable_insert(struct htable *h, int key, int val) {
    int idx = (unsigned)key % BUCKETS;
    pthread_mutex_lock(&h->lock[idx]);   /* only lock this bucket */
    struct entry *e = malloc(sizeof *e);
    e->key = key; e->val = val;
    e->next = h->bucket[idx];
    h->bucket[idx] = e;
    pthread_mutex_unlock(&h->lock[idx]);
}

Here is a fact that surprises most people: modern CPUs and compilers do not execute your code in the order you wrote it. Both the compiler and the CPU reorder instructions for performance, as long as the reordering produces the same result in a single-threaded execution. In a multi-threaded context, this can break your synchronization.

Consider:

int x = 0, y = 0;
// Thread A:        // Thread B:
x = 1;             y = 1;
print(y);          print(x);

You might expect at least one of x or y to be 1 when printed. But on ARM or PowerPC (and even x86 in some configurations), the CPU can reorder the store and the load, so both threads can print 0. This is not a bug in the CPU — it is a specified behavior of the memory model.

A memory barrier (also called a fence) is an instruction that enforces ordering. It tells the CPU: do not move memory operations from one side of this barrier to the other.

• asm volatile("" ::: "memory") — compiler barrier only (prevents compiler reordering)
• __sync_synchronize() / atomic_thread_fence(memory_order_seq_cst) — full hardware + compiler barrier
• x86: MFENCE, LFENCE, SFENCE; ARM: DMB, DSB, ISB

The C11 memory model exposes this cleanly through memory_order in <stdatomic.h>:

• memory_order_relaxed: no ordering guarantee beyond atomicity. Fastest. Fine for simple counters.
• memory_order_acquire: no load/store after this can be reordered before it. Used when acquiring a lock or reading a flag.
• memory_order_release: no load/store before this can be reordered after it. Used when releasing a lock or writing a flag.
• memory_order_seq_cst: full sequential consistency (most expensive). Safe default when unsure.

The rule of thumb: mutexes and POSIX primitives insert the right barriers automatically at lock/unlock. You only need to think about barriers explicitly when using raw atomics (lock-free programming).

/* Spinlock using acquire/release semantics — correct ordering */
#include <stdatomic.h>

typedef atomic_int spinlock_t;

void lock(spinlock_t *l) {
    int expected;
    do {
        expected = 0;
    } while (!atomic_compare_exchange_weak_explicit(
                l, &expected, 1,
                memory_order_acquire,  /* acquire barrier on success */
                memory_order_relaxed));
}

void unlock(spinlock_t *l) {
    atomic_store_explicit(l, 0, memory_order_release); /* release barrier */
}

Many data structures are read far more often than they are written. A regular mutex forces all readers to serialise even when no writer is present — wasteful, since concurrent reads are perfectly safe.

A reader-writer lock (rwlock) distinguishes between:

• Read lock (shared): multiple readers can hold it simultaneously.
• Write lock (exclusive): when a writer holds it, no readers or other writers can proceed.

POSIX: pthread_rwlock_t, pthread_rwlock_rdlock, pthread_rwlock_wrlock, pthread_rwlock_unlock. Linux kernel: rwlock_t (spinlock-based, for use in interrupt context) and struct rw_semaphore (sleeping, for process context).

Reader-writer locks introduce a starvation tradeoff:

• Writer starvation: a constant stream of readers keeps the lock held, writers never get in. Linux's rw_semaphore is write-preferring to avoid this.
• Reader starvation: a write-preferring lock stops new readers when a writer is queued, potentially starving readers if writers are frequent.

When reader-writer locks hurt: the bookkeeping (atomically incrementing/decrementing the reader count) itself costs memory bandwidth. On many-core NUMA machines, the cacheline containing the reader count bounces between cores. For very frequent short reads, a sequence lock (seqlock) or RCU (Read-Copy-Update) may be faster.

The Linux kernel's RCU (Read-Copy-Update) is a beautiful extreme of read-side optimization: read-side is wait-free and requires no atomic operations, while writes create a new version of the data and wait for all current readers to complete. It is used for routing tables, process lists, and hundreds of other kernel data structures. RCU is beyond this module's scope but is the logical next step.

#include <pthread.h>
#include <stdio.h>

static pthread_rwlock_t rwlock = PTHREAD_RWLOCK_INITIALIZER;
static int shared_data = 0;

void reader(int id) {
    pthread_rwlock_rdlock(&rwlock);   /* shared — many OK */
    printf("Reader %d sees: %d\n", id, shared_data);
    pthread_rwlock_unlock(&rwlock);
}

void writer(int new_val) {
    pthread_rwlock_wrlock(&rwlock);   /* exclusive */
    shared_data = new_val;
    printf("Writer set: %d\n", new_val);
    pthread_rwlock_unlock(&rwlock);
}