Readers–Writers Problem

The problem

A database, a file or an in-memory table is shared by many processes. Some only read it. Others write (change) it. What must be allowed?

	Reader is inside	Writer is inside
A reader wants in	✓ yes, readers can share	✗ no, it might see half-written data
A writer wants in	✗ no, the reader might see the data change	✗ no, two writers would corrupt each other

In short: many readers at once, or one writer alone, never both. This is the idea behind the shared and exclusive locks of a database and behind the read-write locks of operating systems and programming languages.

Locking the database for everybody would be correct but wasteful: readers would take turns although they never conflict. The challenge is to allow the sharing without letting a group of readers shut the writers out forever.

Solution 1: readers first

Two semaphores and a counter:

semaphore mutex = 1      // protects readcount
semaphore wrt   = 1      // 1 = nobody inside, 0 = a writer or a group of readers is inside
int readcount   = 0      // how many readers are inside

writer:                          reader:
  wait(wrt)                        wait(mutex)
  ...write...                      readcount++
  signal(wrt)                      if readcount == 1: wait(wrt)     // first reader locks writers out
                                   signal(mutex)
                                   ...read...
                                   wait(mutex)
                                   readcount--
                                   if readcount == 0: signal(wrt)   // last reader lets writers in
                                   signal(mutex)

The readers act as one group: the first reader takes wrt for the whole group, and the last one gives it back. Any reader arriving while others are inside just bumps readcount and walks in. Watch readcount and wrt change in the 3D model.

The problem: writer starvation

A waiting writer sits in wait(wrt). As long as some reader is still inside, wrt stays 0. If a new reader arrives before the last one leaves, it simply joins. In the 3D model, R1, R2, R3 and R4 overlap one after another, so W1 waits 9 time units and W2 waits 9 even though they arrived early. With a heavy stream of readers the writers could wait forever: starvation.

Solution 2: writers first

Now give writers priority: once a writer is waiting, no new reader may enter. The readers already inside finish, the writer goes in, and then the next waiting writer, and only when no writer is waiting do the readers return.

In the model, W1 arrives at t = 1 while R1 is reading. R2 (arriving at t = 2) is now held back, R1 leaves at t = 4, W1 and then W2 write, and R2 only enters at t = 8. Writers waited just 3 units each. The cost has moved to the readers, and if writers kept arriving, readers could starve. (This needs more semaphores in code. Textbooks use five.)

Solution 3: fair, in arrival order

Starvation disappears if nobody can overtake anybody. Put everyone in one FIFO queue:

• If the head of the queue is a reader, let it in, together with every reader right behind it.
• If the head is a writer, wait until the database is empty and let it in alone.

The classic implementation adds a turnstile: a semaphore that every process must pass through (wait(turn) … signal(turn)) before it asks for the database. A writer holds the turnstile while it waits for wrt, so no reader behind it can slip past.

Request	Arrives	Readers first: waits	Writers first: waits	Fair: waits
R1 (read 4)	0	0	0	0
W1 (write 2)	1	9	3	3
R2 (read 3)	2	0	6	4
W2 (write 2)	3	9	3	6
R3 (read 3)	5	0	3	6
R4 (read 3)	7	0	1	4

No policy is “best”: readers first gives readers perfect service, writers first keeps data fresh, and the fair policy has no starvation but gives up some of the sharing among readers. Real systems choose by workload. A cache that is read thousands of times per write prefers readers. A banking ledger may prefer writers.

Compared with dining philosophers

The dining philosophers problem is about deadlock: everyone holds one resource and waits for another. Readers–writers is about starvation and fairness: the system never stops, but some process may never get its turn. Both are classics of process synchronization.

Code

First the semaphore solution from above with Python threads. wrt is a plain Lock, which, unlike a real mutex, may be released by a different thread than the one that took it, exactly what “last reader unlocks” needs. A check counts conflicts (a writer together with anything else) and finds none:

import threading, time, random

mutex = threading.Lock()      # protects readcount
wrt = threading.Lock()        # held by the writer, or by the group of readers
audit = threading.Lock()      # only used to check the result
readcount = 0
inside = {'readers': 0, 'writers': 0}
violations = []

