Reader–Writer Problem and Semaphore-Based Process Synchronization

Verified Sources

Sep 11, 2026

The Reader–Writer problem is a classic process synchronization problem in operating systems. It occurs when multiple processes or threads share a data object—such as a file, database record, buffer, or in-memory structure—and some processes only read while others modify it.

The central requirement is:

Multiple readers may access the shared resource simultaneously.
A writer must obtain exclusive access.
Readers must not access the resource while a writer is modifying it.
The synchronization policy should minimize starvation and preserve data consistency.

A reader–writer lock therefore provides two modes of access: concurrent read access or exclusive write access.

Readers–writer lock - Overview of concurrent reader access, exclusive writer access, and preference-related starvation. ↩

Core Principle

Readers can share the resource with other readers, but a writer must be alone. The synchronization mechanism must protect both the resource and the bookkeeping data used to count active readers.

1. Why the Problem Exists

Suppose several processes access a shared file:

Readers inspect its contents without changing them.
Writers update its contents.
Several readers can safely inspect the same stable version at once.
A writer changing the file while a reader is reading may expose incomplete or inconsistent data.
Two writers modifying the file concurrently may overwrite one another or corrupt its state.

Without synchronization, the following race condition may occur:

Writer A reads the old value.
Writer B reads the same old value.
Writer A writes an update.
Writer B writes its update based on stale data.
Writer A’s update is lost.

The problem is not that concurrency is always unsafe. Rather, the permitted concurrency depends on the operation:

Access combination	Safe?	Reason
Reader + reader	Yes	Neither operation modifies the resource
Reader + writer	No	The reader may observe partial or inconsistent state
Writer + writer	No	Concurrent modifications can conflict
One writer alone	Yes	Exclusive modification preserves consistency

A simple mutex would ensure correctness by allowing only one process at a time, but it would unnecessarily serialize readers. The reader–writer solution increases concurrency by allowing a group of readers to enter together.

ReaderWriterLock Class - Microsoft documentation describing concurrent reads and exclusive writes. ↩

2. Semaphore Fundamentals

A semaphore is a synchronization primitive manipulated through two atomic operations:

wait(S)—also called P, down, or acquire
signal(S)—also called V, up, or release

Conceptually:

wait(S): \begin{cases} S \leftarrow S-1 & \text{if access is available}\\ \text{block the caller} & \text{otherwise} \end{cases}

signal(S): \begin{cases} S \leftarrow S+1\\ \text{wake a waiting process, if one exists} \end{cases}

The operations must be atomic: no other process may observe or interrupt the semaphore update halfway through. A semaphore initialized to $1$ is commonly used as a binary semaphore, while a semaphore initialized to a larger value can represent multiple permits.

For the reader–writer problem, two binary semaphores are sufficient for the classic reader-preference solution:

Semaphore or variable	Initial value	Purpose
`mutex`	$1$	Protects updates to `readCount`
`wrt`	$1$	Controls access to the shared resource
`readCount`	$0$	Counts active readers

wrt acts as a gate:

A writer must execute wait(wrt) before writing.
The first reader executes wait(wrt) and blocks writers.
The last reader executes signal(wrt) and allows a writer to proceed.

Semaphores in Process Synchronization - Description of semaphore wait and signal operations and their synchronization role. ↩

3. Reader-Preference Semaphore Solution

The classic solution gives priority to readers already arriving or entering. It uses mutex to protect the reader counter and wrt to protect the shared resource.

Reader logic

A reader performs these actions:

Acquire mutex.
Increment readCount.
If it is the first reader, acquire wrt.
Release mutex.
Read the shared resource.
Acquire mutex again.
Decrement readCount.
If it is the last reader, release wrt.
Release mutex.

Writer logic

A writer:

Acquires wrt.
Writes the shared resource exclusively.
Releases wrt.

The key insight is that only the first reader blocks writers and only the last reader releases them. Readers arriving while another reader is active can join the current reader group.

Readers-Writers Problem - Reader-preference algorithm using mutex, wrt, and readCount. ↩

Reader-Preference Semaphore Algorithm

