Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 66 ยท Synchronization

The Readers-Writers Problem

Allow many readers or one writer at a time. Build the readers-preference and writer-friendly semaphore solutions and measure writer starvation in Python.

A shared database table, a cache, a configuration file: many threads only read it, a few write it. Reading does not change anything, so any number of readers can safely work at the same time. A writer, on the other hand, must be alone: if it modifies data while a reader looks at it, the reader sees a half-finished update.

The rules of the readers-writers problem:

  1. Many readers may be inside at the same time.
  2. A writer needs exclusive access: no readers and no other writers.

A plain mutex would be correct but wasteful, because it would make readers wait for each other. Real systems use this pattern everywhere: Linux rwlock, Java ReentrantReadWriteLock, database lock modes (shared and exclusive locks).

First solution: readers have preference

The trick: readers share a counter read_count, protected by a small mutex. The first reader to arrive locks the writers out; the last reader to leave lets them back in.

TEXT
semaphores:  mutex = 1   (protects read_count)
             wrt   = 1   (exclusive access to the data)
shared:      read_count = 0

reader:                          writer:
    wait(mutex)                      wait(wrt)
    read_count += 1                  ... write ...
    if read_count == 1:              signal(wrt)
        wait(wrt)      # first in locks writers out
    signal(mutex)
    ... read ...
    wait(mutex)
    read_count -= 1
    if read_count == 0:
        signal(wrt)    # last out lets writers in
    signal(mutex)
stateDiagram-v2
    [*] --> Free
    Free --> Reading: first reader arrives (takes wrt)
    Reading --> Reading: more readers join
    Reading --> Free: last reader leaves (releases wrt)
    Free --> Writing: writer arrives (takes wrt)
    Writing --> Free: writer leaves (releases wrt)

The data is Free, shared by Readers, or held by one Writer.

Run it on the mini kernel from the semaphores lesson. We watch two invariants: a writer is never in together with anyone else, and several readers really can overlap.

Python Readers-preference solution

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

No rule is broken, and several readers do overlap, so the lock is both safe and more concurrent than a mutex.

The catch: writer starvation

The solution is called readers-preference: as long as at least one reader is inside, new readers walk straight in. If readers keep arriving in a steady stream, read_count never drops to zero, wrt is never released, and a waiting writer starves.

The fix is writer-friendly (or fair) logic: once a writer is waiting, no new reader may enter until that writer has had its turn. A common version adds a turnstile semaphore that every reader and writer must pass through briefly:

TEXT
reader:  wait(turnstile); signal(turnstile); ...same as before...
writer:  wait(turnstile)            # blocks new readers while we wait
         wait(wrt)
         ... write ...
         signal(turnstile); signal(wrt)

Let us measure the difference. Four readers read again and again; one writer wants in once. We report the simulation "tick" at which the writer got to write.

Python Does the writer ever get in?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With readers-preference the writer gets in after about 18% of the run on average (it has to wait for a moment when no reader happens to be inside); with the turnstile, after about 3%, as soon as the readers already inside leave. A random scheduler is gentle on writers; with a steady stream of overlapping readers in a real system the gap is much worse. The price of fairness: readers now sometimes wait for a writer.

Third variant and real locks

A third variant gives writers strict priority; it then can starve readers instead. Because every choice favours someone, production locks pick a policy and document it, or use ticket/queue ordering so requests are served in arrival order. Some also offer upgrade (turning a read lock into a write lock), which is easy to get wrong because two readers upgrading at the same time deadlock.

Use a reader-writer lock when reads are much more frequent than writes and a read takes a while. If critical sections are tiny, the bookkeeping costs more than a plain mutex.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Who takes the wrt semaphore in the readers-preference solution?

    The first reader locks writers out for the whole group of readers; each writer takes wrt for itself.
  2. 2. What is the purpose of the mutex semaphore in the reader code?

    read_count is shared among readers, so incrementing and decrementing it needs its own protection.
  3. 3. What problem does readers-preference suffer from?

    As long as the reader count never reaches zero, wrt is never released and the writer never runs.
  4. 4. How does the turnstile fix help the writer?

    A waiting writer holds the turnstile, so new readers queue behind it while the readers already inside finish.

Summary

  • Readers may share access; a writer needs exclusive access.
  • The classic solution counts readers: the first locks writers out, the last lets them in.
  • Readers-preference can starve writers; a turnstile (or arrival-order queue) makes the lock fair at some cost to read throughput.
  • Real reader-writer locks choose a policy; upgrading read locks to write locks is a deadlock risk.

Next: Dining Philosophers and the Sleeping Barber