Backport limitations

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Backport limitations

Mike Skells
Hi
I noticed (which backporting some code) that the semaphores do not allow for multi acquires
 
Is there a specific reason for this is it just lack of dev resources. I use this is current J5 code and I am looking to not try to rewrite that code to do the backport
 
Mike

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Backport limitations

Dawid Kurzyniec
Mike Skells wrote:
> Hi
> I noticed (which backporting some code) that the semaphores do not
> allow for multi acquires
>  
> Is there a specific reason for this is it just lack of dev resources.
> I use this is current J5 code and I am looking to not try to rewrite
> that code to do the backport
It is the latter (dev resources), plus it seemed low priority comparing
to other things. I didn't have time to sit and analyze how the j.u.c.
implementation avoids the risk of deadlock / starvation, which I suppose
it must do at least for fair semaphores.

I'll try to look into this soon.
Regards,
Dawid

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

RE: Backport limitations

David Holmes-3
Dawid,

> It is the latter (dev resources), plus it seemed low priority comparing
> to other things. I didn't have time to sit and analyze how the j.u.c.
> implementation avoids the risk of deadlock / starvation, which I suppose
> it must do at least for fair semaphores.

j.u.c doesn't do anything special with this. What deadlock/starvation risks
where you thinking of?

Cheers,
David Holmes

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Backport limitations

Dawid Kurzyniec
David Holmes wrote:

> Dawid,
>
>  
>> It is the latter (dev resources), plus it seemed low priority comparing
>> to other things. I didn't have time to sit and analyze how the j.u.c.
>> implementation avoids the risk of deadlock / starvation, which I suppose
>> it must do at least for fair semaphores.
>>    
>
> j.u.c doesn't do anything special with this. What deadlock/starvation risks
> where you thinking of?
>
>  
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.

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.

Regards,
Dawid

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

RE: Backport limitations

David Holmes-3
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

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Backport limitations

Dawid Kurzyniec
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

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

RE: Backport limitations

David Holmes-3
> Dawid Kurzyniec writes:
> So you're saying it's a strict FIFO? (Except for tryAcquire(n) which can
> still succeed even though acquire(n) would block?)

Yes.

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

Yes a loop would be equivalent to greedy. But for non-fair you have a choice
between:
 - greedy and risk deadlock; or
 - non-greedy and risk starvation

I think I'm mis-remembering some things. :)

Cheers,
David

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Backport limitations

Dawid Kurzyniec
In reply to this post by Mike Skells
Mike Skells wrote:
> Hi
> I noticed (which backporting some code) that the semaphores do not
> allow for multi acquires
>  
> Is there a specific reason for this is it just lack of dev resources.
> I use this is current J5 code and I am looking to not try to rewrite
> that code to do the backport
>  

I have just finished implementing multi-acquires for fair semaphores;
the code is available in backport CVS and the latest daily build at
http://dcl.mathcs.emory.edu/util/backport-util-concurrent/. (It passes
unit tests, but if anybody is able to more thoroughly test it, I would
appreciate some feedback). For non-fair semaphores, the problem is a bit
more fundamental. Current implementation of release(n) wakes up exactly
n threads using notify(). If all of the waiters turn out to be
multi-acquirers however, it might be the case that all awoken threads
must go back to sleep, and no thread would proceed at least until next
notify. Is this acceptable?

An alternative would be to notifyAll(), but it would affect performance
- using the fair version instead might actually be a better idea.

Thus far, I have taken a conservative approach and left multi-acquires
for non-fair semaphores unimplemented (UnsupportedOperationException
thrown from blocking acquire(n) etc if n >= 2). Non-blocking
tryAcquire(n) works, however.

Regards,
Dawid

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest