Hardware Reference
In-Depth Information
Note that the algorithm in Figure 4.17 has a pseudo-polynomial complexity. In fact,
the guarantee of the entire task set requires O ( nN ) steps, where n is the number of
tasks and N is the number of iterations in the inner loop, which does not depend
directly on n , but on the period relations.
4.5.3
WORKLOAD ANALYSIS
Another necessary and sufficient test for checking the schedulability of fixed priority
systems with constrained deadlines was proposed by Lehoczky, Sha, and Ding [LSD89].
The test is based on the concept of Level- i workload, defined as follows.
Definition 4.1 The Level- i workload W i ( t ) is the cumulative computation time re-
quested in the interval (0 ,t ] by task τ i and all the tasks with priority higher than P i .
For a set of synchronous periodic tasks, the Level- i workload can be computed as
follows:
t
T h
C h .
W i ( t )= C i +
h : P h >P i
(4.19)
Then, the test can be expressed by the following theorem:
Theorem 4.3 (Lehoczky, Sha, Ding, 1989) A set of fully preemptive periodic tasks
can be scheduled by a fixed priority algorithm if and only if
i =1 ,...,n
t
(0 ,D i ]: W i ( t )
t.
(4.20)
Later, Bini and Buttazzo [BB04] restricted the number of points in which condition
(4.20) has to be checked to the following Testing Set :
de =
TS i
P i− 1 ( D i )
(4.21)
where
P i ( t ) is defined by the following recurrent expression:
P 0 ( t )=
{
t
}
P i− 1 T i T i
(4.22)
P i ( t )=
∪P i− 1 ( t ) .
Thus, the schedulability test can be expressed by the following theorem:
Search WWH ::




Custom Search