Auto-Adaptive scheduler - Final chapter ( the numbers ) ...

[Davide Libenzi]

On Fri, 28 Jan 2000, Marco Colombo wrote:
[..]

I'll skip all umor and related ...

> Please point me to the code you've written, instead of the books you've
> read. This way i can get a better picture of your ideas on OS designing.

If You'd readed the patch probably We can stop about speaking about cache
misses of the patch itself, and we're speaking about the real question that can
makes the patch die.
Can We admit such RQ loads in Linux, or We can say that in the rare cases
that shows this behaviour We can tollerate a non optimal scheduler response ?
Even if I've received mail from guys that has servers with RQ > 30, and as I've
stated into the opening message of this thread ( four question marks ), I'm all
but sure about the convenience of merging the patch itself.

"Kernel code bloat" vs. "Uman loads gain"  :  1 - 0

This is a good reject point.

Not about speaking of "great cache trashing", etc.. that the patch itself don't
have.

> 
> 		 long RQ <=> high loads			(1)
> 

With high loads I've ever meant high number of tasks in RQ ( since I'm
measuring scheduling times versus RQ length ), so for that it counts it's true.


> > How many switch / sec will do a system with RQ << 1 ?
> > Stay big say 500 ( keep this number in mind ).
> > 

As I've reported to Jamie this is a my "misses" ;)
Double misses ;))


> Let me state this: switch rate has *nothing* to do with load, nor does
> the RQ. [ And RQ is not the same of context switching rate, BTW ].

100 % agree.


> That's 1 
> That's 2
> That's 3
> That's 4

When Larry, Rik and Jamie state that long RQ are not usual, I agree
with them ( see question marks above ).
When They speak about cache misses, I agree with them if it's a general
discussion about the need of keeping low the cache footprint of the kernel
code, but I can't agree if we speak about a "great cache trashing" of the patch.


> 
> 		long RQ <=> broken design (somewhere)	(2)
> 

As I've said You in a private mail, I can agree with You here but I think You
can agree with me that this "broken design" exists.


> 
> 		long RQ <=> something very bad happening	(3)
> 

I prefer to reserve the phrase "very bad" for other things ;) , but I can agree
here.


> [analysis skipped]
> 
> > The data cache cost of the patch with RQ < "Cluster scheduler boot point" is
> > a variabile
> > onto the stack ( 4 bytes ), that thinking on about, I can even remove.
> > The code cache cost of the patch with RQ < "Cluster scheduler boot point" is
> > 0,
> > due to the fact that the code is the same of the previous scheduler.
> > There is the block of code of the cluster scheduler that can be moved out of
> > fast path,
> > but I think that It'll be better to keep it on fast path since we need it
> > faster under
> > high workloads not with RQ < 2.
> 
> Againg, you can have high workloads with RQ ~= 1!

As You see from my previous emails I've ever meant "high workloads" with 
"long RQ".


> > But all of this topics would be clear if that guys that shoot over my patch
> > cache misses,
> > would have readed it.
> 
> You should be reading, in the first place...

I insist, I You want to speak about cache misses read the patch.

> The cache issue mainly cames into play when the system is LOADED... and:
> - this can happen with RQ being small. The scheduler should be optimized
>   for that (and actually is), since this is the NORMAL condition under
>   high loads;

And my patch ? Please underline its cache misses more than the current scheduler
have and weight the difference with the current scheduler ones.

> - by the time you get a long RQ, the system is so overloaded (in real cases)
>   that the cache issue is a MAJOR one anyway, no matter the scheduler...

I can agree here, more a process run higher is the probability that it touches
new RAM locations.


> And, yes, I can think of a way to enlarge the RQ without other big
> system impacts. Just spawn N identical processes (or threads, whatever),
> doing just endless for(;;); and you'll see you RQ go to N.
> This is NOT a RL workload. And anyway you'll patch will have little
> effect on this. The scheduler gets invoked only 1/timeslice times a second.
> No matter how long the RQ is.

IRQs apart, this is an evidence.


> The only thing you can do to get the scheduler play a major role, is
> to have the threads do *nothing*, just release the CPU as soon as they
> get scheduled. I can't think of any real world application that will
> come close to that behaviour, unless it's very badly designed (or very
> badly used).

This is what threads.c do, but it's an instrument for switch times measurements.


To summarize ( and conclude ) with all guys that have taken part to discussion :

1) RQ > 30 exist in "nature" and is proved by vmstats ( of real loads not
benchs ) that other guys post me

2) We can agree to consider these cases as rare

3) We agree on keeping scheduler cache ( and icache ) footprint as low as
possible ( even if I think that to make a single cache miss to have a percent of
improvement You must push the system at high switch / sec )

4) We agree on the fact that improving scheduler switch times You don't have
a great overall gain. As You can see in the message that open this thread,
since the gain percent You get on the scheduler must be multiplied by the
schedule time percent You get about 5% with 40 threads.
Higher _scheduler_ performance will came with higher RQ, but I agree that
these are exceptional cases.

5) I don't agree when You say that the patch have a "great cache trashing".
This means that You've not readed the patch.

6) I can agree finally when You say to reject the patch due to the fact that,
as outlined above :

"Kernel code bloat" vs. "Uman loads gain"  :  1 - 0


Cheers,
Davide.

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