10.1.1.95.9702.pdf


Aperçu du fichier PDF 10-1-1-95-9702.pdf - page 6/39

Page 1...4 5 67839


Aperçu texte


TU/e, CS-Report 07-11, April 2007

6

Given this theorem, we conclude that time 0 in Figure 3 is a critical instant for both task τ 1 and τ2 . From this figure, we
therefore derive that the worst-case response times of tasks τ 1 and τ2 are 2 and 5, respectively. The next theorems can be
used to determine the worst-case response times analytically.
Theorem 2 (Theorem 4.2 in [5]). The worst-case response time WR i of a task τi is given by the smallest x ∈ R+ that satisfies
the following equation, provided that x is at most Ti .

x
Cj
x = Ci + ∑
(7)
j<i T j

Theorem 3 (Theorem 4.3 in [5]). The worst-case response time WR i of task τi can be found by the following iterative procedure.
(0)

WRi

(l+1)

WRi

=
=

Ci



Ci + ∑

j<i

(l)
WRi

Tj

(8)



C j,

l = 0, 1, . . .

(9)

The procedure is stopped when the same value is found for two successive iterations of l, or when the deadline D i is exceeded.

3.2 Worst-case occupied times
In Figure 3, task τ 2 is preempted at time 15 due to a release of task τ 1 , and resumes its execution at time 17. The span of time
from a task τ’s release till the moment in time that τ can start or resume its execution after completion of a computation time
C is termed occupied time. The worst-case occupied time (WO) of a task τ is the longest possible span of time from a release
of τ till the moment in time that τ can start or resume its execution after completion of a computation C. In [5], it has been
shown that the worst-case occupied time can be described in terms of the worst-case response time as follows.
WOi (Ci ) = lim WRi (x).
x↓Ci

(10)

Considering Figure 3, we derive that worst-case occupied times WO 2 (0) and WO2 (C2 ) of task τ2 are equal to 2 and 7,
respectively. The next theorems can be used to determine the worst-case occupied times analytically.
Theorem 4 (Theorem 4.4 in [5]). When the smallest positive solution of (7) for a computation time C i is at most Di , the
worst-case occupied time WOi of a task τi with a computation time Ci ∈ [0,Ci ] is given by the smallest non-negative x ∈ R
that satisfies


x
(11)
+ 1 C j.
x = Ci + ∑
Tj
j<i

Theorem 5 (Theorem 4.5 in [5]). The worst-case occupied time WO i of task τi can be found by the following iterative
procedure.

∑ C j for Ci = 0
(0)
j<i
(12)
=
WOi
WRi
for Ci > 0



(l)
WOi
(l+1)
WOi
= Ci + ∑
(13)
+ 1 C j , l = 0, 1, . . .
Tj
j<i
The procedure is stopped when the same value is found for two successive iterations of l.