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. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
