The Completely Fair Scheduler

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

Comments

Isnt this called Cron ?

[Anonymous Coward]

I thought Linux used Cron as a scheduler ?

Re:Isnt this called Cron ?

[ozamosi]

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.

Re:Isnt this called Cron ?

[LiquidCoooled]

Can't we just give the processes weapons and let them decide which follows?

Re:Isnt this called Cron ?

[sphealey]

> Can't we just give the processes weapons and
> 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

Re:Isnt this called Cron ?

[HerrEkberg]

Just throw this into the kernel and we are good to go.

Re:Isnt this called Cron ?

[Progman3K]

Yes, that's called psDoom
http://psdoom.sourceforge.net/

Re:Isnt this called Cron ?

[Anonymous Coward]

Coming up with an idea (even if totally made up) and the backing it up with arguments is much harder than memorization and regurgitation and actually backing it up with things having to do with that class shows you have learned something, or at least know about the concepts discussed in the class.

Re:Isnt this called Cron ?

[sphealey]

That guy was actually the best test writer and overall course designer that I have ever had among all the academic (through a masters) teachers and corporate trainers I have encountered. When you finished his course you received exactly the grade you deserved according to the formal definitions of the grades; as you indicate one didn't receive an A in that class unless one actually _understood_ the material [for the record I was in the B+ group ;-( - which was a correct evalution]. Not surprisingly it also turned out to be one of the most useful classes I ever took as well.

sPh

Re:Isnt this called Cron ?

[theonetruekeebler]

Okay -- Since I'm not allowed to drink beer in class I'll just have to post this from home.

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.

Re:Isnt this called Cron ?

[smittyoneeach]

You mean this was the "old school" where you were graded on the basis of something they used to call "learning".
"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.

Re:Isnt this called Cron ?

[kcbrown]

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.

