Re: [PATCH] V-3.0 Single Priority Array O(1) CPU Scheduler Evaluation

[Peter Williams]

William Lee Irwin III wrote:
> William Lee Irwin III wrote:
> On Wed, Aug 04, 2004 at 12:40:15PM +1000, Peter Williams wrote:
>
> > The timer would be deactivated whenever the number of runnable tasks for 
> > the runqueue goes below 2.  The whole thing could be managed from the 
> > enqueue and dequeue functions i.e.
> > dequeue - if the number running is now less than two cancel the timer 
> > and otherwise decrease the expiry time to maintain the linear 
> > relationship of the interval with the number of runnable tasks
> > enqueue - if the number of runnable tasks is now 2 then start the time 
> > with a single interval setting and if the number is greater than two 
> > then increase the timer interval to maintain the linear relationship.
> > I'm assuming here that add_timer(), del_timer() and (especially) 
> > mod_timer() are relatively cheap.  If mod_timer() is too expensive some 
> > alternative method could be devised to maintain the linear relationship.
>
>
> Naive schemes reprogram the timer device too frequently.

I had a look at mod_timer() and I agree that it's too expensive to call 
every time a task gets queued or dequeued.

> Software
> constructs are less of a concern. This also presumes that taking timer
> interrupts when cpu-intensive workloads voluntarily yield often enough
> is necessary or desirable.

Voluntary yielding can't be relied upon.  Writing a program that never 
gives up the CPU voluntarily is trivial.  Some have been known to do it 
without even trying :-)

> This is not so in virtualized environments,
> and unnecessary interruption of userspace also degrades performance.

Peter
--
Peter Williams                                   pwil3058@xxxxxxxxxxxxxx

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/