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

Peter Williams
2004-08-04T00:38:33Z

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

While pondering this I have stumbled on a problem that rules out using a
rotating list for implementing promotion. The problem is that one of
the requirements is that once a SCHED_NORMAL task is promoted to the
MAX_RT_PRIO slot it stays there (as far as promotion is concerned).
With the rotating list this isn't guaranteed and, in fact, any tasks
that are in the MAX_RT_PRIO slot when promotion occurs will actually be
demoted to IDLE_PRIO - 1.

Promotion should be a rare event as it is unnecessary if there's less
than two tasks on the runqueue and when there are more than one task on
the runqueue the interval between promotions increases linearly with the
number of runnable tasks. It is also an O(1) operation albeit with a
constant factor determined by the number of occupied SCHED_NORMAL
priority slots.

I will modify the code to take better advantage of the fact that
promotion is not required when the number of runnable tasks is less than
2 e.g. by resetting next_prom_due so that the first promotion after the
number of runnable tasks exceeds 1 will only occur after a full
promotion interval has expired. At normal loads (and with sensible
promotion interval settings i.e. greater than the time slice size) this
should result in promotion never (or hardly ever) occurring and the
overhead of do_promotions() will only have to be endured when it's
absolutely necessary.