Hardware Reference
In-Depth Information
5.8
NON-EXISTENCE OF OPTIMAL SERVERS
The Slack Stealer always advances all available slack as much as possible and uses
it to execute the pending aperiodic tasks. For this reason, it originally was consid-
ered an optimal algorithm; that is, capable of minimizing the response time of every
aperiodic request. Unfortunately, the Slack Stealer is not optimal because to mini-
mize the response time of an aperiodic request, it is sometimes necessary to schedule
it at a later time even if slack is available at the current time. Indeed, Tia, Liu, and
Shankar [TLS95] proved that, if periodic tasks are scheduled using a fixed-priority
assignment, no algorithm can minimize the response time of every aperiodic request
and still guarantee the schedulability of the periodic tasks.
Theorem 5.2 (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 valid algorithm exists that minimizes the response time of every
soft aperiodic request.
Proof.
Consider a set of three periodic tasks with
C
1
=
C
2
=
C
3
=1and
T
1
=3,
T
2
=4and
T
3
=6, whose priorities are assigned based on the RM algorithm. Fig-
ure 5.23a shows the schedule of these tasks when no aperiodic requests are processed.
Now consider the case in which an aperiodic request
J
1
, with
C
a
1
=1, arrives at time
t
=2. At this point, any algorithm has two choices:
1. Do not schedule
J
1
at time
t
=2. In this case, the response time of
J
1
will be
greater than 1 and, thus, it will not be the minimum.
2. Schedule
J
1
at time
t
=2. In this case, assume that another request
J
2
, with
C
a
2
=1, arrives at time
t
=3. Since no slack time is available in the interval
[3
,
6],
J
2
can start only at
t
=6and finish at
t
=7. This situation is shown in
Figure 5.23b.
However, the response time of
J
2
achieved in case 2 is not the minimum. In fact, if
J
1
were scheduled at time
t
=3, another unit of slack would have been available at time
t
=4; thus,
J
2
would have been completed at time
t
=5. This situation is illustrated
in Figure 5.23c.
The above example shows that it is not possible for any algorithm to minimize the
response times of
J
1
and
J
2
simultaneously. If
J
1
is scheduled immediately, then
J
2
Search WWH ::
Custom Search