The Readers-Writers Problem

The Readers-Writers problem models a shared resource accessed by two classes of processes: readers, which only inspect the resource and never modify it, and writers, which modify the resource and require it to be in a stable, unseen-by-others state while doing so. The synchronization goal is captured by two invariants that any correct solution must guarantee: 1. Writer exclusivity: while a writer holds the resource, no reader and no other writer may access it. 2. Reader concurrency: any number of readers may access the resource simultaneously, provided no writer is currently writing. A solution that only enforces invariant (1) via a single mutex, wrapping both readers and writers in the same critical section, is safe but not efficient — it destroys the concurrency that readers could have enjoyed. A correct Readers-Writers solution must let overlapping reads proceed in parallel while still serializing writes against everything else. There is a third, often underspecified dimension: fairness (liveness). Because readers can keep arriving and overlapping with each other, a writer might never find a moment when the reader count drops to zero — this is the seed of writer starvation, and symmetric reasoning gives reader starvation under writer-favoring policies. This is why the problem is traditionally presented in three variants:

• First Readers-Writers Problem (readers-preferred): no reader should wait if the resource is currently open for reading, even if a writer is queued. Writers may starve.
• Second Readers-Writers Problem (writers-preferred): once a writer is queued, no new reader may start ahead of it. Readers may starve.
• Third Readers-Writers Problem (fair / no-starvation): readers and writers are served in roughly arrival order — neither class can indefinitely block the other.

All three variants are built from the same primitive toolbox: binary semaphores or mutexes for mutual exclusion, plus a shared counter tracking how many readers are currently active. The key trick is that only the first reader to arrive needs to lock out writers, and only the last reader to leave needs to unlock them — intermediate readers just increment/decrement a counter under a short-lived mutex.

Variant 1 — Readers-preferred

``` shared: integer read_count = 0 semaphore mutex = 1 // protects read_count semaphore resource = 1 // controls access to the shared resource Reader(): wait(mutex) read_count = read_count + 1 if read_count == 1: wait(resource) // first reader locks out writers signal(mutex) // -- critical section: read the resource -- wait(mutex) read_count = read_count - 1 if read_count == 0: signal(resource) // last reader lets writers in signal(mutex) Writer(): wait(resource) // -- critical section: write the resource -- signal(resource) ``` Walk through the logic. `resource` is a binary semaphore acting as the "writer lock" — whoever holds it has exclusive access. Readers do not each acquire `resource`; instead they acquire it collectively, using `read_count` as a reference count. The first reader to arrive when `read_count` goes from 0 to 1 grabs `resource`, blocking any writer. Every subsequent reader just increments the counter and proceeds directly to reading — no wait on `resource` at all, hence unlimited reader concurrency. The last reader to leave, dropping `read_count` from 1 to 0, releases `resource`. As long as at least one reader is active, `resource` stays held, so a writer that arrives mid-stream must wait — and if new readers keep trickling in before the count hits zero, the writer waits indefinitely. This is the textbook readers-preferred bias.

Variant 2 — Writers-preferred

To flip the bias, add a second gate: once a writer is waiting, new readers must not slip in ahead of it. ``` shared: integer read_count = 0 integer write_count = 0 semaphore mutex1 = 1 // protects read_count semaphore mutex2 = 1 // protects write_count semaphore resource = 1 // exclusive resource lock semaphore service_queue = 1 // gate that blocks new readers when a writer is waiting Reader(): wait(service_queue) // must pass this gate to even try wait(mutex1) read_count = read_count + 1 if read_count == 1: wait(resource) signal(mutex1) signal(service_queue) // -- critical section: read -- wait(mutex1) read_count = read_count - 1 if read_count == 0: signal(resource) signal(mutex1) Writer(): wait(mutex2) write_count = write_count + 1 if write_count == 1: wait(service_queue) // first waiting writer closes the gate to new readers signal(mutex2) wait(resource) // -- critical section: write -- signal(resource) wait(mutex2) write_count = write_count - 1 if write_count == 0: signal(service_queue) // last writer reopens the gate signal(mutex2) ``` Here `service_queue` is the writer's weapon. As soon as one writer is waiting (`write_count` goes 0→1), it grabs `service_queue`, which every new reader must pass through before even registering itself. Readers already past the gate and already reading finish normally (the writer still waits for `resource` to be free), but no new reader can join the party once a writer is queued. When the last queued writer finishes (`write_count` back to 0), the gate reopens for readers. This inverts the starvation risk: a continuous stream of writers can now starve readers.

