OS Notes

Readers-Writers Problem

The readers-writers synchronization problem — first readers-writers problem (readers preference), second variant (writers preference), and starvation-free solutions.

Introduction

Consider a shared database. Many processes might want to read the database simultaneously — and that is perfectly safe because reading does not modify data. But when a process wants to write (update) the database, it must have exclusive access — no readers or other writers should access the data during the update. This is the readers-writers problem.

This problem appears constantly in real systems: file systems (multiple readers, exclusive writer), databases (shared locks for SELECT, exclusive locks for UPDATE), and caches (concurrent reads, exclusive invalidation). It differs from simple mutual exclusion because we want to allow concurrent reads while only restricting writes. Using a simple mutex for all access would be correct but unnecessarily restrictive — it would serialize readers that could safely proceed in parallel.

Problem Constraints

The four rules that any solution must enforce:

Multiple readers can read simultaneously (shared access)
Only ONE writer can write at a time (exclusive access)
When a writer is writing, NO readers can read
When any reader is reading, NO writer can write

The challenge lies in implementing these rules efficiently while considering fairness — should readers or writers have priority when both are waiting?

First Readers-Writers Problem (Readers Preference)

Readers have priority — as long as any reader is active, new readers can enter immediately without waiting. Writers must wait until ALL readers finish.

Example

semaphore mutex = 1; // Protects read_count semaphore write_lock = 1; // Exclusive access for writing int read_count = 0; // Number of active readers void reader() { while (true) { // Entry section wait(&mutex); read_count++; if (read_count == 1) wait(&write_lock); // First reader locks out writers signal(&mutex); // === READING (shared access) === read_data(); // Exit section wait(&mutex); read_count--; if (read_count == 0) signal(&write_lock); // Last reader allows writers signal(&mutex); } } void writer() { while (true) { wait(&write_lock); // Exclusive access // === WRITING (exclusive access) === write_data(); signal(&write_lock); } }

How it works:

The first reader to arrive acquires write_lock, blocking all writers
Subsequent readers just increment read_count and proceed (no waiting!)
The last reader to leave releases write_lock, allowing a waiting writer to proceed
mutex protects the read_count variable from race conditions

Problem with this solution: Writers can starve. If readers continuously arrive, read_count never reaches 0, and writers wait forever. In a busy system with many read requests, a writer might never get to execute.

Second Readers-Writers Problem (Writers Preference)

When a writer is waiting, no new readers are allowed to start reading. Currently active readers finish, but new readers queue behind the waiting writer. This prevents writer starvation but can potentially starve readers.

Example

semaphore mutex = 1; // Protects read_count semaphore write_lock = 1; // Exclusive access for writing semaphore read_try = 1; // Writers can block new readers int read_count = 0; void reader() { while (true) { wait(&read_try); // Check if a writer is waiting (blocks if yes) wait(&mutex); read_count++; if (read_count == 1) wait(&write_lock); // First reader blocks writers signal(&mutex); signal(&read_try); // Allow other readers to check read_data(); wait(&mutex); read_count--; if (read_count == 0) signal(&write_lock); // Last reader unblocks writer signal(&mutex); } } void writer() { wait(&read_try); // Block new readers from starting wait(&write_lock); // Wait for current readers to finish write_data(); signal(&write_lock); signal(&read_try); // Allow readers again }

How it works:

A writer acquires read_try first, which blocks any new reader from entering
Then the writer waits on write_lock for existing readers to finish
Once all current readers exit (releasing write_lock), the writer proceeds
After writing, the writer releases read_try, allowing queued readers to proceed

Third Readers-Writers Problem (Fair / Starvation-Free)

Neither readers nor writers should starve. Access is granted in FIFO order — whoever arrives first (reader or writer) is served next.

Example

semaphore order_queue = 1; // Enforces arrival order (FIFO) semaphore write_lock = 1; // Exclusive write access semaphore mutex = 1; // Protects read_count int read_count = 0; void reader() { wait(&order_queue); // Wait your turn in FIFO order wait(&mutex); read_count++; if (read_count == 1) wait(&write_lock); signal(&mutex); signal(&order_queue); // Release so next in queue can proceed read_data(); wait(&mutex); read_count--; if (read_count == 0) signal(&write_lock); signal(&mutex); } void writer() { wait(&order_queue); // Wait your turn in FIFO order wait(&write_lock); // Get exclusive access signal(&order_queue); // Release so next (reader) can queue write_data(); signal(&write_lock); }

This solution ensures that requests are serviced roughly in arrival order. A writer arriving between groups of readers will be served between those groups, not after all of them.

Read-Write Locks in Practice

Modern systems provide read-write lock primitives that implement these semantics efficiently:

c example

#include <pthread.h>

pthread_rwlock_t rwlock = PTHREAD_RWLOCK_INITIALIZER;

void reader() {
    pthread_rwlock_rdlock(&rwlock);  // Shared lock (multiple OK)
    read_data();
    pthread_rwlock_unlock(&rwlock);
}

void writer() {
    pthread_rwlock_wrlock(&rwlock);  // Exclusive lock (only one)
    write_data();
    pthread_rwlock_unlock(&rwlock);
}

Java's ReadWriteLock

java example

ReadWriteLock lock = new ReentrantReadWriteLock();

// Reader
lock.readLock().lock();
try { readData(); }
finally { lock.readLock().unlock(); }

// Writer
lock.writeLock().lock();
try { writeData(); }
finally { lock.writeLock().unlock(); }

Real-World Applications

System	Readers	Writers	Preference
Database (MVCC)	SELECT queries	INSERT/UPDATE	Readers (snapshots)
Linux kernel	RCU read-side	RCU update	Readers (lock-free reads)
DNS cache	DNS lookups	Cache refresh	Readers
Configuration	Apps reading config	Admin hot-reload	Writers
Web cache	Serving cached pages	Cache invalidation	Depends on SLA

Performance Considerations

Read-write locks are not always better than simple mutexes:

If writes are frequent (> 20% of operations), the overhead of managing readers may exceed the benefit
If read operations are very short, contention on the reader count variable creates its own bottleneck
Modern alternatives like RCU (Read-Copy-Update) in Linux provide wait-free reads at the cost of delayed memory reclamation

Rule of thumb: Use read-write locks when reads vastly outnumber writes AND read operations are expensive enough that parallelism provides measurable benefit.

Key Takeaways

The readers-writers problem allows concurrent reads but requires exclusive writes
First variant (readers preference): readers never wait for other readers, but writers may starve
Second variant (writers preference): waiting writers block new readers, but readers may starve
Third variant (fair/FIFO): no starvation for either party, but reduced concurrency
Read-write locks (pthread_rwlock, Java ReentrantReadWriteLock) are the standard practical implementation
The problem appears everywhere: databases, file systems, caches, and configuration management
Choose the variant that matches your system's priorities: read throughput vs write latency vs fairness

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Readers-Writers Problem.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Operating Systems topic.

Search Terms

operating-systems, operating systems, operating, systems, process, synchronization, readers, writers

Continue learning this concept

