The Reader Writer Problem
The Reader Writer Problem, introduced by Courtois, Heymans, and Parnas in 1971, captures a situation that appears in virtually every database, file system, and shared configuration system: some processes only need to read data, while others need to modify it.
The key insight is that readers do not interfere with each other, but writers interfere with everyone. Treating all access as exclusive (like a simple mutex) wastes parallelism. The challenge is allowing maximum read concurrency while still protecting writes.
The Rules
Access Matrix:
Reader Writer
Reader OK BLOCK
Writer BLOCK BLOCK
Allowed: Multiple readers at the same time.
Blocked: Writer + anyone else (reader or writer).- Multiple readers can access the shared data concurrently since none of them modify it.
- A writer needs exclusive access. No readers or other writers can be active while a write is happening.
- If a reader reads while a writer is mid-update, it may get half-old and half-new data (inconsistent read).
- If two writers update simultaneously, their changes can conflict and corrupt the data.
First Readers-Writers Problem (Reader Preference)
In this variant, readers are given priority. As long as at least one reader is active, new readers can enter freely even if a writer is waiting. The writer must wait until every single reader has finished.
The Solution
| Primitive | Initial Value | Purpose |
|---|---|---|
| rw_mutex (semaphore) | 1 | Controls access to the shared resource. Writers acquire it for exclusive access. First reader acquires it to block writers. |
| mutex (semaphore) | 1 | Protects the read_count variable from concurrent modification by readers. |
| read_count (integer) | 0 | Tracks the number of readers currently reading. Only the first and last reader interact with rw_mutex. |
// --- Writer ---
void writer() {
wait(rw_mutex); // Exclusive access
write_data(); // Critical section
signal(rw_mutex); // Release
}
// --- Reader ---
void reader() {
wait(mutex); // Protect read_count
read_count++;
if (read_count == 1)
wait(rw_mutex); // First reader blocks writers
signal(mutex);
read_data(); // Multiple readers here simultaneously
wait(mutex); // Protect read_count
read_count--;
if (read_count == 0)
signal(rw_mutex); // Last reader lets writers in
signal(mutex);
}Step-by-Step Trace
Initial: read_count=0, rw_mutex=1, mutex=1
R1 enters: read_count=1, first reader -> wait(rw_mutex) -> rw_mutex=0
R1 is reading.
R2 enters: read_count=2, not first -> skips rw_mutex
R2 is reading alongside R1.
W1 arrives: calls wait(rw_mutex) -> rw_mutex=0 -> W1 BLOCKS
R3 enters: read_count=3, not first -> skips rw_mutex
R3 reads freely. W1 still waiting.
R1 exits: read_count=2, not last -> no signal.
R2 exits: read_count=1, not last -> no signal.
R3 exits: read_count=0, LAST reader -> signal(rw_mutex) -> rw_mutex=1
W1 unblocked: W1 acquires rw_mutex. Writes exclusively.Second Readers-Writers Problem (Writer Preference)
To fix writer starvation, the second variant gives writers priority. Once a writer signals its intent, no new readers are admitted. Existing readers finish, and then the writer enters. This guarantees writers are never starved by a flood of readers.
| Additional Primitive | Initial Value | Purpose |
|---|---|---|
| read_try (semaphore) | 1 | Readers must acquire this before updating read_count. Writers lock it to block new readers. |
| write_count (integer) | 0 | Tracks waiting and active writers. |
| w_mutex (semaphore) | 1 | Protects write_count. |
// --- Writer (with priority) ---
void writer() {
wait(w_mutex);
write_count++;
if (write_count == 1)
wait(read_try); // First writer blocks new readers
signal(w_mutex);
wait(rw_mutex); // Exclusive access to resource
write_data();
signal(rw_mutex);
wait(w_mutex);
write_count--;
if (write_count == 0)
signal(read_try); // Last writer lets readers in
signal(w_mutex);
}
// --- Reader (with writer priority) ---
void reader() {
wait(read_try); // Check: are writers waiting?
wait(mutex);
read_count++;
if (read_count == 1)
wait(rw_mutex);
signal(mutex);
signal(read_try); // Let other readers/writers check
read_data();
wait(mutex);
read_count--;
if (read_count == 0)
signal(rw_mutex);
signal(mutex);
}Now when a writer arrives, it locks read_try, which prevents any new readers from starting. Existing readers finish their work, and once the last one exits, the writer gets exclusive access. Readers can only resume after all waiting writers have finished.
Reader Preference vs Writer Preference
| Aspect | Reader Preference (First Problem) | Writer Preference (Second Problem) |
|---|---|---|
| Who gets priority | Readers. New readers enter even while writers wait. | Writers. New readers are blocked once a writer arrives. |
| Starvation risk | Writers can starve under continuous read traffic. | Readers can starve under continuous write traffic. |
| Read throughput | Maximum. Readers never wait for other readers. | Reduced. Readers pause when writers are waiting. |
| Write latency | Potentially unbounded. Writers wait for all readers. | Bounded. Writers get access as soon as current readers finish. |
| Complexity | Simpler. 2 semaphores + 1 counter. | More complex. 4 semaphores + 2 counters. |
| Best for | Read-heavy systems where writes are rare (DNS caches, config files). | Write-critical systems where data freshness matters (real-time databases). |
Full Implementation in C++ (Reader Preference)
#include <iostream>
#include <thread>
#include <mutex>
#include <semaphore>
#include <chrono>
#include <vector>
std::counting_semaphore<1> rw_mutex(1);
std::counting_semaphore<1> count_mutex(1);
int read_count = 0;
int shared_data = 0;
void writer(int id) {
for (int i = 0; i < 3; i++) {
std::cout << "Writer " << id << " waiting..." << std::endl;
rw_mutex.acquire(); // Exclusive access
shared_data += 10;
std::cout << "Writer " << id << " wrote. Data: "
<< shared_data << std::endl;
std::this_thread::sleep_for(std::chrono::milliseconds(400));
rw_mutex.release();
std::cout << "Writer " << id << " done." << std::endl;
std::this_thread::sleep_for(std::chrono::milliseconds(200));
}
}
void reader(int id) {
for (int i = 0; i < 3; i++) {
count_mutex.acquire();
read_count++;
if (read_count == 1)
rw_mutex.acquire(); // First reader blocks writers
count_mutex.release();
std::cout << "Reader " << id << " reading. Data: "
<< shared_data << " (active readers: "
<< read_count << ")" << std::endl;
std::this_thread::sleep_for(std::chrono::milliseconds(300));
count_mutex.acquire();
read_count--;
if (read_count == 0)
rw_mutex.release(); // Last reader lets writers in
count_mutex.release();
std::cout << "Reader " << id << " done." << std::endl;
std::this_thread::sleep_for(std::chrono::milliseconds(100));
}
}
int main() {
std::cout << "Reader Writer Problem Simulation" << std::endl;
std::cout << "----------------------------------" << std::endl;
std::thread w1(writer, 1);
std::thread r1(reader, 1), r2(reader, 2), r3(reader, 3);
w1.join();
r1.join(); r2.join(); r3.join();
std::cout << "----------------------------------" << std::endl;
std::cout << "Final data: " << shared_data << std::endl;
return 0;
}Output:
Reader Writer Problem Simulation
----------------------------------
Writer 1 waiting...
Reader 1 reading. Data: 0 (active readers: 1)
Reader 2 reading. Data: 0 (active readers: 2)
Reader 3 reading. Data: 0 (active readers: 3)
Reader 1 done.
Reader 2 done.
Reader 3 done.
Writer 1 wrote. Data: 10
Writer 1 done.
Reader 1 reading. Data: 10 (active readers: 1)
Reader 2 reading. Data: 10 (active readers: 2)
...
----------------------------------
Final data: 30Multiple readers access the data simultaneously (active readers: 3), while the writer gets exclusive access only after all readers exit. The active readers count printed in the output confirms true read parallelism.
Where This Shows Up
| System | Readers | Writers | Preferred Variant |
|---|---|---|---|
| Database (OLTP) | SELECT queries | INSERT/UPDATE/DELETE | Writer preference (data freshness matters) |
| DNS Cache | Thousands of lookups per second | Periodic cache refresh | Reader preference (reads vastly outnumber writes) |
| Configuration File | Hundreds of threads reading config | Admin pushing a config update | Writer preference (stale config is dangerous) |
| In-Memory Cache | Application threads reading cached data | Background thread refreshing entries | Reader preference (cache hits should be fast) |
| File System Metadata | Programs listing directories | File create/delete operations | Writer preference (metadata integrity is critical) |
The Reader Writer Problem is one of the most practically relevant synchronization problems because the read-vs-write distinction exists in nearly every shared resource. A naive mutex forces readers to take turns even though they could safely run in parallel. The reader-writer solution unlocks that parallelism, and choosing the right priority variant ensures neither readers nor writers are starved for your specific workload.
Sort the Concepts
Classify each scenario based on whether Reader Preference or Writer Preference is the better fit.