Practical 6: the Readers-Writers Problem

writes made, 2 writers x 4 rounds : 8
the record is still consistent      : yes
readers that saw a half-written one : 0
more than one reader inside at once : yes

Four lines, and every one of them is a claim the program checked.

• 8 writes from two writers of four rounds each, so no write was lost: the two writers were

never inside together.

• The record is consistent at the end, and no reader ever saw a half-written one, so no

reader was ever inside while a writer was.

• Four readers were inside at once, which is the whole point. A plain mutex would have made

that number 1, and the program would have been correct and needlessly slow.

That last number is what tells you the solution is a readers-writers solution and not just a lock. It is worth printing in your own program for exactly that reason.

The three pieces of that solution

resource, a binary semaphore, is the right to touch the data. A writer takes it for itself. The readers take it collectively.

readers_inside, a counter, is how the readers know whether they are the first or the last. It is shared, so it needs its own lock.

count_lock, a mutex, guards that counter. Without it, two readers arriving together could both see readers_inside go from 0 to 1 and both call sem_wait(&resource), and the second one would block for ever on a semaphore the first one is holding.

Notice that sem_wait(&resource) is called while holding count_lock, which contradicts the rule from Practical 5 about not blocking while holding a lock. It is safe here, and knowing why is worth a mark: the only thread that can be holding resource is a writer, and a writer never asks for count_lock, so there is no cycle. The four Coffman conditions need a circular wait and there is none. That is the difference between a rule of thumb and a proof.

Writer starvation, run

The solution above has a defect, and it is not a bug: it does exactly what it was designed to do, and what it was designed to do is unfair.

resource is released only when the last reader leaves. If readers keep arriving, there is never a moment with no reader inside, so the writer waits for ever. That is starvation: not a deadlock, because everybody else is making progress, but one thread that never gets its turn.

Here is that made concrete. Two readers, staggered so that one is always inside, and a writer that asks once.

#include <stdio.h>
#include <time.h>
#include <pthread.h>
#include <semaphore.h>

static int  readers_inside;
static long reads_done;
static sem_t resource;
static pthread_mutex_t count_lock = PTHREAD_MUTEX_INITIALIZER;

static void nap(long ms)
{
    struct timespec t = { ms / 1000, (ms % 1000) * 1000000L };
    nanosleep(&t, NULL);
}

static void *reader(void *arg)
{
    long stagger = (long) arg;
    nap(stagger);                        /* so the two readers overlap */

    for (;;) {
        pthread_mutex_lock(&count_lock);
        if (++readers_inside == 1)
            sem_wait(&resource);
        pthread_mutex_unlock(&count_lock);

        nap(40);                         /* a long read */

        pthread_mutex_lock(&count_lock);
        reads_done++;
        if (--readers_inside == 0)
            sem_post(&resource);
        pthread_mutex_unlock(&count_lock);
        /* and straight back round: no pause at all */
    }
    return NULL;
}

static void *writer(void *arg)
{
    (void) arg;
    sem_wait(&resource);                 /* the writer waits here for ever */
    printf("the writer got in after %ld reads\n", reads_done);
    sem_post(&resource);
    return NULL;
}

int main(void)
{
    sem_init(&resource, 0, 1);

    pthread_t r1, r2, w;
    pthread_create(&r1, NULL, reader, (void *) 0L);
    pthread_create(&r2, NULL, reader, (void *) 20L);
    nap(100);                            /* let the readers get going */
    pthread_create(&w, NULL, writer, NULL);

    pthread_join(w, NULL);
    printf("main: finished\n");
    return 0;
}

That program prints nothing at all, ever. The two readers overlap, readers_inside never reaches 0, resource is never released, and the writer sits in sem_wait until the machine is switched off:

$ gcc -Wall -Wextra -pthread -o starve starve.c
$ timeout 5 ./starve
$ echo $?
124

Three runs, three timeouts. The listing is marked in this book as a program that never finishes, so a version of it that did get the writer in would have been reported as a failure. The starvation is measured, not asserted.

Starvation is not deadlock, and an examiner will ask for the difference:

The second solution: writers preferred

The mirror image. A writer that is waiting stops new readers from going in, so the readers already inside finish and then the writer gets its turn.

It is built by counting the waiting writers as well, and giving them a semaphore of their own:

