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

Justin Sampson jsampson at guidewire.com
Tue Dec 23 17:12:33 EST 2014

Doug Lea wrote:

> Right. We just need to rule out any interpretation that waiters
> are prioritized by counts. There is nothing in any method spec
> that supports this interpretation.

Hmm, I don't think it's really an expectation of "priority" or
"preference." It's simply a (mistaken, apparently) expectation that
if _any_ threads can make progress then _some_ such thread will be
allowed to do so.

> We had ineffectively discouraged it by mentioning that
> bulk-acquire was a "convenience". But without being explicit,
> prioritization is only implicitly ruled out, for example by
> contemplating the impossibility of being both FIFO and prioritized
> in fair mode.

Maybe FIFO + "priority" is impossible, but FIFO + "progress" is not
necessarily so... 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

And if I understand correctly, the latter is true in non-fair mode
as well, with the sole exception of the occasional barging thread
that doesn't even end up on the queue at all.

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.

> And so even experts can be led to believe that the implementation
> might be wrong.

I'm not an expert, but the thing that's really bugging me, the more
that I think about this, is the claim that acquire(int) is just like
a loop but "atomic." That would seem to imply that it acquires
either all of the desired permits or none of them. That would
further seem to imply that any existing permits remain available for
other threads to acquire. The surprising thing is that the permits
are _officially_ still "available" but _effectively_ no other thread
can acquire them, except by barging!

So perhaps that's the essence of what needs to be communicated: If a
thread calls acquire(N) when M < N permits are available, it
effectively places a hold on those M permits until the entire N
permits are available, with the sole exception that in non-fair mode
another thread might acquire the held permits by barging.


More information about the Concurrency-interest mailing list