04. Classical Synchronization Problems

In concurrent systems engineering, theoretical concepts like mutual exclusion, semaphores, and condition variables are evaluated against a battery of classical archetypes.

These classical problems are not merely intellectual puzzles: they encapsulate real-world architectural challenges found in UNIX pipe implementations, network socket buffers, database transaction engines, and multiprocessor operating system kernels.

1. The Bounded-Buffer (Producer-Consumer) Problem

The Bounded-Buffer Problem (originally formulated by Edsger W. Dijkstra) is the definitive architectural archetype for asynchronous decoupled systems.

In modern computing, execution threads rarely operate in lockstep. A network card receives ethernet frames at gigabit line rate, an operating system audio server generates PCM audio buffers, and a database storage engine writes transaction log entries asynchronously to NVMe storage. In each scenario, an execution thread producing data must coordinate with an independent execution thread consuming data through a fixed-size storage buffer in memory.

Formal Problem Specification & System Invariants

The architecture consists of one or more producers and one or more consumers sharing a circular ring buffer partitioned into N discrete slots:

• Producer Obligation: Generates data items and deposits them into the buffer. A producer must be blocked from inserting when the buffer is full (count == N).
• Consumer Obligation: Extracts data items from the buffer and consumes them. A consumer must be blocked from extracting when the buffer is empty (count == 0).
• Mutual Exclusion Invariant: The physical slots, head/tail pointers, and metadata must never be modified by more than one thread concurrently.

The Tri-Semaphore Architecture

To solve the bounded-buffer problem without busy waiting, Dijkstra established the canonical tri-semaphore architecture:

semaphore_t mutex; /* Binary semaphore: initialized to 1 (Buffer locked = 0, free = 1) */
semaphore_t empty; /* Counting semaphore: initialized to N (Vacant slots available) */
semaphore_t full;  /* Counting semaphore: initialized to 0 (Populated items available) */

empty + full = N

Complete POSIX C Implementation

Below is the complete, industrial-grade implementation using POSIX semaphores (semaphore.h):

/* Production Bounded-Buffer Implementation Using POSIX Semaphores */
#include <semaphore.h>
#include <pthread.h>
#include <stdbool.h>

#define BUFFER_CAPACITY 8

typedef struct {
    int data[BUFFER_CAPACITY];
    int head;                  /* Index for next insert: head = (head + 1) % N */
    int tail;                  /* Index for next remove: tail = (tail + 1) % N */
    sem_t mutex;               /* Binary semaphore guarding buffer pointers */
    sem_t empty;               /* Counting semaphore tracking vacant slots */
    sem_t full;                /* Counting semaphore tracking available items */
} bounded_buffer_t;

void buffer_init(bounded_buffer_t *b) {
    b->head = 0;
    b->tail = 0;
    sem_init(&b->mutex, 0, 1);               /* Binary mutex: init 1 */
    sem_init(&b->empty, 0, BUFFER_CAPACITY); /* Empty slots: init N */
    sem_init(&b->full,  0, 0);               /* Full items: init 0 */
}

void buffer_produce(bounded_buffer_t *b, int item) {
    sem_wait(&b->empty); /* 1. Decrement empty slots (Blocks if buffer full!) */
    sem_wait(&b->mutex); /* 2. Acquire critical section lock */

    /* Critical Section: Insert item into circular ring */
    b->data[b->head] = item;
    b->head = (b->head + 1) % BUFFER_CAPACITY;

    sem_post(&b->mutex); /* 3. Release critical section lock */
    sem_post(&b->full);  /* 4. Increment full items (Wakes waiting consumer) */
}

int buffer_consume(bounded_buffer_t *b) {
    sem_wait(&b->full);  /* 1. Decrement full items (Blocks if buffer empty!) */
    sem_wait(&b->mutex); /* 2. Acquire critical section lock */

    /* Critical Section: Extract item from circular ring */
    int item = b->data[b->tail];
    b->tail = (b->tail + 1) % BUFFER_CAPACITY;

    sem_post(&b->mutex); /* 3. Release critical section lock */
    sem_post(&b->empty); /* 4. Increment empty slots (Wakes waiting producer) */

    return item;
}

