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

Gregg Wonderly gregg at wonderly.org
Thu Dec 25 02:26:40 EST 2014


Why wouldn't the best implementation be something like the following?  What 
specific nuances of all
the described variations are necessary for functional code, verses side effects 
of hardware limitations or
implementations that must be dealt with by not guaranteeing progress in some 
semi fair fashion?

void acquire(int n) {
     int m;
     synchronized( this ) {
         do {
             // perform up to n acquires and return what we could get
             m = tryAcquire(n);
             if( m < n ) {
                 // release what we got since we didn't get everything we needed
                 // release() will wake up everyone
                 release(m);
                 // get in line to see the next set of changes
                 wait(this);
             }
         } while( m < n );
     }
}

Gregg

On 12/23/2014 5:54 PM, David Holmes wrote:
> 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.
>
> David
>
>> 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
> _______________________________________________
> 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