Re: [Announce] [patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]

Nick Piggin
2007-04-17T06:44:48Z

On Tue, Apr 17, 2007 at 04:23:37PM +1000, Peter Williams wrote:
> Nick Piggin wrote:
> >And my scheduler for example cuts down the amount of policy code and
> >code size significantly.
>
> Yours is one of the smaller patches mainly because you perpetuate (or
> you did in the last one I looked at) the (horrible to my eyes) dual
> array (active/expired) mechanism.

Actually, I wasn't comparing with other out of tree schedulers (but it
is good to know mine is among the smaller ones). I was comparing with
the mainline scheduler, which also has the dual arrays.

> That this idea was bad should have
> been apparent to all as soon as the decision was made to excuse some
> tasks from being moved from the active array to the expired array. This

My patch doesn't implement any such excusing.

> essentially meant that there would be circumstances where extreme
> unfairness (to the extent of starvation in some cases) -- the very
> things that the mechanism was originally designed to ensure (as far as I
> can gather). Right about then in the development of the O(1) scheduler
> alternative solutions should have been sought.

Fairness has always been my first priority, and I consider it a bug
if it is possible for any process to get more CPU time than a CPU hog
over the long term. Or over another task doing the same thing, for
that matter.

> Other hints that it was a bad idea was the need to transfer time slices
> between children and parents during fork() and exit().

I don't see how that has anything to do with dual arrays. If you put
a new child at the back of the queue, then your various interactive
shell commands that typically do a lot of dependant forking get slowed
right down behind your compile job. If you give a new child its own
timeslice irrespective of the parent, then you have things like 'make'
(which doesn't use a lot of CPU time) spawning off lots of high
priority children.

You need to do _something_ (Ingo's does). I don't see why this would
be tied with a dual array. FWIW, mine doesn't do anything on exit()
like most others, but it may need more tuning in this area.

> This disregard for the dual array mechanism has prevented me from
> looking at the rest of your scheduler in any great detail so I can't
> comment on any other ideas that may be in there.

Well I wasn't really asking you to review it. As I said, everyone
has their own idea of what a good design does, and review can't really
distinguish between the better of two reasonable designs.

A fair evaluation of the alternatives seems like a good idea though.
Nobody is actually against this, are they?

> >I haven't looked at Con's ones for a while,
> >but I believe they are also much more straightforward than mainline...
>
> I like Con's scheduler (partly because it uses a single array) but
> mainly because it's nice and simple. However, his earlier schedulers
> were prone to starvation (admittedly, only if you went out of your way
> to make it happen) and I tried to convince him to use the anti
> starvation mechanism in my SPA schedulers but was unsuccessful. I
> haven't looked at his latest scheduler that sparked all this furore so
> can't comment on it.

I agree starvation or unfairness is unacceptable for a new scheduler.

> >For example, let's say all else is equal between them, then why would
> >we go with the O(logN) implementation rather than the O(1)?
>
> In the highly unlikely event that you can't separate them on technical
> grounds, Occam's razor recommends choosing the simplest solution. :-)

O(logN) vs O(1) is technical grounds.

But yeah, see my earlier comment: simplicity would be a factor too.