Readers-Writers Problem | Concurrency Roadmap

Language-specific mechanics: Concurrency Language Manual →

The problem

A shared resource (a database, a file, an in-memory data structure) is accessed by two kinds of threads: readers, who only read it, and writers, who modify it. The synchronization constraints are asymmetric by design:

Any number of readers may access the resource concurrently — reads don't conflict with other reads, so serializing them (as a plain mutex would) needlessly destroys parallelism.
A writer needs exclusive access — no readers and no other writers may be active while it writes.

This is the formal generalization of "a mutex is too conservative when the operation is read-only," and it's the concurrency-primitives-level version of a pattern you already know from databases: shared (read) locks vs. exclusive (write) locks. Real systems reach for this constantly — java.util.concurrent.locks.ReentrantReadWriteLock, Rust's RwLock, and copy-on-write data structures are all direct answers to this exact problem.

Why a plain mutex is the wrong tool

A single mutex around the resource is trivially correct (it enforces exclusive access for everyone), but it's needlessly slow under a read-heavy workload: a hundred concurrent readers on a mutex-protected resource run one at a time, even though none of them would ever conflict with each other. The entire point of solving this problem "properly" is unlocking that concurrency for the common case (usually far more reads than writes) while preserving correctness for the rare case (writes).

First readers-writers problem: reader-preference

The classical semaphore solution uses one mutex protecting a reader count, plus one binary semaphore/mutex (resource, sometimes called wrt) that guards the resource itself:

readcount = 0                     # shared, protected by mutex
mutex     = Semaphore(1)          # protects readcount
resource  = Semaphore(1)          # exclusive access to the actual resource

reader():                          writer():
    mutex.wait()                       resource.wait()
    readcount += 1                     write()
    if readcount == 1:                 resource.signal()
        resource.wait()      # first reader locks out writers
    mutex.signal()
    read()
    mutex.wait()
    readcount -= 1
    if readcount == 0:
        resource.signal()    # last reader lets writers back in
    mutex.signal()

The key idea: only the first arriving reader competes with writers for resource; every subsequent reader just increments readcount and proceeds immediately, since the first reader already established that no writer is active. Symmetrically, only the last departing reader releases resource back for writers.

This solution has a real, well-documented flaw: it gives strict preference to readers. If readers keep arriving faster than the gaps between them close, a waiting writer can be postponed indefinitely — a waiting writer never blocks a new reader from joining, because new readers only ever check readcount, never anything the writer set. This is called writer starvation, and it's the textbook downside of this exact solution — not a bug, a documented trade-off of prioritizing read throughput.

Second readers-writers problem: writer-preference

To fix writer starvation, add a second gate (often called readTry) that a writer can close the instant it starts waiting, blocking any new readers from joining — while readers already in the critical section are allowed to finish:

writer_count = 0                  # shared, protected by wmutex
wmutex       = Semaphore(1)
readTry      = Semaphore(1)       # gate new readers can be blocked at
resource     = Semaphore(1)

writer():                           reader():
    wmutex.wait()                       readTry.wait()   # blocked if a writer is waiting/active
    writer_count += 1                   mutex.wait()
    if writer_count == 1:               readcount += 1
        readTry.wait()  # close the gate for new readers    if readcount == 1:
    wmutex.signal()                         resource.wait()
    resource.wait()                     mutex.signal()
    write()                             readTry.signal()  # done checking in, gate reopens for the *next* one
    resource.signal()                   read()
    wmutex.wait()                       mutex.wait()
    writer_count -= 1                   readcount -= 1
    if writer_count == 0:               if readcount == 0:
        readTry.signal()                    resource.signal()
    wmutex.signal()                     mutex.signal()

This closes the writer-starvation hole — once a writer signals intent, no new reader can check in until that writer (and any writers queued behind it) have gone — but it introduces the mirror-image problem: reader starvation under a write-heavy workload, since a continuous stream of writers can keep the gate perpetually closed to readers. It also reduces read throughput more than the first solution, since even a single pending writer now blocks every new reader, not just new writers.

Third readers-writers problem: fair (starvation-free for both)

