[lkml]   [2010]   [Aug]   [3]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: periods and deadlines in SCHED_DEADLINE
    On Sun, 2010-07-11 at 08:46 +0200, Bjoern Brandenburg wrote:
    > I'd be hesitant to just assume that it "approximates G-EDF"
    > sufficiently well to apply any of the published G-EDF tests.

    OK, suppose that for each cpu we keep the earliest and next-earliest
    deadline in a table. Then on wakeup (job release) we pick the cpu with
    the currently last deadline to preempt (we push the task).

    On sleep (job completion) we look for the earliest among all
    next-earliest deadlines to select the next runnable task (we pull the

    If we serialize all this using one big lock around this [ {earliest,
    next-earliest} ] table, we've basically implemented G-EDF, agreed?

    Now replace that global lock with an algorithm that looks at the table,
    finds the last-earliest or earliest-next-earliest in a lock-less
    fashion, then locks the target cpu's rq->lock, verifies the result and
    either continues or tries again.

    So we replace the global lock with cmpxchg like loops using 2 per-cpu
    locks. Our current SCHED_FIFO balancer does just this and is found to be
    a very good approximation of global-fifo (iirc there's one funny case,
    but I can't remember, maybe Steve or Gregory can remember the details).

     \ /
      Last update: 2010-08-03 10:19    [W:0.020 / U:7.152 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site