Second Algorithm Solution to Readers-Writer

Question

I'm having a really hard time understanding the Second Algorithm to the Readers-Writers problem. I understand the general concept, that the writers will get priority over the readers (readers can starve). I even understand the conditional variable implementation of this algorithm Reader/Writer Locks in C++. However, the semaphore & mutex implementation makes no sense to me. This is an example from Wikipedia:

int readcount, writecount; (initial value = 0)
semaphore mutex 1, mutex 2, mutex 3, w, r ; (initial value = 1)

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 done

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


WRITER
    P(mutex 2);
      writecount := writecount + 1;
      if writecount = 1 then P(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);

[http://en.wikipedia.org/wiki/Readers-writers_problem][2]

I don't understand what the three semaphores (mutex 3, r, and mutex 1) are for in the reader lock. Isn't one semaphore enough for the readcount?

Answer 1

mutex 1 protects the readcount variable; mutext 2 protects writecount variable; mutex r protects the reading operations and mutext w protects the writing operations.

1) Let's suppose a writer comes in:

Signals mutex 2 and increments writercount to account for the extra writer (itself) Since it is the only process that can change writercount (as it is holding mutex 2), it can safely test whether it is the only writer (writercount==1), if true, it signals mutex r to protect readers from coming in -- other writers (writercount > 1) can enjoy the mutex rbeing signaled already.

The writer then signals mutex w to protect its changes from other (concurrent) writers.

Last writer (writecount==1) releases mutex r to let readers perform their tasks.

2) Let's suppose a reader comes in:

Signals mutex 3 to protect the readers' setup logic from other readers; then signals mutex r to protect from other writers (remember, r is signaled while writers are operating); then signals mutex 1 to protect readcount (from other readers that might be exiting) and if it is the first reader (readercount == 1), signals mutex w to protect from writers (now excludes writers from performing their operations).

Reading can be done parallel, so no protection is needed from other readers while reading (remember, mutex w is being held at this point, so no intereference from writers)

Then the last reader resets the write mutex (w) to allow writers.

---

The trick that prevents writer starvation is that writers pose as readers (when signaling mutex p), so have a good chance of getting scheduled even when there are many readers. Also, mutex 3 prevents too many readers from waiting on mutex r, so writers have a good chance to signal r when they come.

Answer 2

Have a look at Concurrent Control with "Readers" and "Writers" by P.J. Courtois, F. Heymans, and D.L. Parnas, which is the reference for the code at Wikipedia. It explains why are all the mutexes needed.