Anthony Williams wrote:
I'm interested in the following scenario:
- K active readers are holding the lock - a writer is waiting for the above - L readers are wating for the writer
Since you seem to only store K+L (Chris's algorithm has separate counts), how do you know when to signal the writer?
Maybe it's not /quite/ the same algorithm, but it's certainly very similar.
The answer to your question is "when all K+L readers have finished". i.e., my algorithm gives readers priority.
Maybe this isn't such a good thing; in the "common" scenario of one writer thread and many readers, a waiting writer needs to block waiting readers, otherwise the writer might starve if the readers overlap each other.
Not good. :-)
Chris's algorithm goes to the other extreme --- writers always take priority, and no readers will take the lock if there are any waiting writers. If there is more than one writer thread, then the readers might starve.
Not good either. :-)
The way I see it, the ideal is that a waiting writer will block any fresh readers until all the current readers have gone away, but once that happens, and the lock is released, the waiting writer and the waiting readers will compete equally.
I agree that this (or a variation of it) is the best policy. I've tried to implement it in my prototype. Unfortunately, it has a different problem; the L readers (and potentially M writers) that are blocked by the pending/active writer are then serialized by the mutex mx_. Ideally, there would be an M+L (or M+1, or M+kL, where 0<k<1) tie after the writer unlocks, and if a reader wins it, all readers should proceed. There's also an implementation by Ion Gaztañaga: http://boost.cvs.sourceforge.net/boost/boost/boost/interprocess/sync/interprocess_upgradable_mutex.hpp?revision=1.4&view=markup in which he implements yet another Terekhov algorithm (AFAIK). Not lock-free enough, though.