Re: O(1) scheduler

Andi Kleen (ak@muc.de)
Sat, 29 May 1999 10:08:09 +0200

>The run-priority of processes is determined by fine-grain time
>accounting. The scheduler would read the RTSC register (or the timer
>chip internal counter on pre-Pentium processors) once each time it needs
>rescheduling, and decrease the time budget of the currently active by
>the amount of time the process has been run. If the integer part (run
>priority) decreases, the process has to be moved to another bucket, and
>there is inserted at the front. Now the scheduler would schedule the
>first process in the highest bucket.

This has some problems:

- old CPUs that don't have a TSC, so you need a fall back.
- the standard TSC counts interrupts and bottom halves too. It would
be unfair to charge them to a process (I believe the SMP scheduler in 2.2
has the same problem)

I think you can do user mode only cycle counting using some performance
counter MTRRs on newer CPUs, but this gets really Vendor and Processor Type
dependent. Also it should work on non IA32 CPUs too.

On the rest I have no opinion.

-Andi

-
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/