EXAMPLE 3 Scheduling Two Processors
To illustrate this method, consider the order-requirement digraph in Figure 3.10a. Suppose we wish to schedule these tasks on two processors. Initially, there are two critical paths of length 64: T1, T2, T3 and T1, T4, T3. Thus, we place T1, first on the priority list. With T1, “gone,” there is a new critical path of length 60 (T5, T6, T4, T3) that starts with T5, so T5 is placed second on the priority list. At this stage, with T, and T5 removed, we have the residual order-requirement digraph shown in Figure 3.10b. In this diagram, there are paths of length 50 (T2, T3), 56 (T6, T4, T3), 36 (T6, T4, T7), and 24 (T8, T9, T10). Because T6 heads the path that is currently longest in length, it is placed third in the priority list. Once T6 is removed from Figure 3.10b, there is a tie for which is the longest path remaining, because both T2, T3 and T4, T3 are paths of length 50.
When there is a tie between two longest paths, we place next on the priority list the lowest-numbered task heading a longest path. In the example shown here, this means that T2 is placed next on the priority list, to be followed by T4. Continuing in this fashion, we obtain the priority list T1, T5, T6, T2, T4, T3, T8, T9, T7, T10. Note that the order of T7 and T10 was decided using the rule for breaking ties. The list-processing algorithm is now applied using this priority list and the order-requirement digraph in Figure 3.10a. We obtain the schedule in Figure 3.11.
