CIS 4307: Readers and Writers

There are a number of Classical Concurrency Problems, that is, of problems that allow us to examine in a simplified form typical problems that arise when we write concurrent programs. One of these problems is the Readers and Writers problem (other such problems are the Producers and Consumers problem, the Dining Philosophers problem, the Barbers problem, the Smokers problem, the Monkey Rock problem, ..). The Readers and Writers problem was originally proposed in [1]. There is a data structure, say S, a group of processes that can read from S, the Reader processes, and a group of processes that can write to S, the Writer processes. A writer process must operate in mutual exclusion with respect to all other processes. A reader process can operate concurrently with other readers. Here is a simple solution to the readers and writers problem:

        GLOBAL VARIABLES:
                mutex, db : semaphore := 1; // Mutual exclusion semaphores
                readcount : integer   := 0;
        READER:
                p(mutex);
                readcount++;
                if (readcount is 1) then p(db);
                v(mutex);
                CRITICAL REGION where we read
                p(mutex);
                readcount--;
                if (readcount  is 0) then v(db);
                v(mutex);
        WRITER:
                p(db);
                CRITICAL REGION where we write
                v(db);

Notice that in this solution on the semaphore db we will have at most one reader (all other readers will wait on mutex). But once a reader gets in, all waiting readers can (but not necessarily do [why?]) get in ahead of waiting writers. When a writer finishes, if there are waiting readers and writers, either readers or a writer will run.

Here is a paraphrase of the "classic" solution from [1]. In this solution Writers are given absolute priority over Readers.

        GLOBAL VARIABLES:
                mutex1 : semaphore := 1; // all semaphores here are mutual exclusion
                mutex2 : semaphore := 1;
                mutex3 : semaphore := 1;
                db     : semaphore := 1;
                r      : semaphore := 1;
                readcount, writecount : integer := 0;
        READER:
                p(mutex3);
                  p(r);
                    p(mutex1);
                    readcount++;
                    if (readcount is 1) then p(db);
                    v(mutex1)
                  v(r);
                v(mutex3);
                CRITICAL REGION where we read
                p(mutex1);
                readcount--;
                if (readcount is 0) then v(db);
                v(mutex1);
        WRITER:
                p(mutex2);
                writecount++;
                if (writecount is 1) then p(r);
                v(mutex2);
                p(db);
                CRITICAL REGION where we write
                v(db);
                p(mutex2);
                writecount--;
                if (writecount is 0) then v(r);
                v(mutex2);

In this solution:

mutex3 is only used by entering readers and it will force them to compete with each other without interfering with the writers or exiting readers. [One of the aims is to reduce the number of processes contending for use of a semaphore - in particular to restrict to at most one the number of readers on r competing with writers waiting on the completion of a writer currently in the critical region.]
mutex1 is only used by exiting readers and at most one entering reader. It protects the use of the readcount variable and it will force these readers to compete with each other without interfering with the writers.
mutex2 is only used by writers. It protects writecount.
r makes sure that if a reader is in the critical region and a writer is waiting no further reader can use the resource. This is achieved by the first entering writer locking r and keeping it locked until the last writer exit. Thus no reader in that time can get to db, thus cannot compete with entering writers.
Finally db makes sure that the appropriate mutual exclusion exists between the readers and the writers, and among the writers.

The two solutions we have seen differ only in the way they schedule readers and writers. This kind of scheduling established by the use of synchronization commands (here p and v on semaphores) is called intermediate scheduling as distinct from the microscheduling taking place at the ready queue and in the semaphores themselves, and from the macroscheduling taking place at the level of jobs.

Here is an additional solution, due to Kleiman,Shah, and Smaalders, using threads: rwl.h and rwl.c.

Notice that we have looked at implementations of the Readers and Writers problem starting from semaphores. In practice often systems provide as basic system primitives reader-and-writer locks, so that the user does not need to implement this kind of mechanism.

[1]P.J.Courtois,F.Heymans,D.L.Parnas: Concurrent Control with "Readers" and "Writers", CACM October 1971