Hardware Reference
In-Depth Information
a contradiction.
Only If
. If an aperiodic request enters the system periodically, with period
T
s
and
execution time
C
s
=
T
s
U
s
, the server behaves exactly as a periodic task with period
T
s
and execution time
C
s
, and the total utilization factor of the processor is
U
p
+
U
s
.
Hence, if the whole task set is schedulable, from the EDF schedulability bound [LL73]
we can conclude that
U
p
+
U
s
≤
1.
6.5
EARLIEST DEADLINE LATE SERVER
The Total Bandwidth Server is able to provide good aperiodic responsiveness with ex-
treme simplicity. However, a better performance can still be achieved through more
complex algorithms. For example, looking at the schedule in Figure 6.6, we could
argue that the second and the third aperiodic requests may be served as soon as they
arrive, without compromising the schedulability of the system. This is possible be-
cause, when the requests arrive, the active periodic instances have enough slack time
(laxity) to be safely preempted.
Using the available slack of periodic tasks for advancing the execution of aperiodic re-
quests is the basic principle adopted by the EDL server [SB94, SB96]. This aperiodic
service algorithm can be viewed as a dynamic version of the Slack Stealing algorithm
[LRT92].
The definition of the EDL server makes use of some results presented by Chetto and
Chetto [CC89]. In this paper, two complementary versions of EDF - namely, EDS and
EDL - are proposed. Under EDS the active tasks are processed as soon as possible,
whereas under EDL they are processed as late as possible. An important property of
EDL is that in any interval [0
,t
] it guarantees the maximum available idle time. In the
original paper, this result is used to build an acceptance test for aperiodic tasks with
hard deadlines, while here it is used to build an optimal server mechanism for soft
aperiodic activities.
To simplify the description of the EDL server,
ω
J
(
t
) denotes the following
availability
function
, defined for a scheduling algorithm
A
and a task set
J
:
ω
J
(
t
)=
1
if the processor is idle at
t
0
otherwise.
Search WWH ::
Custom Search