[concurrency-interest] Backport limitations

Dawid Kurzyniec dawidk at mathcs.emory.edu
Tue May 2 23:06:33 EDT 2006


David Holmes wrote:
> Dawid Kurzyniec writes:
>   
>> Well, the same as in dining philosophers scenario. Say my semaphore has
>> 10 permits. I have 50 threads competing. 49 of them always acquire then
>> release a single permit, and the 50th thread attempts to acquire 10
>> permits at once. Then, if implemented that no permits are "grabbed"
>> until all of them can be acquired, the 50th thread runs a risk of being
>> starved.
>>     
>
> The implementation requires that all permits be available at the same time -
> so you can't grab one, hold it, wait for the next etc. But in a fair
> semaphore the fact that one thread is waiting for 10 permits say, when less
> than 10 are available, will cause other acquires to block until after the
> first thread is satisfied. So to avoid starvation you need a fair semaphore.
>
> But also be aware that tryAcquire can barge even in a fair implementation.
>
>   
So you're saying it's a strict FIFO? (Except for tryAcquire(n) which can 
still succeed even though acquire(n) would block?)
> BTW way back when there was a Semaphore class and a FairSemaphore class, the
> bulk operations were only in the FairSemaphore class. For a non-fair
> semaphore there's no practical difference between a bulk acquire(n) and a
> loop doing n seperate acquires.
>
>   
Hmmm... wouldn't loop be equivalent to a greedy implementation though, 
and prone to deadlocks? (That is, unless the loop was smart enough to be 
able to back off)

Anyway, I think I understand the behavior now. Thanks!

Regards,
Dawid



More information about the Concurrency-interest mailing list