Slashdot Mirror
The Completely Fair Scheduler
hichetu writes "Kernel trap has a nice summary of what is going on behind the scenes to change the Linux Scheduler. The O(1) Linux scheduler is going to be changed so that it is fair to interactive tasks. You will be surprised to know that O(1) is really too good not to have any side-effects on fairness to all tasks."
That is for scheduling background tasks that run once a day (or whatever you set it to)
This is for scheduling CPU resouces in real time. To decide if Firefox or Apache is going to be executed the following split second.
In computer science, Big O notation is used for the complexity of a task.
> What it could really do with is I/O prioritisation.
ionice. Available since 2005-08-28.
> And an equivalent of "top" for monitoring processes' I/O activity would also be extremely handy
I agree, that would be nice.
A scheduler is the piece of software that brings you the illusion of multi-tasking. Because a single processor (with a single core) can only run one process at the same time, the operating system switches the process currently running. And it does this very fast (IIRC up to 1000 times a second in the case of linux).
The scheduler decides which process runs when and has to make sure that no process has to wait in the queue forever without getting his share of CPU time (this is what is called "starving").
Since the scheduler is a program by itself, it has a specific runtime characteristic, usually dependent of the number of programs waiting for their CPU share. The special property of the current scheduler in linux is that its runtime is in fact independent of this number. That's expressed in CS by O(1).
Here's how Linux 2.6.x task scheduler works:
- A "runqueue" keeps track of all essential tasks assigned to a given CPU [Queue is O(1) efficient]
- Each runqueue contains two priority arrays, the active and the expired. As a task completes, it is moved (during the move, the new timeslice is calculated - the point of debate and largest fundamental change to the task scheduler) [Moving from static array to static array is O(1) efficient]
- When the active priority array is finished, the expired array becomes the active array [Swapping 2 pointers is O(1) efficient]
- The priority arrays are of fixed length 140, as that is the amount of priority levels Linux has [O(140) = O(1)]
The point of debate comes if two threads have the same priority, in which case they are put on a round robin in the priority array. However, the confusion comes in that the execution is O(n) (which makes sense if you think about it), but the scheduler itself handles these at O(1) efficiency.My UID is a prime number. Yeah, I planned that.
Well, yes & no. It really was Con's RSDL that got ppl looking seriously into changing the mainline scheduler (there already being several out-of-mainline alternatives like nicksched, etc.)
Con's scheduler seemed to work better at higher workloads than the mainline, by just trying to distribute load evenly and not trying pretty interactivity tricks. But several ppl did say it didn't perform well for certain X client workloads. That's when Ingo's CFS was posted.
There really is 2 alternatives Ingo's CFS & Con's SDL that's being simultaneously tested by the kernel developers now, and none is accepted into mainline.
So it wouldn't be fair to say that CFS is *the* next Linux scheduler. It could be SDL as well.