lkml.org 
[lkml]   [2010]   [Nov]   [11]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [RFC][PATCH 09/22] sched: add period support for -deadline tasks
    Il 11/11/2010 20:43, Peter Zijlstra ha scritto:
    >> The more correct --in the sense that it at least yield a sufficient (not
    >> necessary!) condition-- thing to do would be
    >> sum_i(runtime_i/min{deadline_i,period_i})<=threshold.
    >>
    >> So, what you think we should do? Can I go for this latter option?
    > So sufficient (but not necessary) means its still a pessimistic approach
    > but better than the one currently employed, or does it mean its
    > optimistic and allows for unschedulable sets to be allowed in?
    It means that, if the new task passes the test, then it has its
    guaranteed runtime_i over each time horizon as long as min{deadline_i,
    period_i} (and all of the other tasks already admitted have their
    guarantees as well of course). From the perspective of analyzing
    capability of the attached task to meet its own deadlines, if the task
    has a WCET of runtime_i, a minimum inter-arrival period of period_i, and
    a relative deadline of deadline_i, then it is guaranteed to meet all of
    its deadlines.

    Therefore, this kind of test is sufficient for ensuring schedulability
    of all of the tasks, but it is not actually necessary, because it is too
    pessimistic. In fact, consider a task with a period of 10ms, a runtime
    of 3ms and a relative deadline of 5ms. After the test passed, you have
    actually allocated a "share" of the CPU capable of handling 3ms of
    workload every 5ms. Instead, we actually know that (or, we may actually
    force it to), after the deadline at 5ms, this task will actually be idle
    for further 5ms, till its new period. There are more complex tests which
    account for this, in the analysis.

    Generally speaking, with deadlines different from periods, a tighter
    test (for partitioned EDF) is one making use of the demand-bound
    function, which unfortunately is far more heavyweight than a mere
    utilization check (for example, you should perform a number of checks
    along a time horizon that can go as far as the hyper-period [LCM of the
    periods] of the considered task-set -- something that may require
    arbitrary precision arithmetics in the worst-case). However, you can
    check the *RT* conferences in the last 10 years in order to see all the
    possible trade-offs between accuracy of the test and the imposed
    computation requirement/overhead.

    Summarizing, the test suggested by Dario is sufficient to ensure the
    correct behavior of the accepted tasks, under the assumption that they
    stick to the "sporadic RT task model", it is very simple to implement in
    the kernel, but it is somewhat pessimistic. Also, it actually uses only
    2 parameters, the runtime and the min{deadline_i, period_i}.
    This clarifies also why I was raising the issue of whether to have at
    all the specification of a deadline \neq period, in my other e-mail. If
    the first implementation will just use the minimum of 2 of the supplied
    parameters, then let them be specified as 1 parameter only: it will be
    easier for developers to understand and use. If we identify later a
    proper test we want to use, then we can exploit the "extensibility" of
    the sched_params.

    My 2 cents.

    T.

    --
    Tommaso Cucinotta, Computer Engineering PhD, Researcher
    ReTiS Lab, Scuola Superiore Sant'Anna, Pisa, Italy
    Tel +39 050 882 024, Fax +39 050 882 003
    http://retis.sssup.it/people/tommaso



    \
     
     \ /
      Last update: 2010-11-12 00:37    [W:9.020 / U:0.020 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site