I remember the talks about how wonderful O(1) scheduler would be (as of 2.6.0), now it's considered the old-and-complicated, and will be replaced in 2.6.23.

Mike briefly describes what is a scheduler and what's new in the new Linux scheduler, called CFS.