Skip to main content

Readers-Writers with Fairness

What This Concept Is​

The readers-writers problem coordinates access to a shared resource under two access modes:

  • Many readers may access the resource concurrently.
  • At most one writer may access, and only when no readers are active.

Correctness requires mutual exclusion between writers and readers, plus a fairness policy that decides who goes next. Three standard policies:

  • Reader-preferring. New readers can enter even if a writer is waiting. Simple; can starve writers forever under sustained read load.
  • Writer-preferring. Once a writer is waiting, no new reader may enter until the writer has run. Simple; can starve readers when writers continuously arrive.
  • Fair (FIFO / no-starvation). Readers and writers queue in arrival order; batches of readers may overlap if they arrive before any waiting writer. This is the policy used by most production locks (std::shared_mutex, Go's sync.RWMutex, Java's StampedLock semantics).

Pick a policy consciously; do not discover it from behavior.

Why It Matters Here​

Readers-writers locks are the standard answer for read-heavy shared data: configuration, DNS caches, routing tables, in-memory indexes. Using a plain mutex on read-heavy state discards most of the parallelism available; using a readers-writers lock without thinking about fairness can introduce starvation under production load.

This is also the first concurrency problem in the module where the specification includes a fairness property beyond safety and liveness.

Concrete Example​

Reader-preferring readers-writer lock:

typedef struct {
    pthread_mutex_t m;
    pthread_cond_t  ok_to_read, ok_to_write;
    int active_readers;
    int active_writers;     // 0 or 1
} rwlock_t;

void read_lock(rwlock_t *rw) {
    pthread_mutex_lock(&rw->m);
    while (rw->active_writers > 0) pthread_cond_wait(&rw->ok_to_read, &rw->m);
    rw->active_readers++;
    pthread_mutex_unlock(&rw->m);
}
void read_unlock(rwlock_t *rw) {
    pthread_mutex_lock(&rw->m);
    if (--rw->active_readers == 0) pthread_cond_signal(&rw->ok_to_write);
    pthread_mutex_unlock(&rw->m);
}
void write_lock(rwlock_t *rw) {
    pthread_mutex_lock(&rw->m);
    while (rw->active_readers > 0 || rw->active_writers > 0)
        pthread_cond_wait(&rw->ok_to_write, &rw->m);
    rw->active_writers = 1;
    pthread_mutex_unlock(&rw->m);
}
void write_unlock(rwlock_t *rw) {
    pthread_mutex_lock(&rw->m);
    rw->active_writers = 0;
    pthread_cond_broadcast(&rw->ok_to_read);   // let waiting readers through
    pthread_cond_signal(&rw->ok_to_write);
    pthread_mutex_unlock(&rw->m);
}

This starves writers: new readers skip past a waiting writer as long as at least one reader keeps reading.

Writer-preferring fix: add waiting_writers counter and a rule that new readers block if active_writers + waiting_writers > 0. Now readers can starve.

Fair fix: add a FIFO queue of waiters with types (reader/writer). New readers enter only if they are at the head of the queue or adjacent to another reader at the head. No starvation; more code.

Common Confusion / Misconception​

"A readers-writers lock is strictly better than a mutex for read-heavy data." Only if the read critical section is large enough to outweigh the bookkeeping. For sub-microsecond reads, a plain mutex often beats a fancy rwlock. Under mixed workloads where most operations actually need write access, a mutex is strictly better.

"Reader-preferring is simpler, so it is usually correct for my case." It is correct in the sense of no data race, but on busy servers sustained read load will freeze writers forever. Config updates will not deploy; GC-style maintenance writers will not run. This is a real production failure mode.

"std::shared_mutex has deterministic fairness." The C++ standard does not guarantee a specific policy. Different implementations differ. If you need a specific policy, build it.

How To Use It​

When choosing a readers-writers strategy:

  1. Measure the read:write ratio. If writes are more than ~20%, use a plain mutex.
  2. Estimate the read critical-section length. Under 100 ns, a plain mutex usually wins.
  3. If a readers-writers lock fits, pick a fairness policy deliberately:
    • read-bursty, rare writes -> writer-preferring
    • writer-bursty, rare reads -> mutex (writes dominate anyway)
    • balanced, no acceptable starvation -> fair / FIFO
  4. Document the policy in the lock's name: RWLockWriterPriority, RWLockFIFO.

Check Yourself​

  1. Why does reader-preferring starve writers?
  2. Why do you need a broadcast when a writer releases the lock?
  3. When is a plain mutex faster than an rwlock even on read-heavy workloads?

Mini Drill or Application​

Implement a reader-preferring rwlock in C + pthreads. Run 10 readers and 1 writer on a shared counter: each reader sleeps 10 ms inside the read section, the writer sleeps 5 ms inside the write section. Measure how long the writer waits. Then convert to writer-preferring and compare.

Read This Only If Stuck​