Inside the Linux 2.6 Completely Fair Scheduler

"On the other side are the technological advances made in the platform, including architectures (multiprocessing, symmetric multithreading, non-uniform memory access [NUMA]) and virtualization. Also embedded here is the balance between interactivity (user responsiveness) and overall fairness. From this perspective, it's easy to see how difficult the scheduling problem can be within Linux.

"A short history of Linux schedulers

"Early Linux schedulers used minimal designs, obviously not focused on massive architectures with many processors or even hyperthreading. The 1.2 Linux scheduler used a circular queue for runnable task management that operated with a round-robin scheduling policy. This scheduler was efficient for adding and removing processes (with a lock to protect the structure). In short, the scheduler wasn't complex but was simple and fast.

"Linux version 2.2 introduced the idea of scheduling classes, permitting scheduling policies for real-time tasks, non-preemptible tasks, and non-real-time tasks. The 2.2 scheduler also included support for symmetric multiprocessing (SMP).

"The 2.4 kernel included a relatively simple scheduler that operated in O(N) time (as it iterated over every task during a scheduling event). The 2.4 scheduler divided time into epochs, and within each epoch, every task was allowed to execute up to its time slice. If a task did not use all of its time slice, then half of the remaining time slice was added to the new time slice to allow it to execute longer in the next epoch. The scheduler would simply iterate over the tasks, applying a goodness function (metric) to determine which task to execute next. Although this approach was relatively simple, it was relatively inefficient, lacked scalability, and was weak for real-time systems. It also lacked features to exploit new hardware architectures such as multi-core processors."

Complete Story

Related Stories:

• 2.6.32 is Out! But a Word of Caution Around CFQ(Dec 07, 2009)
• The 2009 Linux Kernel Summit(Nov 03, 2009)
• Building Your Own Linux Kernel: Tricky kernel options (part 3)(Oct 22, 2009)
• Tuning CFQ - What Station is That?(Oct 15, 2009)
• The realtime preemption mini-summit(Oct 09, 2009)
• I Have a Schedule to Keep - IO Schedulers(Oct 07, 2009)
• Ingo Molnar Tests New BF Scheduler(Sep 09, 2009)
• Con Kolivas returns with a new scheduler(Sep 01, 2009)