Hardware Reference
In-Depth Information
Jeffay and Stone [JS93] found a schedulability condition for a set of
n
hard tasks and
m
interrupt handlers. In their work, the analysis is carried out by assuming a discrete
time, with a resolution equal to a tick. As a consequence, every event in the system
occurs at a time that is a multiple of the tick. In their model, there is a set
of
m
handlers, characterized by a worst-case execution time
C
i
and a minimum separation
time
T
i
, just as sporadic tasks. The difference is that interrupt handlers always have
a priority higher than the application tasks.
I
The upper bound,
f
(
l
), for the interrupt handling cost in any time interval of length
l
can be computed by the following recurrent relation [JS93]:
f
(0) = 0
f
(
l
)=
f
(
l
if
i
=1
l
C
i
−
1) + 1
>f
(
l
−
1)
T
i
(10.1)
f
(
l
−
1)
otherwise.
In the particular case in which all the interrupt handlers start at time
t
=0, function
f
(
l
) is exactly equal to the amount of time spent by processor in executing interrupt
handlers in the interval [0
,l
].
Theorem 10.1 (Jeffay-Stone)
A set
T
of
n
periodic or sporadic tasks and a set
I
of
m
interrupt handlers is schedulable by EDF if and only if for all
L
,
L
≥
0
,
L
T
i
C
i
n
≤
L
−
f
(
L
)
.
(10.2)
i
=1
The proof of Theorem 10.1 is very similar to the one presented for Theorem 4.5. The
only difference is that, in any interval of length
L
, the amount of time that the processor
can dedicate to the execution of application tasks is equal to
L
−
f
(
L
).
It is worth noting that Equation (10.2) can be checked only for a set of points equal
to release times less than the hyperperiod, and the complexity of the computation is
pseudo-polynomial.
Search WWH ::
Custom Search