Process SynchronizationCritical Section ProblemDeep dive into the critical section problem — requirements, software solutions (Peterson\Process SynchronizationDining Philosophers ProblemThe classic dining philosophers problem — problem statement, naive solution showing deadlock, correct solutions using semaphores, monitors, and resource hierarchy.Process SynchronizationProducer-Consumer ProblemThe classic producer-consumer (bounded buffer) synchronization problem — solutions using semaphores, mutex locks, and monitors with complete code examples.Process SynchronizationMonitorsUnderstanding monitors as a high-level synchronization construct — encapsulation, condition variables, wait and signal operations, and comparison with semaphores.Process SynchronizationMutex LocksUnderstanding mutex locks for mutual exclusion — acquire and release operations, spinlocks vs blocking mutexes, recursive mutexes, and practical mutex usage patterns.Process SynchronizationSemaphoresComplete guide to semaphores — counting and binary semaphores, wait() and signal() operations, implementation, usage patterns, and solving synchronization problems with semaphores.

PreviousProducer-Consumer Problem NextSemaphores

OS Notes

Readers-Writers Problem

The readers-writers synchronization problem — first readers-writers problem (readers preference), second variant (writers preference), and starvation-free solutions.

Introduction

Problem Constraints

The four rules that any solution must enforce:

Multiple readers can read simultaneously (shared access)
Only ONE writer can write at a time (exclusive access)
When a writer is writing, NO readers can read
When any reader is reading, NO writer can write

The challenge lies in implementing these rules efficiently while considering fairness — should readers or writers have priority when both are waiting?

First Readers-Writers Problem (Readers Preference)

Readers have priority — as long as any reader is active, new readers can enter immediately without waiting. Writers must wait until ALL readers finish.

Example

How it works:

The first reader to arrive acquires write_lock, blocking all writers
Subsequent readers just increment read_count and proceed (no waiting!)
The last reader to leave releases write_lock, allowing a waiting writer to proceed
mutex protects the read_count variable from race conditions

Second Readers-Writers Problem (Writers Preference)

Example

How it works:

A writer acquires read_try first, which blocks any new reader from entering
Then the writer waits on write_lock for existing readers to finish
Once all current readers exit (releasing write_lock), the writer proceeds
After writing, the writer releases read_try, allowing queued readers to proceed

Third Readers-Writers Problem (Fair / Starvation-Free)

Neither readers nor writers should starve. Access is granted in FIFO order — whoever arrives first (reader or writer) is served next.

Example

This solution ensures that requests are serviced roughly in arrival order. A writer arriving between groups of readers will be served between those groups, not after all of them.

Read-Write Locks in Practice

Modern systems provide read-write lock primitives that implement these semantics efficiently:

c example

#include <pthread.h>

pthread_rwlock_t rwlock = PTHREAD_RWLOCK_INITIALIZER;

void reader() {
    pthread_rwlock_rdlock(&rwlock);  // Shared lock (multiple OK)
    read_data();
    pthread_rwlock_unlock(&rwlock);
}

void writer() {
    pthread_rwlock_wrlock(&rwlock);  // Exclusive lock (only one)
    write_data();
    pthread_rwlock_unlock(&rwlock);
}

Java's ReadWriteLock

java example

ReadWriteLock lock = new ReentrantReadWriteLock();

// Reader
lock.readLock().lock();
try { readData(); }
finally { lock.readLock().unlock(); }

// Writer
lock.writeLock().lock();
try { writeData(); }
finally { lock.writeLock().unlock(); }

Real-World Applications

System	Readers	Writers	Preference
Database (MVCC)	SELECT queries	INSERT/UPDATE	Readers (snapshots)
Linux kernel	RCU read-side	RCU update	Readers (lock-free reads)
DNS cache	DNS lookups	Cache refresh	Readers
Configuration	Apps reading config	Admin hot-reload	Writers
Web cache	Serving cached pages	Cache invalidation	Depends on SLA

Performance Considerations

Read-write locks are not always better than simple mutexes:

If writes are frequent (> 20% of operations), the overhead of managing readers may exceed the benefit
If read operations are very short, contention on the reader count variable creates its own bottleneck
Modern alternatives like RCU (Read-Copy-Update) in Linux provide wait-free reads at the cost of delayed memory reclamation

Rule of thumb: Use read-write locks when reads vastly outnumber writes AND read operations are expensive enough that parallelism provides measurable benefit.

Key Takeaways

The readers-writers problem allows concurrent reads but requires exclusive writes
First variant (readers preference): readers never wait for other readers, but writers may starve
Second variant (writers preference): waiting writers block new readers, but readers may starve
Third variant (fair/FIFO): no starvation for either party, but reduced concurrency
Read-write locks (pthread_rwlock, Java ReentrantReadWriteLock) are the standard practical implementation
The problem appears everywhere: databases, file systems, caches, and configuration management
Choose the variant that matches your system's priorities: read throughput vs write latency vs fairness

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Readers-Writers Problem.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Operating Systems topic.

Search Terms

operating-systems, operating systems, operating, systems, process, synchronization, readers, writers

Continue learning this concept

PreviousProducer-Consumer Problem NextSemaphores