On Oct 26, 2006, at 9:20 PM, Peter Dimov wrote:
Howard Hinnant wrote:
Here is my implementation of Terekhov's *fair* read/write algorithm, with upgradable thrown in. This algorithm is just as you say: The OS alone decides who gets to run next.
http://home.twcny.rr.com/hinnant/cpp_extensions/upgrade_mutex.html
I'm having trouble eliminating the notify_all from the unlock() "fast path". Under Windows, it is ridiculously expensive; all other algorithms run circles around it, even those that had errors in them. :-) Did you have an unconditional notify_all in your "real" unlock?
No. I had extra 1-bit flags that let me know if there was someone waiting on gates 1 or 2: static const unsigned write_entered_ = 1U << (sizeof(unsigned) *_STD::__char<>::bits-1); static const unsigned upgradable_entered_ = write_entered_ >> 1; static const unsigned entry_sleeping_ = upgradable_entered_ >> 1; static const unsigned fw_sleeping_ = entry_sleeping_ >> 1; static const unsigned max_readers_ = ~(write_entered_ | upgradable_entered_ | entry_sleeping_ | fw_sleeping_); So the fast path would check these bits and avoid the notify_all if they weren't set. Btw, cool suggestion on the twist in the rdlock. I got half way through implementing it, discovered a fatal flaw, got half way through writing up why it's a fatal flaw and convinced myself it wasn't a fatal flaw. :-) Still tinkering... Looks promising! :-) -Howard