Hardware Reference
In-Depth Information
will not be minimized. On the other hand, if
J
1
is delayed to minimize
J
2
, then
J
1
will suffer. Hence, there is no optimal algorithm that can minimize the response time
of any aperiodic request.
Note that Theorem 5.2 applies both to clairvoyant and online algorithms since the
example is applicable regardless of whether the algorithm has a priori knowledge of
the aperiodic requests. The same example can be used to prove another important
result on the minimization of the average response time.
Theorem 5.3 (Tia, Liu, Shankar)
For any set of periodic tasks ordered on a given
fixed-priority scheme and aperiodic requests ordered according to a given aperiodic
queueing discipline, no online valid algorithm exists that minimizes the average re-
sponse time of the soft aperiodic requests.
Proof.
From the example illustrated in Figure 5.23 it is easy to see that, if there is only
request
J
1
in each hyperperiod, then scheduling
J
1
as soon as possible will yield the
minimum average response time. On the other hand, if
J
1
and
J
2
are present in each
hyperperiod, then scheduling each aperiodic request as soon as possible will not yield
the minimum average response time. This means that, without a priori knowledge of
the aperiodic requests' arrival, an online algorithm will not know when to schedule
the requests.
5.9
PERFORMANCE EVALUATION
The performance of the various algorithms described in this chapter has been com-
pared in terms of average response times on soft aperiodic tasks. Simulation experi-
ments have been conducted using a set of ten periodic tasks with periods ranging from
54 to 1200 units of time and utilization factor
U
p
=0
.
69. The aperiodic load was
varied across the unused processor bandwidth. The interarrival times for the aperiodic
tasks were modeled using a Poisson arrival pattern with average interarrival time of
18 units of time, whereas the computation times of aperiodic requests were modeled
using an exponential distribution. Periods for PS, DS, PE, and SS were set to handle
aperiodic requests at the highest priority in the system (priority ties were broken in
favor of aperiodic tasks). Finally, the server capacities were set to the maximum value
for which the periodic tasks were schedulable.
Search WWH ::
Custom Search