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

[Peter Williams <pwil3058@bigpond.net.au>]

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@bigpond.net.au

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