Re: [boost] shared_mutex deadlocks?

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2008-04-21 16:04:41

On Apr 21, 2008, at 2:10 PM, Peter Dimov wrote:
>>>> shared_mutex is not designed for this scenario, since you have high
>>>> contention. shared_mutex is designed for infrequent updates.
>
> Some more observations.
>
> The same writer starvation occurs with 2 reader threads, so it's not  
> caused by the overcommit. Two reader threads on two cores is common.
>
> The update frequency doesn't matter; a lower update frequency would  
> just scale the time it takes to perform 1M updates, it will not  
> change the average writer wait time.
>
> Some wait times (2R+1W):
>
> atomics: 7.673 microseconds
> lightweight_mutex (CRITICAL_SECTION): 3.069 us
> shared_mutex: 760 us
> rw_mutex (my implementation): 665 us (same problem)
> pthread_rwlock_t, pthreads-win32: 7.108 us
> rw_mutex (Hinnant/Terekhov): 85.532 us
>
> This last line uses my reimplementation of Howard Hinnant's read/ 
> write mutex based on his description; Howard credits Alexander  
> Terekhov with the original algorithm. It does stall the writer a bit  
> in exchange for optimal reader throughput, but doesn't suffer from  
> outright starvation.
>
> I've attached my (not production quality) implementation of this  
> rwlock.
> <rw_mutex.hpp>_______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

I've so far only looked at your implementation for a few minutes.  The  
lock-reduced version is tricky.  It has been three years since I did  
this, but when I did, I needed 3 flags instead of your two.  That may  
have been because I was guarding against max-readers and you're not,  
not sure yet.  When I wrote it, it was on ppc only and so used the  
lwarx/stwcx. instructions directly and so was not written in a compare/ 
exchange style.

It might be interesting to run this http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2406.html#shared_mutex_imp 
  through your test.  It is the algorithm, but not "lock reduced".

-Howard