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:0.593 / U:0.292 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site