Hardware Reference
In-Depth Information
Proof.
If
. The condition is sufficient for the schedulability of the periodic task set
under EDF, thus even under EDL, which is a particular implementation of EDF. Now,
observe that in each schedule produced by the IPE algorithm the completion times of
the periodic instances are never greater than the completion times of the corresponding
instances in
σ
, which is the schedule of the periodic task set under EDL. That is, no
periodic instance can miss its deadline. The thesis follows.
Only If
. Trivial, since the condition is necessary even for the periodic task set only.
6.6.2
REMARKS
The reclaiming of unused periodic execution time can be done in the same way as for
the DPE server. When a periodic task completes, its spare time is added to the corre-
sponding aperiodic capacity. Again, this behavior does not affect the schedulability of
the system. The reason is of course the same as for the DPE server.
To implement the IPE server, the two arrays
must be precomputed before
the system is run. The replenishments of the server capacity are no longer peri-
odic, but this does not change the complexity, which is comparable with that of DPE.
What can change dramatically is the memory requirement. In fact, if the periods
of periodic tasks are not harmonically related, we could have a huge
hyperperiod
H
= lcm(
T
1
,...,T
n
), which would require a great memory space to store the two
arrays
E
and
D
E
and
D
.
6.7
IMPROVING TBS
The deadline assignment rule used by the TBS algorithm is a simple and efficient
technique for servicing aperiodic requests in a hard real-time periodic environment.
At the cost of a slightly higher complexity, such a rule can be modified to enhance
aperiodic responsiveness. The key idea is to shorten the deadline assigned by the TBS
as much as possible, still maintaining the periodic tasks schedulable [BS99].
If
d
k
is the deadline assigned to an aperiodic request by the TBS, a new deadline
d
k
can be set at the estimated worst-case finishing time
f
k
of that request, scheduled by
EDF with deadline
d
k
. The following lemma shows that setting the new deadline
d
k
at the current estimated worst-case finishing time does not jeopardize schedulability:
Search WWH ::
Custom Search