Readers-Writers (LLD)

Problem statement (interviewer prompt)

Design a synchronisation class that allows N concurrent readers but only one writer at a time. Implement and compare read-preferring, write-preferring, and fair (FIFO) policies; explain the starvation each prevents.

classDiagram
  class ReadWriteLock {
    <<interface>>
    +readLock() Lock
    +writeLock() Lock
  }
  class ReadPreferLock {
    -readerCount : int
    -lock : Mutex
    -writeMutex : Mutex
    +acquireRead()
    +releaseRead()
    +acquireWrite()
    +releaseWrite()
  }
  class WritePreferLock {
    -waitingWriters : int
    -activeWriter : boolean
  }
  class FairLock {
    -queue : FIFOQueue
  }
  ReadWriteLock <|.. ReadPreferLock
  ReadWriteLock <|.. WritePreferLock
  ReadWriteLock <|.. FairLock

Read-preferring is fastest but starves writers; write-preferring starves readers; FIFO is fair but slower.

classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;

The readers-writers lock is everywhere: caches, in-memory DBs, configuration services. The policy determines who starves under load.

Class hierarchy

classDiagram
  class ReadWriteLock {
    <<interface>>
    +readLock() Lock
    +writeLock() Lock
  }
  class ReadPrefer {
    -readers : int
    -mtx : Mutex
    -writeMtx : Mutex
  }
  class WritePrefer {
    -readers, writersWaiting : int
    -activeWriter : boolean
    -mtx : Mutex
    -okToRead, okToWrite : Condition
  }
  class FairFIFO {
    -mtx : Mutex
    -fifo : Deque~Request~
  }
  ReadWriteLock <|.. ReadPrefer
  ReadWriteLock <|.. WritePrefer
  ReadWriteLock <|.. FairFIFO

Read-preferring (first solution)

class ReadPrefer:
    def __init__(self):
        self.readers = 0
        self.read_mtx = Lock()      # protects readers count
        self.write_mtx = Lock()     # exclusive while any writer

    def acquire_read(self):
        with self.read_mtx:
            self.readers += 1
            if self.readers == 1:
                self.write_mtx.acquire()

    def release_read(self):
        with self.read_mtx:
            self.readers -= 1
            if self.readers == 0:
                self.write_mtx.release()

    def acquire_write(self): self.write_mtx.acquire()
    def release_write(self): self.write_mtx.release()

A continuous stream of readers can starve writers forever.

Write-preferring

Track waiting writers; readers wait if any writer is waiting. New readers queue behind pending writes; writers don't starve.

class WritePrefer:
    def __init__(self):
        self.readers = 0
        self.writers_waiting = 0
        self.active_writer = False
        self.mtx = Lock()
        self.ok_read = Condition(self.mtx)
        self.ok_write = Condition(self.mtx)

    def acquire_read(self):
        with self.mtx:
            while self.active_writer or self.writers_waiting > 0:
                self.ok_read.wait()
            self.readers += 1

    def release_read(self):
        with self.mtx:
            self.readers -= 1
            if self.readers == 0:
                self.ok_write.notify()

    def acquire_write(self):
        with self.mtx:
            self.writers_waiting += 1
            while self.active_writer or self.readers > 0:
                self.ok_write.wait()
            self.writers_waiting -= 1
            self.active_writer = True

    def release_write(self):
        with self.mtx:
            self.active_writer = False
            if self.writers_waiting > 0:
                self.ok_write.notify()
            else:
                self.ok_read.notify_all()

Burst of writes can now starve readers if writers always have one pending.

Fair (FIFO)

A single FIFO queue of waiters; reads can run concurrently only if they're contiguous at the head.

sequenceDiagram
  participant R1 as Read 1
  participant W as Write
  participant R2 as Read 2
  participant R3 as Read 3
  Note over R1,R3: all arrive in order
  R1->>R1: acquire (head, reads run together)
  R2->>R2: blocked by W ahead
  W->>W: waits for R1
  R1-->>W: done, W now runs
  W-->>R2: done, R2 + R3 run together

No starvation; throughput lower because parallel reads queue behind any pending write.

When to choose

Workload	Policy
Read-dominated, writes rare	Read-preferring
Writes can't be delayed (caches, config)	Write-preferring
Mixed; SLAs both ways	Fair (FIFO)
Java default	ReentrantReadWriteLock(fair=false) (read-preferring-ish)

