TU/e, CS-Report 07-11, April 2007
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 ). 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 = Ci + ∑
j<i T j
Theorem 3 (Theorem 4.3 in ). The worst-case response time WR i of task τi can be found by the following iterative procedure.
Ci + ∑
l = 0, 1, . . .
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 , 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).
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 ). 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
+ 1 C j.
x = Ci + ∑
Theorem 5 (Theorem 4.5 in ). The worst-case occupied time WO i of task τi can be found by the following iterative
∑ C j for Ci = 0
for Ci > 0
= Ci + ∑
+ 1 C j , l = 0, 1, . . .
The procedure is stopped when the same value is found for two successive iterations of l.