Menu
I might be a little late on this but I was going through how various production schedulers work recently and I came across the O(1) scheduler which was replaced by the Completely Fair Scheduler, or CFS, both by Ingo Molnár.
As the name suggests the O(1) scheduler takes constant time but CFS is O(log N). Then why was such a move made? Obviously, there must have been a good reason. If it has to do with making applications more responsive, then how does CFS help? (And why do others still use a multilevel feedback queue approach?)
261
CFS scheduler picks next process based on minimum virtual time and to get this value efficiently its using Red-Black tree(rbtree), using rbtree we will get minimum O(h) here h is height of rbtree. But, using min-heap we can get min virtual time process in O(1) time only.
CFS is quite simple algorithm for the process scheduling and it is implemented using RED BLACK Trees and not queues. So all the process which are on main memory are inserted into Red Black trees and whenever a new process comes it is inserted into the tree.
The vruntime is the virtual runtime of a process which helps in tracking for how much time a process has run. The vruntime is a member of the sched_entity structure defined in include/linux/sched.h. The min_vruntime represents the minimum vruntime of a cfs runqueue.
The LINUX Kernel used the O(n) scheduler between version 2.4 and 2.6. n is the number of runnable processes in the system. O(n) scheduler divides the processor's time into a unit called epochs. Each task is allowed to use at max 1 epoch.
A large part of it was because of internal 'competition' and confrontation with a chap called Con Kolivas. Sometimes you have to look at the people involved as much as the tech.
87
for interactivity and responsiveness as the reason this O(1) was moved out of stac
30
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
