Reader-Writer Locks and the Starvation They Invite

The premise of a reader-writer lock is that readers do not conflict with each other. A structure that is read far more often than it is written should not serialize the reads, so the lock admits any number of concurrent holders in shared mode and exactly one in exclusive mode. The premise is sound, and the implementation is a counting problem: the lock must know how many readers are inside before it can admit a writer. Everything difficult about the primitive follows from how that count is kept and from what happens when readers keep arriving.

One word holding two kinds of state

The compact encoding puts the reader count and the writer state in a single machine word so that transitions are a single atomic operation. A common arrangement reserves the sign bit for “a writer holds the lock” and the remaining bits for the number of readers. Acquiring in shared mode is then a compare-and-swap loop that increments the low field only if the sign bit is clear; acquiring exclusively is a compare-and-swap that sets the sign bit only if the whole word is zero.

#include <stdatomic.h>

#define WRITER_BIT 0x80000000u

static atomic_uint rw;

static void rd_lock(void)
{
    unsigned v = atomic_load_explicit(&rw, memory_order_relaxed);
    for (;;) {
        if (v & WRITER_BIT) {               /* a writer holds the lock */
            v = atomic_load_explicit(&rw, memory_order_relaxed);
            continue;
        }
        if (atomic_compare_exchange_weak_explicit(&rw, &v, v + 1,
                memory_order_acquire, memory_order_relaxed))
            return;
        /* on failure v holds the current word; retry with that value */
    }
}

static void rd_unlock(void)
{
    /* Release: the decrement must not precede the reads it protects. */
    atomic_fetch_sub_explicit(&rw, 1, memory_order_release);
}

static void wr_lock(void)
{
    unsigned expected = 0;
    while (!atomic_compare_exchange_weak_explicit(&rw, &expected, WRITER_BIT,
            memory_order_acquire, memory_order_relaxed))
        expected = 0;                       /* succeeds only from a zero count */
}

static void wr_unlock(void)
{
    atomic_store_explicit(&rw, 0, memory_order_release);
}

The encoding has a hard ceiling: with 31 usable bits, the lock admits just over two billion simultaneous readers, which is not a practical limit, but the same layout on a 16-bit counter field would cap at 32,767. Linux’s rwlock_t takes 30 bits for the reader count and gives the two remaining bits to a writer state, which lets a writer be queued rather than merely present. Some implementations widen the counter to a separate word and accept that the two states are not updated together, which reintroduces the ordering problem the single word avoided.

The cost that does not appear in the encoding is coherence traffic. Every reader acquisition writes the word, and every release writes it again, so a read-mostly workload where readers come and go continuously keeps the line in motion. On a machine with many cores the read lock can be more expensive than a plain mutex when the critical section is short, because the mutex at least has the property that only one core touches the line at a time. This is the counterintuitive result that makes rwlocks a poor default: they pay off when reads are long or when the read side is genuinely concurrent and mostly quiescent, not when the read critical section is a few loads.

A refinement used in some implementations is per-CPU or per-node reader counts, so that each core increments a counter it owns and the writer sums them. The write side then pays a cost proportional to the number of cores, which is acceptable if writes are rare, and the readers stop contending on one line. The design trades a fixed write-side cost for the removal of the read-side hot spot.

The starvation that read-preference creates

The naive policy is: a reader may enter whenever no writer holds the lock. A writer waits until the reader count reaches zero. That policy is read-preferring, and it has an unbounded failure mode. If readers arrive faster than a writer can be admitted, the count never reaches zero and the writer waits forever. Each individual reader behaves correctly; the system as a whole does not. The pattern needs only a steady arrival rate, not a malicious one: a server with a few worker threads polling a shared configuration will keep the count above zero indefinitely.

The same failure appears in the opposite direction with a writer-preferring policy, where a new reader is blocked as soon as a writer is waiting. A stream of writers then starves readers, and because writers exclude each other, the starvation is worse: a reader can wait behind an unbounded sequence of exclusive sections.

Neither policy is wrong in isolation; each is a statement about which side is expected to be rarer. The defect is choosing one without knowing the arrival distribution. A phase-fair design removes the choice by making admission depend on the phase of the lock rather than on the identity of the requester, alternating between a phase in which readers are admitted and a phase in which a single writer is admitted, and tracking arrivals within the phase so that a batch of readers cannot extend its phase by arriving late. The bound is then on the number of arrivals in one phase, not on the total arrival rate.

