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

William Lee Irwin III
2004-08-03T10:49:27Z

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