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

Oleksandr Otenko oleksandr.otenko at oracle.com
Mon Dec 29 20:40:20 EST 2014


This is a good way to put it. Still, a few more points need clarifying.

eg

if M+N permits are released in bulk, will two threads (one waiting for 
M, another for N) get woken up or not. Certainly, if they arrive in the 
nick of time (acquire without going to sleep), both will succeed. But 
what if both are asleep? If so, then the wording would need to state 
something like "the longest queue of threads the sum of whose permits is 
<=P"

Or contracted to:

fair semaphore: at any given time the longest waiting thread requires 
N>P permits, and all other threads wait until the longest waiting thread 
is allowed to proceed. This already means that if for the longest 
waiting thread N <= P, it can't be waiting.

unfair semaphore: at any given time the threads requiring N>P permits 
are waiting, and some other threads may be waiting for them to proceed 
first. Rather vague about who can proceed, but that's unfairness for 
you: can you be sure a thread makes progress? no, unless you are sure 
/all/ threads are N<=P.

semaphore not intended: at any give time /only/ threads requiring N>P 
permits are waiting [and threads requiring N<=P can't be waiting]. This 
is what some think semaphore means, but doesn't implement.


Alex


On 26/12/2014 10:59, Justin Sampson wrote:
> 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
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20141230/ec05f062/attachment.html>


More information about the Concurrency-interest mailing list