Home/Learn/Operating Systems/Readers-Writers Problem

Readers-Writers Problem

Intermediate

Synchronization

The readers-writers problem allows multiple readers to read shared data concurrently but requires exclusive access for writers, balancing throughput and fairness.

Overview

The readers-writers problem models a shared resource (a database, a file, an in-memory data structure) where multiple concurrent reads are safe (readers do not modify data) but a write must be exclusive (no other reader or writer). Three variants exist. First readers-writers (readers preferred): a new reader can always enter even if writers are waiting — can starve writers. Second readers-writers (writers preferred): once a writer is waiting, no new readers are admitted — can starve readers. Fair readers-writers: arrivals are queued in order — no starvation but lower throughput. Java's ReadWriteLock (ReentrantReadWriteLock) implements the fair variant. For highly-read, rarely-written data structures, read-write locking can dramatically improve throughput over exclusive locking — particularly valuable for caches, routing tables, and configuration data.

ReentrantReadWriteLock: Multiple Readers, Exclusive Writer

ReentrantReadWriteLock exposes two lock views: readLock() (shared — multiple concurrent holders) and writeLock() (exclusive — one holder, blocks readers and writers). Read locks can be acquired by any number of threads simultaneously as long as no write lock is held. This allows read-heavy workloads to proceed in parallel, limited only by memory bandwidth.

Java — ReentrantReadWriteLock with concurrent reads and exclusive write

// Read-write lock: concurrent reads, exclusive writes
ReentrantReadWriteLock rwLock = new ReentrantReadWriteLock(true); // fair=true
Lock readLock  = rwLock.readLock();
Lock writeLock = rwLock.writeLock();

Map<String, String> sharedConfig = new HashMap<>();

// Multiple readers can proceed simultaneously
Runnable reader = () -> {
    readLock.lock();
    try {
        // All reader threads proceed in parallel — no blocking between readers
        String value = sharedConfig.get("key");
        System.out.printf("[%s] Read: %s%n", Thread.currentThread().getName(), value);
        Thread.sleep(50); // simulate read processing
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    } finally {
        readLock.unlock();  // ALWAYS unlock in finally
    }
};

// Writer gets exclusive access — blocks all readers and writers
Runnable writer = () -> {
    writeLock.lock();
    try {
        sharedConfig.put("key", "value-" + System.currentTimeMillis());
        System.out.printf("[%s] Write completed%n", Thread.currentThread().getName());
        Thread.sleep(20); // simulate write processing
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    } finally {
        writeLock.unlock();
    }
};

// Throughput comparison: 10 readers, 1 writer
ExecutorService exec = Executors.newFixedThreadPool(12);
for (int i = 0; i < 10; i++) exec.submit(reader);
exec.submit(writer);
exec.submit(reader);  // this reader doesn't block other readers
exec.shutdown();
exec.awaitTermination(5, TimeUnit.SECONDS);

Write Lock Downgrade and Starvation Analysis

ReentrantReadWriteLock supports lock downgrade: a thread holding the write lock can acquire the read lock, then release the write lock — the update and subsequent read are atomic relative to other writers. Upgrade (read → write) is NOT supported and causes deadlock. With fair=false (default), writers can starve in a read-heavy workload. Measure read vs write throughput to tune fair mode.

Java — lock downgrade pattern and fair vs non-fair read-write lock trade-offs

// Lock downgrade: write then downgrade to read (atomic transition)
ReentrantReadWriteLock rwl = new ReentrantReadWriteLock();
volatile String cachedValue = null;

void refreshAndRead() {
    rwl.writeLock().lock();           // acquire write lock
    try {
        cachedValue = fetchFromDB();  // update under write lock
        rwl.readLock().lock();        // acquire read lock BEFORE releasing write
    } finally {
        rwl.writeLock().unlock();     // downgrade: release write, keep read
    }
    try {
        processValue(cachedValue);    // read while holding read lock
    } finally {
        rwl.readLock().unlock();
    }
    // Between writeLock.unlock() and readLock.unlock(): only readers allowed (shared)
    // No writer can sneak in and change cachedValue during processValue()
}

// Starvation analysis with ReentrantReadWriteLock(fair=false):
// In a read-heavy system (e.g. 100 readers/sec, 1 writer/sec):
// → writers may wait very long (reader-preferred default)
// Fix: ReentrantReadWriteLock(fair=true) — FIFO ordering, prevents starvation
// Cost: ~30% lower throughput due to fairness overhead

String fetchFromDB() { return "db-data-" + System.currentTimeMillis(); }
void processValue(String v) { /* process */ }

Key Points to Remember

1Multiple readers can hold the read lock concurrently — no blocking between readers.
2A writer requires exclusive access — blocks all readers and other writers.
3First readers-writers (readers preferred): writers may starve; second (writers preferred): readers may starve.
4Java ReentrantReadWriteLock(fair=true) prevents starvation at the cost of some throughput.
5Lock downgrade (write → read) is supported; lock upgrade (read → write) is NOT and causes deadlock.
6ReadWriteLock provides significant throughput gains for read-heavy, write-rare workloads (caches, config).

Interview Questions

What is the readers-writers problem and what are its two classic variants?

MediumGoogle

How does ReentrantReadWriteLock improve throughput over exclusive locking?

MediumAmazon

Why is lock upgrade (read to write) not supported and what problem does it cause?

HardUber

When would you choose ReadWriteLock over a simple synchronized block?

MediumAdobe

Ask Aria about Readers-Writers Problem

Your personal AI tutor — ask anything about this concept

Revision Status

Personal Notes

Discussion

Loading discussion…

Producer-Consumer Problem

Dining Philosophers Problem