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

Peter Williams
2004-08-05T01:07:12Z

> 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.