Hardware Reference
In-Depth Information
D OV ER : A COMPETITIVE ALGORITHM
9.2.6
Koren and Shasha [KS92] found an online scheduling algorithm, called D over , which
has been proved to be optimal, in the sense that it gives the best competitive factor
achievable by any online algorithm (that is, 0.25).
As long as no overload is detected, D over behaves like EDF. An overload is detected
when a ready task reaches its Latest Start Time (LST) ; that is, the time at which the
task's remaining computation time is equal to the time remaining until its deadline. At
this time, some task must be abandoned: either the task that reached its LST or some
other task.
In D over , the set of ready tasks is partitioned in two disjoint sets: privileged tasks and
waiting tasks. Whenever a task is preempted it becomes a privileged task. However,
whenever some task is scheduled as the result of a LST , all the ready tasks (whether
preempted or never executed) become waiting tasks.
When an overload is detected because a task J z
reaches its LST , then the value of
J z
is compared against the total value V priv
of all the privileged tasks (including the
value v curr
of the currently running task). If
v z > (1 + k )( v curr + V priv )
(where k is ratio of the highest value density and the lowest value density task in the
system), then J z
is executed; otherwise, it is abandoned. If J z
is executed, all the
privileged tasks become waiting tasks. Task J z
can in turn be abandoned in favor of
another task J x that reaches its LST , but only if
v x > (1 + k ) v z .
It is worth observing that having the best competitive factor among all online algo-
rithms does not mean having the best performance in any load condition. In fact,
in order to guarantee the best competitive factor, D over may reject tasks with values
higher than the current task but not higher than the threshold that guarantees optimal-
ity. In other words, to cope with worst-case sequences, D over does not take advantage
of lucky sequences and may reject more value than it is necessary. In Section 9.2.7,
the performance of D over is tested for random task sets and compared with the one of
other scheduling algorithms.
Search WWH ::




Custom Search