Re: [PATCH] V-3.0 Single Priority Array O(1) CPU Scheduler Evaluation
From: Peter Williams
Date: Tue Aug 03 2004 - 19:40:03 EST
William Lee Irwin III wrote:
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
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
Peter Williams pwil3058@xxxxxxxxxxxxxx
"Learning, n. The kind of ignorance distinguishing the studious."
-- Ambrose Bierce
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/