CFS and O(1) scheduler - Embedded

This is a discussion on CFS and O(1) scheduler - Embedded ; Hi, Currently, Completely Fair Scheduler(CFS) is being used in 2.6.23 kernels . What is the drawback of O(1) scheduler that was in earlier kernels ? How can i visualise those differences ? I searched the internet, but i did not ...

+ Reply to Thread
Results 1 to 17 of 17

Thread: CFS and O(1) scheduler

  1. CFS and O(1) scheduler

    Hi,
    Currently, Completely Fair Scheduler(CFS) is being used in 2.6.23
    kernels .
    What is the drawback of O(1) scheduler that was in earlier kernels ?
    How can i visualise those differences ?

    I searched the internet, but i did not find a very elaborative
    document
    that talks in detail about this.
    Can someone here provide me a link for that ?

    Thx in advans,
    Karthik Balaguru

  2. Re: CFS and O(1) scheduler

    > What is the drawback of O(1) scheduler that was in earlier kernels ?

    I once was told, that the O(1) scheduler uses a lot more (program code
    and) RAM than the old O(n) scheduler and thus in a system that uses
    cache not in a very optimized way (especially ARM is said to be bad here
    as the cache is between the CPU and the MMU and not between the MMU and
    the RAM) the O(1) scheduler slows down the overall performance if there
    is not a huge amount of active processes/threads. In embedded systems
    usually there are not that many processes.

    I don't know anything about the "Completely Fair Scheduler". so I can't
    comment on that one.

    -Michael

  3. Re: CFS and O(1) scheduler

    karthikbalaguru wrote:
    > [...]
    > I searched the internet, but i did not find a very elaborative
    > document that talks in detail about this.
    > Can someone here provide me a link for that ?


    http://people.redhat.com/mingo/cfs-s...design-CFS.txt

    Juergen


  4. Re: CFS and O(1) scheduler

    >
    > http://people.redhat.com/mingo/cfs-s...design-CFS.txt
    >


    Thanks for the interesting explanation on the CFS.

    The article is wrong when stating that there is no processor that does
    completely fair scheduling in hardware. This is _exactly_ how explicit
    multithreaded processors are designed.

    See the ip5K processor (www.ubicom.com). Same has ten hardware "threads"
    and with each clock cycle a scheduling table decide which of the active
    ones is executed. So you can make several processes run at exactly the
    same speed or define a different scheduling (e.g. 50%, 25%, 12,5% 12,5%
    and such). Of course there also is a simple priority scheme additionally.

    -Michael

  5. Re: CFS and O(1) scheduler

    It seems that the CFS imposes an scheduling overhead of O(n). While this
    is perfectly appropriate for just a few threads, the O(1) scheduler
    should be faster with thousands of threads (which of course is never
    relevant with "embedded" Linux).

    -Michael

  6. Re: CFS and O(1) scheduler

    Michael Schnell wrote:
    > It seems that the CFS imposes an scheduling overhead of O(n).


    Just curious, but why do you say that?

    > While this
    > is perfectly appropriate for just a few threads, the O(1) scheduler
    > should be faster with thousands of threads (which of course is never
    > relevant with "embedded" Linux).


    > -Michael


  7. Re: CFS and O(1) scheduler

    >> It seems that the CFS imposes an scheduling overhead of O(n).
    >
    > Just curious, but why do you say that?


    The text suggests that it does not create multiple complex lists. AFAIK,
    this is how the O(1) scheduler provides the O(1) feature but at the same
    time imposes a lot more overhead then the old O(n) scheduler when there
    are only a few threads.

    But of course I may be wrong.

    -Michael

  8. Re: CFS and O(1) scheduler

    Michael Schnell wrote:

    > It seems that the CFS imposes an scheduling overhead of O(n). While this
    > is perfectly appropriate for just a few threads, the O(1) scheduler
    > should be faster with thousands of threads (which of course is never
    > relevant with "embedded" Linux).


    As it uses a red-black tree, it should only be O(log n) not O(n). Or am I
    wrong?

    Juergen


  9. Re: CFS and O(1) scheduler

    Michael Schnell wrote:
    >>
    >> http://people.redhat.com/mingo/cfs-s...design-CFS.txt
    >>

    >
    > Thanks for the interesting explanation on the CFS.
    >
    > The article is wrong when stating that there is no processor that does
    > completely fair scheduling in hardware. This is _exactly_ how explicit
    > multithreaded processors are designed.


    No, the article is right. Perhaps it should state "...there is no perfect
    processor *everyone have* ...". ;-)

    Juergen

  10. Re: CFS and O(1) scheduler

    >
    > 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

  11. Re: CFS and O(1) scheduler

    On Dec 7, 12:37 pm, Michael Schnell
    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.

  12. Re: CFS and O(1) scheduler

    > 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.


    Now this again is interesting regarding embedded use.

    I learned that it needs a lot of code and RAM to do an O(1) scheduler.

    While with many processes, this is very appropriate, for embedded
    projects with only a few active processes, the old O(N) scheduler is a
    lot faster - especially when the cache size is limited, which also is
    true with most embedded projects.

    So it might be a good idea to use the old O(N) scheduler with (small)
    embedded devices. Is there a possibility to drop same in when compiling
    the Kernel ?

    -Michael

  13. Re: CFS and O(1) scheduler

    What I find disturbing on that issue is that the software developers and
    the hardware developers seem to live on different planets.

    E.g. the extremely talented (free open source) software developers don't
    know about the revolutionary "explicit multithreading" CPU design.
    Instead they concentrate mainly on mainstream hardware like IA32,
    IA32-64, IA64, PPC and ARM. They even ignore the greatly evolving
    virtual CPUs in FPGAs (such as NIOS, MicroBlaze and MICO), that are
    extremely suitable for many embedded projects. There are Linux ports for
    all of them, but supposedly there is no chance to see them fully
    supported in the main Linux tree some day soon. I would wish for these
    CPUs and the IP5K (no Linux port on the horizon yet) to get more
    acknowledgment in the open source community.

    And the extremely talented (commercial) hardware developers (e.g. at
    Ubicom, maybe not the "inventors" of this CPU architecture, but those
    who did the first multithreaded chip) don't build the OS that comes with their SDK on the
    work of the Linux community, even though the 5K Chip would be able to
    run µCLinux with great performance and is very suitable for vitalization
    in order to support "virtual peripherals" (i.e. extremely hard
    realtime). Instead the 5K SDK comes with their propriety (though
    provided with all sources) OS. As of next year, same is said to be
    upgraded to offer a POSIX API. IMHO, a Linux port would be the much
    better investment.

    -Michael

  14. Re: CFS and O(1) scheduler

    vitalization -> virtualization. Oh zthis spell checker

  15. Re: CFS and O(1) scheduler

    Michael Schnell wrote:

    > What I find disturbing on that issue is that the software developers and
    > the hardware developers seem to live on different planets.


    Full ACK. Did you ever discuss with a hardware developer about some stupid
    hardware details that runs me (software dev) crazy?

    > [...] they concentrate mainly on mainstream hardware [...]


    Yes. What else should they do?

    > I would wish for these
    > CPUs and the IP5K (no Linux port on the horizon yet) to get more
    > acknowledgment in the open source community.


    This CPU sounds very exotic....

    If you pay for the development, I think you will get the support you wish to
    have. Free beer != free speek....

    Juergen


  16. Re: CFS and O(1) scheduler

    >
    > Full ACK. Did you ever discuss with a hardware developer about some stupid
    > hardware details that runs me (software dev) crazy?


    Yep ! But happily I'm the senior in the company right now .

    >
    >> [...] they concentrate mainly on mainstream hardware [...]

    >
    > Yes. What else should they do?


    OK. At the moment it seems to be more important to help Linux with the
    fight for the desktops.

    But I'm doing embedded work and thus...

    >
    >> I would wish for these
    >> CPUs and the IP5K (no Linux port on the horizon yet) to get more
    >> acknowledgment in the open source community.

    >
    > This CPU sounds very exotic....


    IMHO, it's the best CPU design available for embedded stuff. From the
    programmer's POV it looks like 10 CPUs that you can dynamically balance
    the performance of.

    I did an in-depth research on embedded CPU chips and finally the 5K got
    the second place for our application, the NIOS in an Altera FPGA being
    the winner, mainly due predicted design lifetime and the use of Linux.

    >
    > If you pay for the development, I think you will get the support you wish to
    > have. Free beer != free speek....
    >


    OK. I'm about to start with the NIOS project and happily I found a very
    active support for NIOS on the µCLinux mailing list. I suppose on the
    long run I'll be able to contribute some little pieces, too.

    Of course this is driven by work payed by companies that use Linux in
    their embedded devices or that provide chips, but it's open source work
    and should result in code that is worth to be accepted in the main tree.

    -Michael

  17. Smile Re: CFS and O(1) scheduler

    1. CFS is of O(log2n) complex and o(1) is as its name represents
    2. CFS is used for higher accuracy and granular preemption where o(1) is also but not as much nano second granular as CFS.
    3. CFS is known for fairness and interactivity..where as O(1) losses after a threshold.
    4. CFS basically a scheduler for desktop, and microkernel devices for its benifits.

    Shubham Tiwari ( : ) )

+ Reply to Thread