The Ingo Scheduler

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

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.

What’s wrong? The new clean desk test
View Comments
You Might Like
Join the discussion
Be the first to comment on this article. Our Commenting Policies