Messages in this thread | | | Date | Wed, 04 Aug 2004 11:36:59 +1000 | From | Peter Williams <> | Subject | Re: [PATCH] V-3.0 Single Priority Array O(1) CPU Scheduler Evaluation |
| |
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@bigpond.net.au
"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@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |