The problem

Many threads share one piece of data: a record, a cache, a routing table. Readers only look at it, writers change it. Any number of readers may use it at the same time, because reading changes nothing. A writer needs it alone: no other writer, and no reader that could see a half-written value. A plain mutex would be correct but wasteful, since it would also make readers take turns. The readers–writers problem (Courtois, Heymans and Parnas, 1971) asks for a lock that lets readers share and gives writers exclusive access, and every solution has to decide who goes first when both kinds are waiting.

How to use the animation

Each thread runs the code under its role in an endless loop, and a coloured marker shows the line it will run next. Every step runs exactly one line, atomically; any thread may run between two steps. Step threads by hand to build an interleaving, or let the scheduler choose. A blocked thread moves into the queue of the semaphore it waits on. The SHARED DATA box holds what all threads share: the counters and the record itself. A writer stores a new value such as "W1#2" (W1's second write) there, and a reader carries a copy of it back to its thread box. The chips next to the record show who is using it right now. The timeline at the bottom has one column per step: green while a reader is inside, orange while a writer is inside, red while a thread is blocked. The number after each thread's name is how long it has been waiting to get in, or the longest wait so far. The check above the timeline turns red if a writer is ever inside together with anyone else.

1. Readers-preference

int read_count = 0;
semaphore mutex = 1;      // protects read_count
semaphore rw_mutex = 1;   // the record: held by one writer, or by the readers as a group

reader:                                   writer:
    wait(mutex)                               wait(rw_mutex)
    read_count++                              write the record
    if (read_count == 1) wait(rw_mutex)       signal(rw_mutex)
    signal(mutex)
    read the record
    wait(mutex)
    read_count--
    if (read_count == 0) signal(rw_mutex)
    signal(mutex)

The first reader to arrive locks rw_mutex on behalf of all readers, and the last one to leave unlocks it; readers in between only update read_count. So rw_mutex is taken by one thread and released by another, which a semaphore allows but most mutex implementations do not. If a writer holds the record, the first reader blocks on rw_mutex while holding mutex, so later readers queue on mutex behind it. That is harmless, because they could not enter anyway.

The weakness: as long as a new reader arrives before the last one leaves, read_count never drops to 0 and a waiting writer never gets in. This is writer starvation. See Readers-preference tab, Demo: writer starves, where W1's row stays red for the whole run.

Step chart of read_count over time under readers-preference. The first reader takes rw_mutex when read_count goes from 0 to 1; reads by R1, R2, R3, R1 and R2 overlap so the count moves between 1 and 2 and never drops to 0 until the last reader leaves and signals rw_mutex. W1 is blocked on rw_mutex the whole time and writes only at the very end.
The first reader in locks rw_mutex for the whole group and the last one out unlocks it, so overlapping readers keep W1 waiting.

2. Writers-preference

reader:                                   writer:
    wait(read_try)                            wait(wmutex)
    wait(rmutex)                              write_count++
    read_count++                              if (write_count == 1) wait(read_try)
    if (read_count == 1) wait(resource)       signal(wmutex)
    signal(rmutex)                            wait(resource)
    signal(read_try)                          write the record
    read the record                           signal(resource)
    wait(rmutex)                              wait(wmutex)
    read_count--                              write_count--
    if (read_count == 0) signal(resource)     if (write_count == 0) signal(read_try)
    signal(rmutex)                            signal(wmutex)

Every reader must pass read_try briefly on its way in. The first writer that arrives takes read_try and keeps it until the last waiting writer is done, so once a writer is waiting no new reader can start. Readers already inside finish, then the writers go one by one through resource. Now the starvation is the other way round: a steady stream of writers keeps write_count above 0 and readers wait forever. See Writers-preference tab, Demo: readers wait.

3. A fair solution

semaphore queue = 1;      // the turnstile: everyone passes it in arrival order

reader:                                   writer:
    wait(queue)                               wait(queue)
    wait(mutex)                               wait(rw_mutex)
    read_count++                              signal(queue)
    if (read_count == 1) wait(rw_mutex)       write the record
    signal(queue)                             signal(rw_mutex)
    signal(mutex)
    read the record
    ... leave as in version 1 ...

Every thread first passes a FIFO turnstile. A writer that is waiting for the record holds the turnstile, so readers who arrive after it queue behind it instead of joining the readers inside. Threads are admitted in arrival order: consecutive readers still share the record, and nobody starves as long as the semaphore queues are FIFO. See Fair tab, Demo: arrival order and Demo: no starvation, which is the starvation schedule of version 1 on the fair version.

Why read_count needs its own mutex

read_count++ looks like one operation, but the processor loads the value, adds one and stores it back. The Bug version shows it as two lines, tmp = read_count and read_count = tmp + 1, without a mutex around them. In Bug: read_count without mutex tab, Demo: writer gets in, R2 loads read_count = 1 and is preempted; R1 leaves as the "last" reader and releases rw_mutex; R2 then stores 2 and, because the count is not 1, skips wait(rw_mutex). A writer finds rw_mutex free and enters while R2 is reading. The same race could leave read_count one too high, and then rw_mutex is never released: every writer blocks forever.

The three versions side by side

Readers-preferenceWriters-preferenceFair
A reader arrives while readers are inside and a writer waitsenters at oncewaits for the writerwaits for the writer
Who can starvewritersreadersnobody (FIFO queues)
Reader throughputhighestlowestin between
Freshness of what readers seemay be old for a long timeupdates land quicklyin arrival order
R1 is reading when W1, R2 and W2 arrive in that order. Readers-preference: R2 joins R1 at once, then W1, then W2; writers can starve. Writers-preference: R1, then W1, then W2, then R2; readers can starve. Fair turnstile: R1, W1, R2, W2 in arrival order; nobody starves.
The same arrivals get the record in three different orders: readers-preference lets R2 jump the queue, writers-preference lets W2 jump it, the fair version keeps arrival order.

Readers–writer locks in practice

  • POSIX pthread_rwlock_t: the policy is left to the implementation. glibc prefers readers by default and offers PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP.
  • Java ReentrantReadWriteLock: new ReentrantReadWriteLock(true) is the fair (FIFO) version. The default mode is not fair, but a new reader does wait if the thread at the head of the queue is a writer, which prevents starvation in practice. StampedLock adds optimistic reads that take no lock at all.
  • Go sync.RWMutex: once a writer is waiting, new readers block, so writers are not starved. Rust std::sync::RwLock and C++ std::shared_mutex leave the policy to the platform.
  • Linux kernel: rw_semaphore for code that may sleep, rwlock_t for spinning. For data that is read very often, a seqlock lets readers go ahead and retry if a writer changed the data meanwhile, and RCU lets readers run with no lock at all while writers publish new copies.
  • Databases use shared (S) and exclusive (X) locks on rows and tables: the same idea with many locks. Engines with MVCC, such as PostgreSQL and InnoDB, sidestep the problem for plain reads: a reader sees an older version of the row and never blocks a writer. See PostgreSQL and MySQL.

A readers–writer lock is not free: it is more work than a mutex and every reader still writes to the shared read_count, so the processor's cache line bounces between cores. When the critical section is short, a plain mutex is often faster. The lock pays off when reads are long and much more frequent than writes.

See also: Bounded buffer (producer–consumer), the other classic synchronization problem. Dining philosophers puts starvation next to deadlock and livelock.