Re: [Threads-devel] reader/writer locks

From: Anthony Williams (anthony_at_[hidden])
Date: 2007-08-04 03:15:35

>> Sort of. A waiting writer will block all new readers until
>> all existing readers (or the single existing writer) are
>> done. At this point, all waiting threads (readers and
>> writers) will unblock and compete.
>
> I'm not quite sure what that means.  I was under the impression that the
> standard way to do this is that all new readers block and the writers go
> one
> at a time until they are all done, at which point all waiting readers can
> get shared access to the resource.
>
> If everyone unblocks, does that mean that after all existing readers are
> done, one of the waiting readers can grab the mutex, then the writer
> starts
> waiting again forcing all other readers to wait, so in effect you have the
> possibility that one waiting reader goes at a time, ad infinitum, for as
> long as readers continue to queue and grab the mutex before a waiting
> writer?

Yes, that's a possibility. It is up to the OS scheduler to ensure that
threads don't wait for ever. If there are 49 waiting readers and 1 waiting
writer then there's a 1 in 50 chance that the writer will wake first.

It's done this way to prevent reader starvation. If writers have priority,
then a waiting writer will prevent readers from proceeding until that
writer is finished. If the writer is in a tight loop and reacquires the
write lock soon after it is done, or there are multiple writers, then no
readers will ever proceed. If waiting writers don't block the readers then
the writer will starve. By unblocking all threads, the OS can decide which
thread gets the lock. We had extensive discussions about this on the main
boost list when I was developing the win32 implementation of this
algorithm.

Anthony
-- 
Anthony Williams
Just Software Solutions Ltd - http://www.justsoftwaresolutions.co.uk
Registered in England, Company Number 5478976.
Registered Office: 15 Carrallack Mews, St Just, Cornwall, TR19 7UL