def enter(kind):
    with audit:
        inside[kind] += 1
        if inside['writers'] > 1 or (inside['writers'] and inside['readers']):
            violations.append('conflict!')

def leave(kind):
    with audit:
        inside[kind] -= 1

def reader():
    global readcount
    with mutex:
        readcount += 1
        if readcount == 1:
            wrt.acquire()             # the first reader locks writers out
    enter('readers'); time.sleep(random.random() / 50); leave('readers')
    with mutex:
        readcount -= 1
        if readcount == 0:
            wrt.release()             # the last reader lets writers in

def writer():
    with wrt:
        enter('writers'); time.sleep(random.random() / 50); leave('writers')

threads = [threading.Thread(target=random.choice([reader, reader, writer])) for _ in range(40)]
for t in threads: t.start()
for t in threads: t.join()
print('violations:', violations)   # violations: []

Second, a simulator for the three policies, using the same six requests as the 3D model:

def schedule(requests, policy):
    """requests: (name, 'R' or 'W', arrival, duration). Returns {name: start time}.
    policy: 'reader' (readers first), 'writer' (writers first) or 'fair' (arrival order)."""
    start, end = {}, {}
    waiting, readers, writer = [], set(), None
    t = 0
    while len(start) < len(requests) or readers or writer:
        for who in [x for x in readers | {writer} if x and end[x] == t]:
            readers.discard(who)                   # finished: leave the database
            writer = None if who == writer else writer
        waiting += [r for r in requests if r[2] == t]

        def admit(r):
            nonlocal writer
            waiting.remove(r)
            start[r[0]], end[r[0]] = t, t + r[3]
            if r[1] == 'W':
                writer = r[0]
            else:
                readers.add(r[0])

        writers_waiting = [r for r in waiting if r[1] == 'W']
        if policy == 'reader' and writer is None:
            for r in [r for r in waiting if r[1] == 'R']:
                admit(r)                           # readers first, even if a writer waits
            if not readers and writers_waiting:
                admit(writers_waiting[0])
        elif policy == 'writer' and writer is None:
            if writers_waiting:
                if not readers:
                    admit(writers_waiting[0])      # writers first; readers wait
            else:
                for r in [r for r in waiting if r[1] == 'R']:
                    admit(r)
        elif policy == 'fair':
            while waiting and writer is None:      # strictly in arrival order
                head = waiting[0]
                if head[1] == 'W' and readers:
                    break
                admit(head)
                if head[1] == 'W':
                    break
        t += 1
    return start

requests = [('R1', 'R', 0, 4), ('W1', 'W', 1, 2), ('R2', 'R', 2, 3),
            ('W2', 'W', 3, 2), ('R3', 'R', 5, 3), ('R4', 'R', 7, 3)]
for policy in ('reader', 'writer', 'fair'):
    start = schedule(requests, policy)
    print(policy, dict(sorted(start.items())))
    print('   waits', {n: start[n] - at for n, kind, at, d in requests})
# reader {'R1': 0, 'R2': 2, 'R3': 5, 'R4': 7, 'W1': 10, 'W2': 12}
#    waits {'R1': 0, 'W1': 9, 'R2': 0, 'W2': 9, 'R3': 0, 'R4': 0}
# writer {'R1': 0, 'R2': 8, 'R3': 8, 'R4': 8, 'W1': 4, 'W2': 6}
#    waits {'R1': 0, 'W1': 3, 'R2': 6, 'W2': 3, 'R3': 3, 'R4': 1}
# fair {'R1': 0, 'R2': 6, 'R3': 11, 'R4': 11, 'W1': 4, 'W2': 9}
#    waits {'R1': 0, 'W1': 3, 'R2': 4, 'W2': 6, 'R3': 6, 'R4': 4}

Common mistakes

• Locking the whole database for readers too. That is correct but throws away the concurrency that readers–writers is all about.
• Forgetting the mutex around readcount. Two readers can both see readcount == 0 and both call wait(wrt), which deadlocks the second one.
• Calling wait(wrt) for every reader. Only the first reader locks, and only the last one unlocks.
• Saying “readers first” is deadlock-prone. It is not: the risk is starvation, a very different problem.
• Assuming the writers-first fix is “free”. It just moves the starvation to the readers. Only a fair, arrival-order policy removes both.