[concurrency-interest] Backport limitations

David Holmes dcholmes at optusnet.com.au
Tue May 2 22:50:49 EDT 2006


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.

> On the other hand, with greedy implementation (i.e. grab all that you
> can until you get as many as you need), if I have two threads both
> trying to get 8 permits (out of 10), they may get stuck after getting,
> say, 5 each.

The implementation isn't greedy so with a fair semaphore the first to ask
will be the first to get.

Hope that clarifies the behaviour.

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.

Cheers,
David Holmes



More information about the Concurrency-interest mailing list