Hardware Reference
In-Depth Information
Given a set of
n
jobs
J
i
(
C
i
,D
i
,V
i
), where
C
i
is the worst-case computation time,
D
i
its relative deadline, and
V
i
the importance value gained by the system when the
task completes within its deadline, the maximum cumulative value achievable on the
task set is clearly equal to the sum of all values
V
i
; that is, Γ
max
=
i
=1
V
i
.In
overload conditions, this value cannot be achieved, since one or more tasks will miss
their deadlines. Hence, if Γ
∗
is the maximum cumulative value that can be achieved
by any algorithm on a task set in overload conditions, the performance of a scheduling
algorithm
A
can be measured by comparing the cumulative value Γ
A
obtained by
A
with the maximum achievable value Γ
∗
.
9.2.2
ON-LINE VERSUS CLAIRVOYANT
SCHEDULING
Since dynamic environments require online scheduling, it is important to analyze the
properties and the performance of online scheduling algorithms in overload condi-
tions. Although there exist optimal online algorithms in normal load conditions, it is
easy to show that no optimal on-line algorithms exist in overloads situations. Consider
for example the task set shown in Figure 9.7, consisting of three tasks
J
1
(10
,
11
,
10),
J
2
(6
,
7
,
6),
J
3
(6
,
7
,
6).
Without loss of generality, we assume that the importance values associated to the
tasks are proportional to their execution times (
V
i
=
C
i
) and that tasks are firm, so no
value is accumulated if a task completes after its deadline. If
J
1
and
J
2
simultaneously
arrive at time
t
0
=0, there is no way to maximize the cumulative value without
knowing the arrival time of
J
3
. In fact, if
J
3
arrives at time
t
=4or before, the
maximum cumulative value is Γ
∗
=10and can be achieved by scheduling task
J
1
(see Figure 9.7a). However, if
J
3
arrives between time
t
=5and time
t
=8, the
maximum cumulative value is Γ
∗
=12, achieved by scheduling task
J
2
and
J
3
, and
discarding
J
1
(see Figure 9.7b). Note that if
J
3
arrives at time
t
=9or later (see
Figure 9.7c), then the maximum cumulative value is Γ
∗
=16and can be accumulated
by scheduling tasks
J
1
and
J
3
. Hence, at time
t
=0, without knowing the arrival
time of
J
3
, no online algorithm can decide which task to schedule for maximizing the
cumulative value.
What this example shows is that without an a priori knowledge of the task arrival
times, no online algorithm can guarantee the maximum cumulative value Γ
∗
. This
value can only be achieved by an ideal clairvoyant scheduling algorithm that knows
the future arrival time of any task. Although the optimal clairvoyant scheduler is a pure
theoretical abstraction, it can be used as a reference model to evaluate the performance
of online scheduling algorithms in overload conditions.
Search WWH ::
Custom Search