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:
> 
>>>Hmm. Given do_promotions() I'd expect fenceposts, not iteration over
>>>the priority levels of the runqueue.
> 
> 
> On Tue, Aug 03, 2004 at 10:33:36AM +1000, Peter Williams wrote:
> 
>>I don't understand what you mean.  Do you mean something like the more 
>>complex promotion mechanism in the (earlier) EBS scheduler where tasks 
>>only get promoted if they've been on a queue without being serviced 
>>within a given time?
> 
> 
> An array of size N can be rotated in O(1) time

And with a smaller constant than my do_promotions(). :-)

> if an integer is kept
> along with it to represent an offset that has to be added to externally-
> visible indices mod N to recover the true index.

OK.  Now I understand.

The main reason that I didn't do something like that is that 
(considering that real time tasks don't get promoted) it would complicate:

1. the selection (in schedule()) of the next task to be run as it would 
no longer be a case of just finding the first bit in the bitmap,
2. determining the appropriate list to put the task on in 
enqueue_task(), etc., and
3. determining the right bit to turn off in the bit map when dequeuing 
the last task in a slot.

As these are frequent operations compared to promotion I thought it 
would be better to leave the complexity in do_promotion().  Now that 
you've caused me to think about it again I realize that the changes in 
the above areas may not be as complicated as I thought would be 
necessary.  So I'll give it some more thought.

Thanks for the suggestion
Peter
-- 
Peter Williams                                   pwil3058@bigpond.net.au

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