1. Introduction
The Readers–Writers Problem is one of the most important synchronization problems in Operating Systems. It models situations where multiple processes or threads access a shared data resource, but different types of access have different requirements.
The problem distinguishes between two categories of processes:
Readers → Only read data
Writers → Modify data
Since reading does not change the shared data, multiple readers can safely access the resource simultaneously. Writing, however, changes the data and therefore requires exclusive access.
The challenge is to maximize concurrency while maintaining data consistency.
This problem is fundamental because it appears in many real-world systems such as:
Database Management Systems
File Systems
Shared Memory Systems
Operating System Caches
Web Servers
Concurrent Applications
Formally:
The Readers–Writers Problem concerns coordinating concurrent access to shared data such that multiple readers may access the data simultaneously, while writers require exclusive access.
2. Core Idea
The central idea behind the Readers–Writers Problem is:
Readers → Shared Access
Writers → Exclusive Access
Unlike mutex-based synchronization:
One Process At A Time
Readers–Writers synchronization allows:
Multiple Readers Together
which improves concurrency and system performance.
The key rule is:
No Reader During Writing
No Writer During Reading
3. Conceptual Visualization
Consider a shared database.
Reader 1
\
\
Reader 2 -----> Shared Database
/
/
Reader 3
All readers can access simultaneously.
However:
Writer
↓
Shared Database
requires exclusive control.
During writing:
All Readers Blocked
and
Other Writers Blocked
4. Constraints
Any correct Readers–Writers solution must satisfy several constraints.
4.1 Multiple Readers Allowed
Several readers may access the resource simultaneously.
Example:
R1 Reading
R2 Reading
R3 Reading
This is safe because reading does not alter data.
4.2 Only One Writer Allowed
At any moment:
Maximum One Writer
may access the resource.
Example:
W1 Writing
W2 Waiting
4.3 No Reader During Writing
If a writer is active:
Readers Must Wait
to avoid inconsistent data.
4.4 No Writer During Reading
If readers are currently accessing data:
Writer Must Wait
until all readers finish.
5. Variants of the Readers–Writers Problem
Over time, several versions of the problem have been proposed depending on how access priority is assigned.
5.1 First Readers–Writers Problem (Reader Priority)
Rule
Readers are given preference.
If readers are currently active:
New Readers
Can Enter Immediately
even if a writer is waiting.
Example
Reader Active
Writer Waiting
New Reader Arrives
New Reader Allowed
Advantage
High reader throughput.
Problem
Writers may wait indefinitely.
Writer Starvation
can occur.
5.2 Second Readers–Writers Problem (Writer Priority)
Rule
Writers receive preference.
If a writer is waiting:
New Readers Blocked
until the writer executes.
Example
Writer Waiting
Reader Arrives
Reader Must Wait
Advantage
Prevents writer starvation.
Problem
Readers may starve.
Reader Starvation
can occur if writers continuously arrive.
5.3 Third Readers–Writers Problem (Fair Solution)
The objective is:
No Starvation
for either readers or writers.
Access is granted in a balanced manner.
Characteristics:
Fair scheduling
FIFO ordering
Equal treatment
This is the preferred approach in modern systems.
6. Semaphore Solution (Reader Priority)
The classical solution uses semaphores.
Initialization
int read_count = 0;
semaphore mutex = 1;
semaphore wrt = 1;
Meaning of Variables
read_count
Tracks active readers.
Number Of Readers
currently accessing data.
mutex
Protects:
read_count
from race conditions.
wrt
Controls access to shared data.
Reader Or Writer Access
Reader Code
Step-by-Step Explanation
Reader Arrives
read_count++
increments reader count.
First Reader
If:
read_count == 1
the first reader acquires:
wrt
This prevents writers from entering.
Reading
Multiple readers may now access data concurrently.
R1 Reading
R2 Reading
R3 Reading
Reader Leaves
read_count--
decrements reader count.
Last Reader
When:
read_count == 0
the last reader releases:
wrt
allowing writers to proceed.
Writer Code
wait(wrt);
/* Writing */
signal(wrt);
Step-by-Step Explanation
Writer Requests Access
wait(wrt)
If readers or another writer are active:
Writer Waits
Writing
Once acquired:
Writer Has Exclusive Access
No readers or writers can enter.
Completion
Writer releases:
signal(wrt)
allowing others to proceed.
7. Working Mechanism
The synchronization behavior can be summarized as:
Reader Access
Reader Arrives
↓
Increment Count
↓
First Reader Blocks Writers
↓
Read Data
↓
Decrement Count
↓
Last Reader Releases Writers
Writer Access
Writer Arrives
↓
Acquire wrt
↓
Write Data
↓
Release wrt
Result:
Multiple Readers Allowed
Single Writer Allowed
8. Key Insight
The most important observation is:
Readers can safely share access because they do not modify data, whereas writers require complete exclusivity because they change the shared resource.
Thus:
Readers → Concurrent
Writers → Exclusive
This principle is the foundation of Readers–Writers synchronization.
9. Problem: Starvation
While the semaphore solution works, it may suffer from starvation.
9.1 Writer Starvation
In reader-priority systems:
Reader
Reader
Reader
Reader
Reader
keep arriving continuously.
The writer waits forever.
Writer Never Executes
Example
W Waiting
R1 Arrives
R2 Arrives
R3 Arrives
R4 Arrives
...
Writer remains blocked indefinitely.
9.2 Reader Starvation
In writer-priority systems:
W1 Waiting
W2 Waiting
W3 Waiting
Readers may never receive access.
Reader Starvation
occurs.
10. Solutions to Starvation
Several techniques are used to prevent starvation.
10.1 Fair Scheduling
Requests are served in arrival order.
FIFO Access
ensures fairness.
10.2 Queue-Based Synchronization
Processes enter a waiting queue.
Example:
R1
W1
R2
W2
served sequentially.
10.3 Aging
Waiting processes gradually gain priority.
Long Wait
↓
Higher Priority
This guarantees eventual execution.
11. Readers–Writers Problem vs Read–Write Locks
| Feature | Read–Write Locks | Readers–Writers Problem |
|---|---|---|
| Nature | Practical Synchronization Tool | Theoretical Synchronization Model |
| Purpose | Actual Implementation | Conceptual Understanding |
| Supports Multiple Readers | Yes | Yes |
| Supports Exclusive Writers | Yes | Yes |
| Priority Policies | Reader, Writer, Fair | Same Variants |
| Usage | Real Systems | Teaching and Analysis |
Relationship
The Readers–Writers Problem is the theoretical foundation behind:
Read–Write Locks
used in real operating systems and databases.
12. Real-World Analogy
Consider a library.
Readers
People reading books.
Many Readers Allowed
because reading does not change the book.
Writer
An editor updating a book.
One Editor Only
because modifications change the content.
During editing:
Readers Must Wait
Once editing finishes:
Readers May Resume
This perfectly mirrors the Readers–Writers Problem.