[lkml]   [2012]   [Apr]   [11]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: [PATCH 08/16] sched: add period support for -deadline tasks.
    Il 11/04/2012 21:32, Steven Rostedt ha scritto:
    > On Fri, 2012-04-06 at 09:14 +0200, Juri Lelli wrote:
    >> @@ -293,7 +293,11 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se)
    >> * assigned (function returns true if it can).
    >> *
    >> * For this to hold, we must check if:
    >> - * runtime / (deadline - t)< dl_runtime / dl_deadline .
    >> + * runtime / (deadline - t)< dl_runtime / dl_period .
    >> + *
    >> + * Notice that the bandwidth check is done against the period. For
    >> + * task with deadline equal to period this is the same of using
    >> + * dl_deadline instead of dl_period in the equation above.
    > First, it seems that the function returns true if:
    > dl_runtime / dl_period< runtime / (deadline - t)
    > I'm a little confused by this. We are comparing the ratio of runtime
    > left and deadline left, to the ratio of total runtime to period.
    > I'm actually confused by this premise anyway. What's the purpose of
    > comparing the ratio? If runtime< (deadline - t) wouldn't it not be able
    > to complete anyway? Or are we thinking that the runtime will be
    > interrupted proportionally by other tasks?

    That's a well-known property of the CBS scheduling algorithm:
    the "unblock rule" says that, when a task wakes up, if the residual
    budget over residual deadline fits within the allocated "bandwidth",
    then we can keep the current (abs) deadline and residual budget
    without disrupting the schedulability of the system (i.e., ability of
    other admitted tasks to meet their deadlines).
    Otherwise, we should reset the status, i.e., refill budget and set
    the deadline a period in the future, because keeping the current
    abs deadline of the task would result in breaking guarantees
    promised to other tasks.
    Imagine a task going to sleep and waking
    too close to its deadline: its deadline would be the closest in the
    system, and it wouldn't allow anyone else to run. However, if its
    residual budget is also big, then this is going to not allow anyone
    to run for too much. Now, when doing the classical easy admission
    test for single-CPU EDF (sum of budgets over periods <= 1), we
    hadn't accounted for such a scenario with tasks blocking (which can
    actually be accounted for by using far more complex tests knowing
    for how long each task will block etc.). However, using the CBS, we
    can keep the easy test and add the simple cut-off rule at task
    wake-up which adds "temporal isolation", i.e., the capability
    to not disrupt others' guarantees if I sleep for too much.
    Said this, I guess/hope the rule is implemented right :-)

    For a formal proof, I think you can refer to the Abeni's paper(s):

    -) Integrating Multimedia Applications in Hard Real-Time Systems, RTSS '98

    which redirects on the Technical Report:
    -) Server Mechanisms for Multimedia Applications

    Hope this helps,


    Tommaso Cucinotta, Computer Engineering PhD, Researcher
    ReTiS Lab, Scuola Superiore Sant'Anna, Pisa, Italy
    Tel +39 050 882 024, Fax +39 050 882 003

     \ /
      Last update: 2012-04-12 01:15    [W:0.026 / U:4.432 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site