POSIX does not settle the question. pthread_rwlock_rdlock and pthread_rwlock_wrlock are required to be correct, but neither the preference between readers and writers nor the order of admission is fixed by the standard, so the same program can starve a writer on one C library and not on another. A program that depends on either behaviour is depending on the implementation rather than on the standard. The only portable fairness tools are the timed variants and the non-blocking attempt, and neither guarantees order.

What the lock cannot express

Several operations that look natural are not expressible in the shared-exclusive model.

Upgrading a read lock to a write lock is not a supported operation. Two readers that both attempt the upgrade deadlock against each other, each waiting for the other’s read lock to be released, and no implementation can distinguish that case from a legitimate wait. POSIX does not provide pthread_rwlock_upgrade, and the portable pattern is to release the read lock and acquire the write lock, revalidating the data afterwards. Downgrading cannot deadlock, because the thread gives up a stronger claim before asking for a weaker one, but the two steps are not atomic and another writer may slip in between.

Recursive read locking is required but bounded. POSIX says a thread may hold multiple concurrent read locks on the same object, provided it performs the same number of unlocks, and it leaves the guaranteed maximum to the implementation: the read lock may fail once that maximum is exceeded. The counter therefore has to accommodate a value above one for a single thread, which rules out an encoding that treats “held” as a single bit. Nesting is legal; combining it with a write acquisition in the same thread is not, and the ordering hazard is the same one that makes upgrades unsafe.

Finally, the primitive has no notion of priority. A high-priority writer waits behind whatever readers are present, and the readers may themselves be blocked on something the writer holds, forming an inversion that the rwlock cannot break. The remedy lives in the mutex layer, as described in priority inversion and inheritance.

Why the reader’s decrement needs release order

A detail in the encoding decides whether the lock is correct at all. The writer’s release must be ordered before the next acquisition, but the writer is not the thread that performs the handoff: between its release and the next acquisition there may be a long run of reader increments and decrements. Those are read-modify-write operations on the same word, so the ordering travels with the word as long as each of them observes the value left by its predecessor.

What the reader’s own decrement must guarantee is narrower and easier to get wrong. It must not become visible to a waiting writer before the reader’s loads from the critical section have completed. A relaxed decrement that a compiler or a store buffer may hoist above those loads lets the writer acquire the lock and start writing while a reader is still copying the data. A release on the decrement forbids exactly that reordering: everything the reader did before the subtract must be visible to any thread that observes the subtract’s value. The writer’s acquire on the compare-and-swap from zero then completes the edge, so a writer that succeeds knows that every prior reader’s loads precede its stores. A plain relaxed subtract is safe only on a machine whose ordering is stronger than the language model requires, which is why such code passes on x86 and fails after a port. A stronger model makes the increment’s acquire redundant as well, but the release on the decrement is the part that carries correctness, and it is the part most often left out. The ordering rules themselves are covered in acquire and release ordering.

A writer’s release is simpler: it clears the whole word with release semantics, and the next reader or writer acquires it. But the writer must also ensure that no reader is still inside before it begins. The compare-and-swap from zero to the writer bit is both the test and the claim, so a writer that observes zero knows that every prior reader has decremented, and the acquire on that operation orders the readers’ loads before the writer’s stores.

Alternatives that avoid the trade

The starvation question exists because the lock must decide who goes next among conflicting requests. Designs that avoid the decision by removing the conflict tend to be better than designs that arbitrate it well.

A sequence lock lets readers proceed without registering at all: they read a version counter, copy the data, and check the counter again, retrying if it changed. No reader ever blocks a writer, so writer starvation is impossible by construction, and the cost moves to the reader in the form of retries. This is the subject of seqlocks and optimistic readers.

Read-copy-update goes further and lets readers run concurrently with a writer that replaces the published version, by having the writer build a new copy, publish it with a single pointer store, and defer reclamation of the old one until every pre-existing reader has finished. Readers pay nothing at all, not even a counter increment, and the cost lands on the writer and on the reclamation machinery. The mechanism is developed in read-copy-update and grace periods.

A plain mutex is the third alternative and is often the right one. When the read critical section is a handful of instructions, the cost of a shared-exclusive lock’s bookkeeping exceeds the serialization it avoids, and the simple lock is both faster and free of the fairness question. The measurement that distinguishes the cases is the ratio of read-section duration to the coherence cost of the lock word, not the ratio of read operations to write operations, which is the number usually quoted and the wrong one.

The practical summary is that an rwlock is a bet that reads dominate and that read sections are long enough to amortize the shared counter. When the bet holds, the lock delivers concurrency that a mutex cannot. When it fails, the symptom is either a hot cache line or a writer that never runs, and both are visible only under load.