Confusion in the solution to first readers-writers synchronization

Question

I am studying the solution to “First Readers-Writers Problem” from the book Operating System Concepts (9th edition) and it describes:

First readers–writers problem, requires that no reader be kept waiting unless a writer has already obtained permission to use the shared object. In other words, no reader should wait for other readers to finish simply because a writer is waiting.

And what I have understood from this is that if there is any reader running and a writer comes, then that writer would be blocked until reader has completed. But during the completion of the first reader, if there comes another reader (or multiple readers), then that (those) reader(s) will be given priority over the writer.

First of all please correct me if I am wrong here. But if am right, then what I have understood is that, the code for the reader below does not guarantee this.

Code for reader-writer is given below:

//data structures
semaphore rw_mutex = 1;
semaphore mutex = 1;
int read_count = 0;

//Code for writer
do {
   wait(rw_mutex);
   . . .
   /* writing is performed */
   . . .
   signal(rw_mutex);
} while (true);

//Code for reader
do {
   wait(mutex);            //Line 01
   read_count++;

   if (read_count == 1)
      wait(rw_mutex);      //Line 02

   signal(mutex);
   . . .
   /* reading is performed */
   . . .

   wait(mutex);            //Line 03
   read_count--;

   if (read_count == 0)
      signal(rw_mutex);    //Line 04

   signal(mutex);
} while (true);

Now suppose following sequence of events occurs:

• Suppose a first reader comes and it blocks the writer on the line mentioned as Line 02 in comments.
• Then a writer comes which is waiting for rw_mutex.
• Then the first reader is executing the code line mentioned as Line 03 in comments and it has locked the mutex semaphore.
• At the same time a second reader comes and it starts waiting on the line mentioned as Line 01 in comments.
• Now when the first reader executes Line 04, it releases the lock on rw_mutex and the writer which was waiting in its while loop is unlocked now and starts executing.
• The second reader will be unlocked when the first reader executes the line after Line 04 that signals the mutex semaphore.

Now if we see the overall flow, then the writer runs before the second reader. So does the code logic work the same as described above?

Please correct me if I am wrong.

Answer 1

But during the completion of the first reader, if there comes another reader (or multiple readers), then that (those) reader(s) will be given priority over the writer.

It's a bit more subtle. The second reader is not given priority. Rather, the reader is not blocked by the first reader. This means that if the first reader takes sufficiently long, then the second reader will eventually start reading, even if there is also a writer waiting to take the lock. It is possible however to have a sequence of events where:

• A first reader is reading.
• The first reader has finished its task and starts releasing the reader-writer lock. This is not an atomic operation: the first reader needs to perform several operations (decrement read_count, test it for zero, and call signal on rw_mutex), and these operations must look atomic from other processes' point of view so they are performed in a critical section, protected by mutex. Thus “starts releasing the reader-writer lock” means “takes mutex”.
• A second reader enters the system and starts working on acquiring the reader-writer lock, but it has not yet finished acquiring the reader-writer lock. The second reader waits on mutex, which is currently held by the first reader.
• A writer enters the system and starts working on acquiring the reader-writer lock: it waits on rw_mutex.
• The first reader is releasing the reader-writer lock, and it signals rw_mutex, allowing the writer to take it.

This sequence of events is what is going on in the scenario you describe: the second reader is waiting at line 01, and the first reader goes through line 03 then line 04.

In typical operation, this scenario will not occur often, because it depends on the second reader starting to wait on mutex while the first reader holds it. Given that the first reader only keeps that semaphore for a very short time, this scheduling is unlikely: most of the time, mutex is not held.

If the second reader arrives (i.e. calls wait(mutex)) before the first reader enters the critical section to release the reader-writer lock, then the second reader can start reading while the first reader is still reading, and the writer only gets the reader-writer lock once the second reader has finished. If the second reader arrives after the first reader exits that critical section, then it is clear that the already-waiting writer will grab the lock first. It's only if the second reader arrives during the first reader's critical section that there is this possibility of inversion where the writer arrives after the second reader, while the first reader is still in the critical section, and then the writer wins the race.

This kind of rarely-occurring scenario is an illustration of why concurrency is difficult. It's rare, but you still need to make sure your algorithm works in this case, because when it does occur, if your algorithm is buggy, it can bring your system down in a way that's hard to identify and fix. Here, this scenario specifically illustrates the need for mutex: without it, the second reader and the writer could both take the reader-writer lock.

In situations with low contention (i.e. it's rare that multiple processes want the same lock at the same time), as long as your algorithm is correct, the fact that the writer sneaks past the second reader is irrelevant. In situations with high contention, this kind of inversion can lead to starvation, and sometimes more sophisticated algorithm ensuring some kind of fairness property are needed.