Of course, with such a scheduler, something like the Doom system administration tool (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:

1. When you have two or more system administrators, all running the process manager, the system itself becomes a warzone with innocent processes being killed by the dozen as the administrators go on rampages in their attempts to kill each other for supreme control of the system.
2. Certain weapons, such as the BFG, are powerful enough to take out all but the most heavily armored processes, and since some of them are area effect weapons, a lot of innocent processes will bite the dust as a result of their usage.
3. Lightly-armored processes will need additional protection in the form of fast reflexes to avoid being hit.
4. Eventually the administrators will begin using aimbots and the like. One can see where the resulting arms race will go. Obviously the aimbots will have to run on a different system since otherwise they'll be potential targets.
5. "Spawn camping" takes on a whole new meaning. Newly created processes become very vulnerable compared with running under earlier versions of Linux. Normal users will have an increasingly difficult time starting tasks like OpenOffice and will start to migrate back to Windows or other OSes with clearly inferior schedulers.
6. Due to all of the above, the system will eventually become unusable by anyone but the system administrators. The sysadmins will, of course, say that this is how it should be.

In short, Linux will quickly become the must-have operating system for gamers, but at the expense of the general purpose desktop.

Re:Isnt this called Cron ?

[shaitand]

'Grades should evaluate the ability to *use* the material of a course.'

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.

Fair?

[alienmole]

If scheduling was completely fair, this would have been a frist ps0t.

Smells like Communism

[0xdeadbeef]

Free software: because some processes are more equal than others.

Re:Smells like Communism

[Anonymous Coward]

Yes, each process according to its needs,
each CPU according to its abilities.

Surprised?

[WombatDeath]

You will be surprised to know that O(1) is really too good not to have any side-effects on fairness to all tasks.

No I won't, because I don't know what the hell it means.

Hah! In your face, Taco!

Re:Surprised?

[Eevee]

In computer science, Big O notation is used for the complexity of a task.

Re:Surprised?

[jrschulz]

A scheduler is the piece of software that brings you the illusion of multi-tasking. Because a single processor (with a single core) can only run one process at the same time, the operating system switches the process currently running. And it does this very fast (IIRC up to 1000 times a second in the case of linux).

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

Re:Surprised?

[BiggerIsBetter]

In computer science, Big O notation is used for the complexity of a task.

Meanwhile, outside computer science, Big O faces are used for the completion of a task.

Re:Surprised?

[Otter]

I think the intended meaning is "Unsurprisingly, the O(1) behavior came at the expense of optimum scheduling."

I/O prioritisation

[Doug Neal]

Linux really doesn't need a new process scheduler. What it could really do with is I/O prioritisation. Windows now has it, so there's no excuse. CPU power is fairly abundant these days so managing its usage is less of an issue than it used to be, but I/O bandwidth is often in short supply and I/O-bound applications can choke a system and make interactive processes a pain in the ass to use. I'd like to see some way of reserving and limiting bandwidth to particular devices for particular processes. And an equivalent of "top" for monitoring processes' I/O activity would also be extremely handy... as far as I know, the system calls don't even exist in the kernel to do this yet.

Re:I/O prioritisation

[tepples]

And an equivalent of "top" for monitoring processes' I/O activity would also be extremely handy... as far as I know, the system calls don't even exist in the kernel to do this yet. Windows has this to an extent. I press Ctrl+Shift+Esc to open Windows Task Manager, then View > Select Columns... > turn on Page Faults Delta, and I see the penalty for sticking with the 6-year-old paid-for PC that I still use.

Re:I/O prioritisation

[Anonymous Coward]

> What it could really do with is I/O prioritisation.
ionice. 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.

Re:I/O prioritisation

[Stephen Williams]

And an equivalent of "top" for monitoring processes' I/O activity would also be extremely handy

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:

echo 1 >/proc/sys/vm/block_dump

I/O is then logged to the kernel ring buffer, and can be retrieved with dmesg. The entries look like:

pdflush(138): WRITE block 1161864 on dm-4
pdflush(138): WRITE block 0 on dm-3
pdflush(138): WRITE block 524328 on dm-3
pdflush(138): WRITE block 786952 on dm-3
pdflush(138): WRITE block 786960 on dm-3

When you've finished, do

echo 0 >/proc/sys/vm/block_dump

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

Re:I/O prioritisation

[jawtheshark]

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

Re:I/O prioritisation

[DaleGlass]

atop seems to have support for disk monitoring, but it requires a kernel patch:

http://www.atconsultancy.nl/atop/kernpatch.html

Re:I/O prioritisation

[ppc_digger]

I agree, that would be nice.
Don't you mean "that would be ionice"?

Re:I/O prioritisation

[Animats]

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.

Re:I/O prioritisation

[Breakfast Pants]

A one line script does the trick, name it kplayer and put it in ~/bin (and put ~/bin at the top of your $PATH):

#!/bin/sh
nice -n -19 ionice -c 1 /usr/bin/kplayer

Re:I/O prioritisation

[Handyman]

In fact, this functionality is pretty darn useless. (I should know, I got it into 2.6. :-) ) For read I/O it's okay, but for write I/O it sucks. The thing is, what's logged is the actual I/Os, which are generally done by pdflush (if the modifying process doesn't use fsync, which it usually doesn't), and kjournald if you're using ext3. The only thing that's logged otherwise is that a process dirties an inode, but that doesn't tell you how many pages it's modified. You get something like

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.

Re:I/O prioritisation

[Animats]

Actually, that was the Mars Pathfinder. 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.

credit goes to Con Kolivas

[phrasebook]

This new scheduler may have 'Ingo Molnar' written all over it but I'll be giving the credit to ck!

Re:credit goes to Con Kolivas

[jb.cancer]

Well, yes & no. It really was Con's RSDL that got ppl looking seriously into changing the mainline scheduler (there already being several out-of-mainline alternatives like nicksched, etc.)

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.

Optimizations leading to less optimized code

[suv4x4]

It's a very interesting phenomenon.

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

[Anonymous Coward]

On Multics, tasks that used up their CPU were put in a lower priority run queue and tasks that didn't use up their CPU time were put into a higher priority run queue.

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

[Hognoxious]

I used Multics, but I thought it prioritised the tasks by how thick the cards were.

Re:O(1) - what a huge misnomer

[Watson Ladd]

Actually the Linux scheduler is O(1). Processes are placed on O(1) queues, and the oldest processes on each queue are compared to each other. The number of queues is fixed, so Linux only has 5 nice levels. This is a scheduler because newer processes on a queue do not deserve the time more then the processes ahead of them.

