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

[Peter Williams]

William Lee Irwin III wrote:
> William Lee Irwin III wrote:
>
> > > 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.
>
>
> On Wed, Aug 04, 2004 at 10:37:57AM +1000, Peter Williams wrote:
>
> > 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.

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

> On Wed, Aug 04, 2004 at 10:37:57AM +1000, Peter Williams wrote:
>
> > 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.
>
>
> On Wed, Aug 04, 2004 at 10:37:57AM +1000, Peter Williams wrote:
>
> > 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.

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?

Peter
--
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/