Variant 3 — Fair (no-starvation) solution

The fair solution enforces arrival-order service using a single additional mutex acting as a ticket turnstile: every arriving thread, reader or writer, must pass through it in order, and it is held only long enough to be granted a place in line. ``` shared: integer read_count = 0 semaphore mutex = 1 // protects read_count semaphore resource = 1 // exclusive resource lock semaphore turnstile = 1 // FIFO-ish entry gate for both readers and writers Reader(): wait(turnstile) // take a ticket, in arrival order signal(turnstile) // release it immediately after passing wait(mutex) read_count = read_count + 1 if read_count == 1: wait(resource) signal(mutex) // -- critical section: read -- wait(mutex) read_count = read_count - 1 if read_count == 0: signal(resource) signal(mutex) Writer(): wait(turnstile) // take a ticket, in arrival order wait(resource) // hold turnstile until resource acquired signal(turnstile) // -- critical section: write -- signal(resource) ``` The insight: `turnstile` is a single-slot gate that any thread — reader or writer — must acquire before it is allowed to proceed toward `resource`. A writer holds `turnstile` while it waits for `resource`, which blocks any later-arriving reader from jumping the queue past it (readers immediately release `turnstile` after passing, but they must still wait behind a writer currently holding it). Because every thread queues on the same semaphore in arrival order (most semaphore implementations service waiters FIFO), no class can be perpetually skipped: any writer or reader that requests access will be granted it within a bounded number of turns, once currently-active operations finish.

Time complexity. Each `Reader()` call performs a constant number of semaphore operations (at most two `wait`/`signal` pairs on `mutex`, and occasionally one pair on `resource` or `turnstile`), so per-operation overhead is O(1) regardless of how many readers are concurrently active. This is the entire point: the cost of admitting a reader does not scale with the number of readers already inside, unlike a design that made every reader individually acquire the full resource lock. `Writer()` similarly performs O(1) semaphore operations. Contention (time spent blocked) is workload-dependent, not part of the asymptotic operation count, but worth noting qualitatively: under a read-heavy load with readers-preferred, writer waiting time is unbounded in the worst case (see pitfalls); under the fair solution, waiting time for any thread is bounded by the number of threads that arrived strictly before it, which is finite in any real system.

Space complexity. Each variant needs O(1) additional shared state beyond the resource itself: one or two integers (`read_count`, possibly `write_count`) and two or three semaphores. This is independent of the number of readers or writers in the system — no per-thread bookkeeping is required by the synchronization mechanism itself (though a queue-based real implementation may add O(n) space for explicit ticket tracking).

Correctness — safety. The core invariant to prove is mutual exclusion of writers against everyone. Consider variant 1. `resource` is a binary semaphore, so at most one holder exists at any time. A writer only proceeds past `wait(resource)` if it becomes that holder. Readers as a group only proceed past the reader gate when the first reader (in the `read_count` 0→1 transition) has itself become the holder of `resource`; all subsequent readers piggyback on that same held permit without re-acquiring it. Since `resource` has exactly one holder at a time, either that holder is "the readers as a group" (with `read_count ≥ 1`) or it is a single writer — never both. This is enforced because `read_count` mutations happen under `mutex`, so the 0→1 and 1→0 transitions are atomic and cannot race with each other or with a writer's `wait(resource)`. Hence writer-exclusivity holds by induction on the sequence of semaphore operations: initially `resource` is free (1), and every `wait`/`signal` pair preserves the invariant that at most one logical class (readers-as-a-group or a single writer) holds it. The same style of argument applies to variants 2 and 3, with the additional gates (`service_queue`, `turnstile`) only affecting who is allowed to attempt the acquisition, never weakening the exclusivity guarantee provided by `resource` itself. This is a useful general principle: safety is guaranteed by the innermost lock (`resource`); fairness is layered on top via outer gates that shape arrival order without ever bypassing the innermost lock.

