Slashdot Mirror

← Back to Stories (view on slashdot.org)

The Completely Fair Scheduler

Posted by CmdrTaco on 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."

20 of 292 comments (clear)

  1. Isnt this called Cron ? by Anonymous Coward · · Score: 5, Funny


    I thought Linux used Cron as a scheduler ?

    1. Re:Isnt this called Cron ? by ozamosi · · Score: 5, Informative

      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.

    2. Re:Isnt this called Cron ? by LiquidCoooled · · Score: 5, Funny

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

      --
      liqbase :: faster than paper
    3. Re:Isnt this called Cron ? by sphealey · · Score: 5, Interesting

      > 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

    4. Re:Isnt this called Cron ? by HerrEkberg · · Score: 5, Funny

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

    5. Re:Isnt this called Cron ? by Anonymous Coward · · Score: 5, Insightful

      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.

    6. Re:Isnt this called Cron ? by sphealey · · Score: 5, Interesting

      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

    7. Re:Isnt this called Cron ? by theonetruekeebler · · Score: 5, Funny
      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.

      --
      This is not my sandwich.
    8. Re:Isnt this called Cron ? by kcbrown · · Score: 5, Interesting

      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.

      --
      Use 'slashdot stuff' in the subject line in any email you send me if you want to get past the spam filter.
  2. Smells like Communism by 0xdeadbeef · · Score: 5, Funny

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

    1. Re:Smells like Communism by Anonymous Coward · · Score: 5, Funny

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

  3. Surprised? by WombatDeath · · Score: 5, Funny

    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!

    1. Re:Surprised? by Eevee · · Score: 5, Informative

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

    2. Re:Surprised? by jrschulz · · Score: 5, Informative

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

  4. I/O prioritisation by Doug+Neal · · Score: 5, Interesting

    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.

    1. Re:I/O prioritisation by Anonymous Coward · · Score: 5, Informative

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

    2. Re:I/O prioritisation by Stephen+Williams · · Score: 5, Interesting
      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
  5. The Mother of All Comp-Sci Flame Wars by mosel-saar-ruwer · · 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:

    $DEITY does not play dice with the Turing Machine.
  6. Re:O(1) - what a huge misnomer by ASBands · · 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.
    --
    My UID is a prime number. Yeah, I planned that.
  7. Re:credit goes to Con Kolivas by jb.cancer · · Score: 5, Informative

    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.