V-3.0 Single Priority Array O(1) CPU Scheduler Evaluation

3. Priority based O(1) scheduler with active/expired arrays replaced by a single array and an O(1) promotion mechanism plus scheduling statistics with new interactive bonus mechanism and throughput bonus mechanism:

Quoted 1 line · Peter Williams

3. Priority based O(1) scheduler with active/expired arrays replaced by a single array and an O(1) promotion mechanism plus scheduling statistics with new interactive bonus mechanism and throughput bonus mechanism:

Hmm. Given do_promotions() I'd expect fenceposts, not iteration over the priority levels of the runqueue.

Quoted 2 lines

Hmm. Given do_promotions() I'd expect fenceposts, not iteration over the priority levels of the runqueue.

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?

Quoted 2 lines · William Lee Irwin III

Quoted 2 lines

Hmm. Given do_promotions() I'd expect fenceposts, not iteration over the priority levels of the runqueue.

Quoted 1 line · Peter Williams

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

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.

Quoted 6 lines · Peter Williams

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.

Quoted 7 lines

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.

Quoted 7 lines · William Lee Irwin III

Quoted 7 lines

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.

Quoted 1 line · Peter Williams

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.

Aperiodic rotations defer movement until MAX_RT_PRIO's slot is evacuated.

Quoted 2 lines

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.

The asymptotics were in terms of SCHED_NORMAL priorities.

Quoted 1 line · Peter Williams

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.

The primary concern was that ticklessness etc. may require it to occur during context switches.

Quoted 1 line

Aperiodic rotations defer movement until MAX_RT_PRIO's slot is evacuated.

Unfortunately, to ensure no starvation, promotion has to continue even when there are tasks in MAX_RT_PRIO's slot.

Quoted 2 lines

The primary concern was that ticklessness etc. may require it to occur during context switches.

On a tickless system, I'd consider using a timer to control when do_promotions() gets called. I imagine something similar will be necessary to manage time slices?

Quoted 1 line · William Lee Irwin III

Quoted 1 line

Aperiodic rotations defer movement until MAX_RT_PRIO's slot is evacuated.

Quoted 1 line · Peter Williams

Unfortunately, to ensure no starvation, promotion has to continue even when there are tasks in MAX_RT_PRIO's slot.

One may either demote to evict MAX_RT_PRIO immediately prior to rotation or rely on timeslice expiry to evict MAX_RT_PRIO. Forcibly evicting MAX_RT_PRIO undesirably accumulates tasks at the fencepost.

Quoted 2 lines · William Lee Irwin III

Quoted 2 lines

The primary concern was that ticklessness etc. may require it to occur during context switches.

Quoted 1 line · Peter Williams

On a tickless system, I'd consider using a timer to control when do_promotions() gets called. I imagine something similar will be necessary to manage time slices?

This is an alternative to scheduler accounting in context switches. Periodicity often loses power conservation benefits.

Quoted 6 lines

Quoted 2 lines

Unfortunately, to ensure no starvation, promotion has to continue even when there are tasks in MAX_RT_PRIO's slot.

One may either demote to evict MAX_RT_PRIO immediately prior to rotation or rely on timeslice expiry to evict MAX_RT_PRIO. Forcibly evicting MAX_RT_PRIO undesirably accumulates tasks at the fencepost.

It's starting to get almost as complex as the current scheme :-)

Quoted 3 lines

One may either demote to evict MAX_RT_PRIO immediately prior to rotation or rely on timeslice expiry to evict MAX_RT_PRIO. Forcibly evicting MAX_RT_PRIO undesirably accumulates tasks at the fencepost.

It's starting to get almost as complex as the current scheme :-)

Quoted 2 lines

This is an alternative to scheduler accounting in context switches. Periodicity often loses power conservation benefits.

The timer would be deactivated whenever the number of runnable tasks for the runqueue goes below 2. The whole thing could be managed from the enqueue and dequeue functions i.e.
dequeue - if the number running is now less than two cancel the timer

and otherwise decrease the expiry time to maintain the linear relationship of the interval with the number of runnable tasks enqueue - if the number of runnable tasks is now 2 then start the time with a single interval setting and if the number is greater than two then increase the timer interval to maintain the linear relationship. I'm assuming here that add_timer(), del_timer() and (especially) mod_timer() are relatively cheap. If mod_timer() is too expensive some alternative method could be devised to maintain the linear relationship.

William Lee Irwin III wrote:

Quoted 4 lines · Peter Williams

The timer would be deactivated whenever the number of runnable tasks for the runqueue goes below 2. The whole thing could be managed from the enqueue and dequeue functions i.e. dequeue - if the number running is now less than two cancel the timer and otherwise decrease the expiry time to maintain the linear relationship of the interval with the number of runnable tasks enqueue - if the number of runnable tasks is now 2 then start the time with a single interval setting and if the number is greater than two then increase the timer interval to maintain the linear relationship. I'm assuming here that add_timer(), del_timer() and (especially) mod_timer() are relatively cheap. If mod_timer() is too expensive some alternative method could be devised to maintain the linear relationship.

Naive schemes reprogram the timer device too frequently.

Software
constructs are less of a concern. This also presumes that taking timer interrupts when cpu-intensive workloads voluntarily yield often enough is necessary or desirable.

This is not so in virtualized environments,
and unnecessary interruption of userspace also degrades performance.

Quoted 3 lines

Software constructs are less of a concern. This also presumes that taking timer interrupts when cpu-intensive workloads voluntarily yield often enough is necessary or desirable.

Voluntary yielding can't be relied upon. Writing a program that never gives up the CPU voluntarily is trivial. Some have been known to do it without even trying :-)

Quoted 3 lines · William Lee Irwin III

Quoted 3 lines

Software constructs are less of a concern. This also presumes that taking timer interrupts when cpu-intensive workloads voluntarily yield often enough is necessary or desirable.

On Thu, Aug 05, 2004 at 11:06:51AM +1000, Peter Williams wrote:

Quoted 1 line

Voluntary yielding can't be relied upon. Writing a program that never gives up the CPU voluntarily is trivial. Some have been known to do it without even trying :-)

No reliance is implied. In such a scenario, the timers for timeslice expiry are always cancelled because userspace voluntarily yields first, so no timer interrupts are delivered. Should userspace fail to do so, timer interrupts programmed for timeslice expiry would not be cancelled.