6

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?

Community
  • 1
  • 1
ayl
  • 384
  • 1
  • 5
  • 14
  • Would you please post a link to the algorithm or Wikipedia page to ensure we are all looking at the same thing? – gbulmer Apr 02 '12 at 10:06

2 Answers2

11

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.

Attila
  • 28,265
  • 3
  • 46
  • 55
  • Thanks for the explanation Attila. The write portion makes perfect sense, but the read portion is still unclear to me. Maybe to understand this better you could explain what would happen if there were no mutex 3 and mutex 1 semaphores (only r semaphore remains to protect the readcount)? – ayl Apr 02 '12 at 11:16
  • 4
    Readcount is protected by `mutex 1`. `mutex 3` is used to limit the number of concurrent readers waiting on `r` to 1 (to prevent writer starvation). `r` is used to coordinate access between readers and writers – Attila Apr 02 '12 at 12:19
4

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.

svick
  • 236,525
  • 50
  • 385
  • 514