Re: [Threads-devel] shared_mutex strategy

Subject: Re: [Threads-devel] shared_mutex strategy
From: Chris M. Thomasson (cristom_at_[hidden])
Date: 2010-05-19 17:12:23

"Damien R" <damienrg+list_at_[hidden]> wrote in message 
news:4BF3A2C0.6010606_at_gmail.com...
> Anthony Williams wrote:
>> If a reader gets the lock first, then more readers will be allowed to get 
>> the lock until a waiting writer wakes and registers its intent.
>
> Yes, so in the worst case, only one reader will be able to read because
> when the last reader unlocks the mutex, it notifies all waiters. For eg:
> ----
> reader 0, 1, 2, 3 and writer 0 have the same priority
>
> reader 0, 1, 2, 3 and writer 0 are waiting
>
> last_reader notify all waiters
>
> reader 0 call lock_shared and increment the number of readers
> writer call lock(), so it change the state and wait until it is wake up
> reader 1, 2, 3 call lock_shared() and wait because the state was changed
> by the writer
>
> reader 0 release lock change state, notify all waiters
> ----
>
> Do you agree ?

I have no time to make a proper response; sorry! Anyway...

FWIW, I have created another "contention strategy" for an older read/write 
mutex algorithm of mine that totally eliminates any possible chance of 
starvation and is 100% fair. Please note that this differs from Anthony's 
algorithm in that I am explicitly managing the contention in a strict 
alternating fashion where he is letting the OS manage things. That is if 
there are readers, and a writer comes in, then that writer automatically 
owns the lock after the last reader leaves. Now if a batch of readers come 
in after that writer, then the entire batch owns the lock after that writer 
unlocks. Everything is strictly interleaved which means that there are no 
"thundering herds" of waiting readers and writers that get awoken. Believe 
it or not... I implement this algorithm without using ANY loops!

Here is some further context:

http://relacy.pastebin.com/f3cab2025
(the algorithm implemented in Relacy Race Detector)

http://groups.google.com/group/comp.programming.threads/msg/51534f11c3b570b7
(fairly detailed description of the algorithm where I clear up some of 
Eric's concerns)

http://groups.google.com/group/comp.programming.threads/msg/2d3193a8018ef859
(Eric understands the algorithm!  :^D)

Who knows, it might be of some use to you...

;^)