Digg - What is the Completely Fair Scheduler? (via Mowser)

Introducing Digg Dialogg!
Check out the first Digg Dialogg with Nancy Pelosi. More guests to be announced soon!

What is the Completely Fair Scheduler?

immike.net — A pretty detailed explanation about whats up with the upcoming 2.6.23 Linux kernel release.

Bury

Favorite?

bedoyle 1 year 28 days ago, made popular 1 year 27 days ago

471 diggs digg it

49 Comments Who Dugg It? Blog It Email It

« View All Comments

Dougman82, on 10/10/2007, -7/+2Hmmm... 20 diggs and 0 comments later, site down.

mmalone, on 10/10/2007, -0/+9Eh. It's not from this... and it should be up now. Another article on the site is on Digg, and the same article just hit del.icio.us front page. Been serving like 20 requests/sec all day. Tons of comments => tons of cache invalidations => server slowdown.

Try now and it should be all good.

Dougman82, on 10/10/2007, -1/+6Sweet, got through. Actually a very interesting article. I was wondering what was behind the new CFS scheduler.

geminitojanus, on 10/10/2007, -0/+8The article both over-complicates what's going on, and fails to explain some fairly simple-to-know facts.

First of all, CFS is still a O(1) scheduler, all context switches happen in constant time. All that CFS improves on is the precision of switches; before, the scheduler uses ticks and there are some odd conditions where a process can use a huge amount of CPU time, without ever being taxed for it (for example, if the process enters on the tick but leaves before the tick, it's not charged for the amount of processing time that happened within the tick.

With CFS, we get rid of "Jiffies", "time slices" and "Hz time", and we just do it on raw nanosecond-time. It's "Completely Fair", because it keeps a journal of exactly how long each process has the CPU, and balances that time out amongst processes evenly. We have a billion nanoseconds in a second, with one process running, it gets the whole billion nanoseconds, with two, each process gets half a billion (minus a few nanoseconds used for each context switch), and so on and so forth. This is nothing but an optimization of the previous scheduling algorithm. [For those who are interested, "nice" still works by calculating exact runtime, adjusted for the process's nice level, ahead of time as part of the scheduler's overhead and is even more precise than before.] myfanwy, on 10/10/2007, -1/+3hmm, CFS scheduler; is that a case of redundant RAS syndrome? mmalone, on 10/10/2007, -0/+3@geminitojanus: my understanding is that CFS is O(log n), not O(1), since it uses a red-black tree to organize processes and selects the leftmost node for execution. Search time on an rbtree is O(log n). Am I missing something?

There are other differences from the current O(1) scheduler too. For example, CFS doesn't do any interactive process identification. And with CFS the time quantum is more variable than with the current scheduler since they're partially determined by the amount of CPU time other processes on the box are using. I wouldn't call CFS "nothing but an optimization."

myfanwy, on 10/10/2007, -0/+1bugger, wrong place

OneAndOnlySnob, on 10/10/2007, -1/+1209 diggs and 31 comments later, site up. Hmm indeed.

Login or register to add a comment

Create a new account or login to join in the conversation on Digg. You'll also be able to Digg stories to help promote things you like.