Problem 18 Readers-Writers

The scenario

Many threads need access to the same shared data structure — a cache, a configuration object, an in-memory index, a document. Most of the time they only read; occasionally one of them must write. The coordination rule is:

• Multiple readers can run at the same time.
• Writers must be alone. While a writer is in, no reader and no other writer may enter.

This is the readers-writers problem. It is different from a plain mutex problem because the rule is asymmetric: readers share the critical section with each other but not with writers. A single mutex would serialize readers too, throwing away most of the concurrency. A readers-writer lock (or a pair of semaphores) is the standard answer.

The naive bug: one mutex for everybody

The first instinct is to guard the whole structure with one synchronized block or ReentrantLock. That is safe, but it turns every reader into a serial bottleneck:

private final Object lock = new Object();

// reader
synchronized (lock) { return cache.get(key); }

// writer
synchronized (lock) { cache.put(key, value); }

With one mutex, ten simultaneous readers execute one after another even though none of them mutates anything. The exact-once invariant is satisfied, but the throughput is wrong for a read-heavy workload. The point of readers-writers is to widen the lock from one-at-a-time to many-readers-or-one-writer.

Java: ReentrantReadWriteLock

java.util.concurrent.locks.ReentrantReadWriteLock splits one lock into two: a readLock() that multiple threads can hold, and a writeLock() that excludes everyone. The rule above is enforced by the lock itself.

import java.util.concurrent.locks.ReentrantReadWriteLock;

public class ReadWriteCache<K,V> {
    private final ReentrantReadWriteLock rw = new ReentrantReadWriteLock();
    private final Map<K,V> map = new HashMap<>();

    public V get(K key) {
        rw.readLock().lock();
        try {
            return map.get(key);
        } finally {
            rw.readLock().unlock();
        }
    }

    public void put(K key, V value) {
        rw.writeLock().lock();
        try {
            map.put(key, value);
        } finally {
            rw.writeLock().unlock();
        }
    }
}

Important caveats:

• A thread holding the read lock cannot "upgrade" to the write lock. Upgrading would deadlock because the writer waits for all readers, and the current reader waits for itself. If you may need to write, take the write lock from the start.
• ReentrantReadWriteLock is not automatically fair. Under heavy read load, a waiting writer can be starved by a continuous stream of new readers.

Writer starvation and the two policy variants

The hard design question is not how to allow concurrent reads; it is what to do when a writer is waiting while readers keep arriving. There are three policies:

Policy	Behavior	Throughput	Risk
Reader preference	New readers jump ahead of a waiting writer.	Very high for reads.	Writers can starve indefinitely.
Writer preference	Once a writer waits, no new reader enters until the writer is done.	Lower peak read throughput.	Readers may wait, but writes make progress.
Fair / FIFO	Threads are served in arrival order.	Lowest aggregate throughput.	No starvation, predictable latency.

ReentrantReadWriteLock(true) is fair in the sense of queue order, but fair ordering is usually slower because it reduces concurrency. Most production caches use writer-preferring semantics to guarantee that updates eventually land.

To see why reader preference starves a writer, watch the active-reader count under a steady arrival of readers while one writer waits:

t	Event	Active readers	Writer W1
0	R1 takes the read lock	1	blocks — a reader is in
1	R2 arrives before R1 leaves	2	still blocked
2	R1 leaves, but R3 arrives the same instant	≥1	never observes 0
…	readers keep overlapping	>0 forever	starved

The writer can only enter when the read count hits exactly 0, and under reader preference an overlapping stream of readers never lets it reach 0. Writer preference flips the rule: the moment W1 is queued, new readers park (the waitingWriters > 0 guard in the implementation below), so the in-flight readers drain to 0 and W1 gets in.

Monitor implementation: writer preference

The same policy can be built by hand from one monitor (a lock plus a condition) and three counters — activeReaders, waitingWriters, and a writerActive flag. This is the classic writers-preference solution (Courtois et al., 1971; Herlihy & Shavit). The one rule that keeps it deadlock-free: every blocking wait is mutex.wait(), which releases the monitor — a thread must never park while holding a lock a peer needs to release it.

class WriterPreferringLock {
    private int activeReaders  = 0;
    private int waitingWriters = 0;
    private boolean writerActive = false;
    private final Object mutex = new Object();

    // reader entry protocol
    void readLock() throws InterruptedException {
        synchronized (mutex) {
            // writer preference: yield to a writer that is active OR merely waiting
            while (writerActive || waitingWriters > 0) { mutex.wait(); }
            activeReaders++;
        }
    }

    void readUnlock() {
        synchronized (mutex) {
            if (--activeReaders == 0) { mutex.notifyAll(); }  // last reader wakes a writer
        }
    }

    // writer entry protocol
    void writeLock() throws InterruptedException {
        synchronized (mutex) {
            waitingWriters++;
            while (writerActive || activeReaders > 0) { mutex.wait(); }
            waitingWriters--;
            writerActive = true;
        }
    }

    void writeUnlock() {
        synchronized (mutex) {
            writerActive = false;
            mutex.notifyAll();   // wake queued writers first (they re-check), then readers
        }
    }
}

The waitingWriters > 0 guard in readLock is what gives writers priority: the instant one writer is queued, new readers park instead of jumping ahead, so the writer is guaranteed to observe activeReaders == 0 and get in. Note the earlier temptation — a binary semaphore acquire()d inside the synchronized block — is exactly the deadlock trap: with two writers, one writer's unlock needs the monitor to clear its flag while a first reader sits inside the monitor blocked on that same semaphore, and neither can proceed. Waiting only via mutex.wait() (which drops the monitor) removes that cycle entirely.

Go: sync.RWMutex

Go's sync.RWMutex provides the same two-lock contract with RLock/RUnlock and Lock/Unlock. Since Go 1.5 it is writer-preferring: if a writer is waiting, new readers block until the writer finishes, preventing writer starvation.

type Cache struct {
    mu   sync.RWMutex
    data map[string]string
}

func (c *Cache) Get(key string) string {
    c.mu.RLock()
    defer c.mu.RUnlock()
    return c.data[key]
}

func (c *Cache) Set(key, value string) {
    c.mu.Lock()
    defer c.mu.Unlock()
    c.data[key] = value
}

As in Java, do not try to upgrade from RLock to Lock; release the read lock first, then acquire the write lock (and re-check the condition, because another writer may have changed the value).

When NOT to use a readers-writer lock

• Short critical sections. The extra bookkeeping can cost more than the serialization it saves.
• Write-heavy workloads. If writers are common, they serialize everything anyway and the lock adds overhead.
• Need lock upgrading. Neither Java nor Go supports read→write upgrade. Use a plain mutex or restructure so the write path is entered directly.
• Strongly consistent reads after a write. A readers-writer lock gives isolation, not ordering across separate calls; your storage still needs a proper happens-before edge.

Interview takeaways

• The readers-writers problem is about asymmetric concurrency: share among readers, exclude writers.
• The key trade-off is reader throughput vs writer latency/starvation.
• Always release the correct lock: a read lock must be released with readUnlock, a write lock with writeUnlock. Mixed unlock calls corrupt the state.
• Know the starvation story: a naive reader-preference lock can block writers forever; production runtimes usually prefer writers.

Sources: Herlihy & Shavit, The Art of Multiprocessor Programming (readers-writers semaphore solutions); Go sync.RWMutex documentation; Java ReentrantReadWriteLock documentation.

Who picks which policy — and why

The right policy is dictated by the read:write ratio and how much staleness the reads can tolerate. Real systems land all over the map:

System	Policy	Why that choice
Go sync.RWMutex	Writer-preferring (since 1.5)	Guards shared program state where an update must eventually land; a reader stream must not starve the writer.
Java ReentrantReadWriteLock (default)	Non-fair — readers can barge	Optimises aggregate throughput; if writes must land promptly you opt into new ReentrantReadWriteLock(true) for FIFO fairness.
Linux seqlock (kernel timekeeping)	Extreme reader preference — readers never block; they retry on a concurrent write	Reads (e.g. reading the clock) are ultra-hot and must be wait-free; writes are rare, so making a reader re-read on conflict is cheaper than ever blocking it.
Postgres / InnoDB (MVCC)	No reader-writer lock on rows at all — snapshot versioning	OLTP is read-heavy and cannot afford readers blocking writers or vice versa, so each reader sees a consistent snapshot while writers create new row versions.
Config / feature-flag cache	Copy-on-write: build a new map, atomically swap an AtomicReference	Reads sit on the hot path and must pay zero locking; writes (a config reload) are rare enough to afford rebuilding the whole map.

The pattern behind the table: the more lopsided the read:write ratio and the more staleness reads tolerate, the further you push toward reader preference — and past a point you drop the lock entirely for snapshots or copy-on-write so writers never block reads at all. When writes must be seen promptly you choose writer preference; when you need predictable latency and no starvation on either side you pay for fair / FIFO ordering.

Drill ladder

• L1: In the hand-built monitor, which state guards the data invariant, and which one gives writers priority?
• L2: Trace reader-preference starvation of a waiting writer in 4 steps (see the table above).
• L3: How does Go's sync.RWMutex avoid writer starvation, and why can a database prefer MVCC over any of these policies?

I'm working on the problem **Problem 18 Readers-Writers** (Concurrency). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Explain the optimal approach to **Problem 18 Readers-Writers** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

I'll paste my solution to **Problem 18 Readers-Writers**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Give me 2 problems that use the SAME underlying pattern as **Problem 18 Readers-Writers**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.