[concurrency-interest] Semaphore doc bug [Was: Enforcing ordered execution of critical sections?]
dl at cs.oswego.edu
Wed Dec 24 07:16:53 EST 2014
On 12/23/2014 05:12 PM, Justin Sampson wrote:
> The behavior _could have been_ that the earliest
> thread in the queue _that can make progress_ is selected. Instead,
> the earliest thread in the queue is selected, even if it can't make
The spec does not even guarantee that the earliest is selected
unless in fair mode. The implementation just so happens to
use a mostly-FIFO-with-barging algorithm because it provides
good throughput. But if we discovered that, say, randomized
selection had better throughput, we'd switch to it. (Aside:
one performance issue with AQS-based synchronizers
is that they haven't adapted to spin more to compensate
for increasing context-switch overhead on most platforms.
We'll probably address this.)
I agree that the spec could have made stronger promises,
and that this would have been useful in priority-based
applications. But doing so would require a new method or
more likely a new class.
> Actually, that reminds me of something else in the docs that struck
> me as odd. The docs say that when a thread barges in, "logically the
> new thread places itself at the head of the queue of waiting
> threads." But isn't the actual behavior that a _successful_ barging
> thread never touches the queue and an _unsuccessful_ barging thread
> ends up at the tail of the queue just as if it hadn't tried to
> barge? The head of the queue is not actually involved in either case
> so it seems confusing (to me) to claim that it is "logically" so.
Sorry; but I'm not sure of a better way to explain this without
overly constraining implementations. The only reason for mentioning
barging at all in spec is to explain why non-fair tryAcquire
may succeed even if there are waiting threads.
> The surprising thing is that the permits
> are _officially_ still "available" but _effectively_ no other thread
> can acquire them, except by barging!
Again, this is unlikely to be surprising to the intended
audience (that was not communicated well): Users occasionally
needing to acquire multiple permits without needing to hand-craft
More information about the Concurrency-interest