APERIODIC TASK SCHEDULING - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 66

ing paths on the tree and build a complete schedule in polynomial time. Heuristic
algorithms may produce a feasible schedule in polynomial time; however, they do not
guarantee to find it, since they do not explore all possible solutions.

3.4.1 BRATLEY'S ALGORITHM

( 1

| NO PREEM | FEASIBLE )

The following algorithm was proposed by Bratley et al. in 1971 [BFR71] to solve the
problem of finding a feasible schedule of a set of non-preemptive tasks with arbitrary
arrival times. The algorithm starts with an empty schedule and, at each step of the
search, visits a new vertex and adds a task in the partial schedule. With respect to the
exhaustive search, Bratley's algorithm uses a pruning technique to determine when
a current search can be reasonably abandoned. In particular, a branch is abandoned
when

the addition of any node to the current path causes a missed deadline;

a feasible schedule is found at the current path.

To better understand the pruning technique adopted by the algorithm, consider the task
set shown in Figure 3.10, which also illustrates the paths analyzed in the tree space.

To follow the evolution of the algorithm, the numbers inside each node of the tree indi-
cate which task is being scheduled in that path, whereas the numbers beside the nodes
represent the time at which the indicated task completes its execution. Whenever the
addition of any node to the current path causes a missed deadline, the corresponding
branch is abandoned and the task causing the timing fault is labeled with a ( † ).

In the example, the first task considered for extending the empty schedule is J 1 , whose
index is written in the first node of the leftmost branch of the tree. Since J 1 arrives at
t =4and requires two units of processing time, its worst-case finishing time is f 1 =6,
indicated beside the correspondent node. Before expanding the branch, however, the
pruning mechanism checks whether the addition of any node to the current path may
cause a timing fault, and it discovers that task J 2 would miss its deadline, if added. As
a consequence, the search on this branch is abandoned and a considerable amount of
computation is avoided.

In the average case, pruning techniques are very effective for reducing the search
space. Nevertheless, the worst-case complexity of the algorithm is still O ( n · n !).