Hardware Reference
In-Depth Information
∀
i
=1
,...,n
j
:
P
j
<P
i
{
max
q
j
−
1
}≤
β
i
.
This implies that to achieve feasibility we must have
∀
i
=1
,...,n
q
i
≤
k
:
P
k
>P
i
{
min
β
k
+1
}
Hence, the longest non-preemptive interval
Q
i
that preserves feasibility for each task
τ
i
is
Q
i
=min
k
:
P
k
>P
i
{
β
k
+1
}
.
(8.22)
The
Q
i
terms can also be computed more efficiently, starting from the highest priority
task (
τ
1
) and proceeding with decreasing priority order, according to the following
theorem:
Theorem 8.2
The longest non-preemptive interval
Q
i
of task
τ
i
that preserves feasi-
bility can be computed as
Q
i
=min
{
Q
i−
1
,β
i−
1
+1
}
(8.23)
where
Q
1
=
∞
and
β
1
=
D
1
−
C
1
.
Proof.
The theorem can be proved by noting that
k
:
P
k
>P
i
{
min
β
k
+1
}
=min
{
k
:
P
k
>P
i−
1
{
min
β
k
+1
}
,β
i−
1
+1
}
,
and since from Equation (8.22)
Q
i−
1
=min
k
:
P
k
>P
i−
1
{
β
k
+1
}
we have that
Q
i
=min
{
Q
i−
1
,β
i−
1
+1
}
,
which proves the theorem.
Note that in order to apply Theorem 8.2,
Q
i
is not constrained to be less than or equal
to
C
i
, but a value of
Q
i
greater than
C
i
means that
τ
i
can be fully executed in non-
preemptive mode. The algorithm for computing the longest non-preemptive intervals
is illustrated in Figure 8.12.
Search WWH ::
Custom Search