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.
I haven't read the actual paper so I can't comment on Josh's statements. However, making this particular algorithm O(1) has less to do with the calculations being spread over time and more to do with the fact that calculating the timeslices, among other things, is done when the task is moved to the expired priority array (when the task's timeslice expires) rather than calculating all tasks' timeslice when they all expire. It also has much to do with the two (active and expired) priority arrays and how the next task to run is picked using a bitmap representing all of the active priorities. So no matter how many tasks are in the runqueue, it never takes any longer to schedule the next task (this is the real source of the O(1) capability).
I haven't read the actual code but just the paper, so if you have a better explanation please share it.
Secondly, the paper says that the timeslice calculation is done by:
#define BASE_TIMESLICE(p) (MIN_TIMESLICE + \ ((MAX_TIMESLICE - MIN_TIMESLICE) * \ (MAX_PRIO-1 - (p)->static_prio) / (MAX_USER_PRIO-1)))
none of the variables here seem to be non-constant. So is this calculation once-only or done at every timeslice expiration?
Thanks, Bahadir
-- Kernelnewbies: Help each other learn about the Linux kernel. Archive: http://mail.nl.linux.org/kernelnewbies/ FAQ: http://kernelnewbies.org/faq/
-- Kernelnewbies: Help each other learn about the Linux kernel. Archive: http://mail.nl.linux.org/kernelnewbies/ FAQ: http://kernelnewbies.org/faq/
