The Linux scheduler has undergone considerable improvements since
version 1.0, but it's still evolving. This week, I will explain the
novelties of the so-called "Ingo scheduler", the one that is about to
supplant the 2.4 scheduler.
Limitations of the 2.4 Scheduler
The scheduler determines which process in the active tasks' queue will
execute next. A sophisticated algorithm weighs a process's priority,
the CPU time it has received thus far, its' affinity to a specific CPU
(in SMP systems), and its scheduling class. A scheduling class can be
one of three: real-time, user-space, and non pre-emptible. The goodness
() function, which is the core of the scheduler, weighs all of these
factors and produces a result called "the process's goodness".
The Big Oh Notation
Let's get a bit more technical. The "Big-Oh notation" is used in
computer sciences to describe an upper bound on the execution time of
an algorithm in terms of the size of its input set. According to this
notation, the current scheduler is classified as O(n) because its
goodness() function scans the entire active queue every time it
schedules a process. The longer the queue is, the longer the time taken
to select the next process. For most applications, this isn't really a
problem because the marginal overhead of each additional process is
measured in microseconds; however, in real-time environments, this
indeterminacy is unacceptable.
The Ingo Scheduler
The new scheduler uses a different goodness algorithm that has a
constant execution time, regardless of the number of currently active
processes. It simply reads the current queue until it finds the first
process eligible for running and runs it. When that process has
consumed its time quantum, it is moved to another queue called
the "expired queue". Once the current active queue has been emptied,
the expired queue becomes the active queue. As you can see, the
execution time of this algorithm is independent of the number of active
processes. Therefore, the Ingo scheduler is classified as O(1) , where O
(1) indicates constant time execution. Another feature of the Ingo
scheduler is kernel preemption support, a topic we discussed several
weeks ago (see http://www.itworld.com/nl/lnx_tip/11022001).
Although it seems that only real time systems will benefit from the new
scheduler, the Ingo scheduler includes many bug fixes and enhancements
that will improve the overall performance on most systems. Remember,
however, that this product remains under development and, as such, it
might still have undiscovered bugs and glitches.