CFS and O(1) scheduler

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

Juergen

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

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

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

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

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

Juergen

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

Juergen

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.

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

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

vitalization -> virtualization. Oh zthis spell checker :)

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

Yes. What else should they do?

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

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

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

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.

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