Talk:Readers–writers problem

Latest comment: 2 years ago by 198.206.219.131 in topic First readers–writers problem

Deutsch

edit

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

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

No optimal solution

edit

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)Reply

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)Reply


Correct solutions

edit

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.Reply

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.Reply

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)Reply

Code for the second problem not reproducing the cited paper

edit

The posted code for the second problem is lacking one reader mutex (mutex 3 in the original paper). — Preceding unsigned comment added by 193.25.220.243 (talk) 12:45, 14 December 2016 (UTC)Reply

First readers–writers problem

edit

The explanation given for the "entry section" in the First Readers-Writers Problem" is confusing. The terms "entry section" and "exit section" are never defined. The line comments seem to suggest that the Entry section is the critical section prior to the line that says "Do the reading", and the Exit section is the critical section after the reading operation. But then what the does the sentence "Before entering the critical section, every new reader must go through the entry section" mean?? Also the necessity for the rmutex doesn't seem to be about race conditions as it is about ensuring no reader gets blocked from reading by another reader, which is suboptimal, as mentioned in the introduction to the section. If everyone agrees, I would like to change the text to make this clear 198.206.219.131 (talk) 21:16, 26 November 2021 (UTC)Reply