> If you are thinking of a new scheduler, would it be possible to design
> one that doesn't have to traverse the task_list as much as the current
> one? The current scheduler is O(n) in the number of processes. A fix
> to that would help the kernel ultimately end up being independent of
> the number of processes.
no, look harder ... the current scheduler only depends on the number of
_runnable_ processes (*). Search back a c.o.l.d discussion with DejaNews
where a kiva.com employee posted statistics that show that a heavy-duty
website has 1 runnable process 90% of the time, never going higher than
nr_runnable == 15 or so. Ie. schedule() is O(1) for a _busy_ webserver.
being independent on nr_tasks is _not_ the goal. The goal is to have a
fast scheduler, and thats not only schedule(), it's add_to_runqueue(),
remove_from_runqueue() and schedule(). And it's not the goal to have a
nice theoretical algorithm, which is, by the way, slower in RL. So the
goal is not to optimize <schedule()|1>, but to optimize <schedule()|RL()>.
[nevertheless it might be possible to build a faster scheduler, no doubt,
but not for the mentioned reasons].
Another point is the flexibility of goodness(). _Only_ this function knows
about 'scheduling policies', the rest of the scheduler is completely
generic. [independent of things like cache affinity, CPU affinity, RT
scheduling, <fill in whatever future feature>]
-- mingo
(*): isnt exactly true, we have (rare) 'recalculation' events which are
O(nr_tasks). They have a probability of 1/(20*nr_runnable), ie. decreasing
with more runnable processes and being very small even with 1 runnable
process). Unfortunately, there is one exception in 2.0.33 (recent 2.1
kernels are fixed), sched_yield(), it caused counter-recalculation for
every schedule(). This showed up in certain (valid, really scheduling)
benchmarks. Again, this was fixed recently in 2.1.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu