Messages in this thread | | | Date | Mon, 06 Mar 2000 00:09:00 +0100 | From | Bernd Paysan <> | Subject | Re: Why are Suns so slow? |
| |
[posted in comp.arch and comp.sys.intel, cc'ed to linux-kernel mailing list]
ttk@goblin.flyingcroc.net > The Linux community has made strong steps in all of these directions, > but still has a long journey ahead.
The last discussion when someone posted a O(1) scheduler to replace the O(n) scheduler (with a single global run-queue for all processors), there was a huge mumble bumble on the kernel mailing list about "introducing bloat" and "long runqueues don't happen" and "the constant factor is important" (which was almost zero for that algorithm, since he didn't use his improvements for very short run queues), so it's somewhat questionable. I don't see why they have a "long journey", since the scheduler algorithms in question are well-known text-book algorithms.
The basic principle of the BSD/QNX scheduler (and all other prioritized O(1) schedulers) is to have a run-queue for each priority (or "goodness" or whatever you call it - just quantisize it so that there aren't too many queues). When descheduling a process, you remember which one was the highest used run-queue, compute the priority of the process to deschedule, and put it into the corresponding run-queue - first to get a bonus for processes that are already cached in, last on sched_yield(). When scheduling, you take the first process out of the highest priority run-queue.
SMP-variation: keep separated run-queues for each processor. Usually schedule only within the own CPU's run-queue, and only look at other processor's run-queues, if their highest unscheduled priority is within some offset higher than yours. This means that for the average case, the scheduler is also lock-free (reading the global max-priority is atomic, and therefore doesn't need a lock - and updating is rare), and you get CPU preferrance for free.
Since a lot of things that are done explicit in the Linux goodness() function are done implicit here (like preferring processes that ran on the same CPU last time or to keep the previous process running as long as nobody has definitely higher goodness), the algorithm should have *lower* constant factor than the current O(n) scheduler, and should be already better if there is one process to run.
There were several patches to the Linux kernel in the past that all featured one of those O(1) schedulers, and none of them made it into the kernel. Linux kernel hackers: even though the BSDers are arrogant, they are not always wrong. O(n) schedulers don't belong to high-loaded servers. IMHO the 2.4er kernel should provide a lock-free O(1) scheduler (well, basically), if it should run well on machines with many CPUs.
-- Bernd Paysan "If you want it done right, you have to do it yourself" http://www.jwdt.com/~paysan/
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
| |