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

Justin Sampson jsampson at guidewire.com
Fri Dec 26 05:59:51 EST 2014


My point about barging was that if the queue is an implementation
detail, perhaps it's best not to mention it at all, especially in
the non-fair case.

I'm not personally advocating for any stronger promises in the
specification, I'm just jumping in with the hope of clarifying
something that seemed weird to me (and, I believe, to several other
folks in this discussion). Calling acquire(N) "merely a convenience"
or "just like a loop but atomic" really doesn't do justice to its
actual semantics in either fair or non-fair mode.

Here's an attempt at describing my own current understanding, at
this point in the discussion, of Semaphore's intended semantics, in
a minimally-constrained way, without using the words 'queue',
'atomic', 'barging', or 'convenience'. :)

1. Any acquire or tryAcquire call for N permits will either succeed
   in acquiring exactly N permits or will not acquire any permits.

2. If any acquire or tryAcquire call returns false or throws
   InterruptedException, that call will not have acquired any
   permits.

3. When fair == true and there are P > 0 available permits:

   3a. If the acquire or tryAcquire call that has been waiting the
       longest is for N <= P permits, then it will succeed.
   3b. If the acquire or tryAcquire call that has been waiting the
       longest is for N > P permits, then no acquire or tryAcquire
       call will succeed until more permits are released, except as
       described in 3c.
   3c. A zero- or one-argument tryAcquire call for N <= P permits
       may succeed immediately even if there are other acquire or
       tryAcquire calls already waiting.

4. When fair == false and there are P > 0 available permits:

   4a. If every waiting acquire or tryAcquire call is for N <= P
       permits, then one of them will succeed.
   4b. If any waiting acquire or tryAcquire call is for N > P
       permits, then it is possible that no waiting acquire or
       tryAcquire call will succeed until more permits are released.
   4c. Any acquire or tryAcquire call for N <= P permits may succeed
       immediately even if there are other acquire or tryAcquire
       calls already waiting.

Rules 3b and 4b cover the bits that had us tripped up in the
OrderedExecutor discussion.

Cheers,
Justin



More information about the Concurrency-interest mailing list