Linux 2.6: The O(1) Scheduler Revolution

In the old 2.4 kernel, the scheduler had a dirty secret: it was $O(n)$. Every time the kernel needed to pick a new process to run, it had to iterate through every runnable process. If you had 10,000 processes, your system spent more time thinking about what to do than actually doing it.

Ingo Molnar's new $O(1)$ scheduler in Kernel 2.6.0 fixes this once and for all.

How it Works: Two Arrays

The scheduler maintains two "priority arrays" per CPU: active and expired.

1. It picks the highest priority task from the active array.
2. When a task uses up its time slice, it's moved to the expired array.
3. When the active array is empty, the two arrays are swapped (a simple pointer flip).

Since the kernel uses bitfields to track which priority levels have tasks, finding the next task takes the same amount of time whether you have 10 processes or 10,000.

Interactive "Bonus"

The scheduler also tries to be smart about "interactivity." If a process sleeps a lot (like a text editor waiting for keystrokes), it gets a priority "bonus." If it's a CPU-hogging compile job, it gets penalized. This makes the 2.6 desktop feel incredibly snappy compared to 2.4.

Preemption is Here

For the first time, the Linux kernel is now "preemptible." This means even if the kernel is busy doing a system call, a high-priority user process can kick it off the CPU. This is a massive win for audio processing and real-time applications.

If you're still running 2.4 on your production web servers, it's time to plan the migration. The 2.6 kernel isn't just an update; it's a fundamental shift in how Linux handles massive scale.