Re: [RFC][PATCH 09/22] sched: add period support for -deadline tasks

[Tommaso Cucinotta <tommaso.cucinotta@sssup.it>]

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