Re: [Lse-tech] Re: Futexes III : performance numbers

[george anzinger <george@mvista.com>]

Hubertus Franke wrote:
> 
> On Tuesday 05 March 2002 09:08 pm, Rusty Russell wrote:
> > In message <20020305212210.B10A33FF04@smtp.linux.ibm.com> you write:
> > > On Tuesday 05 March 2002 02:01 am, Rusty Russell wrote:
> > > > 1) FUTEX_UP and FUTEX_DOWN defines. (Robert Love)
> > > > 2) Fix for the "decrement wraparound" problem (Paul Mackerras)
> > > > 3) x86 fixes: tested on dual x86 box.
> > > >
> > > > Example userspace lib attached,
> > > > Rusty.
> > >
> > > I did a quick hack to enable ulockflex to run on the latest interface
> > > that Rusty posted.
> >
> > Cool... is this 8-way or some such "serious" SMP?  How about the
> > below microoptimization (untested, but you get the idea).
> >
> > > Now 3 processes
> > >  3  1  5  4 k      0   0   0   99.98   0.00   0.00 0.033284   242040
> > >  3  1  5  4 m     0   0   0    0.29   0.00   0.00 0.018406  1979992
> > >  3  1  5  4 f      0   0   0   99.71   0.00   0.00 0.028083   306140
> > >  3  1  5  4 c      0   0   0    7.79   0.00   4.00 0.437084   774175
> > >
> > > Interesting... the strict FIFO ordering of my fast semaphores limits
> > > performance as seen by 99.71% contention, so we always ditch
> > > into the kernel. Convoy Avoidance locks 2.5 times better.
> >
> > Hmmm... actually I'm limited FIFO, in that I queue on the tail and do
> > wake one.  Of course, someone can come in userspace and grab the lock
> > while the guy in the kernel is waking up, and this is clearly
> > happening here.
> >
> > This can be fixed, I think, by saying to the one we wake up "you have
> > the lock" and never actually changing the value to 1.  This might cost
> > us very little: I'll send another patch this afternoon.
> >
> 
> Well, yes it can be fixed as I did in my package, but it comes at a
> substantial cost as seen above. The question is whether to simply
> ignore strict FIFO requirements ?
> Doing the FIFO leads to the convoy problem, namely your lock arrival
> becomes the scheduling queue.
> As seen above from the nonexisting contention,  mootexes completely
> exhaust their scheduling quantum before allowing anybocy else to grap
> the lock. This is desired behavior particular for high traffic, low lockhold
> time locks, but not for others.
> 
> In this case you simply hand over the lock and won't allow anybody
> in user space to grap it during the time window one is woken up in
> the kernel.
> Also, from my own experience doing a spinning lock that way
> 
> Another issue, is a few more operations, what would be nice is to be
> able to wake up all waiting processes and have them recontent?

Unless you are ready to go to priority queues (IMHO the preferred
approach) this is the only way to avoid priority inversion, especially
in a real time environment.

-- 
George           george@mvista.com
High-res-timers: http://sourceforge.net/projects/high-res-timers/
Real time sched: http://sourceforge.net/projects/rtsched/