lkml.org 
[lkml]   [2004]   [Aug]   [3]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH] V-3.0 Single Priority Array O(1) CPU Scheduler Evaluation
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.


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.


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

\
 
 \ /
  Last update: 2005-03-22 14:04    [from the cache]
©2003-2011 Jasper Spaans. Advertise on this site