ArsTechnica Explains O(1) Scheduler

geogeek writes "The recent release of Linux's 2.6 kernel introduces a number sweeping improvements. These can be hard to understand without a background in programming. This week's Linux.ars examines the improved scheduler for an enthusiast audience, concisely explaining its nuances and the practical effects of an O(1) design."

Comments

Re:Ars' Piece

[spectecjr]

Windows XP, for example, isn't all that great in this area, and often one process can too easily slow things down. This is even further emphasized when all the processes you're working with are actually the main "explorer.exe" process; eg, you do something in Windows Explorer that blocks (spin up a CD drive) and everything else (the "desktop", task bar, etc) all become unresponsive...

The kernel hasn't slowed down in that case; it's the GUI layer which has slowed down. It hit a bottleneck.

Interestingly, it would appear that Windows has used an O(1) scheduler in Windows NT and up since at least NT 4.0 (which came out in 1996).

It's also interesting to note that it has the same priority-boosting for IO threads that Linux has.

"Windows NT also uses additional priority adjustments based on other events, such as momentarily boosting thread priority when it returns from an I/O call"

Detailed explanation of the NT4.0 scheduler

Easier to read version of the above

Part 1 of a slightly more indepth (but in some places inaccurate)* article

Part 2 of the article

*The article makes it sound like it's O(N) in places; it's not. The scheduler is using a set of priority lists, which are kept in-order at insertion time when a thread exits its context, by the thread inserting itself at the end of the list for its priority.