Hardware Reference
In-Depth Information
P
i
θ
i
τ
1
3
3
τ
2
2
3
τ
3
1
2
Table 8.2
Preemption thresholds assigned to the tasks of Table 8.1.
1
τ
1
3
τ
2
6
τ
3
0
2
4
6
8
10
12
14
16
18
20
Figure 8.8
Schedule produced by preemption thresholds for the task set in Table 8.1.
Note that at
t
=6,
τ
1
can preempt
τ
3
since
P
1
>θ
3
. However, at
t
=10,
τ
2
cannot
preempt
τ
3
, being
P
2
=
θ
3
. Similarly, at
t
=12,
τ
1
cannot preempt
τ
2
, being
P
1
=
θ
2
.
8.3.1
FEASIBILITY ANALYSIS
Under fixed priorities, the feasibility analysis of a task set with preemption thresholds
can be performed by the feasibility test derived by Wang and Saksena [WS99], and
later refined by Regehr [Reg02]. First of all, a task
τ
i
can be blocked only by lower
priority tasks that cannot be preempted by it; that is, by tasks having a priority
P
j
<P
i
and a threshold
θ
j
≥
P
i
. Hence, a task
τ
i
can experience a blocking time equal to the
longest computation time among the tasks with priority lower than
P
i
and threshold
higher than or equal to
P
i
. That is,
B
i
=ma
j
{
C
j
−
1
|
P
j
<P
i
≤
θ
j
}
(8.10)
where the maximum of an empty set is assumed to be zero. Then, the response time
R
i
of task
τ
i
is computed by considering the blocking time
B
i
, the interference before
its start time (due to the tasks with priority higher than
P
i
), and the interference after
its start time (due to tasks with priority higher than
θ
i
), as depicted in Figure 8.7. The
analysis must be carried out within the longest Level-
i
active period
L
i
, defined by the
following recurrent relation:
Search WWH ::
Custom Search