lkml.org 
[lkml]   [2007]   [Sep]   [3]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [ANNOUNCE/RFC] Really Fair Scheduler
    Hi,

    On Sun, 2 Sep 2007, Daniel Walker wrote:

    > For instance if there are three tasks in the system. Call them A,B, and
    > C.
    >
    > then
    >
    > time equals "time of A" + "time of B" + "time of C"

    Ok, let's take a simple example. :)

    If we have three task A, B, C, each with a weight of 1, 2, 3, so the
    weight sum is 6. If we let these three tasks run over a period of 12s,
    each task gets time/weight_sum*weight_{t} seconds, that is each task gets
    2, 4, 6 seconds of runtime.
    The basic idea of CFS is now that using this formula, the time is
    distributed to the active tasks and accounted against the runtime they
    get. Let's assume a time slice of 1s, where each task gets
    1s/weight_sum*weight_{t} of eligible runtime every second, so in the
    following table the task column contains the values (eligible runtime
    - obtained runtime):

    time current A B C fair_clock
    1 C 1/6-0 2/6-0 3/6-1 1/6
    2 C 2/6-0 4/6-0 6/6-2 2/6
    3 C 3/6-0 6/6-0 9/6-3 3/6
    4 B 4/6-0 8/6-1 12/6-3 4/6
    5 B 5/6-0 10/6-2 15/6-3 5/6
    6 A 6/6-1 12/6-2 18/6-3 6/6
    7 C 7/6-1 14/6-2 21/6-4 7/6
    8 C 8/6-1 16/6-2 24/6-5 8/6
    9 C 9/6-1 18/6-2 27/6-6 9/6
    10 B 10/6-1 20/6-3 30/6-6 10/6
    11 B 11/6-1 22/6-4 33/6-6 11/6
    12 A 12/6-2 24/6-4 36/6-6 12/6

    Practically the eligible runtime part isn't updated constantly, but a
    delta against the last update is used. If everything is working
    correctly in the end the difference between the eligible and obtained
    runtime is zero.

    Peter's patches now make an interesting step, basically they change the
    position of the weight_{t} variable, so every task get's now
    1s/weight_sum per second and weight_{t} is now used to scale the
    obtained runtime instead:

    time current A B C fair_clock
    1 C 1/6-0/1 1/6-0/2 1/6-1/3 1/6
    2 C 2/6-0/1 2/6-0/2 2/6-2/3 2/6
    3 C 3/6-0/1 3/6-0/2 3/6-3/3 3/6
    4 B 4/6-0/1 4/6-1/2 4/6-3/3 4/6
    5 B 5/6-0/1 5/6-2/2 5/6-3/3 5/6
    6 A 6/6-1/1 6/6-2/2 6/6-3/3 6/6
    7 C 7/6-1/1 7/6-2/2 7/6-4/3 7/6
    8 C 8/6-1/1 8/6-2/2 8/6-5/3 8/6
    9 C 9/6-1/1 9/6-2/2 9/6-6/3 9/6
    10 B 10/6-1/1 10/6-3/2 10/6-6/3 10/6
    11 B 11/6-1/1 11/6-4/2 11/6-6/3 11/6
    12 A 12/6-2/1 12/6-4/2 12/6-6/3 12/6

    As you can see here the fair_clock part is the same for every task in
    every row, so that it can be removed, this is basically the step I do in
    my patch:

    time current A B C fair_clock
    1 C 0/1 0/2 1/3 1/6
    2 C 0/1 0/2 2/3 2/6
    3 C 0/1 0/2 3/3 3/6
    4 B 0/1 1/2 3/3 4/6
    5 B 0/1 2/2 3/3 5/6
    6 A 1/1 2/2 3/3 6/6
    7 C 1/1 2/2 4/3 7/6
    8 C 1/1 2/2 5/3 8/6
    9 C 1/1 2/2 6/3 9/6
    10 B 1/1 3/2 6/3 10/6
    11 B 1/1 4/2 6/3 11/6
    12 A 2/1 4/2 6/3 12/6

    This means fair_clock isn't used in the runtime calculation anymore and
    time isn't relative to fair_clock, but it's an absolute value. It looks
    relatively simple, but it means all calculations involving fair_clock
    deltas and wait_runtime values have to be redone in this context and
    that's the part where I need some help with - some of the tuning
    features aren't converted yet.
    The importance of this step is that it removes a major error source for
    the accuracy of the scheduler. All these fractions have to be rounded to
    integer values at some point and the main problem here is that the
    denominator in the fair_clock calculation is variable - it changes with
    the number of active tasks and it requires quite some resolution, so the
    error doesn't become noticable.

    fair_clock isn't used here anymore, but it's still used to initialize the
    time value of new tasks. For this I can approximate it and that is the
    major part of the math involved to make it so accurate, that the error
    doesn't grow over time and stays within a certain limit.
    The basic idea here is to compensate for the rounding errors which are
    inevitable. Let's look at the last row at time 12, if we add up the time
    values and denormalize them (remove the weight part), we get a sum like
    this: round(2/1)*1 + round(4/2)*2 + round(6/3)*3 ~= 12, that means I don't
    use the real time value 12, I use an approximated time value instead which
    is calculated from the individual task times so it includes the rounding
    errors that happened during the calculation of these task times.

    Basically that's it and I hope that explains the basic math a bit easier. :-)

    bye, Roman
    -
    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: 2007-09-03 20:23    [W:0.029 / U:1.564 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site