Correctness — liveness / fairness. This is where the three variants diverge, and honestly stating the tradeoff is essential:

• Variant 1 (readers-preferred) guarantees that any reader arriving while reading is in progress is served promptly (no reader waits behind a writer that hasn't yet started). It does not guarantee writers ever get served if readers arrive faster than they leave — a continuously-refreshed nonempty set of readers keeps `resource` held forever from the writer's perspective.
• Variant 2 (writers-preferred) guarantees writers are served promptly once queued (no writer waits behind a "new" reader that arrived after it). It does not guarantee readers ever get served if writers arrive back-to-back — the gate `service_queue` can stay closed indefinitely.
• Variant 3 (fair) guarantees that any thread's wait time is bounded by the number of threads queued strictly ahead of it at arrival, assuming the underlying semaphore implementation wakes waiters in FIFO order (a common but not universal guarantee — POSIX does not mandate FIFO wakeup for semaphores, so real deployments sometimes need explicit ticket queues to guarantee this rigorously).

Tradeoffs, stated plainly. More fairness costs more synchronization overhead and reduces peak reader throughput, because the turnstile forces every reader to serialize briefly even when no writer is present. Readers-preferred maximizes reader throughput at the cost of writer starvation risk. Writers-preferred protects data freshness (writers get in fast) at the cost of reader starvation risk. There is no free lunch — the correct choice is workload-dependent, which is precisely why real systems (databases, kernels) expose configurable or hybrid policies rather than picking one variant universally.

Consider the fair (variant 3) solution with three readers R1, R2, R3 and one writer W, arriving in this order: R1, W, R2, R3. Assume each thread takes a small, nonzero amount of time in its critical section, and semaphore waiters are released in FIFO arrival order.

Trace the key subtlety at t1–t3: because W grabs `turnstile` and does not release it until it has also acquired `resource`, R2 and R3 — even though they only want to read — cannot slip past W. This is exactly the fairness property: W is served before R2 and R3 despite R1 having started first (R1 was already in progress and is allowed to finish, which is unavoidable since preemption mid-critical-section is not assumed). Contrast this with variant 1 (readers-preferred): at t2 and t3, R2 and R3 would not block on any writer-related gate at all — they would join `read_count` immediately (2, then 3), potentially keeping `resource` held by "the readers" indefinitely if a R4, R5, ... kept arriving, starving W completely. The fair solution's turnstile is precisely the mechanism that prevents that outcome.

The Readers-Writers problem was first formalized in the context of early operating systems research on structuring concurrent access to shared data structures, growing directly out of the broader program of using semaphores to express classic synchronization patterns.

Reader-writer locks are a standard primitive in nearly every mainstream concurrency library: POSIX `pthread_rwlock_t`, Java's `java.util.concurrent.locks.ReentrantReadWriteLock`, C++'s `std::shared_mutex`, and .NET's `ReaderWriterLockSlim` all expose exactly the readers-share / writers-exclusive contract described here, typically with a configurable or writer-preferring fairness policy to avoid the classic starvation trap. Relational databases use reader-writer locking (often multi-granularity, at the row, page, and table level) to let concurrent `SELECT` queries proceed while an `UPDATE` waits for exclusive access to the rows it touches. Filesystems and kernel data structures use reader-writer spinlocks and Read-Copy-Update (RCU) to let many CPU cores traverse routing tables or process lists concurrently while updates are rare and serialized. Version control systems and configuration-management tools apply the same logic at a coarser grain: many clients can read a repository's HEAD state concurrently, but a commit that changes it needs exclusivity over the update. Understanding this problem is also the natural stepping stone to reasoning rigorously about Starvation and Livelock, since the readers-preferred and writers-preferred solutions are the cleanest concrete examples of a synchronization scheme that is perfectly safe yet fails to be live for one class of participants — a theme that recurs throughout concurrent systems design and connects back to the guarantees (or lack of them) offered by the underlying semaphore implementation itself.

Ask the tutor: Can you show how the fair solution's guarantees break down if the underlying semaphore does not wake waiters in FIFO order?