Hardware Reference
In-Depth Information
H = a
First Come First Served (FCFS)
H = C
Shortest Job First (SJF)
H = d
Earliest Deadline First (EDF)
H = T
Earliest Start Time First (ESTF)
est
H = d + w C
EDF + SJF
H = d + w T
EDF + ESTF
est
Figure 3.11
Example of heuristic functions that can be adopted in the Spring algorithm.
where
W
is a weight that can be adjusted for different application environments. Fig-
ure 3.11 shows some possible heuristic functions that can be used in Spring to direct
the search process.
In order to handle precedence constraints, another factor
E
, called
eligibility
, is added
to the heuristic function. A task becomes eligible to execute (
E
i
=1) only when
all its ancestors in the precedence graph are completed. If a task is not eligible, then
E
i
=
∞
; hence, it cannot be selected for extending a partial schedule.
While extending a partial schedule, the algorithm determines whether the current
schedule is
strongly feasible
; that is, also feasible by extending it with any of the re-
maining tasks. If a partial schedule is found not to be strongly feasible, the algorithm
stops the search process and announces that the task set is not schedulable, otherwise
the search continues until a complete feasible schedule is met. Since a feasible sched-
ule is reached through
n
nodes and each partial schedule requires the evaluation of
most
n
heuristic functions, the complexity of the Spring algorithm is
O
(
n
2
).
Backtracking can be used to continue the search after a failure. In this case, the al-
gorithm returns to the previous partial schedule and extends it by the task with the
second smallest heuristic value. To restrict the overhead of backtracking, however, the
maximum number of possible backtracks must be limited. Another method to reduce
the complexity is to restrict the number of evaluations of the heuristic function. Due
to that, if a partial schedule is found to be strongly feasible, the heuristic function is
applied not to all the remaining tasks but only to the
k
remaining tasks with the earliest
deadlines. Given that only
k
tasks are considered at each step, the complexity becomes
Search WWH ::
Custom Search