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