The Deadlock Inversion Trap & Resource Allocation Graphs

In concurrent algorithm design, the order of lock acquisition dictates system liveness.

Consider the catastrophic defect that occurs if an inexperienced developer swaps the order of the two wait calls in the producer routine:

/* FATAL: Inverted Lock Acquisition Ordering */
void flawed_producer(bounded_buffer_t *b, int item) {
    sem_wait(&b->mutex); /* STEP 1: Claim mutex FIRST (Catastrophic Error!) */
    sem_wait(&b->empty); /* STEP 2: Check empty slot availability */

    b->data[b->head] = item;
    b->head = (b->head + 1) % BUFFER_CAPACITY;

    sem_post(&b->mutex);
    sem_post(&b->full);
}

[Producer] → (holds mutex) → [blocks on empty] ← (produced by Consumer)
   ↑                                                      ↓
   ±——————————— [Consumer blocks on mutex] ←———————————±

The Win32 Windows Alternative

On Windows, the Bounded-Buffer problem can be implemented using native Win32 Kernel Semaphore Handles:

/* Windows Win32 Bounded-Buffer Implementation */
#include <windows.h>

typedef struct {
    int data[BUFFER_CAPACITY];
    int head, tail;
    HANDLE hMutex; /* Mutex object or CRITICAL_SECTION */
    HANDLE hEmpty; /* Counting semaphore: init N, max N */
    HANDLE hFull;  /* Counting semaphore: init 0, max N */
} win_bounded_buffer_t;

void win_produce(win_bounded_buffer_t *b, int item) {
    WaitForSingleObject(b->hEmpty, INFINITE); /* 1. Wait for vacant slot */
    WaitForSingleObject(b->hMutex, INFINITE); /* 2. Acquire buffer lock */

    b->data[b->head] = item;
    b->head = (b->head + 1) % BUFFER_CAPACITY;

    ReleaseMutex(b->hMutex);                  /* 3. Release buffer lock */
    ReleaseSemaphore(b->hFull, 1, NULL);      /* 4. Signal populated item */
}

2. The Dining Philosophers Problem

Originally formulated by Edsger W. Dijkstra in 1965 as an examination problem on synchronizing tape drives, and later refined into its allegorical form by C. A. R. Hoare, the Dining Philosophers Problem is the definitive paradigm for resource allocation deadlocks in multi-threaded operating systems.

The problem models concurrent processes competing for limited, mutually exclusive non-preemptible resources (such as multiple disk spindles, database row locks, or memory channels).

Formal Specification

Five philosophers sit around a circular dining table:

• Each philosopher spends their entire life alternating between two internal states: Thinking and Eating.
• In the center of the table lies a communal bowl of spaghetti. Between each pair of adjacent philosophers lies a single chopstick (or fork). There are 5 philosophers and exactly 5 chopsticks.
• Eating spaghetti requires two chopsticks simultaneously: a philosopher must acquire both their left chopstick and their right chopstick.
• A chopstick can only be held by one philosopher at a time. When a philosopher finishes eating, they put down both chopsticks and return to thinking.

The Naive Implementation & The Coffman Deadlock Conditions

The naive solution maps each chopstick to an individual binary semaphore (chopstick[5], each initialized to 1). Each philosopher runs an identical, symmetric routine:

/* FLAWED: Naive Symmetric Philosopher Routine */
sem_t chopstick[5]; /* Initialized to 1 */

void philosopher_naive(int i) {
    while (true) {
        think();
        sem_wait(&chopstick[i]);             /* 1. Pick up left chopstick */
        sem_wait(&chopstick[(i + 1) % 5]);   /* 2. Pick up right chopstick */

        eat();

        sem_post(&chopstick[i]);             /* 3. Put down left chopstick */
        sem_post(&chopstick[(i + 1) % 5]);   /* 4. Put down right chopstick */
    }
}

