Hardware Reference
In-Depth Information
empty schedule
partial schedule
feasible
schedule
complete
schedule
F
F
F
Figure 3.9
Search tree for producing a non-preemptive schedule.
known a priori, then no online algorithm can decide whether to stay idle at time 0 or
execute task
J
1
. A scheduling algorithm that does not permit the processor to be idle
when there are active jobs is called a
non-idle
algorithm. By restricting to the case of
non-idle scheduling algorithms, Jeffay, Stanat, and Martel [JSM91] proved that EDF
is still optimal in a non-preemptive task model.
When arrival times are known a priori, non-preemptive scheduling problems are usu-
ally treated by branch-and-bound algorithms that perform well in the average case
but degrade to exponential complexity in the worst case. The structure of the search
space is a search tree, represented in Figure 3.9, where the root is an
empty schedule
,
an intermediate vertex is a
partial schedule
, and a terminal vertex (
leaf
)isa
com-
plete schedule
. Since not all leaves correspond to feasible schedules, the goal of the
scheduling algorithm is to search for a leaf that corresponds to a feasible schedule.
At each step of the search, the partial schedule associated with a vertex is extended by
inserting a new task. If
n
is the total number of tasks in the set, the length of a path
from the root to a leaf (
tree depth
) is also
n
, whereas the total number of leaves is
n
!
(
n
factorial). An optimal algorithm, in the worst case, may make an exhaustive search
to find the optimal schedule in such a tree, and this may require to analyze
n
paths of
length
n
!, with a complexity of
O
(
n
n
!). Clearly, this approach is computationally
intractable and cannot be used in practical systems when the number of tasks is high.
ยท
In this section, two scheduling approaches are presented, whose objective is to limit
the search space and reduce the computational complexity of the algorithm. The first
algorithm uses additional information to prune the tree and reduce the complexity in
the average case. The second algorithm adopts suitable heuristics to follow promis-
Search WWH ::
Custom Search