Slashdot Log In
The Completely Fair Scheduler
Posted by
CmdrTaco
on Sun Apr 22, 2007 10:31 AM
from the i'm-always-late dept.
from the i'm-always-late dept.
hichetu writes "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."
Related Stories
[+]
Linux Gets Completely Fair Scheduler 274 comments
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."
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Full
Abbreviated
Hidden
Loading... please wait.
Isnt this called Cron ? (Score:5, Funny)
I thought Linux used Cron as a scheduler ?
Re:Isnt this called Cron ? (Score:5, Informative)
This is for scheduling CPU resouces in real time. To decide if Firefox or Apache is going to be executed the following split second.
Parent
Re:Isnt this called Cron ? (Score:5, Funny)
Parent
Re:Isnt this called Cron ? (Score:5, Interesting)
> let them decide which follows?
That is actually the kind of question that my Operations Research professor (who also did a lot of work in CPU simulation and performance estimating) used to throw onto final exams as the "separate the B+ from the A" question. If your answer was interesting enough he would send you over to one of his Masters candidates to see if it could be taken any further. So I wouldn't count your suggestion out from the start!
sPh
Parent
The Mother of All Comp-Sci Flame Wars (Score:5, Funny)
GP: Can't we just give the processes weapons and let them decide which follows?
P: That is actually the kind of question that my Operations Research professor (who also did a lot of work in CPU simulation and performance estimating) used to throw onto final exams as the "separate the B+ from the A" question. If your answer was interesting enough he would send you over to one of his Masters candidates to see if it could be taken any further. So I wouldn't count your suggestion out from the start!
Behold: The Mother of All Possible Comp Sci Flame Wars: The Darwinistically Selected Genetic Algorithms -vs- the Intelligently Designed Algorithms.
Bumper Stickers $4.95; T-Shirts $19.95:
Parent
Re:Isnt this called Cron ? (Score:5, Funny)
Want to give each process a weapon? Fine. But they have to earn ammunition.
Every time a process gives up its slot, it's given a round of ammunition. It has the option of "shooting" a process ahead of it in the queue, thereby expending a round of ammunition. A shot process must give up its slot in the next round. Whether it loses all its ammo when it respawns remains a research question.
There are two floating point tunable parameters, "accuracy" and "rampage." "Accuracy" is the likelihood that a given shot will actually hit the process it aims at. "Rampage" is the tendency of a process to save up rounds for a while then go on a spree.
Okay, there's a third parameter, "armor," which is the odds of a hit actually becoming an injury. This is meant to protect system processes against luser jobs, and top-level processes against spawned threads.
Of course, the scheduler itself is a boss job that can't be killed, has perfect armor and has infinite ammo.
For the purpose of top and other job monitoring tools we can replace a process's "NICE" score with a "VIOLENCE" score -- an aggregate of their armor, accuracy, rampage tendencies and current ammo supply. We can rename the renice utility to medicate. The important thing about medication is that it eventually wears off, unless you specify the -l (lobotomize) option, which turns the process into a harmless drooling vegetable. Its companion utilities are aim and armor, which tune a job's accuracy and armor class, respectively.
There are two important things about this approach. First, it's probabilistic instead of purely heirarchical. Second, it should give Jack Thompson the screaming heebie jeebies. In fact, I'm going to call this the JTMS scheduler -- the Jack Thompson Murder Simulator Scheduler.
I'm sure this concept can be explored further, but the bar's about to close.
Parent
Re:Isnt this called Cron ? (Score:5, Interesting)
Of course, with such a scheduler, something like the Doom system administration tool [unm.edu] (perhaps more like Quake where you can aim vertically as well as horizontally) will become the preferred method of managing the processes on a system.
For one thing, the processes will obviously shoot back, as the process manager itself (which you see as yourself when running it) is a running process, and thus subject to being fired upon by the other processes.
Secondly, a headshot obviously gets you a "lobotomize" effect. This could pose a problem if one of the other processes hits you with a headshot...
Finally, the application of a medpack to an injured process invokes the "medicate" action.
There are a few possible problems with this, of course:
In short, Linux will quickly become the must-have operating system for gamers, but at the expense of the general purpose desktop.
Parent
Re:Isnt this called Cron ? (Score:5, Insightful)
Parent
Re:Isnt this called Cron ? (Score:5, Interesting)
sPh
Parent
Re:Isnt this called Cron ? (Score:4, Interesting)
"Progress" has saved us all of that stress and ambiguity.
Now, you just pay a small mountain of cash for tuition, and walk away with your "A".
It's all about efficiency these days.
Parent
Re:Isnt this called Cron ? (Score:4, Insightful)
I disagree. That falls back to a measure of the intellect of the individual. That will play a role after school but you don't go to school to demonstrate your abilities or use material, you go to learn material.
'An A-level student is one who grasps the course material so well that he builds on it to produce other conclusions.'
I agree with that. Someone who has a fully grasp of the material understands it well. As I said, the grade should reflect understanding of the material that you took the course to learn. It should not reflect intellect (beyond that required to understand said material), creativity, etc.
'If you lack skills needed to compound your understanding of the material, tough luck. A B is not a poor grade...'
I never said a student with a more thorough understanding of the material shouldn't get an A. I said the A shouldn't be reserved for the quick thinking creative writer who can make up nonsense on the spot for a test question. The slow methodical student may have greater insight into the material but be less creative.
This is the same faulty logic that leads to essays and papers as a measure of understanding. Papers do demonstrate understanding but they aren't the best tool to do so. If papers are primary method used to measure understanding then you aren't ultimately measuring comprehension of the material, you are measuring writing ability.
Parent
Re:Isnt this called Cron ? (Score:5, Funny)
Parent
Re:Isnt this called Cron ? (Score:5, Informative)
http://psdoom.sourceforge.net/ [sourceforge.net]
Parent
Fair? (Score:5, Funny)
Smells like Communism (Score:5, Funny)
Re:Smells like Communism (Score:5, Funny)
each CPU according to its abilities.
Parent
Re:Linux is fading away (Score:4, Insightful)
Alternative explanation: People have less problems now using Linux, so they google less for solutions on Linux problems.
Third explanation: Linux documentation got substantially better, so people have less need to use Google as a substitute.
Fourth explanation: The larger density of Linux installations comes with a larger density of Linux experts, so people are more likely to consult their local Linux guru than Google.
Pick your favorite choice or make up yet another explanation.
Yes, those explanations are all completely made up, but so was the explanation you had in mind.
Parent
Surprised? (Score:5, Funny)
No I won't, because I don't know what the hell it means.
Hah! In your face, Taco!
Re:Surprised? (Score:5, Informative)
Parent
Re:Surprised? (Score:5, Funny)
Meanwhile, outside computer science, Big O faces are used for the completion of a task.
Parent
Re: (Score:3, Funny)
Re:Surprised? (Score:5, Informative)
The scheduler decides which process runs when and has to make sure that no process has to wait in the queue forever without getting his share of CPU time (this is what is called "starving").
Since the scheduler is a program by itself, it has a specific runtime characteristic, usually dependent of the number of programs waiting for their CPU share. The special property of the current scheduler in linux is that its runtime is in fact independent of this number. That's expressed in CS by O(1).
Parent
Re:Surprised? (Score:5, Informative)
Parent
I/O prioritisation (Score:5, Interesting)
Re:I/O prioritisation (Score:5, Interesting)
Parent
Re:I/O prioritisation (Score:4, Informative)
Now, page faults are indeed a form of I/O, but a page fault is technically seen just the fact that some memory required isn't in physical memory. I don't think the parent poster was talking about that. One of the most common reasons for page faults are simply that a block of memory has been swapped to disk, and then suddenly it is required, and as such the block of memory needs to be read into the physical memory.
I'd say: add some memory to that box of yours.
You can read up on it here [wikipedia.org]
Parent
Re:I/O prioritisation (Score:5, Informative)
ionice [die.net]. Available since 2005-08-28.
> And an equivalent of "top" for monitoring processes' I/O activity would also be extremely handy
I agree, that would be nice.
Parent
Re:I/O prioritisation (Score:4, Funny)
Don't you mean "that would be ionice"?
Parent
Re:I/O prioritisation (Score:5, Informative)
#!/bin/sh
nice -n -19 ionice -c 1
Parent
Re: (Score:3, Informative)
I dunno. Linux has has some changes recently in the scheduling department, and an O(1) process scheduler can only be "a good thing". Recently, the I/O block layer got a new scheduler (linky http://kerneltrap.org/node/7637 [kerneltrap.org]). Regarding other I/O prioritization, I can't say with authority that this is needed or not.
Maybe all of these things are related, but in my se
Re: (Score:3, Informative)
Which, presumably, is why they're thinking of taking out its current O(1) process scheduler and replacing it with an O(log(n)) one?
Re:I/O prioritisation (Score:5, Interesting)
I'd love something like that.
There's a way of logging I/O; it's pretty rough-and-ready, not really suitable for permanent use, but can be handy for figuring out what keeps causing a laptop HDD to spin up, for example. As root, do: I/O is then logged to the kernel ring buffer, and can be retrieved with dmesg. The entries look like: When you've finished, do as root to turn it off again.
Like I said, very rough-and-ready, nowhere near as nice as a proper I/O top would be, but there it is.
-Stephen
Parent
Re:I/O prioritisation (Score:5, Informative)
process syslogd dirtied inode daemon.log
process Y dirtied inode some_other_file1
process Z dirtied inode some_other_file2
followed by 300 writes by pdflush, which only specify a device and a block number, not a file name. There's no way you can find out for each of the 300 writes whether it was caused by the "syslogd", X or Z process. So there's no way you can count the amount of write I/O that a process has done.
Parent
Re:I/O prioritisation (Score:4, Informative)
http://www.atconsultancy.nl/atop/kernpatch.html [atconsultancy.nl]
Parent
Re:I/O prioritisation (Score:5, Interesting)
Linux really doesn't need a new process scheduler. What it could really do with is I/O prioritisation.
QNX has that, which is essential for real-time work.
QNX has the advantage that I/O, like almost everything else in QNX, is done via inter-process message passing operations. The message passing system uses priority queues, and so requests to file systems and devices get handled in priority order. So resource managers (file systems, device drivers, etc.) don't have to explicitly handle priorities; it's done for them. Some resource managers, like disk handlers, process multiple requests at a time so they can reorder them to optimize access, but network devices and such are FIFO at the resource manager level and priority ordered at the message level.
The end result is that you can compile or surf the web on a system that's also doing real time work without interfering with the real time tasks.
Parent
Re:I/O prioritisation (Score:4, Interesting)
Actually, that was the Mars Pathfinder [berkeley.edu]. It was running VxWorks, and the effect of the priority inversion was that the stall timer would trip and reset the whole system. The problem was that VxWorks, like QNX, lets you turn off "priority inheritance" on a mutex. This is usually a bad decision, but that was done on the Mars Pathfinder, and created the possibility of a livelock.
So they uploaded a patch to change that mutex to "priority inheritance on", and it worked consistently thereafter.
Parent
credit goes to Con Kolivas (Score:4, Insightful)
Re:credit goes to Con Kolivas (Score:5, Informative)
Con's scheduler seemed to work better at higher workloads than the mainline, by just trying to distribute load evenly and not trying pretty interactivity tricks. But several ppl did say it didn't perform well for certain X client workloads. That's when Ingo's CFS was posted.
There really is 2 alternatives Ingo's CFS & Con's SDL that's being simultaneously tested by the kernel developers now, and none is accepted into mainline.
So it wouldn't be fair to say that CFS is *the* next Linux scheduler. It could be SDL as well.
Parent
Optimizations leading to less optimized code (Score:4, Insightful)
After enough number of iterations trying to optimize a software program to do everything very well compared to the base "naive" solution, you end up with an OS that does everything poorly.
It's counterintuitive, but we see it it every day around us.
The Multics scheduler always seemed very nice (Score:4, Interesting)
So interactive tasks naturally floated to the top and compute bound tasks naturally sank.
(Anyone remember Multics?)
Re:The Multics scheduler always seemed very nice (Score:4, Funny)
Parent
Completely fair? (Score:5, Funny)
Interactive tasks (Score:4, Insightful)
Even so, I'd prefer to have IO better scheduled - ionice doesn't really seem to work at least for me.
Fair schedulers are for the weak (Score:4, Funny)
(from here [sdf-eu.org])
Re:O(1) - what a huge misnomer (Score:4, Informative)
Parent
Re:O(1) - what a huge misnomer (Score:4, Informative)
Parent
Re:O(1) - what a huge misnomer (Score:5, Informative)
Here's how Linux 2.6.x task scheduler works:
- A "runqueue" keeps track of all essential tasks assigned to a given CPU [Queue is O(1) efficient]
- Each runqueue contains two priority arrays, the active and the expired. As a task completes, it is moved (during the move, the new timeslice is calculated - the point of debate and largest fundamental change to the task scheduler) [Moving from static array to static array is O(1) efficient]
- When the active priority array is finished, the expired array becomes the active array [Swapping 2 pointers is O(1) efficient]
- The priority arrays are of fixed length 140, as that is the amount of priority levels Linux has [O(140) = O(1)]
The point of debate comes if two threads have the same priority, in which case they are put on a round robin in the priority array. However, the confusion comes in that the execution is O(n) (which makes sense if you think about it), but the scheduler itself handles these at O(1) efficiency.Parent
Re:O(1) - what a huge misnomer (Score:5, Insightful)
Parent
Re:O(1) - what a huge misnomer (Score:4, Informative)
Parent
Re:O(1) - what a huge misnomer - INCORRECT (Score:5, Informative)
The reason this is important, and the reason they are worried about the act of scheduling the next process rather than time complexity over all N processes, is that if scheduling the next process were not constant time, the percentage of time spent scheduling the next process would grow larger as you added more processes. That's fine if you're on a desktop system and you go from 100 to 200, but as the number starts getting large on (say) big servers, you start running into a situation where all your CPUs are perpetually tied up trying to figure out what process to run next.
O(n) time over N processes is not a problem; you've either got the CPUs or you don't. If you don't, then your performance will suck for reasons that are your own fault. If you do have enough CPUs, then the time spent scheduling will remain in step with the time spent running the processes, and this is fine. However, if the time spent scheduling grew, every time a process was scheduled, across all CPUs, then your $50000 server would be worthless because it wouldn't be able to handle the workloads you intended for it. All those expensive CPUs would sit there figuring out what process to run rather than running it.
So, it is NOT a misnomer. It accurately describes the portion of the problem that the developers are concerned with. It's O(n) over n processes, and that's great because it means you can get to n without breaking down.
Parent