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

[William Lee Irwin III <wli@holomorphy.com>]

On Tue, Aug 03, 2004 at 01:39:02PM +1000, Peter Williams wrote:
> 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.

In such schemes, realtime tasks are considered separately from
timesharing tasks. Finding a task to run or migrate proceeds with a
circular search of the portion of the bitmap used for timesharing tasks
after a linear search of that for RT tasks. The list to enqueue a
timesharing task in is just an offset from the fencepost determined by
priority. Dequeueing is supported with a tag for actual array position.
I did this for aperiodic queue rotations, which differs from your SPA.


-- wli