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

David Holmes davidcholmes at aapt.net.au
Tue Dec 30 20:23:18 EST 2014


On December 24 I wrote:
> Hi Doug,
>
> I still need to go back and check historical notes but this all
> seems wrong to me.

So ... originally acquire(n) was only defined for the explicit FifoSemapore
class, as I explained below back in early 2003:

> David Holmes wrote on Thursday, 6 February 2003 8:27 AM
> To: Asif Qamar; concurrency-interest at altair.cs.oswego.edu
> Subject: RE: [concurrency-interest] Should there also be an acquire
> (long n) method in Semaphore class ?
>
>
> Hello Asif,
>
> > My question is exploratory: why is there no corresponding
> > acquire (int n) method?
>
> There is no acquire(n) method in semaphore because it requires some
> sense of ordering that Semaphore does not provide. You need to decide
> whether a thread waiting for n permits prevents other threads from
> taking any available permits: if the answer is yes then you've
> effectively imposed a Fifo ordering; if no, then it probably doesn't
> do what you want.
>
> There is acquire(n) on FifoSemaphore as the semantics are clear-cut:
> acquire the next n available permits.

However, later that year Doug decided to redesign things:

> 3. Fair subclass
>
> We defined FairSemaphore because acquire(n) is not necessarily
> well-behaved unless you can guarantee ordering. However, in my
> implementation, it IS arguably well-behaved even when fairness is not
> switched on. Here (as with RL), I use "FIFO plus barging": At any
> given time only the oldest thread and (if fairness set false) any
> newly arriving thread are allowed to contend (all others block).  When
> you run problematic acquire(n) cases through this, they don't
> seem particularly bad to me. Still, when people use acquire(n)
> all the time, the almost surely want fair version.

Looking back now I'm not sure we were focussed on the right issue - it is
"arguably well-behaved" the problem is that you can't deduce what the
behaviour might be from the specification, which to me makes acquire(n)
unusable in the non-fair case (unless relying on knowledge of the
implementation).

The class doc we have now:

"This class also provides convenience methods to acquire and release
multiple permits at a time. These methods are generally more efficient and
effective than loops. However, they do not establish any preference order.
For example, if thread A invokes s.acquire(3) and thread B invokes
s.acquire(2), and two permits become available, then there is no guarantee
that thread B will obtain them unless its acquire came first and Semaphore s
is in fair mode. "

is not completely terrible, but does somewhat obscure the fact that
acquire(n) is not really usable in non-fair mode. Perhaps that should be
stated explicitly. Also for the fair case these are not simply convenience
methods - they provide semantics that are impossible to obtain using
multiple acquire() operations!

However the new addition to the method doc:

"This method has the same effect as the loop for (int i = 0; i < permits;
++i) acquire(); except that it atomically acquires the permits all at once:
" (note ending : typo)

is not good! This is a completely meaningless statement in general because
you can not infer what "atomically" means given that the acquire() in the
loop has blocking semantics. I think it would be more meaningful to say
"except that it prevents acquire()'s from other threads from being
interleaved with those in the loop" - but even that is inaccurate in the
face of barging tryAcquires.

David
-----


>
> > On 12/23/2014 06:45 AM, Doug Lea wrote:
> > > On 12/23/2014 01:19 AM, Joe Bowbeer wrote:
> > > Hopefully the doc improvements will prevent this from happening again.
> >
> > I committed these to jsr166 CVS, plus the additional clarification in
> > acquire(int):
> >
> >       * <p>Acquires the given number of permits, if they are available,
> >       * and returns immediately, reducing the number of
> available permits
> >       * by the given amount. This method has the same effect as the
> >       * loop {@code for (int i = 0; i < permits; ++i) acquire();} except
> >       * that it atomically acquires the permits all at once:
>
> To me the "except" part nullifies the initial statement. What does it mean
> to acquire the permits atomically rather than in a loop? The loop
> can cause
> permits to be "reserved" while an atomic acquire of all the
> permits at once
> would not.
>
> > See
> > http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/
> Semaphore.html
>
> Again the example seems wrong to me. If the Semaphore is unfair then all
> permits are available to any acquirer. So as soon as two permits are
> available the acquire(2) can proceed. In contrast a fair Semaphore ensures
> only the head waiter can acquire permits.
>
> David
>
>
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
> _______________________________________________
> 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