On Oct 26, 2006, at 6:04 AM, Anthony Williams wrote:
"Cory Nelson" <phrosty@gmail.com> writes:
Is there a reason for wanting a priority? Why not make the lock fair. I'd rather have locks take out a ticket so everything is processed in a FIFO order, with no starvation.
I think it would be better with no priority, too. I'm working on an algorithm for that.
FIFO means that the OS has no say in the wakeup order; it'd be better if all the waiting threads could block on the same OS sync object, so the OS gets to choose which to wake.
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 If you don't like the "upgradable" part, it strips out cleanly from the code. Just delete everything that refers to "upgradable" and you've got a read/write mutex using Terekhov's algorithm (and rename the mutex). Algorithm in a nutshell: There are two gates. Everyone (readers and writers) wait at gate 1 for entry. When a reader gets into gate 1, he has read ownership. When a writer gets into gate 1, he waits at gate 2 before getting write ownership. While a writer is inside of gate 1, no readers or writers are allowed to pass gate 1. The above algorithm is shown implemented with just mutex and condition variables. The same algorithm is of course implementable using atomics for the "quick path" and I've done that on PPC (but I don't own that code). -Howard