Readers-Writers Problem

Introduction

The Readers-Writers Problem is a synchronization problem where two kinds of threads access the same shared data. Readers only observe the data, while writers modify it.

The goal is to improve concurrency without breaking correctness. Many readers should be allowed to read together, but a writer must get exclusive access while writing.

Core Idea

Access rules depend on whether a thread is reading or writing.

• Readers: They only read shared data, so multiple readers can safely read at the same time.

• Writers: They modify shared data, so a writer needs exclusive access.

• Reader with writer: A reader should not read while a writer is updating the data.

• Writer with readers: A writer should wait while readers are actively reading.

Why This Problem Matters

The Readers-Writers Problem appears when many operations only inspect data, while fewer operations update it. In such cases, using one ordinary mutex for everything may be correct but too restrictive.

This pattern appears in:

• Databases: Many queries read records, while updates need exclusive access.

• Caches: Many requests read cached values, while refreshes modify entries.

• Configuration stores: Services read settings, while administrators update them.

• File systems: Metadata may be read often and updated carefully.

• In-memory indexes: Many lookups happen, while structural changes are less frequent.

The pattern is most useful when reads are much more common than writes.

Reader-Preference Solution

A common version is the reader-preference solution. It allows readers to keep joining while readers are already active, and writers wait until all active readers finish.

This solution uses three shared elements:

• readcount: Counts active readers

• mutex: Protects updates to readcount

• wrt: Controls access to the shared data

mutex protects the count. wrt protects the shared data.

Reader Flow

The reader logic has two important moments: the first reader entering and the last reader leaving.

The first reader calls wait(wrt) to block writers. After that, more readers can join without taking wrt again.

When readers leave, only the last reader calls signal(wrt). That releases the shared data so a waiting writer can proceed.

Writer Flow

The writer logic is simpler because a writer needs exclusive access.

wait(wrt)

write shared data

signal(wrt)

When a writer holds wrt, no other writer should write and no reader should read. This keeps the shared data from being observed during an update.

How the Logic Works

When the first reader arrives, it changes readcount from 0 to 1 and takes wrt. This blocks writers while the reader group is active.

Later readers only update readcount and start reading. They do not need to wait on wrt because the reader group already controls access.

When readers finish, each one decreases readcount. If a reader is not the last one, it does not release wrt. The last reader decreases readcount to 0 and signals wrt, allowing a writer to enter.

This is why readcount must be protected by mutex. Without that protection, two readers could update the count incorrectly.

Starvation and Fairness

Reader preference improves read concurrency, but it can create writer starvation. If new readers keep arriving while readers are already active, a waiting writer may be delayed again and again.

Different versions of the Readers-Writers Problem handle fairness differently:

So this problem is not only about correctness. It is also about the tradeoff between throughput and fairness.

When It Helps

Readers-writers synchronization helps when reads dominate writes. If most operations are reads, allowing many readers together can improve concurrency.

It may not help much when writes are frequent. Since writers need exclusive access, many writes reduce the benefit of shared reading.

Summary

The Readers-Writers Problem controls access to shared data when some threads only read and others write. Readers can share access, but writers need exclusive access.

In the reader-preference semaphore solution, readcount tracks active readers, mutex protects readcount, and wrt protects the shared data. The main caution is fairness: reader preference can improve throughput, but continuous readers may starve writers.