Hardware Reference
In-Depth Information
We finally show that the EDL server is optimal; that is, the response times of the
aperiodic requests under the EDL algorithm are the best achievable.
Lemma 6.3
Let
A
be any online preemptive algorithm,
τ
a periodic task set, and
J
i
an aperiodic request. If
f
τ∪{J
i
}
(
J
i
)
is the finishing time of
J
i
when
τ
∪{
J
i
}
is
scheduled by
A
, then
f
EDL server
τ∪{J
i
}
f
τ∪{J
i
}
(
J
i
)
.
(
J
i
)
≤
Proof.
Suppose
J
i
arrives at time
t
, and let
τ
(
t
) be the set of the current active
periodic instances (ready but not yet completed) and the future periodic instances.
The new task
J
i
is scheduled together with the tasks in
τ
(
t
). In particular, consider
the schedule
σ
of
τ
under
A
. Let
A
be another algorithm that schedules the
tasks in
τ
(
t
) at the same time as in
σ
, and
σ
be the corresponding schedule.
J
i
is
executed during some idle periods of
σ
. Applying Theorem 6.4 with the origin of the
time axis translated to
t
(this can be done since
A
is online), we know that for each
t
≥
∪{
J
i
}
t
Ω
A
τ
(
t
)
(
t, t
)
.
Recall that when there are aperiodic requests, the EDL server allocates the executions
exactly during the idle times of EDL. Being
Ω
EDL
τ
(
t
)
(
t, t
)
≥
Ω
A
Ω
EDL
τ
(
t
)
(
t, f
EDL server
τ
(
t
)
(
t, f
EDL server
(
J
i
))
≥
(
J
i
))
τ∪{J
i
}
τ∪{J
i
}
it follows that
f
τ∪{J
i
}
f
EDL
τ∪{J
i
}
(
J
i
)
.
That is, under the EDL server,
J
i
is never completed later than under the
A
algorithm.
(
J
i
)
≤
6.6
IMPROVED PRIORITY EXCHANGE SERVER
Although optimal, the EDL server has too much overhead to be considered practical.
However, its main idea can be usefully adopted to develop a less complex algorithm
that still maintains a nearly optimal behavior.
The heavy computation of the idle times can be avoided by using the mechanism of
priority exchanges. With this mechanism, in fact, the system can easily keep track of
the time advanced to periodic tasks and possibly reclaim it at the right priority level.
Search WWH ::
Custom Search