Boost logo

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, gregod at, cpdaniel at, john at