User:Miguel.v/sandbox

The third readers-writers problem

In fact, the solutions implied by both problem statements result in starvation — the first readers-writers problem may starve writers in the queue, and the second readers-writers problem may starve readers. Therefore, the third readers-writers problem is sometimes proposed, which adds the constraint that no thread shall be allowed to starve; that is, the operation of obtaining a lock on the shared data will always terminate in a bounded amount of time. A solution with fairness for both readers and writers might be as follows:

int readcount; // (initial value = 0)
semaphore mutex_rdcnt, r, w; // ( initial value = 1 ) 

//READER
        wait(r);
          wait(mutex_rdcnt);
            readcount++;
            if (readcount == 1)
              wait(w);
          signal(mutex_rdcnt);          
        signal(r);

        // reading is performed 

        wait(mutex_rdcnt);
          readcount--;
          if (readcount == 0)
            wait(w);
        signal(mutex_rdcnt);  

//WRITER
        wait(r);
        wait(w);
        signal(r);

         // writing is performed

        signal(w);

Note that sections protected by mutex_rdcnt could be replaced by a suitable fetch-and-add atomic instruction, saving two potential context switches in reader's code.

Note also that this solution can only satisfy the condition that "no thread shall be allowed to starve" if and only if semaphores preserve first-in first-out ordering when blocking and releasing threads. Otherwise, a blocked writer, for example, may remain blocked indefinitely with a cycle of other writers decrementing the semaphore before it can.