Strategy 1: Asymmetric Resource Hierarchy (Dijkstra's Symmetry Breaking)

Deadlock can only occur if a closed circular dependency cycle exists. Dijkstra proved that establishing a strict total ordering over all resources mathematically guarantees freedom from deadlock.

Assign each chopstick a global numerical index from 0 to 4. Establish a rule: every philosopher must always acquire their lower-numbered chopstick first, and their higher-numbered chopstick second:

• For Philosophers 0, 1, 2, and 3: The left chopstick (i) is lower than the right chopstick (i + 1). They pick up left first, then right.
• For Philosopher 4: The left chopstick is 4, but the right chopstick is (4 + 1) % 5 = 0! Because 0 < 4, Philosopher 4 picks up right first (0), then left (4).

/* Strategy 1: Asymmetric Symmetry Breaking */
void philosopher_asymmetric(int i) {
    int left = i;
    int right = (i + 1) % 5;

    while (true) {
        think();

        if (i % 2 == 0) {
            /* Even philosophers: Left first, then Right */
            sem_wait(&chopstick[left]);
            sem_wait(&chopstick[right]);
        } else {
            /* Odd philosophers: Right first, then Left */
            sem_wait(&chopstick[right]);
            sem_wait(&chopstick[left]);
        }

        eat();

        sem_post(&chopstick[left]);
        sem_post(&chopstick[right]);
    }
}

Strategy 2: Tanenbaum's State-Tracking Semaphore Array

While the asymmetric approach prevents deadlock, it can introduce unequal waiting times. Andrew Tanenbaum designed an elegant solution utilizing an explicit state machine array that allows a philosopher to eat only when neither neighbor is eating:

/* Strategy 2: Tanenbaum's State-Tracking Solution */
#define N 5
#define LEFT  ((i + N - 1) % N)
#define RIGHT ((i + 1) % N)

typedef enum { THINKING, HUNGRY, EATING } state_t;

state_t state[N];         /* Tracks state of every philosopher */
sem_t mutex;              /* Binary mutex protecting state[] inspections */
sem_t s[N];               /* One private semaphore per philosopher (init 0) */

void test_neighbors(int i) {
    /* If I am hungry AND neither neighbor is eating, begin eating */
    if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {
        state[i] = EATING;
        sem_post(&s[i]);  /* Wake myself up (increments s[i] from 0 to 1) */
    }
}

void take_forks(int i) {
    sem_wait(&mutex);     /* Enter critical section */
    state[i] = HUNGRY;
    test_neighbors(i);    /* Attempt to claim both forks */
    sem_post(&mutex);     /* Exit critical section */

    sem_wait(&s[i]);      /* Block if forks were not available */
}

void put_forks(int i) {
    sem_wait(&mutex);     /* Enter critical section */
    state[i] = THINKING;
    test_neighbors(LEFT); /* Check if left neighbor can now eat */
    test_neighbors(RIGHT);/* Check if right neighbor can now eat */
    sem_post(&mutex);     /* Exit critical section */
}

Strategy 3: Windows WaitForMultipleObjects

On Windows NT platforms, the dining philosophers problem can be resolved using the kernel's native multi-handle wait capability:

/* Win32 Atomic Multi-Object Fork Acquisition */
#include <windows.h>

HANDLE hChopsticks[5]; /* Mutex handles for each utensil */

void philosopher_win32(int i) {
    HANDLE needed[2];
    needed[0] = hChopsticks[i];
    needed[1] = hChopsticks[(i + 1) % 5];

    while (true) {
        think();

        /* Atomically wait for BOTH mutexes simultaneously (bWaitAll = TRUE) */
        DWORD result = WaitForMultipleObjects(2, needed, TRUE, INFINITE);
        if (result == WAIT_OBJECT_0) {
            eat();
            ReleaseMutex(needed[0]);
            ReleaseMutex(needed[1]);
        }
    }
}

Because WaitForMultipleObjects(..., bWaitAll = TRUE) is an atomic kernel-level operation, the operating system scheduler claims both handles together. If either utensil is held, the thread is suspended without claiming the other, eliminating the "Hold and Wait" Coffman condition.

3. The Readers-Writers Problem

Formulated by P. J. Courtois, F. Heymans, and D. L. Parnas in 1971, the Readers-Writers Problem models concurrent access to a shared resource—such as an in-memory database table, an operating system routing table, or a file system directory cache—where competing threads have asymmetric access requirements:

• Readers: Execute read-only queries. They inspect or extract data without mutating state. Multiple readers may access the shared dataset simultaneously without hazard.
• Writers: Mutate, insert, or delete data. A writer must have strict exclusive access: when a writer is modifying the dataset, no other writer may write, and no reader may read (preventing torn reads, dirty reads, and memory corruption).

The Concurrency Matrix

The Three Classical Variations

The core challenge in solving the Readers-Writers problem is not merely achieving mutual exclusion, but establishing an equitable priority policy between readers and writers.

1. First Readers-Writers (Reader-Preference)

In this classic implementation, readers are given priority over writers. If the database is currently open for reading, any newly arrived reader is permitted to enter immediately, regardless of whether a writer is waiting:

/* First Readers-Writers (Reader-Preference) */
#include <semaphore.h>

int read_count = 0;
sem_t count_mutex; /* Binary semaphore protecting read_count (init 1) */
sem_t db_mutex;    /* Binary semaphore protecting database access (init 1) */

void reader(void) {
    sem_wait(&count_mutex);
    read_count++;
    if (read_count == 1) {
        sem_wait(&db_mutex);   /* First reader locks database against writers */
    }
    sem_post(&count_mutex);

    read_database();           /* Reading is executed concurrently */

    sem_wait(&count_mutex);
    read_count--;
    if (read_count == 0) {
        sem_post(&db_mutex);   /* Last reader unlocks database for writers */
    }
    sem_post(&count_mutex);
}

void writer(void) {
    sem_wait(&db_mutex);       /* Exclusive lock: blocks all readers and writers */
    write_database();
    sem_post(&db_mutex);
}

2. Second Readers-Writers (Writer-Preference)

To prevent writer starvation and ensure database updates are not delayed by an endless stream of reads, Courtois et al. designed the Writer-Preference variant:

• When a writer announces its intent to write, newly arriving readers are prevented from entering the chamber, even if other readers are currently reading.
• Existing readers are allowed to complete their read operations and exit.
• As soon as the last active reader exits, the waiting writer claims the database immediately.
• Trade-off: While writer starvation is eliminated, a continuous stream of write operations will now cause reader starvation.

3. Third Readers-Writers (Fair FIFO Turnstile / No Starvation)

To achieve genuine fairness where neither readers nor writers starve, the algorithm introduces an architectural Turnstile Semaphore (turnstile, initialized to 1):

/* Third Readers-Writers (Fair Turnstile: Starvation-Free) */
int read_count = 0;
sem_t count_mutex; /* Protects read_count (init 1) */
sem_t db_mutex;    /* Exclusive access to database (init 1) */
sem_t turnstile;   /* Fair entry turnstile gate (init 1) */

void fair_reader(void) {
    sem_wait(&turnstile);      /* 1. Pass through entry turnstile */
    sem_wait(&count_mutex);
    read_count++;
    if (read_count == 1) {
        sem_wait(&db_mutex);   /* First reader locks database */
    }
    sem_post(&count_mutex);
    sem_post(&turnstile);      /* 2. Release turnstile for next thread in queue */

    read_database();

    sem_wait(&count_mutex);
    read_count--;
    if (read_count == 0) {
        sem_post(&db_mutex);   /* Last reader unlocks database */
    }
    sem_post(&count_mutex);
}

void fair_writer(void) {
    sem_wait(&turnstile);      /* 1. Claim turnstile gate: BLOCKS new readers */
    sem_wait(&db_mutex);       /* 2. Await active readers to drain; claim database */

    write_database();

    sem_post(&turnstile);      /* 3. Release turnstile gate */
    sem_post(&db_mutex);       /* 4. Release database */
}

Production Systems: POSIX pthread_rwlock_t

In POSIX C systems programming, developers rarely write raw semaphore turnstiles. Instead, the runtime provides native, highly optimized Read-Write Locks (pthread_rwlock_t):

/* Production POSIX Read-Write Lock Usage */
#include <pthread.h>

pthread_rwlock_t rwlock = PTHREAD_RWLOCK_INITIALIZER;

void posix_reader(void) {
    pthread_rwlock_rdlock(&rwlock); /* Shared lock: multiple readers */
    read_database();
    pthread_rwlock_unlock(&rwlock);
}

void posix_writer(void) {
    pthread_rwlock_wrlock(&rwlock); /* Exclusive lock: single writer */
    write_database();
    pthread_rwlock_unlock(&rwlock);
}

Under the GNU C Library (glibc) on Linux, developers can configure the scheduling attribute via pthread_rwlockattr_setkind_np:

• PTHREAD_RWLOCK_PREFER_READER_NP: Default behavior (Reader-preference). Fast for read-heavy workloads, but vulnerable to writer starvation.
• PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP: Writer-preference. Prevents writer starvation by immediately blocking subsequent readers when a writer queues.

The Linux Kernel Revolution: Read-Copy-Update (RCU)

In modern multi-core operating system kernels, traditional reader-writer locks have a fatal performance flaw: cacheline bouncing. Every time a reader acquires rwlock, it must atomically increment an internal reader counter. This atomic write forces cacheline invalidations across all CPU cores, degrading memory bus throughput.

To solve this, the Linux kernel relies heavily on Read-Copy-Update (RCU):

• Zero-Overhead Readers: Readers execute with zero atomic instructions, zero locks, and zero memory bus traffic. Readers simply enter a read-side critical section by disabling local preemption (rcu_read_lock()).
• Copy-on-Write for Writers: When a writer mutates a data structure (such as a linked list node), it creates a private duplicate copy, modifies the copy, and atomically overwrites the shared pointer to point to the new node.
• Grace Period Reclamation: Existing readers continue reading the old node safely. The old memory node is freed only after a Grace Period has elapsed—when every core in the system has undergone at least one voluntary context switch, proving that all concurrent readers have completed.

Windows Readers-Writers & Dispatcher Objects

In the Windows NT architecture, thread synchronization spans two distinct layers: Kernel Dispatcher Objects and lightweight User-Mode SRW Locks.

1. Slim Reader/Writer (SRW) Locks

The Windows Win32 API provides native support for the Readers-Writers problem via SRWLOCK:

/* Windows SRWLock Implementation (Clean & Fast) */
#include <windows.h>

SRWLOCK rw_lock = SRWLOCK_INIT; /* Pointer-sized allocation */

void read_worker(void) {
    AcquireSRWLockShared(&rw_lock); /* Shared access for multiple readers */
    read_database();
    ReleaseSRWLockShared(&rw_lock);
}

void write_worker(void) {
    AcquireSRWLockExclusive(&rw_lock); /* Exclusive access for writers */
    write_database();
    ReleaseSRWLockExclusive(&rw_lock);
}

Unlike POSIX reader-writer locks which can be prone to recursion bugs, SRW locks are explicitly non-reentrant. Acquiring an exclusive SRW lock recursively will trigger a dead stop or access failure, dramatically simplifying internal lock state and reducing the structure to a single machine pointer.

2. Windows Kernel Dispatcher Objects & WaitForMultipleObjects

When synchronization must cross process boundaries or coordinate complex multi-resource graphs, Windows uses Kernel Dispatcher Objects:

• Mutex Objects (CreateMutex): Kernel-managed mutexes that provide cross-process synchronization and automatic dead-owner recovery (abandoned mutex notifications).
• Semaphore Objects (CreateSemaphore): Counting semaphores maintained directly within kernel executive structures.
• Event Objects (CreateEvent): Synchronization signals available in Manual-Reset (broadcast signaling) or Auto-Reset (single-thread release) modes.
• The WaitForMultipleObjects Advantage: A powerful architectural feature unique to Windows. A thread can atomically wait on up to MAXIMUM_WAIT_OBJECTS (64) heterogeneous synchronization objects simultaneously:

  DWORD wait_status = WaitForMultipleObjects(count, object_array, bWaitAll, timeout);

  This solves multi-resource allocation deadlocks (such as Dining Philosophers) by allowing a thread to request all needed utensils simultaneously in an atomic kernel operation.