Re: Calculating timeslices in Linux scheduler

[Octavian Purdila <tavi@xxxxxxxxx>]

On Thursday 03 March 2005 01:40 pm, Bahadir Balban wrote:
> Hi,
>
> I am reading this nice paper by Josh Aas on the linux scheduler. On
> page 19, it says that timeslice calculation is O(1) rather than O(n),
> and for this it says:
>
> "Because timeslices are recalculated when they run out, there is no point
> at which all tasks need new timeslices calculated for them; that is, many
> small constant-time operations are performed instead of iterating over
> however many tasks there happens to be and calculating timeslices for them
> (which would be an undesirable O(n) time algorithm)"
>
> I am not convinced with this argument. You wouldn't make an O(n)
> algorithm O(1) by simply doing the calculation spread over time (still
> for each process, where the n comes from)  as they exhaust timeslices.
>

In 2.4 the timeslices were calculated each time schedule() was run, for every 
runnable process. Since only a few process were changing their timeslice 
between 2 consecutive schedule() runs, calculating the timeslices for all 
running processes has a clear overhead.

In 2.6, when schedule() runs, we don't calculate any timeslices, we just grab 
the best task and timeslices are calculated/updated only as they are needed.

tavi

--
Kernelnewbies: Help each other learn about the Linux kernel.
Archive:       http://mail.nl.linux.org/kernelnewbies/
FAQ:           http://kernelnewbies.org/faq/