[lkml]   [1999]   [May]   [7]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: Overscheduling DOES happen with high web server load.
On Thu, 6 May 1999, Kurt Garloff wrote:

> 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
( 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).


Rik -- Open Source: you deserve to be in control of your data.
| Le Reseau netwerksystemen BV: |
| Linux Memory Management site: |
| Nederlandse Linux documentatie: |

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
Please read the FAQ at

 \ /
  Last update: 2005-03-22 13:51    [W:0.118 / U:5.712 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site