Readers-Writers Problem
Many readers can access shared data concurrently, but writers need exclusive access. The classic problem: which side gets priority? Reader-pref starves writers; writer-pref starves readers; fair locks alternate. Java/Go/Python all ship reader-writer locks.
The problem in plain English
Multiple threads want to use one shared resource. Some only read. Some need to write. The constraints:
- Many readers can read at the same time. They don't conflict.
- A writer needs the resource alone. No other writers, no readers.
- A reader and a writer cannot run at the same time.The bug-prone question is what to do when a reader is reading and a writer arrives. Or when a writer is waiting and a new reader arrives. The answer is the preference policy.
A picture of the lock states
The interesting question is when readers AND writers are queued: who goes next?
Three policies, with their failure modes
| Policy | What it does | What can go wrong |
|---|---|---|
| Reader-preferring | New readers go in even if a writer is waiting | Writer never gets in if readers keep arriving (writer starvation) |
| Writer-preferring | Once a writer is waiting, no new readers can join | Long-running readers can block all reads if many writes arrive (reader starvation) |
| Fair / FIFO | Strict arrival order | Nobody starves; a single writer that arrives temporarily forces all readers to queue, slightly worse throughput |
Most stdlib RW locks are writer-preferring: Java's ReentrantReadWriteLock in non-fair mode, Go's sync.RWMutex. Fair mode is opt-in. Python doesn't ship one in the standard library.
When this problem appears in interviews
What's actually being tested "Implement a thread-safe cache." That's Readers-Writers in disguise. The interviewer wants to see the candidate reach for the right primitive (RW lock, not a plain Mutex) and articulate the tradeoffs (fairness, starvation, the re-entry deadlock).
The senior-level discussion points
- When does an RW lock actually pay off? Read-heavy + non-trivial read work. For tiny critical sections, the bookkeeping overhead exceeds the parallelism benefit.
- Reader vs writer preference? Default to writer-pref. Switch to fair if tail latency on the starved side hurts.
- The re-entry trap, calling another locked method while holding the read lock can deadlock under writer pressure. Sentinel pattern: internal
xxxLockedhelpers. - RCU as the extreme, readers don't lock at all; writers atomically swap versions. Best for read-mostly data; complex for the write path.
What kills naive implementations Forgetting to handle the case where the same thread acquires the read lock twice. Many RW locks are non-reentrant, re-acquiring deadlocks. ReentrantReadWriteLock (Java) is reentrant by design; sync.RWMutex (Go) is intentionally not. Pick based on the call patterns, not by default.
Where this scales
- Database connection pools, many concurrent reads, occasional schema changes (writes).
- Configuration caches, read on every request, write on hot-reload.
- In-memory indexes, read-heavy by nature.
- Routing tables, read on every packet, write on topology change.
Implementations
Standard library RW lock. By default it's non-fair (writer-preferring under contention). Pass true to constructor for fair (FIFO) ordering.
import java.util.concurrent.locks.ReentrantReadWriteLock;
class Cache {
private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
private final Map<String, String> data = new HashMap<>();
public String get(String k) {
lock.readLock().lock();
try { return data.get(k); }
finally { lock.readLock().unlock(); }
}
public void put(String k, String v) {
lock.writeLock().lock();
try { data.put(k, v); }
finally { lock.writeLock().unlock(); }
}
}
// Use fair = true to prevent reader/writer starvation:
// new ReentrantReadWriteLock(true);For interview purposes, knowing how to build one matters. Track active readers + waiting writers; readers wait if any writer is queued (writer-pref). Writers wait until no active readers.
class WriterPreferringRWLock {
private int activeReaders = 0;
private int waitingWriters = 0;
private boolean writerActive = false;
public synchronized void readLock() throws InterruptedException {
while (writerActive || waitingWriters > 0) wait(); // writer-pref
activeReaders++;
}
public synchronized void readUnlock() {
activeReaders--;
if (activeReaders == 0) notifyAll();
}
public synchronized void writeLock() throws InterruptedException {
waitingWriters++;
while (writerActive || activeReaders > 0) wait();
waitingWriters--;
writerActive = true;
}
public synchronized void writeUnlock() {
writerActive = false;
notifyAll();
}
}Key points
- •Readers can run concurrently with each other; writers need exclusive access
- •Reader-preference: writer can starve under sustained reader load
- •Writer-preference: reader can starve when writers always queue
- •Fair / FIFO: alternates by arrival order, slightly slower, no starvation
- •Most stdlib RW locks are writer-preferring (Java, Go, Python's read-write semaphore)