Interesting analysis of linux kernel threading by IBM

[Davide Libenzi]

On Sat, 22 Jan 2000, Sean Hunter wrote:
> On Fri, Jan 21, 2000 at 06:14:09PM +0100, Davide Libenzi wrote:
> > Hi James,
> > 
> > Friday, January 21, 2000 3:02 PM
> > James A Simmons <jsimmons en acsu.buffalo.edu> wrote :
> > > I know the guy form IBM is watching this thread. I see alot of boo and hah
> > > about this patch.
> > 
> > sure ? anyway everyone has its own opinions, but remember that You can
> > optimize the fast path and CPU cacheline
> > as You want, the algorithm still remain an O( N ) where N is the number of
> > processes in RQ.
> 
> Now, since we're talking Big-O notation, lets get some facts in with
> the theory.  O(log n) or even O(1) is not a benefit if the overhead of
> the implementation is high and n is low.  Low-overhead O(n^2) may be
> faster than high-overhead O(log n) for small values of n.  Now, since
> n is the number of runnable processes (usually low in all the
> real-world non-benchmark cases people have stepped up with), and the
> scheduler is very sensitive to overhead (being called hundereds or
> even thousands of times a second),  its very likely that low-overhead
> O(n) will beat even a pretty good O(log n) in the real world.
> 

We can write this :

TS_old = Ko + O( N )
TS_new = Kn + O( log( N ) )

Where N is the RQ size.

Now the curve of TS_new( N ) goes down ( intersect ) the curve TS_old( N ) in a
point that in the worse case I've measured is N = 8 ( I prefer always to report
worse cases to avoid to be shooted ), but I've measured even 4 with a medium
that I can think to be near to six.

> > 
> > > Before we do anything the patch really needs to be
> > > tested and studied under all types of conditions. When we have really
> > > numbers then we can chose what to do with the patch.
> > 
> > This is the thing we all want.
> 
> What I want is a scheduler that does _better_ not worse, at real
> loads, then we're on to a winner.

I'm working on a new version of my cluster scheduler that behave :

0 < N < Nx	TS( T ) = TS_old( T )

Nx <= N < INF	TS( T ) = TS_new( T )

I don't know if I'll succed but I'll try.


Davide.

-- 
All this stuff is IMVHO



-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo en vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/