×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Linux Gets Completely Fair Scheduler

kdawson posted more than 6 years ago | from the take-turns-now dept.

Software 274

SchedFred writes "KernelTrap is reporting that CFS, Ingo Molnar's Completely Fair Scheduler, was just merged into the Linux kernel. The new CPU scheduler includes a pluggable framework that completely replaces Molnar's earlier O(1) scheduler, and is described to 'model an "ideal, precise multi-tasking CPU" on real hardware. CFS tries to run the task with the "gravest need" for more CPU time. So CFS always tries to split up CPU time between runnable tasks as close to "ideal multitasking hardware" as possible.' The new CPU scheduler should improve the desktop Linux experience, and will be part of the upcoming 2.6.23 kernel."

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

274 comments

crap (5, Funny)

cachimaster (127194) | more than 6 years ago | (#19820885)

just finished make xconfig;make from 2.6.22!

Kernel building is pretty fast (3, Insightful)

EmbeddedJanitor (597831) | more than 6 years ago | (#19820943)

Should take you less than 15 minutes to get there again.

If you really want a rough time, see how long it takes to rebuild a different OS.

Re:crap (-1, Troll)

Anonymous Coward | more than 6 years ago | (#19821389)

The new CPU scheduler should improve the desktop Linux experience

Great. A new scheduler will surely attract more masses to Linux than, say, a non-ugly GUI-lib or a sane, standard windowing-environment would. That's the way to go.

Re:crap (2, Funny)

setagllib (753300) | more than 6 years ago | (#19821425)

With desktop environments like GNOME taking up more CPU time per user than all Google servers combined, a strong scheduler is desirable to make it at least sort-of tolerable. Although really, switching to KDE is known to have a much stronger positive effect.

Re:crap (4, Interesting)

Anonymous Coward | more than 6 years ago | (#19821667)

a fair scheduler won't help. BeOS had a very snappy, responsive GUI by being multithreaded (each window was a thread) and giving window/display threads higher priority. Even if the CPU(s) were bogged down with other threads, moving windows, the display stayed responsive. X is single threaded and the window manager architecture makes the problem worse. A fair scheduler doesn't help; it actually makes things worse.

Re:crap (4, Informative)

Hikaru79 (832891) | more than 6 years ago | (#19821753)

Great. A new scheduler will surely attract more masses to Linux than, say, a non-ugly GUI-lib or a sane, standard windowing-environment would. That's the way to go.


Well, no offense, but I'm glad it isn't you that's in charge of making important decisions in that case. I realize that you were probably less than half-serious, but I would hate for the Linux community to ever be in the stage where "attract more masses" is a goal that diverts effort from interesting projects like this one.

With that said, what's wrong with Qt/KDE, particularly the new versions (the ones still in Alpha)? I'd say it is very much a "non-ugly GUI lib", and a "sane windowing environment".

Equal opportunity, affirmative action scheduler (4, Funny)

EmbeddedJanitor (597831) | more than 6 years ago | (#19820887)

For the really touchy-feely OS out there!

Re:Equal opportunity, affirmative action scheduler (2, Funny)

ArcherB (796902) | more than 6 years ago | (#19820923)

For the really touchy-feely OS out there!
Does this mean all apps will play nice? [about.com]

Re:Equal opportunity, affirmative action scheduler (4, Funny)

Lithdren (605362) | more than 6 years ago | (#19821111)

No it just means programs wont crash other programs based purly on the programming langauge that was used to bring them into being. All languages were created equal.

Except Basic. Nobody likes basic.

Re:Equal opportunity, affirmative action scheduler (5, Funny)

Anonymous Coward | more than 6 years ago | (#19821129)

It also means that tasks which were denied adequate runtime in the past will now be favored over current tasks, to make up for the prior unfairness. :)

Re:Equal opportunity, affirmative action scheduler (5, Funny)

Anonymous Coward | more than 6 years ago | (#19821187)

Except Basic. Nobody likes basic.
goto hell you insensitive clod!

Fairness (0, Offtopic)

bdjacobson (1094909) | more than 6 years ago | (#19821477)

What is it about us nerds/geeks that we like things to be completely fair?

Also, lately I've found that life is a lot less stressful when you stop worrying about things being fair or not; and stop worrying that you might have gotten the short end of the stick. Another thing-- all those dreams of grandiosity every nerd/geek has (wooing the beautiful girl, or being the life of a party, etc; but just can't seem to accomplish), you feel far more empowered to do them when you get a full night's sleep, as opposed to staying up running that instance again for the loot, and then being tired the next day. If you treat your school/college work like a game that you want to master (for a very real benefit I might add-- sure, being the best at Fourier transforms might not net you a top NSA job because the government network was brute-forced in 15 seconds by Megatron's minions, but there are more subtle ep33n enhancements that can add up to something similarly lofty in enough time) the point becomes to learn the material not just finish the problems and turn it in. Then you start getting 100's on tests and it feeds back into itself and you know if you want to accomplish something, you can. Then you have fun and try updating your clothing and hair style, and then when you're really cooking you start walking around like a badass because you know you are one. Quite fun actually. But you never get there if you don't learn to give up the petty things (fairness) that get under your skin for the bigger picture of learning to control your charisma.

What I'd rather have... (1)

techno-vampire (666512) | more than 6 years ago | (#19821833)

wooing the beautiful girl...


I think I speak for geeks everywhere when I say that I'd rather have the beautiful girl wooing me!

Re:What I'd rather have... (1)

bdjacobson (1094909) | more than 6 years ago | (#19821871)

wooing the beautiful girl...



I think I speak for geeks everywhere when I say that I'd rather have the beautiful girl wooing me!

No no no those are the aggressive type. A PITA to have a relationship with.

It's Worse Than That (4, Funny)

grcumb (781340) | more than 6 years ago | (#19821581)

A complete fair scheduler for geeks? I can just see it:

PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
1 user 16 0 1464 184 140 S 90.0 86.1 0:01.93 wank
2 user RT 0 0 0 0 S 10.0 13.9 0:00.00 porn
3 user 34 19 0 0 0 Z 0.0 0.0 0:00.00 work
4 user RT 0 0 0 0 Z 0.0 0.0 0:00.00 socialise
5 user 10 -5 0 0 0 Z 0.0 0.0 0:00.31 getadate

Neato (4, Insightful)

friedman101 (618627) | more than 6 years ago | (#19820899)

What sort of gain can the typical linux user expect because of this?

Re:Neato (0)

Anonymous Coward | more than 6 years ago | (#19821063)

Read the FAQ: You will be fairly scheduled, even if you are a complete loser.

Re:Neato (4, Interesting)

fm6 (162816) | more than 6 years ago | (#19821865)

If you mean the typical user running Linux on their PC: probably no effect at all. But a better scheduler would make a lot of difference to a server. And that's the growth market for Linux these days.

Cool (1)

Ximok (650049) | more than 6 years ago | (#19820911)

I had always been impressed with Linux's scheduler. The fact that it is getting better, just makes me happy.

--Insert Microsft Bash Here... not the CLI

Re:Cool (2, Interesting)

tkavanaugh (863507) | more than 6 years ago | (#19821409)

I've always been more impressed with the Solaris' scheduler, I've done a few ports recently of realtime applications to linux from solaris 8 and 10 that have a hard time running properly under linux...
Of course these applications have had years of tuning under SOlaris so it's not an entirely accurate example...

Re:Cool (3, Insightful)

HairyCanary (688865) | more than 6 years ago | (#19821447)

Ha, I was about to come in and say the same thing. I've always been disappointed in the Linux scheduler compared with my Solaris servers. I run an ISP and frequently get abnormally high load spikes -- my Linux servers handle the load poorly, degrading all of the sudden to gridlock. The Solaris servers, on the other hand, degrade gracefully, still serving up requests but getting slower as the load skyrockets.

Cool-If Bush wrote operating systems. (1, Funny)

Anonymous Coward | more than 6 years ago | (#19821437)

"I had always been impressed with Linux's scheduler. The fact that it is getting better, just makes me happy."

I like the "No task left behind" scheduler too.

AWESOME!!!!!!!!!! (-1, Troll)

Anonymous Coward | more than 6 years ago | (#19820913)

You slashdot people are such faggots!

Process Neutrality? (5, Interesting)

Speare (84249) | more than 6 years ago | (#19820917)

I know enough about process scheduling to fill a ketchup cup at the nearest burger joint, but it struck me that this sounds like the debate about "network neutrality" vs "tiered service." The O(1) was supposed to be a very generic decision-making system that made a decision in a very agnostic way (to simplify the work down to a predictable consistent order of work). This CFS strikes me as a system which will have a much higher level of complexity and context awareness, which sounds like some processes will get more than others. The intention is to make it fair in the real world but not necessarily balanced, since not all processes are alike in their needs or expectations of task switching.

This is just rambling on, and admittedly it may be straining a metaphor too far, so don't go crazy biting my head off for not knowing all things about the kernel. See 'ketchup cup' above.

Re:Process Neutrality? (1)

Ximok (650049) | more than 6 years ago | (#19820967)

My knowledge is also limited, but if I understand correctly: if a process under the new CFS system requests more processing time (like say a realtime application) it will have a better chance of getting that time in a timely fashion.

Please someone correct me if you know more.

Re:Process Neutrality? (1)

Tacvek (948259) | more than 6 years ago | (#19821571)

I think nice levels have more to do with that.

I'm thinking what is going on is that programs are often returning part of their timeslice (perhaps because they are waiting for something, so each cycle consists of a breif check of that, followed by returning the rest of the timeslice) will be able to get a larger percentage of the CPU time later, such that the average amount of time the program gets is the same. Basically the idea is to ensure that if there are 'n' processes running, overall they will each average '1/n' of the total CPU time (assuming all have the same nice levels etc.). But I may be totally wrong here too.

The most simple (but terribly naive) scheduler would be one that gives each process a slice of time, in some order, perhaps by the process number, repeating at the beginning when it reaches the end. Obviously that does not allow for many complications, such as processing having different nice levels (priority levels), and processes that give back part (most) of their timeslice some of the time would end up having much less total CPU time over (for example) a 5 minute period than one that always used all of its timeslice.

Re:Process Neutrality? (5, Informative)

Anonymous Coward | more than 6 years ago | (#19821035)

Sort of. Scheduling algorithms are very important for routers too. So there is an analogy. But the analogy isn't with a tiered internet. It's with protocol based QoS. For instance, VoIP requires very low latency, but BitTorrent doesn't. So shaping traffic so that VoIP stuff gets handled by a router first (while minimally affecting BitTorrent) improves the quality of service. On the kernel scheduling side of the analogy, some software needs to have quick access to the processor, often, but for short periods of time. A GUI interface is an example. Real-time software is a more important example.

A tiered internet is something else entirely.

Re:Process Neutrality? (1)

ZachMG (1122511) | more than 6 years ago | (#19821123)

So it won't take twice the bandwidth?

The hope is (0)

Anonymous Coward | more than 6 years ago | (#19821203)

I believe to expose multiple tasks to as much bandwidth as possible, fairly.
Isn't that kooky?

Re:Process Neutrality? (2, Interesting)

mc6809e (214243) | more than 6 years ago | (#19821855)

Scheduling algorithms are very important for routers too. So there is an analogy. But the analogy isn't with a tiered internet. It's with protocol based QoS.


The analogy with a tiered internet is fine, provided you look back far enough in the history of computers.

Before personal computers became common, people got a lot of their work done by renting time on mainframes. People that wanted cheap CPU cycles had their jobs wait for spare cycles. Those that needed immediate answers paid more and their jobs got a higher priority.

In essence some people paid more for lower latency while others that could wait got a discount.

Re:Process Neutrality? (1)

DrkShadow (72055) | more than 6 years ago | (#19821333)

To me, it seems to sound more like QoS:

The processes under the new scheduler are awarded CPU time as needed, as opposed to blindly. Yet at the same time, you're not discriminating solely on the user running the process.

I'd say it sounds good, but I'm not sure how internet analogies work vs processor time...

and on an off note, I really would like it to improve things cause my linux experience (wine * 3, azureus, md5summing/sorting/awking 500 meg files, multiple times in a row) tends to be exceedingly jerky, slow, and can be brought to its knees relatively easily. Even significantly worse than Windows at times. I rather want to try this scheduler to see how things go; though I just installed kernel 2.6.22 and have noticed improvement with the CFS IO scheduler. Interesting.

-DrkShadow

Re:Process Neutrality? (1)

Chandon Seldon (43083) | more than 6 years ago | (#19821395)

and on an off note, I really would like it to improve things cause my linux experience (wine * 3, azureus, md5summing/sorting/awking 500 meg files, multiple times in a row) tends to be exceedingly jerky, slow, and can be brought to its knees relatively easily.

Do you have enough RAM? That sounds more like thrashing than any kind of CPU scheduling issue.

Re:Process Neutrality? (2, Informative)

the_greywolf (311406) | more than 6 years ago | (#19821669)

It works quite well. I use Con Kolivas' SD scheduler (on which CFS is based), and in a similar situation (with heavy I/O and numerous power-hungry apps), it performs exceedingly well.

Ingo tests CFS with a kernel make -j50 - just to give you an idea of what we're shooting for here.

Re:Process Neutrality? (5, Informative)

DreadSpoon (653424) | more than 6 years ago | (#19821377)

I think you have this TOTALLY backwards.

The old scheduler was filled with huge chunks of complex code to try to guess at which processes were interactive and such, and would then specially treat those processes differently when scheduling.

The CFS does none of that. It schedules all processes the same, in a completely fair manner, and doesn't have any special logic in it that tries to classify processes at all, other than nice levels.

The part yet to be merged is the process grouping, which again isn't anything like the interactivity guessing code. It's just a simple way to say "these processes belong together, so when you do the CPU scheduling, treat them as a single group." It's basically just a weighting mechanism with a logical container.

Re:Process Neutrality? (2, Insightful)

Anonymous Coward | more than 6 years ago | (#19821503)

The crucial difference is that the CFS gives/takes processor time to/from processes purely based on improving the overall processor throughput and "responsiveness" of the system. CFS makes its decisions exclusively from a technical standpoint.

This is not comparable to tiered network service because tiered network service makes decisions on what data packets to carry/drop based on political, legal, and business policies.

As an example, CFS will probably place a low priority on background backup tasks and a high priority on real-time audio applications because users will quickly notice if their audio files are skipping but are less likely to notice/care if their backups take slightly longer. This is a feature of a quality scheduler. However, if CFS further increased its preference for real-time audio applications because the programmer owned stock in several music companies then that would be an example of a "tiered service scheduler".

Prediction ... (2, Informative)

Gopal.V (532678) | more than 6 years ago | (#19820929)

I've sort of gazed for a few seconds at the CFS articles and the following phrase caught my attention the most

it uses a time-ordered rbtree to build a 'timeline' of future task execution

But more importantly, I think the factor which'll probably sway me the most is /proc/sys/kernel/sched_granularity_ns. Except I've been salting my config options with one true test [slashdot.org] ... that kind of thing makes you paranoid about random tune-ups :)

For the attention of karma whores (5, Funny)

SoVeryTired (967875) | more than 6 years ago | (#19820983)

Karma Whores:

Steal your insightful comments from http://linux.slashdot.org/article.pl?sid=07/04/22/ 1335255 [slashdot.org]

Re:For the attention of karma whores (4, Insightful)

garcia (6573) | more than 6 years ago | (#19821065)

The sad thing is that the summary reads almost identical:

"Kernel trap has a nice summary of what is going on behind the scenes to change the Linux Scheduler. The O(1) Linux scheduler is going to be changed so that it is fair to interactive tasks. You will be surprised to know that O(1) is really too good not to have any side-effects on fairness to all tasks."

Isnt this called Cron? (4, Funny)

TheVelvetFlamebait (986083) | more than 6 years ago | (#19821117)


I thought Linux used Cron as a scheduler ?
 

Re:Isnt this called Cron? (2, Informative)

Anonymous Coward | more than 6 years ago | (#19821335)

That is for scheduling background tasks that run once a day (or whatever you set it to)

This is for scheduling CPU resouces in real time. To decide if Firefox or Apache is going to be executed the following split second.

Why... (4, Funny)

lawpoop (604919) | more than 6 years ago | (#19821005)

Why does this sound like the title of a Monty Python Skit?

"Why isn't my process getting more CPU time?"

"Well, Sir, it's a Completely Fair Scheduler."

Found the punchline (1)

lawpoop (604919) | more than 6 years ago | (#19821057)

I've found the punchline [slashdot.org] :

I think I'll wait for the unbelievably fair scheduler, or perhaps the ridiculously fair scheduler.
Props to tji [slashdot.org] .

"And now for something COMPLETELY FAIR." (NT) (0)

Anonymous Coward | more than 6 years ago | (#19821163)

no, not the NT scheduler... "NT" stands for "no text," silly!

This comment intentionally left blank (except for this bit... and the bit above)

how it's possible? (2, Informative)

Saija (1114681) | more than 6 years ago | (#19821017)

"The new CPU scheduler should improve the desktop Linux experience"

really? and how it's suppose to do that wonderful thing?
ps: i'm just curious and noob, so please don't smash me... ;)

Re:how it's possible? (0, Offtopic)

bubulubugoth (896803) | more than 6 years ago | (#19821087)

Giving more time to more demanding applications.

Right now, most applications get "time", even if they don't need them... so, you are "wasting time" being a "good kernel/waiter" by going to your customer (process), and asking if he needs something more, just to wait for a "no" as answer.

With this "fair" approach, the waiter is floating, looking at the dishes and knowing his customers, and will provide attention if the customer ask for it, or if the waiter "feels" that the customer will ask for something if offered...

So, the trick about this "fair multitask" is to mediate, between really greedy customers, and very lazy customers, and give enough time to each, so you, as user, feel that the application you need to run fast, for example, a photo processing application, really gets more cpu's time, than for example, that nifty system tray g-mail email notifier...

So, your overall feeling is better performance with the same hardware.

This can also applies to servers...

Re:how it's possible? (1)

DigiShaman (671371) | more than 6 years ago | (#19821255)

With this new scheduler, I'd better expect a very responsive GUI with silky smooth motion. Unless however, the KDE or Gnome is the limitation in this area.

Re:how it's possible? (3, Interesting)

the_greywolf (311406) | more than 6 years ago | (#19821643)

Actually, no, Gnome and KDE aren't the troublemakers. It turns out that certain X drivers are poorly written and X preempts processes vying for CPU. CFS helps improve the situation - almost to the point where you don't notice it.

Re:how it's possible? (2, Informative)

Doctor Memory (6336) | more than 6 years ago | (#19821303)

Right now, most applications get "time", even if they don't need them... so, you are "wasting time" being a "good kernel/waiter" by going to your customer (process), and asking if he needs something more, just to wait for a "no" as answer.
Seriously? What, the kernel switches to a process, the process checks its environment and figures out that the event it was waiting for hasn't happened yet, and goes back to sleep? I can't believe that a project as mature as the Linux kernel would use a scheduler like that. That sounds more like the result of trying to squeeze a scheduler into 256 bytes so you can lock it into two cache lines. I mean seriously, it's like cooperative multitasking with preemption...

I know it's a little "old school", but whatever happened to keeping track of which processes were "runnable" (i.e., had something to do) and which processses were waiting (blocking on I/O, waiting for a semaphore, waiting until the kernel gave them a buffer, etc.)? I kind of liked VMS's scheduler, it would boost the priority of processes that were waiting for TTY input (i.e., users), then gradually (over the next couple of context switches) return the priority to the default. That way, even if the system was busy, interactive users got a little more attention, so the system *felt* faster. I'm sure the Linux scheduler has some equally interesting features.

Re:how it's possible? (1, Informative)

Anonymous Coward | more than 6 years ago | (#19821483)

Sigh...you know just enough to sound like a clueless fucking moron. Obviously, it only gives runnable processes CPU time.

Re:how it's possible? (0)

dryeo (100693) | more than 6 years ago | (#19821529)

Well I hope it really works this way. One reason I still don't use Linux is it is just to jerky for a desktop system. As a server it is great but who needs to click on a link in Seamonkey and the mouse stalls along with everything else?
I've run various versions of Linux and each release seems worse. Slackware 2 (Kernel v1.3) felt really fast and I used it quite a bit. 2.0.x kernels were pretty well as good then and the 2.2.x not much worse. 2.4.x kernels would periodically swap everything to swap and the system would come to a halt. Meanwhile the foreground app seemed to get more and more starved for cycles. Now I periodically boot into Linux, get frustrated with how slow it is, install Fluxbox, and still be frustrated by how slow it is.
Meanwhile I would run the same apps in X under OS/2 and have a smooth computing experience.
I think the saving thing for Linux is most people are coming from Windows and just expect a slow experience.
I'm still running under OS/2 and generally things are smooth. Set up as a desktop system (priority=dynamic) the foreground app gets a priority boost as well as an IO boost while the background apps still get a decent amount of CPU.
There are also other priority levels if you don't care about something getting cycles or even want them to get cycles no matter what for time critical apps.
I'll have to migrate to Linux again eventually and I would really like it to be smooth and also it would be nice if it was configurable, eg which mouse button does what, what a folder looks like and this text app uses this editor and this text app uses this other editor without having to click through a list.
Sure wish IBM way back had actually released the WorkPlace Shell as open source. It could of been fixed, expanded and we would have a great desktop system in Linux.

Re:how it's possible? (1)

the_greywolf (311406) | more than 6 years ago | (#19821633)

Then you will definitely appreciate the new scheduler. It improves nearly all common cases, and (based on my experience with Con's SD scheduler, which CFS is "inspired" from) it makes the whole system snappier, more responsive, and more usable. It's really quite a night-and-day difference.

Re:how it's possible? (1)

Schraegstrichpunkt (931443) | more than 6 years ago | (#19821901)

Right now, most applications get "time", even if they don't need them... so, you are "wasting time" being a "good kernel/waiter" by going to your customer (process), and asking if he needs something more, just to wait for a "no" as answer.

Yeesh. How on earth did you get the idea that you should be commenting about how the Linux scheduler works, since it appears that you don't know what you are talking about. Basically, only processes with task->state == TASK_RUNNING get CPU time. Processes that are waiting for I/O to complete or for a signal to be delivered don't have task->state == TASK_RUNNING.

Re:how it's possible? (3, Informative)

Anonymous Coward | more than 6 years ago | (#19821149)

The CPU scheduler affects the latency of processes. Interactive applications are very latency sensitive - if they do not get scheduled frequently enough the system will feel sluggish. A good desktop scheduler will therefore schedule all of your interactive tasks frequently. I don't understand the details of the CFS, but if it claims to improve the desktop Linux experience then it must do this.

The tradeoff with short timeslices is that there's more overhead due to context switches and so the overall time spent doing useful work on the cpu will be lower. For non-latency sensitive applications it makes sense to keep the cpu residency time of processes high to maximize throughput. Hence the "desktop->server" tunable.

The blurb does mention that that CFS has 'no notion of timeslices' which sounds like nonsense, but I trust Ingo knows what he's talking about so maybe we have different definitions for that term. Anyone care to explain?

Can anyone compare this to Jonathan Lemons Kqueue? (3, Interesting)

Desmoden (221564) | more than 6 years ago | (#19821039)


We saw crazy performance improvements implementing kqueue in bsd, would love to see something that great at handling many sockets standard linux.

Re:Can anyone compare this to Jonathan Lemons Kque (5, Informative)

Defiler (1693) | more than 6 years ago | (#19821069)

This isn't really the same kind of component.
On the other hand, Linux has epoll, which fills the same role as kqueue.
In my experience, epoll is at least as good.
http://www.kegel.com/c10k.html#nb.epoll [kegel.com]

Now MacOS X needs to fix their kqueue bugs, and the world will be a happy place.

Isn't This Called Cron? (0, Funny)

Anonymous Coward | more than 6 years ago | (#19821049)


I thought Linux used Cron as a scheduler ?

Re:Isn't This Called Cron? (2, Informative)

TheCoelacanth (1069408) | more than 6 years ago | (#19821429)

No.

Cron schedules tasks to execute at specified times. This article refers to the kernel's CPU scheduler which determines which running process gets to use the CPU at any given moment.

Questions (2, Interesting)

flar2 (938689) | more than 6 years ago | (#19821085)

Is there a default scheduler in the linux kernel? If so, which is it? Are there several schedulers to choose from? If so, which one(s) do the major distros use? Will the new CFS be the new default or just another choice?

--mm line (4, Informative)

Enderandrew (866215) | more than 6 years ago | (#19821105)

CFS has been available for some time in Andrew Morton's -mm branch of the kernel. If you really want it now, just download his latest patch and there you go.

I've reen running with it for some time, and I really like it. I'm still not sure if it is better than Con Kolivas' SD scheduler in his patchset, but we'll see.

I liked the old O(1) scheduler (1)

OrangeTide (124937) | more than 6 years ago | (#19821131)

I thought the design was pretty elegant. although in practice we've been having huge problems getting Linux to scale past 32 or so CPUs. partially the locking and partially because the scheduler is not smart enough to schedule complex workloads effectively that you see on huge SMP systems.

Anyone with kids can tell you... (5, Funny)

s_p_oneil (795792) | more than 6 years ago | (#19821133)

The only way to make it completely fair is to let one thread slice the time up, and let the other thread choose which slice it wants. ;-)

Re:Anyone with kids can tell you... (2, Funny)

Burdell (228580) | more than 6 years ago | (#19821553)

Yeah, but then when you get three threads, it gets more complicated. Also, one indecisive thread, and everybody stands around and complains while the one tries to decide which slice to take.

Buried (-1, Troll)

Anonymous Coward | more than 6 years ago | (#19821141)

This is one of those times that I wish Slashdot had a "bury" feature so I could mark my discontent with this post and its meaningless user comments. I clicked thinking the discussion would be interesting.

Re:Buried (1)

stonedcat (80201) | more than 6 years ago | (#19821185)

There's a shitty site called digg and several look-a-likes out there for people like you to feel power in the news others post. Go troll there.

Re:Buried (0)

Anonymous Coward | more than 6 years ago | (#19821195)

If you want an intelligent discussion, read the Linux Kernel mailing list. If you want infantile and sophomoric prattle, stay here.

Completly fair = communist? (3, Funny)

smartdreamer (666870) | more than 6 years ago | (#19821209)

So does Linux reached the computer's communist's holy grail?

Re:Completly fair = communist? (1)

Curufinwe Melwasul (1126097) | more than 6 years ago | (#19821617)

Well then processes would have to:
1. stand in line to get a ticket for some cpu time
2. stand in line to get the cpu time...
3. find out that there is no more cpu time available
4. come back the next day and go to 1

Re:Completly fair = communist? (0)

Anonymous Coward | more than 6 years ago | (#19821759)

Ah, but now some get a VIP pass to the front, while others have to take the piss and wait.

Improve how? (2, Interesting)

suv4x4 (956391) | more than 6 years ago | (#19821231)

The new CPU scheduler should improve the desktop Linux experience, and will be part of the upcoming 2.6.23 kernel.

Could someone outline concrete problem the Linux desktop scheduling had right now that are visible resolved by CFS.

I'm not a heavy user of Linux desktop (just servers on the shell), but it was always my experience that Linux handles simultaneous multimedia tasks (for example) better on the same hardware than Windows.

While I contribute this more to architectural problem on the Windows side (such as.. it's quite easy an app to stall Explorer.exe or vice versa, no amount of scheduling helps there), I'm curious to see if there's tangible difference someone could describe with CFS running desktop software in Linux.

Re:Improve how? (3, Informative)

detain (687995) | more than 6 years ago | (#19821587)

Its been already said, but ill repeat just for completion.

Basically right now the scheduler is unbiased, giving ticks to all applications regardless of their need for processing time. An example of this would be in X windows when you have little taskbar icons that rarely do anything, vs having cd burning software running.

The scheduler will quickly learn that most of the time it asks the taskbar application if it needs to do anything, it doesnt, and that most of the time it asks the cd writing software to do anything, it neeeds cpu. So very quickly it will start checking on the cd writing process more frequently than the taskbar process. This will give you a very noticable performance increase in your system.

With this in mind, there should be a very noticable performance increase in all desktop and server systems. This scheduling change is a very big addition to the main branch of the kernel. Its been available for some time in various kernel patches but the fact that its making it to the main kernel branch means its matured enough for prime time and its been ackhowledged as benefitial to the linux kernel.

I for one am anxious to try this out on all our systems. From what Im reading it has some fine tuning options which should be really nice to play with.

How many nanoseconds...? (1)

Joce640k (829181) | more than 6 years ago | (#19822001)

"start checking on the cd writing process more frequently than the taskbar process..."

So how many nanoseconds does it take to ask the taskbar if it wants any CPU?

I can't imagine it making a "very noticable" difference. More like 0.1%

Re:Improve how? (3, Informative)

the_greywolf (311406) | more than 6 years ago | (#19821605)

CFS and Con Kolivas' SD both aim to improve interactivity of processes under high load - in particular, the goal was to reduce scheduling latency for applications which have realtime needs - like audio players. Con Kolivas has been maintaining variations no his low-latency Staircase design for several years with precisely that goal in mind.

On the desktop, it improves latencies for (for example) music players and 3D games, improving performance and elimingating jitter, lag, and general choppiness. Both SD and CFS achieved this under loads as high as 50.

On the server, it can have several benefits, including improved time-to-network latencies. They both want and need test cases for servers that show no detrimental effects. If you want to help, you can try out CFS on a server and report to Ingo if there are performance or latency issues.

Re:Improve how? (0)

Anonymous Coward | more than 6 years ago | (#19821921)

Really? I have had the exact opposite experience with Windows NT based kernels compared to Linux kernels. Audio and video are regularly choppy on Linux, reboot to Windows, and no choppiness.

My understanding is that the NT kernel, which was designed by the original VMS architects, allows for preemption while executing in kernel mode. However, Linux, in it's unpatched form does not allow preemption while in a syscall. This had made Linux unsuitable as a RTOS and for multimedia unless the kernel is patched.

you guys need it (-1, Troll)

Anonymous Coward | more than 6 years ago | (#19821391)

so you know when it's your turn to suck them dicks.

Great name (0)

Anonymous Coward | more than 6 years ago | (#19821443)

Of course, the next one will be the Completely Amazing Scheduler, followed by the Completely Wonderful Scheduler, followed by the Absolutely Perfect Scheduler, followed by the Even More Perfect Scheduler...

Completely Fair? (0)

Anonymous Coward | more than 6 years ago | (#19821535)

I think I'll wait for the unbelievably fair scheduler, or perhaps the ridiculously fair scheduler.

Re:Completely Fair? (0)

Anonymous Coward | more than 6 years ago | (#19821887)

...or the Totally Fair Scheduler, or the Way Fair Scheduler...

Preemptive Kernel? (0)

Anonymous Coward | more than 6 years ago | (#19821573)

Last time I looked, execution could not be preempted when in kernel mode. Has this changed yet?

Poor attribution (3, Insightful)

the_greywolf (311406) | more than 6 years ago | (#19821579)

So little credit is given to Con Kolivas, whose Staircase Deadline scheduler (a more mature and refined design than CFS) spurred Ingo to finally improve his scheduler (which he wrote on the spot because, apparently, Con's scheduler wasn't good enough for him).

And all Con gets is a minor footnote.

Re:Poor attribution (5, Informative)

Anonymous Coward | more than 6 years ago | (#19821683)

Not only does he get very little credit, but the whole experience of trying to get his patches merged into the mainline have soured him on kernel development altogether:
[ck] It is the end of -ck [bhhdoa.org.au]

It is clear that I cannot develop code for the linux kernel intended only to
be used out of mainline and not have mainline get involved somewhere along
the line. Whether it be the users or even other developers repeatedly
asking "when will this be merged". This forever gets me into a cycle of
actually trying to merge the stuff and ... well you all know what happens at
that point (again I had nastier words but decided not to use them.)

This is pretty sad for linux kernel development.

Does this mean that the O(1) scheduler was bad? (1)

iammaxus (683241) | more than 6 years ago | (#19821673)

This update seems to have come relatively soon after the O(1) scheduler (about a year?) which is relatively quick for changes to really important low-level parts of an operating system. Does this mean that the Linux community was relatively unhappy with the O(1) scheduler which was touted as a very good thing at the time?

Re:Does this mean that the O(1) scheduler was bad? (2, Informative)

ArbitraryConstant (763964) | more than 6 years ago | (#19821739)

"This update seems to have come relatively soon after the O(1) scheduler (about a year?) which is relatively quick for changes to really important low-level parts of an operating system. Does this mean that the Linux community was relatively unhappy with the O(1) scheduler which was touted as a very good thing at the time"

The Linux O(1) scheduler has been around since 2002.

It's pretty good, but there are corner cases where you can fool it. For example, if a process classified as interactive goes CPU-bound, it can cause starvation for other processes.

CFS vs. O(1) (5, Informative)

Ingo Molnar (206899) | more than 6 years ago | (#19821707)

(disclaimer, i'm the main author of CFS.)

I'd like to point out that CFS is O(1) too.

With current PID limits the worst-case depth of the rbtree is ~15 [and O(15) == O(1), so execution time has a clear upper bound]. Even with a theoretical system that can have 4 million tasks running at once (!), the rbtree depth would have a maximum of ~20-21.

The "O(1) scheduler" that CFS replaces is O(140) [== O(1)] in theory. (in practice the "number of steps" it takes to schedule is much lower than that, on most platforms.)

So the new scheduler is O(1) too (with a worst-case "number of steps" of 15, if you happen to have 32 thousand tasks running at once(!)), and the main difference is not in the O(1)-ness but in the behavior of the scheduler.

Re:CFS vs. O(1) (2, Interesting)

Anonymous Coward | more than 6 years ago | (#19821777)

I thought the depth of rbtrees were C*ln(n) where 1C2, so that the number of "steps" in going down the tree would be bounded to 16*2 in this case?

Maybe I'm remembering the worst case behaviour of rbtree wrong.

Re:CFS vs. O(1) (5, Informative)

eggnet (75425) | more than 6 years ago | (#19822027)

Big O notation describes performance as "n" approaches infinity. If you cap n, then of course you cap the execution time, that's the case for most any algorithm. What you're describing still remains O(ln(n)).

Frankly big O notation isn't a very good way to describe scheduler performance. Execution time under common loads, and maybe an extreme case would be better. Who cares about an O(1) scheduler that always takes 1 second to schedule the next task :)

Re:CFS vs. O(1) (3, Informative)

Elladan (17598) | more than 6 years ago | (#19822043)

Ingo,

This kind of a silly thing to say. I mean, all terminating algorithms on a finite machine are O(1) ultimately.

For example, your 1 gig machine only has 2^(1024*1024*1024*8) states it can go through to reach an answer, not including disk IO... and as we all know, O(2^[1024*1024*1024*8]) =~ O(10^2585827972) = O(1). :-)

tagged as: CS masturbation 101 (-1, Troll)

Anonymous Coward | more than 6 years ago | (#19821831)

OS Design is a mature, academic discipline, and has been around for quite a long time. You'd think by now, the linux gurus would stop give the impression that they just finish reading the first half of any OS design textbook.

If Turing were alive, he would bitch slap all the linux "gurus", starting with Linus.

brough to you by "occasion", the word in the image.

not unlike NT4 (0, Troll)

Anonymous Coward | more than 6 years ago | (#19821861)

Lets move the timeslices to ring 0 for graphics.. yeah yeah.. then all of the robust file sharing and stuff will slow down, but hey! we can make the gui more responsive..

On a more serious note, this could be cool, especially if system tasks get lower priority in favor of user defined ones, for HPC this could be alright..

It's about that time of year again... (1, Flamebait)

CoughDropAddict (40792) | more than 6 years ago | (#19822015)

Complete rewrite of scheduler, again? Check.

Catchy new name? Check.

Promises that it's much better than the last scheduler? Check.

What, you're trying to tell me that complex heuristics to try to determine the "interactiveness" of processes wasn't the peak of scheduler technology?

I eagerly await the next grand rewrite when something else comes up that they didn't think through. My bets are that it will be the interdependency of I/O scheduling and CPU scheduling: what good is giving a process the CPU if it's swapped out? The VM system is going to immediately try to swap it back in, and switch to another task when this happens, and if memory is short to begin with this will just thrash, thrash, thrash (I'm sure everyone has experienced this at one time or another).

Can't wait for the "Completely Awesome Knows-About-I/O Scheduler."
Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...