[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Calculating timeslices in Linux scheduler

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.

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/