Re: [patch] CFS scheduler, v3

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

Peter Williams wrote:
> William Lee Irwin III wrote:
>> William Lee Irwin III wrote:
>> On Sat, Apr 21, 2007 at 10:23:07AM +1000, Peter Williams wrote:
>>> If some form of precise timer was used (instead) to trigger 
>>> pre-emption then, where there is more than one task with the same 
>>> expected "on CPU" time, only the last would get any CPU (and that's 
>>> only the case if some infinite loop doesn't get created).
>>
>> I think you can check for this and adjust their on-cpu times in various
>> ways and choose what order to run them in. I think it'd end up something
>> of a missed deadline policy.
> 
> Arguably the latest one should go first as its estimate is more likely 
> to be correct being based on more recent info i.e. the other's estimates 
> would be based on less runnable tasks and be optimistic. This would 
> involve pushing them down the queue and pushing items already on the 
> queue downwards is likely to be expensive.  Which is why I prefer the 
> less elegant solution of the periodical interrupt.
> 
> Of course, one solution might be to just add the adjustment to the key 
> time on all tasks on the queue?

I retract this suggestion as it's a very bad idea.  It introduces the 
possibility of starvation via the poor sods at the bottom of the queue 
having their "on CPU" forever postponed and we all know that even the 
smallest possibility of starvation will eventually cause problems.

I think there should be a rule: Once a task is on the queue its "on CPU" 
time is immutable.

Peter
-- 
Peter Williams                                   pwil3058@bigpond.net.au

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