Readers–writers problem

From Wikipedia, the free encyclopedia
  (Redirected from Readers-writers problem)
Jump to: navigation, search

In computer science, the first and second readers-writers problems are examples of a common computing problem in concurrency. The two problems deal with situations in which many threads must access the same shared memory at one time, some reading and some writing, with the natural constraint that no process may access the share for reading or writing while another process is in the act of writing to it. (In particular, it is allowed for two or more readers to access the share at the same time.) A readers-writer lock is a data structure that solves one or more of the readers-writers problems.

The first readers-writers problem[edit]

Suppose we have a shared memory area with the constraints detailed above. It is possible to protect the shared data behind a mutual exclusion mutex, in which case no two threads can access the data at the same time. However, this solution is suboptimal, because it is possible that a reader R1 might have the lock, and then another reader R2 requests access. It would be foolish for R2 to wait until R1 was done before starting its own read operation; instead, R2 should start right away. This is the motivation for the first readers-writers problem, in which the constraint is added that no reader shall be kept waiting if the share is currently opened for reading. This is also called readers-preference, with its solution below:

semaphore wrt=1, mutex=1;
readcount=0;
 
writer()
{
    wait(wrt);
    // Writing is done
    signal(wrt);
}
 
reader()
{
    wait(mutex);
        readcount++;
        if (readcount == 1)
            wait(wrt);
    signal(mutex);
    // Do the Reading
    // (Critical Section Area)
    wait(mutex);
        readcount--;
        if (readcount == 0)
            signal(wrt);
    signal(mutex);
}

The second readers-writers problem[edit]

Above solution is suboptimal, because it is possible that a reader R1 might have the lock, a writer W be waiting for the lock, and then a reader R2 requests access. It would be foolish for R2 to jump in immediately, ahead of W; if that happened often enough, W would starve. Instead, W should start as soon as possible. This is the motivation for the second readers-writers problem, in which the constraint is added that no writer, once added to the queue, shall be kept waiting longer than absolutely necessary. This is also called writers-preference.

A solution to the writers-preference scenario is presented below:.[1] In this code, the semaphore mutex_rdcnt protects the readcount variable, mutex_wrcnt protects the writecount variable, the mutex 'r' protects the reading operation, and the mutex 'w' protects the writing operation.

int readcount, writecount; //(initial value = 0)
semaphore mutex_rdcnt, mutex_wrcnt, mutex_3, w, r; //(initial value = 1)
 
//READER
  wait(mutex_3);
    wait(r);
      wait(mutex_rdcnt);
        readcount++;
        if (readcount == 1)
            wait(w);
      signal(mutex_rdcnt);
    signal(r);
  signal(mutex_3);
 
 // reading is performed
 
  wait(mutex_rdcnt);
    readcount--;
    if (readcount = 0) 
        signal(w);
  signal(mutex_rdcnt);
 
//WRITER
  wait(mutex_wrcnt);
    writecount++;
    if (writecount = 1) 
        wait(r);
  signal(mutex_wrcnt);
 
  wait(w);
   // writing is performed
  signal(w);
 
  wait(mutex_wrcnt);
    writecount--;
    if (writecount = 0) 
        signal(r);
  signal(mutex_wrcnt);

The third readers-writers problem[edit]

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. Here P() is for waiting and V() is for signalling a semaphore. A solution with fairness for both readers and writers might be as follows:

        semaphores: no_waiting, no_accessing, counter_mutex ( initial value is 1 ) 
        shared variables: nreaders ( initial value is 0 ) 
        local variables:  prev, current
 
WRITER:
        P( no_waiting );
        P( no_accessing );
        V( no_waiting );
          ...  write ...
        V( no_accessing );
 
READER:
        P( no_waiting );
          P( counter_mutex );
            prev := nreaders;
            nreaders := nreaders + 1;
            if prev = 0  then P( no_accessing );
          V( counter_mutex );
 
        V( no_waiting );
        ... read ...
        P( counter_mutex );
          nreaders := nreaders - 1;
          current := nreaders;
          if current = 0 then V( no_accessing );
        V( counter_mutex );

Note that sections protected by counter_mutex 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.

See also[edit]

References[edit]

[2] [3] [4]

  1. ^ Communications of the ACM :Concurrent Control with "Readers" and "Writers" P.J. Courtois,* F. H, 1971 [1]
  2. ^ Morris JM (1979) A starvation-free solution to the mutual exclusion problem. Inf Process Lett 8:76–80
  3. ^ Fair Solution to the Reader-Writer-Problem with Semaphores only. H. Ballhausen, 2003 [2]
  4. ^ Faster Fair Solution for the Reader-Writer Problem. V.Popov, O.Mazonka 2013 [3]

External links[edit]