|
|
Boost : |
From: Peter Dimov (pdimov_at_[hidden])
Date: 2006-10-24 12:15:39
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:
in which he implements yet another Terekhov algorithm (AFAIK). Not lock-free
enough, though.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk