[lkml]   [2004]   [Aug]   [3]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    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
    More majordomo info at
    Please read the FAQ at

     \ /
      Last update: 2005-03-22 14:04    [W:0.023 / U:14.636 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site