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

Justin Sampson jsampson at guidewire.com
Tue Dec 30 14:07:21 EST 2014


Oleksandr Otenko wrote:

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

Thanks!

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

Yeah, I was still leaving that somewhat implicit in my rules. If
only the acquire(M) is awoken in that case, the result is a state in
which N permits are available and the acquire(N) has now been
waiting the longest, such that my rule 3a says that it must succeed
as well.

Of course, this whole thread is about making implicit rules more
explicit in the docs!

Maybe instead of, "When fair == xxx and there are P > 0 available
permits," I could have written "*Whenever* there are P > 0 available
permits and fair == xxx," to be more explicit?

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

Nice summaries! Yes, that's all consistent with my understanding.

Cheers,
Justin

P.S. Most of concurrency-interest goes over my head, but I got
excited about this discussion because I figure at _least_ I should
be able to understand the semantics of a *semaphore*! :)



More information about the Concurrency-interest mailing list