CFS and O(1) scheduler

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

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

Re: CFS and O(1) scheduler
Quoted text here. Click to load it

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

Re: CFS and O(1) scheduler
Quoted text here. Click to load it

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

Juergen


Re: CFS and O(1) scheduler
Quoted text here. Click to load it

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

Re: CFS and O(1) scheduler
Quoted text here. Click to load it

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

Juergen

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 <the IP3K), and up to now single million-selling
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

Re: CFS and O(1) scheduler
vitalization -> virtualization. Oh zthis spell checker :)

Re: CFS and O(1) scheduler

Quoted text here. Click to load it

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

Quoted text here. Click to load it

Yes. What else should they do?

Quoted text here. Click to load it

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


Re: CFS and O(1) scheduler
Quoted text here. Click to load it

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

Quoted text here. Click to load it

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

Quoted text here. Click to load it

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.

Quoted text here. Click to load it

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

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

Re: CFS and O(1) scheduler
Quoted text here. Click to load it

Just curious, but why do you say that?

Quoted text here. Click to load it


Re: CFS and O(1) scheduler
Quoted text here. Click to load it

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

Re: CFS and O(1) scheduler

Quoted text here. Click to load it

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

Juergen


Re: CFS and O(1) scheduler
Quoted text here. Click to load it

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

Re: CFS and O(1) scheduler
On Dec 7, 12:37 pm, Michael Schnell
Quoted text here. Click to load it

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.

Re: CFS and O(1) scheduler
Quoted text here. Click to load it

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

Site Timeline