Howard Hinnant wrote:
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.
Thanks, I'll try this tomorrow. Later today, I mean. BTW... why do you count the upgradable among the readers? It seems a bit simpler not to include it in the reader count; it already has a bit all for itself.