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/
