Second readers-writers pr*blem - why is third mutex needed at reader

Question

I do not understand what is the purpose of the outermost mutex at the very beginning of the reader procedure in the common solution to the second readers-writers problem.

To illustrate it, I shall post a code from appropriate wikipedia entry ( link ). I am talking about mutex_3 :

READER
  P(mutex_3);
    P(r);
      P(mutex_1);
        readcount := readcount + 1;
        if readcount = 1 then P(w);
      V(mutex_1);
    V(r);
  V(mutex_3);

  reading is performed

  P(mutex_1);
    readcount := readcount - 1;
    if readcount = 0 then V(w);
  V(mutex_1);

The only answer I can think of is that is serves to stop the influx of new readers. But I think it is already done, apart from its core functionality, by the next mutex, namely r. Am I wrong?

Answer 1

I see this question was asked a while back but I think I'll just post the answer anyway in case it helps others in the future.

We use mutexes to protect a shared resource from being accessed by multiple threads at the same time. In the case of mutex_3, if you look at the code that immediately follows P(mutex_3), we see the shared resource we want to protect is the semaphore r. As such, having mutex_3 ensures that only one reader can execute the section of code between P(r) and V(r) at any one time.

To see why this mutex is important, we also need to consider the code for the writer. From wikipedia:

WRITER

P(mutex_2);
 writecount := writecount + 1;
 if writecount = 1 then **P(r)**;  <-- Writer waits on semaphore r
V(mutex_2);

P(w);
 writing is performed
V(w);

P(mutex_2);
 writecount := writecount - 1;
 if writecount = 0 then V(r);
V(mutex_2);

The key part to note is in bold. As you can see, both the writer and the reader call P(r) on semaphore r. In this case, it is unclear as to whose call succeeds first. We assume the writer does not get any priority in calling P(r) (if it did then mutex_3 is not needed).

However, the problem statement for the second readers-writers problem states that writers should start as soon as possible. If scheduling occurs on a first-come first-serve basis, then in the above case, if the reader manages to call P(r) first, the reader's call succeeds. The writer is then delayed which we do NOT want.

So, the solution is to place a mutex around the setup code for the reader (mutex_3). Now, when a reader calls V(r), there CANNOT be any other reader waiting on r as other readers need to acquire mutex_3 before being able to call P(r) but the current reader holds mutex_3! There CAN however be a writer waiting on r and so in this case the writer's call to P(r) ALWAYS succeeds as soon as possible since it is the only one waiting on r.