Boost logo

Threads-Devel :

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
> 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:
(the algorithm implemented in Relacy Race Detector)
(fairly detailed description of the algorithm where I clear up some of
Eric's concerns)
(Eric understands the algorithm! :^D)

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


Threads-Devel list run by bdawes at, david.abrahams at, gregod at, cpdaniel at, john at