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.
1 import java.util.concurrent.locks.ReentrantReadWriteLock;
2
3 class Cache {
4 private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
5 private final Map<String, String> data = new HashMap<>();
6
7 public String get(String k) {
8 lock.readLock().lock();
9 try { return data.get(k); }
10 finally { lock.readLock().unlock(); }
11 }
12
13 public void put(String k, String v) {
14 lock.writeLock().lock();
15 try { data.put(k, v); }
16 finally { lock.writeLock().unlock(); }
17 }
18 }
19
20 // Use fair = true to prevent reader/writer starvation:
21 // 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.
1 class WriterPreferringRWLock {
2 private int activeReaders = 0;
3 private int waitingWriters = 0;
4 private boolean writerActive = false;
5
6 public synchronized void readLock() throws InterruptedException {
7 while (writerActive || waitingWriters > 0) wait(); // writer-pref
8 activeReaders++;
9 }
10 public synchronized void readUnlock() {
11 activeReaders--;
12 if (activeReaders == 0) notifyAll();
13 }
14 public synchronized void writeLock() throws InterruptedException {
15 waitingWriters++;
16 while (writerActive || activeReaders > 0) wait();
17 waitingWriters--;
18 writerActive = true;
19 }
20 public synchronized void writeUnlock() {
21 writerActive = false;
22 notifyAll();
23 }
24 }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)