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

David Holmes davidcholmes at aapt.net.au
Tue Dec 23 18:54:06 EST 2014

Justin Sampson writes:
> 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.

I tend to agree that referring to this as a priority issue is quite
misleading. In non-fair mode the "queue" is logically just an assemblage of
waiting threads - there is no specified order even if the implementation
constructs one. The problem we have, based on previous discussion, is that
when a waiting thread is given the opportunity to acquire M permits but
needs N, then the opportunity is not given to a second thread to acquire M
(and so on). In a simple wait/notify solution (as earlier shown) this simply
amounts to doing a notifyAll when a release is made.

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

Note that barging via tryAcquire, happens regardless of fairness mode.
Otherwise IIRC barging is only an issue for non-fair mode.

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

Depends on the original logical model that is set up. You can model things
as-if a barging thread was placed at the head of the queue - but the
implementation doesn't actually do that.

> > 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!

I don't like to think if it in terms of barging, but IIUC given 2 available
permits and a thread waiting for 3 and a thread waiting for 2, then a second
thread calling acquire(2) can proceed to get the permits. This would be
"barging" if the waiting thread had been woken up, but it wasn't.


> 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.
> Cheers,
> Justin
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

More information about the Concurrency-interest mailing list