Re:O(1) - what a huge misnomer

[ASBands]

If you want a good description of the old way it works (which is what you're talking about), [PDF Warning] here it is. As this PDF describes, the 2.4.x kernel uses a O(n) fast algorithm for choosing the next task, going through the array of tasks to re-evaluate them. The the Linux 2.6.x scheduler recalculates timeslices as each task uses up its timeslice. In this fashion, the kernel should always know the most important thread, it is simply the next element. Granted, you are doing the same amount of work, but the pauses for re-evaluation are spread out so that you don't get long lapses where nothing important happens.

The Mother of All Comp-Sci Flame Wars

[mosel-saar-ruwer]

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:

$DEITY does not play dice with the Turing Machine.

Completely fair?

[tji]

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

Re:And that relates to "fairness" how?

[wellingj]

The current O(1) schedule is not entirely fair to attain so named O(1) performance. That's how jackass.

Re:O(1) - what a huge misnomer - INCORRECT

[ArbitraryConstant]

You are incorrect because the act of scheduling the next process to run requires constant time regardless of how many processes there are. The O(1) refers to this, correctly.

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.

Re:O(1) - what a huge misnomer

[Watson Ladd]

No. You are wrong. It looks O(n) unless you notice that the processes back on the queue ran more recently then the ones at the front. Therefore they have lower priority then the ones at the front, so we only need to worry about the processes at the front of the queues. To evaluate these priorities we just store the last time they ran, and then subtract from the current time, then add that to the inherent priority.

Re:O(1) - what a huge misnomer

[ASBands]

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.

Interactive tasks

[Zarhan]

For this reason, I've been using Con Kolivas' patches to replace the scheduler. http://members.optusnet.com.au/ckolivas/kernel/ - very helpful especially if you don't have the fastest computer around. Also seems to help a bit with I/O - if my hard drive is trashing for whatever reason, interactive stuff still remains reasonably responsive. Or at least it doesn't make my mouse cursor skip...

Even so, I'd prefer to have IO better scheduled - ionice doesn't really seem to work at least for me.

Re:O(1) - what a huge misnomer

[xenocide2]

It seems like the difference is that people call it an O(1) scheduler to reflect the fact that all the work required to be done at the end of a timeslice (record keeping, picking a new process etc) is done in constant time, and people arguing for O(n) are referring to the cost to schedule all processes. Nobody's saying they can find a schedule for n processes without looking at all of them.

PSDoom (Doom process manager)

[Alwin Henseler]

Good job sending all those /.ers over there, it will be the mother of all process fights on that poor server now. Sysadmins battling their way through hordes of zombies and monster processes, with ammo (ehm.. mem,cpu) running lower and lower until they're out, just as another wave of uglies comes out of nowhere...

Re:Well duh

[Anonymous Coward]

Obviously O(1) is a bad choice. Nice to see Linux learning something from Windows here.

Actually I find the Windows (XP, haven't tried Vista yet) scheduler to be quite horrible especially with regards to interactivity. One resource hog and things pretty much come to a standstill. IMO it's worse than O(1) and no comparison to Con's staircase.

Fair schedulers are for the weak

[hcdejong]

Klingon multitasking systems do not support "time-sharing". When a Klingon program wants to run, it challenges the scheduler in hand-to-hand combat and owns the machine.

(from here)

Re:And that relates to "fairness" how?

[GrievousMistake]

You fail at reading comprehension. Let's rephrase: The current scheduler runs in O(1) time. To do this, it uses an algorithm that sometimes isn't optimal; that is, it isn't entirely fair.
The relation between fairness and algorithmic complexity, is that you may sacrifice fairness to get a lower complexity.
This is just rephrasing GP, I don't know shit enough about schedulers to comment on the actuall algorithms.

Re:Linux is fading away

[maxwell demon]

Possible explanation: More people know about Linux now, so there's less need to Google to learn about it.
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.

Re:This is very impressive

[Anonymous Coward]

They cheated.

Internally, the kernel only has five priority levels. Each one is a queue, and it compares among all of them to determine which task to run, but it only compares the head of the queue. So it's O(5), which is of course O(1), but if it supported an arbitrary number of priority levels (which IMO it should) then it would become O(n) again.