On Aug 22, 2007, at 2:24 PM, Austin Bingham wrote:
Overall I really like the work you've done here.
I have a question about the scheduling of shared v. exclusive locks on shared_mutex. Suppose I have several shared locks already established and then an exclusive lock is tried. Are subsequent shared lock attempts deferred until after theexclusive lock has released? Or is the exclusive lock deferred until after all shared locks (regardless of when they were made) are released? Or is this even defined?
It may be easiest to just leave the scheduling undefined, and perhaps that is the intent of the proposal. Whether it's defined or not, though, it should be documented.
It might be useful, however, if the scheduling policy were configurable. It seems that such a policy could be established on the shared_mutex itself.
I have two answers: 1. This is somewhat of a shocking answer, so please read through the second answer before passing judgement: The proposal purposefully does not mention shared vs exclusive priority. And I would prefer not to. 2. The implementation uses an algorithm which I attribute to Alexander Terekhov. This is a completely fair algorithm, letting the OS scheduler decide which thread is next in line, regardless of whether that thread is seeking shared or exclusive locking. I've beat on this algorithm for years now, stress testing and watching for starvation. I've never seen it starve a reader or a writer. Alexander, if you're listening: REALLY NICE JOB!!! :-) Imho, Alexander's algorithm makes the issue of reader/writer priority moot. If Alexander's algorithm is the automobile, reader/writer policies are the buggy whip. They just aren't needed anymore. I just can't say enough good things about this work. In a nutshell it is a two-gate system. Both readers and writers all wait at the first gate for entry. If no one is yet beyond the first gate, the OS gets to decide who to let in. When a reader gets past the first gate, it has the read lock. When a writer gets past the first gate, it does not yet have the write lock. It must now wait at the second gate until all readers beyond the first gate give up their read lock. While a writer is past the first gate, no one else is allowed to pass through the first gate. The algorithm is implemented here for shared_mutex, and modified appropriately for upgrade_mutex: http://home.twcny.rr.com/hinnant/cpp_extensions/shared_mutex.cpp
Again, this is really excellent and I'm genuinely excited to see this progress. Thanks for all the hard work!
Thanks Austin. -Howard