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 ?

[LiquidCoooled]

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

Re:Isnt this called Cron ?

[HerrEkberg]

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

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 ?

[Syberghost]

Of course, the scheduler itself is a boss job that can't be killed, has perfect armor and has infinite ammo.

Fascist!

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?

[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:The Multics scheduler always seemed very nice

[Hognoxious]

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

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:I/O prioritisation

[ppc_digger]

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

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.

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

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:I/O prioritisation

[dotgain]

If you want me to go on arguing, you'll have to pay for another five minutes.

Schedulers these days I dunnu...

[Nefarious Wheel]

It's all data structures and interrupts nowdays laddie! Data structures and interrupts. Why back in my day we had nice chrome-plated algorithms and fat polling intervals and liked it!

You pesky young folk who think yer flash ram is better than good old reliable ferrite donuts have at with ye! We had disk drives that could pull yer filings out from two feet away on a max seek. Do ya get technology like that nowdays? Do ya? Nuuuuu.....

Mind ye what we had for an OS scheduler was a smiling polish gennelmun who wore too much after shave, and he was a bit much, but we knew which program ran after which we did! Off with ye now, come back when you have a *real* algorithm.

(Walks away muttering at his shoes)