Re: web page on O(1) scheduler

From: Mike Galbraith (efault@gmx.de)
Date: Sun May 25 2003 - 04:17:04 EST

At 07:52 AM 5/22/2003 +0200, Mike Galbraith wrote:
At 08:38 PM 5/21/2003 -0400, Rik van Riel wrote:
On Wed, 21 May 2003, Mike Galbraith wrote:
> At 11:49 PM 5/20/2003 -0700, David Mosberger wrote:
> >Recently, I started to look into some odd performance behaviors of the
> >O(1) scheduler. I decided to document what I found in a web page
> >at:
> >
> > http://www.hpl.hp.com/research/linux/kernel/o1.php
>
> The page mentions persistent starvation. My own explorations of this
> issue indicate that the primary source is always selecting the highest
> priority queue.

It's deeper than that. The O(1) scheduler doesn't consider
actual CPU usage as a factor of CPU priority.

Oh, there's no doubt in my mind that it's _much_ deeper than my little surface scratchings ;-)

It does consider cpu usage though. Your run history is right there in your accumulated sleep_avg. Unfortunately (in some ways, fortunate in others.. conflict) that information can be diluted down to nothing instantly by new input from one wakeup.

Or did you mean that it misses a bunch of cpu usage? I went looking at cpu usage, and...

Unless there's something seriously b0rked in the attached (don't _think_ so, but...;), trusting an irq that happens 1/ms to tick tasks isn't 100% effective, even if you aren't context switching a zillion times faster. The attached diff produced the attached log while running test-starve.c. I get some pretty serious thievery even when doing ho-hum stuff. We can deactivate tasks at _really_ high frequency, and besides, if the timer interrupt doesn't fire while the last runnable task is active, he can be missed for a while and have accumulated up nearly a full ms. It seems to me that with the right timing, you could end up stealing a bunch of cpu (my logs say it's happening a _lot_ under load. again, diff might be b0rked)

-Mike

Attachment: xx.log
Description: Binary data

Attachment: xx.diff
Description: Binary data