Re: Ingo Scheduler

From: Ingo Molnar (
Date: Tue Aug 20 2002 - 10:54:24 EST

On Mon, 19 Aug 2002, Mohamed Ghouse , Gurgaon wrote:

> When the process A (from active queue) has completed its Quantum,
> Scheduler moves process A to the expired queue. & when the active queue
> is empty, the expired queue becomes the active queue & the active queue
> becomes the expired

yes, this is called the 'array switch'. [the unit switched is not a queue,
but an array of queues.]

> The active queue (expired queue) has accumulated the process. It is
> almost similar to the previous active queue. How does the Introduction
> of the expired queue reduce the Time Complexity from O(n) to O(1).

the queue arrays themselves are indexed by priority.

> as my understanding goest that the scheduler needs to produce "process's
> goodness", so the time complexity remains the same.

the new scheduler is not 100% equivalent to the old one - but the concepts
are pretty close. The changes that were done are: different [better]
cache affinity logic, different [better] interactivity detection, better
yield() implementation, different timeslice lengths.

> Another point of non-understanding is Why does the scheduler need to
> know the scheduling class to produce process's goodness?

an RT task needs to be scheduled before any other task.

in the new scheduler RT tasks are in essence just tasks with higher


To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

This archive was generated by hypermail 2b29 : Fri Aug 23 2002 - 22:00:20 EST