Hardware Reference
In-Depth Information
to aperiodic requests. The response times achieved by this method are optimal, so they
cannot be reduced further.
The procedure to compute the idle times of the EDL schedule is described in Chetto
and Chetto [CC89] and is not reported here. However, it is interesting to observe that
not all the idle times have to be recomputed, but only those preceding the deadline of
the current active periodic task with the longest deadline.
The worst-case complexity of the algorithm is
O
(
Nn
), where
n
is the number of
periodic tasks and
N
is the number of distinct periodic requests that occur in the
hyperperiod. In the worst case,
N
can be very large and, hence, the algorithm may
be of little practical interest. As for the Slack Stealer, the EDL server will be used to
provide a lower bound to the aperiodic response times and to build a nearly optimal
implementable algorithm, as described in the next section.
6.5.1
EDL SERVER PROPERTIES
The schedulability analysis of the EDL server is quite straightforward. In fact, all
aperiodic activities are executed using the idle times of a particular EDF schedule;
thus, the feasibility of the periodic task set cannot be compromised. This is stated in
the following theorem:
Theorem 6.5 (Spuri, Buttazzo)
Given a set of
n
periodic tasks with processor uti-
lization
U
p
and the corresponding EDL server (whose behavior strictly depends on
the characteristics of the periodic task set), the whole set is schedulable
if
and
only if
U
p
≤
1
.
Proof.
If
. Since the condition (
U
p
≤
1) is sufficient for guaranteeing the schedulabil-
ity of a periodic task set under EDF, it is also sufficient under EDL, which is a partic-
ular implementation of EDF. The algorithm schedules the periodic tasks according to
one or the other implementation, depending on the particular sequence of aperiodic re-
quests. When aperiodic requests are pending, they are scheduled during precomputed
idle times of the periodic tasks. In both cases the timeliness of the periodic task set is
unaffected and no deadline is missed.
Only If
. If a periodic task set is schedulable with an EDL server, it will be also schedu-
lable without the EDL server, and hence (
U
p
≤
1).
Search WWH ::
Custom Search