Upgrade pitfall

Upgrading a read lock to a write lock (while holding it) → deadlock if two readers both try:

T1 holds read, wants write — waits for T2 to release read
T2 holds read, wants write — waits for T1 to release read

Mitigations: - Release read, acquire write, re-read (lost-update window). - Use intent-write / update lock (SQL Server U lock).

Library RWLocks

Lang	Lock
Java	ReentrantReadWriteLock(fair)
Go	sync.RWMutex (write-preferring-ish)
Rust	tokio::sync::RwLock, std::sync::RwLock
Python	no built-in; use threading.Lock or aiorwlock
C++	std::shared_mutex (C++17+)

When NOT to use RWLock

• Critical section is tiny: a plain mutex beats RWLock's bookkeeping overhead.
• Copy-on-write data is feasible: lock-free reads + occasional swap.
• High write rate: RWLock barely beats mutex.

Where readers-writers fits

flowchart TB
  RW((Readers-<br/>writers lock))
  CP[Concurrency primitives<br/>built on mutex + condvar]
  TD[Threading and deadlocks<br/>upgrade deadlock]
  PO[Pessimistic / optimistic locking<br/>DB analog: S vs X locks]
  CACHE[Caching strategies<br/>read-heavy use cases]
  CP --> RW
  TD -. failure modes .- RW
  PO -. DB analog .- RW
  RW --> CACHE

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class RW service;
    class CP,TD,PO,CACHE datastore;

Glossary & fundamentals

Tag	Concept	What it is	Page
LLD	Concurrency primitives	underlying mutex + condvars	concurrency-primitives
LLD	Threading and deadlocks	upgrade deadlock	threading-and-deadlocks
LLD	Pessimistic vs optimistic locking	DB analog	pessimistic-optimistic-locking
HLD	Caching strategies	top RWLock consumer	caching-strategies

Quick reference

Three policies

Policy	Starves	Use
Read-preferring	Writers	Read-dominated, writes rare
Write-preferring	Readers	Config/cache; writes must apply quickly
Fair FIFO	Nobody	Mixed workloads with SLAs

Read-preferring sketch

• Mutex on reader count
• First reader acquires write-mutex
• Last reader releases write-mutex
• Writers grab write-mutex directly

Write-preferring sketch

• Track writers_waiting
• New readers block if any writer waiting
• Writer wakes one writer; else broadcasts to readers

Upgrade deadlock

Two readers both upgrading to write → mutual wait. Fix: drop read, acquire write, re-validate (lost-update window).

Library RWLocks

• Java: ReentrantReadWriteLock(fair=true|false)
• Go: sync.RWMutex
• Rust: tokio::sync::RwLock, std::sync::RwLock
• C++17+: std::shared_mutex

When NOT to use RWLock

• Tiny critical section (mutex wins)
• COW data structures (lock-free reads)
• High write rate (RWLock overhead > benefit)

Refs

• Courtois et al. - Readers-Writers (CACM 1971)
• Java ReentrantReadWriteLock docs
• Go sync.RWMutex docs

FAQ

What is the readers-writers problem?

Multiple threads want to read shared state in parallel while writes need exclusive access. The design must coordinate them without deadlock and without starving either side.

What is the difference between read-preferring and write-preferring policies?

Read-preferring lets new readers proceed even while a writer waits, maximising throughput but starving writers. Write-preferring blocks new readers once a writer arrives.

How do you implement a fair read-write lock?

Use a FIFO queue of waiters with a flag for shared vs exclusive intent; grant readers in batches until an exclusive request is at the head, then drain readers and admit the writer.

When should you use a read-write lock instead of a plain mutex?

When reads are much more frequent than writes and read sections are non-trivial. For very short critical sections, a plain mutex often outperforms because of less bookkeeping.

How does Java's ReentrantReadWriteLock work?

It maintains a 32-bit count split between shared and exclusive holds, supports lock downgrade from write to read, and offers a fair mode backed by a CLH queue.

Related Topics

• Concurrency Primitives: mutex + condition variable building blocks
• Threading and Deadlocks: the upgrade-deadlock pitfall
• Pessimistic vs Optimistic Locking: the DB analog (S vs X locks)

Further reading

• Paper - Courtois, Heymans, Parnas - Concurrent Control with Readers and Writers (CACM 1971)
• Doc - Java ReentrantReadWriteLock
• Doc - Go sync.RWMutex