Talk:Readers–writers problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Hallo, gibt es diese Page auch in Deutsch? sklia@bluewin.ch

Noch nicht. -- 146.169.52.145 (talk) 18:58, 16 November 2007 (UTC)

Could we by chance let people know that, like other concurency problems, there is no one perfect solution. The solution that you choose to implement is based upon the needs of the system that you are implementing on. What works out best for one system might not be the best for another. Of course, this is many wrong solutions too. But there is no one solution that is the best. —Preceding unsigned comment added by 24.111.186.45 (talk) 17:15, 21 February 2008 (UTC)

One way to "let people know that no one solution is the best" is to list all the solutions, and mention their advantages and disadvantages.
Should we list all those solutions here in this article? Or is there some other article more appropriate for such a list? --68.0.124.33 (talk) 14:35, 17 October 2008 (UTC)


Babobibo (talk) 00:29, 21 February 2012 (UTC) When I first posted my third problem solution I never thought it would cause so much heat! It's just a concurrency problem after all. In regards of "the ubik"'s and AbigailAbernathy's contributions I am sure that both are correct: While proving correctness is quite a pedantic task, it's fairly easy to prove incorrectness by presenting an instance of a concurrent sequence of operations that violates the constraints that not any two writers, nor any writer and reader can access data at the same time. It happens to be impossible to find such a sequence in both cases.

Talking about the case in which the writer does:

P( no_writers ); P( no_readers ); V( no_writers ); ... write ... V( no_readers );

"The ubik" says that he ( or she ) thinks there is a bug. I can imagine what his/her thought was: once the writer leaves the no_writer section it effectively becomes like a reader and can conflict with another reader, but in fact it doesn't, as the writer is not adjusting the nreaders shared variable, so the next reader will correctly block on P(no_reader) until the writer is done.


My first post was like "the ubik" 's version because I think it's more intuitive:

P( no_writers ); P( no_readers ); V( no_readers ); ... write ... V( no_writers );


All in all, I have no opposition to either one, as I don't clearly see any reason to prefer one or the other ( in terms, e.g. of numbers of potential waits, lenght of critical sections etc. ). It would be very interesting to have some experimental studies as to whether one is "better" in connection to parameters like number of readers versus number of writers ratio, or relative frequency of operations, or relative cost of the "write" operation as such versus the cost of reads. All I can say is that on my i7 ( 8-way multiple processor ) the provided solution (with fetch-and-add) is far better than standard pthread_rwlock_... family.


That said, guys, stop undoing each other's solution, toss a coin and move on.



Babobibo (talk) 14:26, 22 February 2012 (UTC) Following with my stream of consciousness, I would like to explain my hint on the fetch_and_add optimization.

Let's say that there is a function

int fetch_and_add( int * variable, int value )

which behaves as stated in related fetch-and-add page: atomically adds value to *variable, puts the result in *variable and returns the content in *variable before it was changed

Then the envisioned solution would be:


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

Code for First Readers Writers Problem (Readers Preference)[edit]

The code added 17 May 2012‎, by Diaa abdelmoneim, for the first readers writers problem (readers preference), is clearly incorrect and is not thread-safe. Moreover, the logic of the code is suspect, such that an easy fix is not available. The code probably should be deleted.

The code was modified slightly to improve formatting on 22 May 2012, by‎ Fragglet, and again on 3 June 2012‎ by 213.151.48.142, but no significant changes were made. In its current format (as of 22 June 2012), the code reads as follows:

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);
}

This code clearly fails at synchronized concurrency in many respects.

And what is the nature of the "Critical Section Area" mentioned in the code? Is the implication that an additional but unshown critical section is needed? Or that there is no need for further synchronization for the reason that the semaphores already provide for access on a mutually-exclusive basis (which they do not).

Moreover, the logic is tortured. What is the point, for example, of waiting on the write semaphore if readcout==1, if the writing thread does not ever change the value of readcount?

The suggested fix is simply to delete the code, or to demand a source that confirms its workability. — Preceding unsigned comment added by 63.207.173.11 (talk) 01:30, 23 June 2012 (UTC)