lkml.org 
[lkml]   [1999]   [May]   [29]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectO(1) scheduler
Hi!

I've made some thoughts about a O(1) scheduler that uses very simple
algorithms. Those are my ideas:

Run-priorities are managed as time budgets. The integer part of the time
budget is the run-priority.

The run queue is a bucked-sorted array of run-priorities. The processes
with same run-priority should be inserted in a LIFO order, this prevents
unneccessary task switches (just being run processes get a small bonus -
one could also use FIFO to give the not-been-run processes a bonus). A
search through the array is only necessary if the highest queue becomes
empty - then the next non-empty bucket has to be found.

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.

Once in a while, the time budgets have to be filled up - as they only
decrease through running processes. To filter out history, each task's
budget first is multiplied by a constant (0.9 or something like that).

RT tasks could have a fixed time budget (e.g. 30%), and therefore their
budget is increased by a constant, or they have a fixed priority, then
their budget is set to a constant. Normal tasks have a relative time
budget, depending on priority. Each task's budget is incremented by
budget*(delta_time/overall_budget). The overall budget is the sum of all
tasks budgets, and is changed when a task is created/deleted or reniced;
for delta_time, the fixed budgets of RT tasks have to be subtracted
first. Then, the active tasks have to be resorted - since this is a
bucket sort with no sub-order, that's O(n), too. There is no need to
perform this often.

The budget/priority relation could be something like
256*64k*(1.18^(-priority)) or something like that (precomputed in a
table, certainly), giving 256 times more run-time for a prio 0 task as a
prio 20 task, and again 256 times more for a prio -20 task (on average);
doublicating every 4 priority steps. The effective run-time also depends
on the filter function, so this has to be computed carefully, because
otherwise low-priority tasks can never accumulate enough budget to
become active (could be intented behaviour, too).

What do you think? It looks easy to implement, is almost always O(1),
and should give nice properties. For SMP, the tasks should be sub-sorted
by the processor they have run last on, to avoid migration (i.e. tasks
ready to run on the own processor are preferred, even if they have one
priority less than those on another processor, and are always preferred
if they have the same priority).

--
Bernd Paysan


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

\
 
 \ /
  Last update: 2005-03-22 13:51    [W:0.059 / U:0.168 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site