Messages in this thread | | | Date | Thu, 27 May 1999 12:06:04 +0000 | From | Bernd Paysan <> | Subject | O(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/
| |