CFS vs O (1) scheduler

I think many have heard that in addition to the standard O (1) scheduler in linux, CFS (Completely Fair Scheduler; "absolutely fair scheduler") appeared, which Ingo Molnar is working on . Actually, I would like to devote this note to a comparison of these two schedulers and a brief review of their main algorithms. At the end of the note, you can read a bit about FreeBSD's ULE scheduling.

preamble:

• O (1) scheduler - in short, the scheduler policy was quite simple: each cpu had 2 queues: in one there are tasks that will be launched soon, in the other - sleeping tasks. when the first stage turned out to be empty, it changed places with the second, respectively, in the second stage, all sleeping processes “woke up”, and in the first it served as a queue for exhausted and asleep processes. therefore, the running time of the algorithm, firstly, does not depend on the class of processes, and secondly, it is constant - O (1).
• Completely Fair Scheduler - uses a red-black tree to store processes , where the key is the wait_runtime of each process. wait_runtime is the number of nanoseconds that a given process has failed or reworked. those. if it is <0, then it processed, if it> 0, then it is underworked. this measure allows you to detect out-of-ballance from the 'ideal case'. depending on the value of wait_runtime, the process takes its place in the tree. if wait_runtime <0, then, I believe, the process will sit at the lower levels, if greater than 0, then closer to the top. therefore, CFS is not an O (1) scheduler , it is O (logN).

amble:
someone might have seen an article on slashdot about how the creator of the bsd's ULE scheduler, Jeff Roberson , commented on CFS:

Imagine that you are working with hundreds or even thousands of running threads, cache misses in case of log n bypass can be quite expensive. Especially because you will have much more scheduling events with so many threads

Indeed, extracting the next process from the tree sometimes requires rebalancing, inserting the process into the tree requires a single polyline and possible rebalancing. but this drawback only manifests itself at a very large n, which is very unlikely to be found on desktops, but can be found on large work stations. from here we can conclude: it is not worth it to install this scheduler on loaded servers / work stations and other machines that are designed to work with a large number of simultaneously running processes / threads.

but this flaw manifests itself like this:

Ingo said that having 1000 running tasks (task - process or thread), the system will increase the cost of context switching ( context switching ) by 20%. This is a tree of 10 levels. In the worst case, another 5 levels may be added, which will lead to a 30% increase in value. It’s not fatal, but you won’t call it good behavior either.

the disadvantages of O (1) scheduler can be attributed to insufficiently good, 'fair' core rebalancing. here is what Ingo himself says in this comment:

The easiest way to describe this is with a simple example: if I run glxgears on my own, it will use exactly 50% of the CPU. If I use the SD scheduler (aka O (1) scheduler) and run the CPU hog on it along with glxgears, both tasks will share the CPU resources. CPU hog will get ~ 60% of the processor time, and glxgears will get 40%. If I use CFS, both tasks will receive 50% of the processor time.

CFS really better allocates better CPU time and scatters tasks around the cores (proven by personal practice).
Also, the advantages of CFS include a significantly shorter response time than O (1). This is confirmed by tests made by Michael Piatrowski. see the results here . Thus, CFS can be safely installed on the desktop, where there is no huge number of simultaneously running processes.

How to install CFS:

First of all, I note that CFS is available for kernels starting with version 2.6.20.
You can get the patch for the kernel version> = 2.6.20 here .
Next, go to the directory with linux sources and apply the patch:

# patch -p1 <sched-cfs-v2.6.2x.1-x.patch

Also, a separate git repository has been allocated for the development of the CFS scheduler . You can pull the repository clone from here .

fw about ULE:

each cpu has 3 queues indexed by priority. 2 queues are used to implement sheduling-classes such as interrupts, rial time and time sharing. the last queue is used for the idle class.
The queue switching policy is similar to O (1) shceduler, i.e. when one line is empty, it is immediately replaced by another. Therefore, the switching time does not depend on the class of processes.
ULE also uses flexible and efficient policies on SMP systems, according to Jeff, scattering tasks between CPUs (cit.) “at least no less than fair than an absolutely fair scheduler.”

more about ULE: ULE.pdf and here .

in fact, it was a test note, as it is the first in this blog. from here there are several questions for those who read: would you be interested to read more (much) in more detail about the implementation of CFS and is it worthwhile to translate further any quotes inserted into the context of the note from English?
Thanks for attention.