lkml.org 
[lkml]   [2010]   [Apr]   [9]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH 4/6] futex: Add FUTEX_LOCK with optional adaptive spinning
Peter W. Morreale wrote:
> On Wed, 2010-04-07 at 20:25 -0700, Darren Hart wrote:
>> Thomas Gleixner wrote:
>>> On Wed, 7 Apr 2010, Darren Hart wrote:
>>>> Thomas Gleixner wrote:

>>>>> if ((curval & FUTEX_TID_MASK) != ownertid) {
>>>>> ownertid = curval & FUTEX_TID_MASK;
>>>>> owner = update_owner(ownertid);
>>>>> }
>>>> Hrm... at this point the owner has changed... so we should break and go
>>>> to sleep, not update the owner and start spinning again. The
>>>> futex_spin_on_owner() will detect this and abort, so I'm not seeing the
>>>> purpose of the above if() block.
>>> Why ? If the owner has changed and the new owner is running on another
>>> cpu then why not spin further ?
>> That's an interesting question, and I'm not sure what the right answer
>> is. The current approach of the adaptive spinning in the kernel is to
>> spin until the owner changes or deschedules, then stop and block. The
>> idea is that if you didn't get the lock before the owner changed, you
>> aren't going to get it in a very short period of time (you have at least
>> an entire critical section to wait through plus whatever time you've
>> already spent spinning). However, blocking just so another task can spin
>> doesn't really make sense either, and makes the lock less fair than it
>> could otherwise be.
>
> Not only less fair, but potentially could cause starvation, no? Perhaps
> you could see this if you changed your model to allow all contended
> tasks to spin instead of just one.

Agreed, and V5 (just posted) does just that.

>
> If a spinning task blocks because of an owner change, and a new task
> enters and starts spinning directly after the owner change, at what
> point does the original task get woken up?

At the time of unlock the owner will have to call FUTEX_WAKE. This task
will wake and attempt to acquire the lock - it will lose races with
aclready running contenders. Lock stealing, adaptive spinning, etc are
all going to lead to less fair locks in exchange for throughput.

> Its likely that the new
> spinner will get the resource next, no? Rinse/repeat with another task
> and the original spinner is starved.
>
> (Or am I missing something? My understanding was that unfairness was
> built-in to this algo... If so, then the above is a possibility, right?)

Yes it is. These locks are typically used in situations where it is more
important that some work gets completed than _which_ work gets completed.

Thanks,

--
Darren Hart
IBM Linux Technology Center
Real-Time Linux Team


\
 
 \ /
  Last update: 2010-04-09 07:43    [W:0.074 / U:0.092 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site