/* the writer's entry protocol */
lock(writer_count_lock);
if (++writers_waiting == 1) wait(readers_may_enter);   /* shut the door on readers */
unlock(writer_count_lock);
wait(resource);

Now the writers do not starve. The readers do: a steady stream of writers keeps readers_may_enter locked and no reader ever gets in. The problem has simply moved.

That is the honest position, and it is the answer to MU's bullet about prioritisation: neither priority is fair, and choosing one is choosing whose starvation you can live with.

The third solution: fair, with a turnstile

The fix is a single extra semaphore that everybody must pass through before joining the readers or the writers. A writer holds it while it waits, so readers arriving after the writer queue behind it; the readers already inside finish, the writer goes in, and then the queue moves again.

It is called a turnstile, and it is four lines of difference from the first program.

#include <stdio.h>
#include <time.h>
#include <pthread.h>
#include <semaphore.h>

#define READERS 4
#define WRITERS 2
#define ROUNDS  4

struct record { int value; int doubled; };

static struct record shared = { 0, 0 };
static int readers_inside, max_readers, torn_reads;

static sem_t resource;                   /* one writer, or the readers as a group */
static sem_t turnstile;                  /* everybody queues here first */
static pthread_mutex_t count_lock = PTHREAD_MUTEX_INITIALIZER;
static pthread_mutex_t tally = PTHREAD_MUTEX_INITIALIZER;

static void nap(long ms)
{
    struct timespec t = { ms / 1000, (ms % 1000) * 1000000L };
    nanosleep(&t, NULL);
}

static void *reader(void *arg)
{
    (void) arg;
    for (int r = 0; r < ROUNDS; r++) {
        sem_wait(&turnstile);            /* queue, so a waiting writer is not overtaken */
        sem_post(&turnstile);            /* and let the next one queue at once */

        pthread_mutex_lock(&count_lock);
        if (++readers_inside == 1)
            sem_wait(&resource);
        if (readers_inside > max_readers)
            max_readers = readers_inside;
        pthread_mutex_unlock(&count_lock);

        int v = shared.value;
        nap(5);
        int d = shared.doubled;
        if (d != 2 * v) {
            pthread_mutex_lock(&tally);
            torn_reads++;
            pthread_mutex_unlock(&tally);
        }

        pthread_mutex_lock(&count_lock);
        if (--readers_inside == 0)
            sem_post(&resource);
        pthread_mutex_unlock(&count_lock);

        nap(3);
    }
    return NULL;
}

static void *writer(void *arg)
{
    (void) arg;
    for (int r = 0; r < ROUNDS; r++) {
        sem_wait(&turnstile);            /* HOLD it: no new reader may join */
        sem_wait(&resource);             /* wait for the readers inside to leave */

        int n = shared.value + 1;
        shared.value = n;
        nap(5);
        shared.doubled = 2 * n;

        sem_post(&resource);
        sem_post(&turnstile);            /* let everybody through again */

        nap(3);
    }
    return NULL;
}

int main(void)
{
    sem_init(&resource, 0, 1);
    sem_init(&turnstile, 0, 1);

    pthread_t rd[READERS], wr[WRITERS];
    for (long i = 0; i < READERS; i++)
        if (pthread_create(&rd[i], NULL, reader, (void *) (i + 1)) != 0)
            return 1;
    for (long i = 0; i < WRITERS; i++)
        if (pthread_create(&wr[i], NULL, writer, (void *) (i + 1)) != 0)
            return 1;

    for (int i = 0; i < READERS; i++)
        pthread_join(rd[i], NULL);
    for (int i = 0; i < WRITERS; i++)
        pthread_join(wr[i], NULL);

    printf("writes made, %d writers x %d rounds : %d\n", WRITERS, ROUNDS, shared.value);
    printf("the record is still consistent      : %s\n",
           shared.doubled == 2 * shared.value ? "yes" : "NO");
    printf("readers that saw a half-written one : %d\n", torn_reads);
    printf("more than one reader inside at once : %s\n",
           max_readers > 1 ? "yes" : "NO");

    sem_destroy(&resource);
    sem_destroy(&turnstile);
    return 0;
}

writes made, 2 writers x 4 rounds : 8
the record is still consistent      : yes
readers that saw a half-written one : 0
more than one reader inside at once : yes

Exactly the same four answers, and readers still get in together, so nothing was given up to buy the fairness. The readers still share; they merely queue politely.

And the starvation is gone

The proof is the starving program from earlier with the turnstile added, under exactly the same load of readers that never stop.

#include <stdio.h>
#include <time.h>
#include <pthread.h>
#include <semaphore.h>

static int  readers_inside;
static long reads_done;
static sem_t resource;
static sem_t turnstile;                  /* the only difference */
static pthread_mutex_t count_lock = PTHREAD_MUTEX_INITIALIZER;

static void nap(long ms)
{
    struct timespec t = { ms / 1000, (ms % 1000) * 1000000L };
    nanosleep(&t, NULL);
}

static void *reader(void *arg)
{
    long stagger = (long) arg;
    nap(stagger);

    for (;;) {
        sem_wait(&turnstile);
        sem_post(&turnstile);

        pthread_mutex_lock(&count_lock);
        if (++readers_inside == 1)
            sem_wait(&resource);
        pthread_mutex_unlock(&count_lock);

        nap(40);

        pthread_mutex_lock(&count_lock);
        reads_done++;
        if (--readers_inside == 0)
            sem_post(&resource);
        pthread_mutex_unlock(&count_lock);
    }
    return NULL;
}

static void *writer(void *arg)
{
    (void) arg;
    sem_wait(&turnstile);                /* holding this stops new readers */
    sem_wait(&resource);
    printf("the writer got in\n");
    sem_post(&resource);
    sem_post(&turnstile);
    return NULL;
}

int main(void)
{
    sem_init(&resource, 0, 1);
    sem_init(&turnstile, 0, 1);

    pthread_t r1, r2, w;
    pthread_create(&r1, NULL, reader, (void *) 0L);
    pthread_create(&r2, NULL, reader, (void *) 20L);
    nap(100);
    pthread_create(&w, NULL, writer, NULL);

    pthread_join(w, NULL);
    printf("main: finished\n");
    return 0;
}

the writer got in
main: finished

The writer gets in, on every run. The readers are still going round with no pause at all; the turnstile is what lets the writer put itself at the head of the queue.

Those two programs are the answer to MU's bullet about fairness. They differ by four lines: two in the reader and two in the writer. One never lets the writer in, and the other always does.

Deadlock prevention here

MU's third bullet ends with deadlock prevention, and in this exercise it comes down to one rule about the order the semaphores are taken.

The writer takes turnstile and then resource. Every thread that takes both takes them in that order. Reverse it in one place, and a writer holding resource while waiting for turnstile, and another holding turnstile while waiting for resource, are a circular wait.

The sem_wait(&resource) inside count_lock in every program on this page looks like a breach of the third rule, and it is safe for the reason given earlier: no writer ever asks for count_lock, so there is no cycle for the readers to complete. A rule of thumb is not a proof, and the proof is always "is there a cycle".

The three solutions, side by side

Procedure

1. Write the first program. Compile with gcc -Wall -Wextra -pthread -o rw1 rw1.c and run it five

times. Check all four printed lines each time.

1. Replace the whole reader protocol with a plain sem_wait(&resource) and sem_post(&resource),

so readers are exclusive too. Run it again: the answers are still right, and the most readers inside at once is now 1. That is a lock, not a readers-writers solution.

1. Remove count_lock from the reader's entry protocol and run it twenty times. Note what

happens, and why two readers arriving together can both try to take resource.

1. Write the starving program. Run it as timeout 5 ./starve; echo $? and record the 124.
2. Add the turnstile to it, four lines, and run it again. Record that the writer gets in.
3. Write the fair version of the full program and confirm the four answers are unchanged.
4. In your journal, write out the difference between deadlock and starvation in two sentences.

Result

Several readers were allowed into shared data at once while a writer had it exclusively, using one semaphore taken collectively by the readers and a counter under its own mutex. More than one reader was inside together on every run, no reader ever observed a half-written record, and no write was lost. Under a continuous load of readers the reader-preference solution starved the writer entirely, confirmed by the program being killed by a five-second timeout on every run. Adding a turnstile of one semaphore let the writer in on every run, with the four readers still sharing, which is fairness without loss.

Where marks are lost

• Using a plain mutex for the readers. It is correct and it is not the exercise. The number of

