> From what I understand, the scheduling is not caused by the timer
> but by blocking and woken processes.
Not only that, the fact that we're using a traditional O(n)
run queue is somewhat of a performance bottleneck.
I'm currently looking into the scheduler used by Alliance
(www.allos.org) and it looks very promising. If I have any
time left, I'll port it to Linux.
It's based on the idea of a priority heap. Processes have
a quantum and a defer value. The quantum value is the length
of the process' time slice and the defer value is the time
at which it will be run next (sort of a deadline).
The process at the top of the heap is the process with the
lowest (run next) defer value. After a process finishes it's
time slice, the defer value is incremented (say, by p->priority)
and the process is sorted down the B-tree. This means that the
algorithm for selecting the best process is O(1) on UP machines
and O(log(nr_cpus)) on SMP machines.
Schedule_timeout() can be replaced by a simple resorting of
the heap. Basically we only need to remove processes from
the heap if they do blocking I/O or wait for a signal
(otherwise they would clutter up the heap).
cheers,
Rik -- Open Source: you deserve to be in control of your data.
+-------------------------------------------------------------------+
| Le Reseau netwerksystemen BV: http://www.reseau.nl/ |
| Linux Memory Management site: http://humbolt.geo.uu.nl/Linux-MM/ |
| Nederlandse Linux documentatie: http://www.nl.linux.org/ |
+-------------------------------------------------------------------+
-
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/