Hello all
I am in a state of confusion.
Reason: How does Ingo Scheduler manages to schedule the entire process with
the help of expired
queue in O(1).
I searched the net for the explaination of Ingo's Scheduler, could not find
one.
My understanding of Ingo's Scheduler
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
Point of confusion
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).
as my understanding goest that the scheduler needs to produce "process's
goodness", so the time complexity remains the same.
Another point of non-understanding is
Why does the scheduler need to know the scheduling class to produce
process's goodness?
TIA
-MG
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
priority.
Ingo