Neither preference is "correct" in general — which one you want is a product decision, not a synchronization one (a cache that's read constantly and written rarely wants reader-preference-like throughput; a system where staleness is dangerous wants writer-preference-like recency). The third readers-writers problem adds the explicit constraint that neither readers nor writers may be starved — every request for access must be satisfied within a bounded amount of time.

The standard construction enforces this with a single shared "service queue" semaphore that both readers and writers must pass through, strictly in arrival order, before contending for the resource itself:

serviceQueue = Semaphore(1)   # FIFO ticket both readers and writers wait on

reader():                          writer():
    serviceQueue.wait()                 serviceQueue.wait()
    # ... reader-preference-style       resource.wait()
    #     readcount/mutex logic,        write()
    #     but release serviceQueue      resource.signal()
    #     immediately after             serviceQueue.signal()
    #     checking in, before
    #     actually reading
    serviceQueue.signal()
    read()

The trick: a reader holds serviceQueue only long enough to register its intent to read (bump readcount, possibly lock resource), then releases the ticket immediately — so a writer arriving after it in real time can queue up right behind, rather than getting stuck behind an unbounded stream of readers that keep arriving "before" it in the reader-preference sense. As long as the underlying semaphore implementation itself doesn't allow indefinite barging (i.e., is at least eventually fair), this bounds both readers' and writers' worst-case wait by the number of requests already queued ahead of them, not by an adversarial arrival pattern of the other group.

Choosing a variant: the trade-off table

Variant	Readers starve?	Writers starve?	Best when
Reader-preference	No	Yes, possible	Read-heavy, staleness-tolerant (caches, config reads)
Writer-preference	Yes, possible	No	Write-correctness-critical, reads can tolerate latency
Fair / FIFO	No	No	General-purpose libraries where you can't assume the workload shape (e.g. `ReentrantReadWriteLock`'s fair mode)

This is exactly the kind of "it depends, and here's specifically what it depends on" answer senior interviewers are listening for — reciting one solution without naming its starvation trade-off is an incomplete answer at this level.

Pitfalls and interview gotchas

Presenting reader-preference as "the" readers-writers solution without naming its writer-starvation flaw. This is the single most common gap in an otherwise-correct answer.
Forgetting that readcount/writer_count themselves need protection. They're shared mutable state read-then-written by every thread, so mutex/wmutex around them is not optional bookkeeping — it's a second, nested synchronization problem inside the larger one, easy to forget once you're focused on the reader/writer semaphore logic.
Conflating this with a simple "one lock for readers, one for writers." Two independent locks don't compose into correct behavior — a writer must be excluded from readers and from other writers, and only the shared coordination shown above (not two separate locks) achieves that.
Assuming ReentrantReadWriteLock-style primitives solve starvation for you by default. Java's implementation is non-fair by default (same barging trade-off as a plain semaphore) — you must explicitly request the fair constructor to get FIFO-ish ordering guarantees, at a real throughput cost.
Missing the connection to Condition Variables & Monitors (next topic). Everything above is expressed with counting/binary semaphores because that's this topic's toolkit, but the identical constraints can be expressed with a mutex + condition variables instead — recognizing that these are two notations for the same underlying constraint (not two different problems) is exactly the connection the next topic will ask you to draw.

Only the first arriving reader competes with writers for resource; only the last departing reader releases it — see the theory above for why this specific solution can starve writers under sustained read load.

type ReaderPreference struct {
    mu        chan struct{} // binary semaphore around readCount
    resource  chan struct{} // binary semaphore for exclusive write
    readCount int
}

func NewReaderPreference() *ReaderPreference {
    r := &ReaderPreference{
        mu:       make(chan struct{}, 1),
        resource: make(chan struct{}, 1),
    }
    r.mu <- struct{}{}
    r.resource <- struct{}{}
    return r
}

func (r *ReaderPreference) ReaderEnter() {
    <-r.mu
    r.readCount++
    if r.readCount == 1 {
        <-r.resource // first reader locks out writers
    }
    r.mu <- struct{}{}
}

func (r *ReaderPreference) ReaderExit() {
    <-r.mu
    r.readCount--
    if r.readCount == 0 {
        r.resource <- struct{}{} // last reader re-admits writers
    }
    r.mu <- struct{}{}
}

func (r *ReaderPreference) Write(action func()) {
    <-r.resource
    defer func() { r.resource <- struct{}{} }()
    action()
}

Same readCount-gates-resource protocol as the textbook, so writers can starve under sustained reads. In production Go you'd reach for sync.RWMutex (RLock/Lock) instead of hand-rolling this — it's shown with channel-semaphores because that's this topic's toolkit, and because seeing the gate makes the starvation trade-off visible.

Further Resources (Optional)

Optional Practice (Extra Reps)

For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.

Implement the Starvation-Free Readers-Writers Problem (OSTEP homework skeleton)OSTEP Homework!4/540m
Puzzle: Readers-Writers Problem, Reader-Preference Solution (Little Book of Semaphores §4.2)The Little Book of Semaphores~3/530m
Implement the Writer-Preference Variant and Identify Which Threads Can Now StarveGeeksforGeeks~4/530m