[concurrency-interest] Semaphore doc bug [Was: Enforcing ordered execution of critical sections?]

Doug Lea 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
> progress.

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
backout loops.


More information about the Concurrency-interest mailing list