Solving the Readers-Writers Problem: Fair Synchronization with Turnstiles

In multi-threaded architecture, reading shared data is intrinsically safe: multiple threads can read memory concurrently without data corruption.

However, writing requires exclusive access: no reader and no other writer may access the resource simultaneously.

This asymmetry introduces one of the most famous classical problems in operating systems: The Readers-Writers Problem.

---

1. The First Variation: Reader Preference (Writer Starvation)

The naive implementation prioritizes read throughput:

// Reader logic:
wait(mutex);
read_count++;
if (read_count == 1) {
    wait(rw_mutex); // First reader locks out writers
}
signal(mutex);

// Read data...

wait(mutex);
read_count--;
if (read_count == 0) {
    signal(rw_mutex); // Last reader releases writers
}
signal(mutex);

The Starvation Flaw:

If reader R₁ is active, a writer W₁ arrives and blocks on rw_mutex.

Before R₁ finishes, reader R₂ arrives. Since read_count > 0, R₂ enters immediately. Before R₂ finishes, R₃ arrives. In a read-heavy system, read_count never drops to zero. The writer starves indefinitely.

---

2. The Fair Solution: The Turnstile Pattern

To guarantee that both readers and writers experience bounded waiting, modern kernels implement a FIFO Turnstile:

semaphore turnstile = 1;
semaphore rw_mutex = 1;
semaphore mutex = 1;
int read_count = 0;

// Reader:
wait(turnstile);
signal(turnstile); // Pass through turnstile

wait(mutex);
read_count++;
if (read_count == 1) wait(rw_mutex);
signal(mutex);

// Read data...

wait(mutex);
read_count--;
if (read_count == 0) signal(rw_mutex);
signal(mutex);

// Writer:
wait(turnstile); // Lock turnstile; blocks subsequent readers!
wait(rw_mutex);

// Write data...

signal(rw_mutex);
signal(turnstile);

How the Turnstile Enforces Fairness:

When a writer arrives, it holds turnstile. Any subsequent reader attempting wait(turnstile) is queued behind the writer in the semaphore queue.

Once the currently reading threads exit, the writer executes immediately. Starvation is mathematically eliminated.

Explore full classical synchronization blueprints at Binary Dose.