1
Step 1
Set mutex = 1, wrt = 1, and readCount = 0. The first semaphore protects the counter, while the second protects the shared resource.
2
Step 2
The reader executes wait(mutex) before modifying readCount. This prevents two readers from changing the counter simultaneously.
3
Step 3
After incrementing the counter, the reader checks whether readCount == 1. If so, it executes wait(wrt), preventing writers from entering.
4
Step 4
The reader executes signal(mutex). Other readers may now update the counter, and all active readers may access the resource.
5
Step 5
The reader reads the shared data while writers remain excluded. Other readers may read concurrently.
6
Step 6
The reader executes wait(mutex), decrements readCount, and checks whether it is the final active reader.
7
Step 7
If readCount == 0, the last reader executes signal(wrt). A waiting writer can now acquire the resource.
8
Step 8
A writer executes wait(wrt), modifies the shared data without readers or other writers, and finally executes signal(wrt).

semaphore mutex = 1;
semaphore wrt = 1;
integer readCount = 0;

Reader:
while true:
    wait(mutex);
    readCount = readCount + 1;

    if readCount == 1:
        wait(wrt);

    signal(mutex);

    read_shared_resource();

    wait(mutex);
    readCount = readCount - 1;

    if readCount == 0:
        signal(wrt);

    signal(mutex);

Writer:
while true:
    wait(wrt);

    write_shared_resource();

    signal(wrt);

4. Why Each Semaphore Is Necessary

`mutex`: protects the reader count

readCount is shared bookkeeping state. If two readers increment or decrement it simultaneously without protection, updates may be lost.

For example, if readCount is $1$ and two readers increment it concurrently, both may read $1$ , both calculate $2$ , and both store $2$ . The correct result should be $3$ .

Thus, the update must be a critical section:

wait(mutex) \rightarrow \text{update } readCount \rightarrow signal(mutex)

`wrt`: protects the shared resource

The wrt semaphore ensures that:

At most one writer accesses the resource.
No writer accesses the resource while any reader is active.
The first reader prevents writers from entering.
The last reader permits writers to enter again.

`readCount`: represents the reader group

The counter determines whether a reader is entering or leaving a reader group:

Transition $0 \rightarrow 1$ : first reader blocks writers.
Transition $1 \rightarrow 2$ , $2 \rightarrow 3$ , and so on: additional readers join.
Transition $1 \rightarrow 0$ : last reader releases writers.

This design separates protection of the counter from protection of the resource. That separation is what permits multiple readers to operate concurrently.

Semaphores - Operating-systems lecture material presenting a semaphore-based reader–writer lock. ↩

Access Concurrency by Synchronization Policy

Conceptual maximum concurrency, assuming several readers are available

5. Correctness Properties

A correct semaphore solution should satisfy the following properties.

Mutual exclusion for writers

Two writers must never write simultaneously:

\#writers \leq 1

Because every writer must hold wrt, only one writer can pass the semaphore at a time.

No reader–writer overlap

A writer cannot enter while readCount > 0, because the first active reader holds wrt.

Conversely, once a writer holds wrt, a new reader cannot become the first reader and acquire it. Therefore:

