Re: CFS and O(1) scheduler

On Dec 7, 12:37 pm, Michael Schnell
<mschnell_at_bschnell_dot...@xxxxxxx> wrote:
As it uses a red-black tree, it should only be O(log n) not O(n). Or am I
wrong?

That is beyond my insight in these algorithms.

It would be great to know which "O" is offers. (even thought it's off
topic in this newsgroup).

Supposedly for servers running a huge number of tasks, the O(1)
scheduler still is the best choice. Here you usually have enough cache
to tame the bigger memory need, too.

I suppose someone who sets up those beasts should be able to select and
install the scheduler he wants.

-Michael

Hi All,

Although I don't have much experience on CFS but according to my
understanding, CFS is also an O(1) scheduler. they have just made same
enhancement to O(1) scheduler to make it work completely fair to
different task. CFS is based on time needed by a process. Since it
maintains RB Tree and always pick the root node to run, its a O(1)
scheduler. It has a separate process to maintain RB tree which run
independent of scheduler.
.

Relevant Pages

  • Re: [PATCH 1/1] New documentation about CFS.
    ... Rewrite of the CFS documentation - because the old one was sorely ... +scheduler implemented by Ingo Molnar and merged in Linux 2.6.23. ... +timestamp and measure the "expected CPU time" a task should have gotten. ...
    (Linux-Kernel)
  • CFS review
    ... executed regions and it's often not exactly trivial code as cfs added ... The advantage of normalization is that it ... The next issue is scheduler granularity, ... int main ...
    (Linux-Kernel)
  • [announce] CFS-devel, performance improvements
    ... announce the latest iteration of the CFS scheduler development tree. ... Scheduler' patch as well and integrated them into CFS. ... metrics from CFS that might have been needed but ended up being ...
    (Linux-Kernel)
  • Re: [patch] CFS scheduler, -v8
    ... I am currently studying the linux scheduler and virtual memory manager to solve some page swapping problems. ... Authors of this paper proposed a scheduler: Earlist Eligible Virtual Deadline First (EEVDF). ... EEVDF uses exactly the same method as CFS to track the execution of each running task. ... EEVDF tries to schedule tasks based on the virtual deadline vd_i where a timeslice l_i should be finished. ...
    (Linux-Kernel)
  • Re: [PATCH] CFS: sched-design-CFS.txt - ambiguity about leftmost and some formatting
    ... this is the CFS scheduler. ... precise multi-tasking CPU" on real hardware. ... disadvantage - the current task gets an unfair amount of CPU time. ... the task schedules (or a scheduler tick happens) the task's CPU usage is ...
    (Linux-Kernel)