readers inside at once must be able to exceed one, and reporting that is how you show it.

• Printing the greatest number of readers inside as though it were fixed. It is not: it

depends on the scheduler, and this page saw both 4 and 3 with four readers.

• No mutex on readers_inside. Two readers arriving together can both believe they are the

first, and the second blocks for ever.

• The first reader locking and every reader unlocking, or the other way round. It is the

first in that locks and the last out that unlocks.

• Saying starvation is a deadlock. In a deadlock nothing progresses; under starvation

everybody else is working normally.

• Claiming a solution is fair because it worked once. Fairness shows up only under load, which

is why the starving program has readers that never pause.

• Forgetting that writers-preferred starves readers. Neither priority is fair; that is the

point of the third solution.

• Taking two semaphores in different orders in different threads, which is a circular wait.
• Not saying why sem_wait inside a mutex is safe here, when the examiner points at it.

For the journal

Write the aim, MU's own wording, and the table of who may be inside with whom. Then the first program in full with its four printed lines, and say what each line proves. Then the starving program, the timeout 5 command and the 124, and the turnstile version with its output, as a pair: those two are the evidence for the fairness bullet. Add the deadlock-against-starvation table. The conclusion: readers may share because reading changes nothing, a writer must be alone, the classical solution starves writers, and one extra semaphore that everybody queues at makes it fair without taking the sharing away.

Quick revision

• Many readers together, or one writer alone, and never both.
• Reader preference: the first reader in takes resource, the last reader out releases it, and

readers_inside is a shared counter needing its own mutex.

• Report whether more than one reader was ever inside at once. If it never was, you have written a

lock and not a readers-writers solution. Do not print the greatest number as a fact: it depends on the scheduler and changes between runs.

• Prove correctness with two fields that must agree, such as value and doubled. A reader that

sees them disagree has read a half-written record.

• Reader preference starves writers; writer preference starves readers. Neither is fair.
• Starvation is not deadlock: under starvation the rest of the system is working.
• A turnstile is one semaphore everybody passes through before entering. A writer holds it while

waiting, so readers arriving later queue behind it. Four lines, and the starvation is gone.

• Deadlock prevention here is one rule: every thread takes the semaphores in the same order, and

releases in the opposite order.

• Blocking while holding a lock is safe only when no cycle can form. The proof is always to look

for a cycle, not to recite the rule.

Questions you should be able to answer

1. State the readers-writers rule. Any number of readers may be inside together, or one writer alone. A writer may never be inside with a reader or with another writer.

2. Why may readers share when a mutex would not allow it? Because reading does not change the data, so two readers cannot interfere with each other. Only writing can leave the data in a state that another thread must not see.

3. In the reader-preference solution, which reader takes the semaphore and which releases it? The first reader to arrive takes it and the last to leave releases it. The readers in between do not touch it.

4. Why does readers_inside need a mutex of its own? Because it is shared. Without it two readers arriving together could both see the count go from 0 to 1 and both try to take resource, and the second would block for ever.

5. Why does the program report only that more than one reader was inside, and not how many? Because the greatest number depends on when the scheduler ran each thread and changes between runs: with four readers this page saw both 4 and 3. That more than one was inside together is a property of the program; the exact number is a coincidence of one run.

6. What is writer starvation, and how was it shown on this page? The writer never gets its turn because readers keep arriving and the count never reaches zero. It was shown by running the program under two readers that never pause: it printed nothing and was killed by a five-second timeout, three times out of three.

7. What is the difference between starvation and deadlock? In a deadlock every thread in the cycle is stuck and nothing at all progresses. Under starvation one thread never gets its turn while the rest of the system works normally.

8. What does a turnstile do, and what does it cost? It is one semaphore that every thread passes through before entering. A writer holds it while it waits, so readers that arrive later queue behind the writer. It costs two extra semaphore operations per reader and nothing in sharing: four readers still get in together.

9. What is the one rule that prevents deadlock in this exercise? Every thread takes the semaphores in the same order, turnstile before resource, and releases in the opposite order. That makes a circular wait impossible.

10. The reader calls sem_wait(&resource) while holding count_lock. Is that not blocking while holding a lock? It is, and it is safe here because the only thread that can hold resource is a writer, and a writer never asks for count_lock. No cycle can form, so no deadlock is possible.