(\#readers > 0) \Rightarrow (\#writers = 0)

and

(\#writers = 1) \Rightarrow (\#readers = 0)

Concurrent readers

Readers after the first do not acquire wrt. They only briefly acquire mutex to update the counter, so they can read the resource concurrently.

Atomic counter transitions

The mutex semaphore ensures that the transitions of readCount are serialized. Consequently, exactly one reader is recognized as the first reader and exactly one as the last reader.

Important Limitation: Writer Starvation

The reader-preference algorithm may starve writers. If readers continuously arrive, the reader count may never reach zero, so a waiting writer may remain blocked indefinitely.

6. Starvation, Fairness, and Alternative Variants

The classic solution is correct for mutual exclusion but does not guarantee fairness.

Reader-preference solution

New readers may enter while a writer is waiting, provided that at least one reader is already active. This maximizes read concurrency but can starve writers.

Writer-preference solution

A writer-preference design prevents new readers from entering once a writer is waiting. Existing readers finish, then the waiting writer proceeds. This avoids writer starvation but can delay readers when writers arrive frequently.

A common semaphore design introduces additional synchronization objects such as:

readTry: prevents readers from bypassing queued writers.
resource: controls the shared resource.
rmutex: protects the reader count.
wmutex: protects the writer count.
readCount and writeCount: track active or waiting participants.

Fair or FIFO solution

A fair solution uses a turnstile or queue so readers and writers are served in arrival order. This reduces starvation but may reduce throughput because readers that could safely run together may be separated by queued writers.

Policy	Main advantage	Main risk
Reader preference	High read throughput	Writers may starve
Writer preference	Writers obtain timely access	Readers may wait longer
Fair/FIFO	Bounded waiting and predictable behavior	More overhead and less batching
Simple mutex	Easy to reason about	Eliminates read concurrency

A practical reader–writer lock should therefore be selected based on workload, fairness requirements, and the cost of blocking.

Readers–writer lock - Explanation of writer starvation under read-preferring policies and the trade-off with write preference. ↩
Readers–writer lock - Overview of concurrent reader access, exclusive writer access, and preference-related starvation. ↩

Tracing a Typical Execution

1
Step 1
mutex = 1, wrt = 1, and readCount = 0. No process is using the resource.
2
Step 2
Reader A acquires mutex, changes readCount to 1, acquires wrt, and releases mutex. Writers are now blocked.
3
Step 3
Reader B acquires mutex, changes readCount to 2, and releases mutex. It does not acquire wrt, because Reader A already blocks writers.
4
Step 4
Writer C executes wait(wrt) and blocks because the reader group holds wrt.
5
Step 5
Reader A decrements readCount from 2 to 1. It does not release wrt because Reader B is still active.
6
Step 6
Reader B decrements readCount from 1 to 0 and releases wrt. The writer may now proceed.
7
Step 7
Writer C acquires wrt, performs its update exclusively, and releases wrt when finished.

Common Questions and Edge Cases

7. Common Errors in Semaphore Implementations

Updating readCount without mutex
This creates a race condition in the counter itself.
Acquiring wrt for every reader
This converts the solution into a one-reader-at-a-time lock and removes the main benefit of the pattern.
Releasing wrt when any reader exits
A writer could enter while other readers remain active.
Holding mutex while performing the actual read
This prevents other readers from updating the counter and unnecessarily reduces concurrency.
Forgetting a matching signal operation
Every successful acquisition must eventually be released along every normal control-flow path.
Changing semaphore order inconsistently
If different code paths acquire synchronization objects in incompatible orders, deadlock may occur.
Assuming reader preference means fairness
Correctness and fairness are separate properties. A solution may preserve data integrity while still starving writers.

Implementation Checklist

Protect readCount with mutex; let only the first reader acquire wrt; let only the last reader release it; keep actual I/O outside mutex; and choose a fairer policy when writers must have bounded waiting.

8. Applications

The reader–writer pattern appears wherever reads are frequent and modifications are less frequent:

In-memory caches
File-system metadata
Configuration objects
Symbol tables
Routing tables
Database records
Operating-system data structures
Shared lookup tables
Web-server state

For example, a configuration object may be read by many request-handling threads while an administrative thread occasionally updates it. Allowing all request threads to read concurrently improves throughput, while exclusive updates preserve consistency.

Modern libraries often provide a dedicated reader–writer lock rather than requiring programmers to implement semaphores manually. Such locks commonly allow concurrent read access and exclusive write access, and some provide separate queues or fairness policies.

ReaderWriterLock Class - Documentation of reader and writer queues and exclusive writer access. ↩

Evolution of the Synchronization Strategy

Unprotected shared access

Stage 1

Readers and writers access the resource without coordination, creating race conditions and possible corruption."

Single mutex

Stage 2

One process enters at a time. Correctness improves, but concurrent readers are unnecessarily serialized."

Reader-preference semaphores

Stage 3

A reader counter and resource semaphore allow multiple readers while excluding writers."

Writer-preference policy

Stage 4

Waiting writers prevent new readers from entering, reducing the risk of writer starvation."

Fair reader–writer lock

Stage 5

A queue or turnstile balances throughput with bounded waiting for both categories."

Reader–Writer Problem Review

1 / 7

Question · Term

What is the Reader–Writer problem?

Click to reveal

Answer · Definition

A synchronization problem involving shared data accessed by multiple readers and writers, where readers may share access but writers require exclusivity.

Knowledge Check

Question 1 of 5

Q1Single choice

Which access pattern is permitted by a correct reader–writer solution?

Multiple readers concurrently, but only one writer with no readers

Multiple writers concurrently, but only one reader

A reader and writer concurrently on the same resource

Readers and writers must always execute one at a time

References

Explore Related Topics

CPU Scheduling Case Study: FCFS vs SJF for a Five-Process Workload

The case study compares FCFS and non‑preemptive SJF scheduling for five processes that all arrive at time 0, showing their Gantt charts, individual waiting times, and average waiting times.

FCFS order A → B → C → D → E; waiting times 0, 10, 11, 13, 14 ms; average  $9.6$  ms.
SJF order B → D → C → E → A (ties broken by arrival order); waiting times 0, 1, 2, 4, 9 ms; average  $3.2$  ms.
With simultaneous arrivals, each process’s waiting time equals the sum of burst times of all jobs scheduled before it.
Non‑preemptive SJF is optimal for minimizing average waiting time when burst lengths are known.
The priority column is irrelevant for this comparison.

Compiler vs Interpreter and the Components of a Language Processing System

Compilers translate an entire program into target code before execution, while interpreters translate and run code incrementally; both are parts of a broader language‑processing system that includes preprocessing, assembly, linking, and loading.

Compiled programs run faster but generate platform‑specific binaries; interpreted programs give immediate feedback and are more portable.
The language‑processing pipeline: preprocessor → compiler (lexical, syntax, semantic analysis → intermediate code → optimization → code generation) → assembler → object code → linker → loader → execution.
Key compiler components: symbol table and error handler, which are used across all phases.
Modern runtimes often blend compilation and interpretation, using intermediate representations and JIT execution.
For exams, first compare compiler vs. interpreter, then describe the full translation workflow.

Understanding Belady's Anomaly in Operating Systems

Belady's Anomaly shows that, for some page‑replacement policies, adding more physical frames can increase the number of page faults.

FIFO (a non‑stack algorithm) does not satisfy the inclusion property and can exhibit the anomaly.
On the reference string  $1,2,3,4,1,2,5,1,2,3,4,5$ , FIFO yields $9$ faults with $3$ frames but $10$ faults with $4$ frames.
Stack algorithms such as LRU or Optimal obey $M(N,t)\subseteq M(N+1,t)$ , guaranteeing that more frames never raise fault counts.
Designing a virtual‑memory system with stack‑based replacement eliminates Belady's Anomaly.

Browse all research articles

Reader–Writer Problem and Semaphore-Based Process Synchronization

Footnotes

Core Principle

1. Why the Problem Exists

Footnotes

2. Semaphore Fundamentals

Footnotes

3. Reader-Preference Semaphore Solution

Reader logic

Writer logic

Footnotes

Reader-Preference Semaphore Algorithm

4. Why Each Semaphore Is Necessary

mutex: protects the reader count

wrt: protects the shared resource

readCount: represents the reader group

Footnotes

Access Concurrency by Synchronization Policy

5. Correctness Properties

Mutual exclusion for writers

No reader–writer overlap

Concurrent readers

Atomic counter transitions

Important Limitation: Writer Starvation

6. Starvation, Fairness, and Alternative Variants

Reader-preference solution

Writer-preference solution

Fair or FIFO solution

Footnotes

Tracing a Typical Execution

Common Questions and Edge Cases

7. Common Errors in Semaphore Implementations

Implementation Checklist

8. Applications

Footnotes

Evolution of the Synchronization Strategy

Unprotected shared access

Single mutex

Reader-preference semaphores

Writer-preference policy

Fair reader–writer lock

Reader–Writer Problem Review

What is the Reader–Writer problem?

Knowledge Check

References

Explore Related Topics

`mutex`: protects the reader count

`wrt`: protects the shared resource

`readCount`: represents the reader group