I should have clarified better. I was not referring to any scheduler with complexity of O(1). I was specifically referring to scheduler predating current CFS in mainline. That scheduler was called O(1), and *no*, current BFS is not similar to that. One of most salient differences being, the history or any history distribution not being maintained by either BFS or CFS. FreeBSD, OTOH, still has a scheduler (ULE) with semantics predating back to that O(1) scheduler linux *had*. Check -- http://jeffr-tech.livejournal.com/24280.html -- for some interesting nitbits. Also, with regards to interactivity (which is what I was referring to earlier when i meant desktops), this scheduler is not up to the mark. There is also a proposal to "clean room" port BFS to FreeBSD among GSoC projects.