EXAMPLE 2 Applying the List-Processing Algorithm
Let’s apply the list-processing algorithm to one possible priority list—T8, T7, T6, …, T1—using two processors and the order-requirement digraph in Figure 3.1. The result is the schedule shown in Figure 3.2, where idle processor time (time during which a processor is not at work on a task) is indicated by white. How does the list-processing algorithm generate this schedule?
85
T8 (task 8) is first on the priority list and ready at time 0 since it has no predecessors. It is assigned to the lowest-numbered free processor, processor 1. Task 7, next on the priority list, is also ready at time 0 and thus is assigned to processor 2. The first processor to become free is processor 2 at time 5. Recall that by assumption 1, once a processor starts work on a task, its work cannot be interrupted until the task is complete. Task 6, the next unassigned task on the list, is not ready at time 5, as can be seen by consulting Figure 3.1. The reason task 6 is not ready at time 5 is that task 5 has not been completed by time 5. In fact, at time 5, the only ready task on the list is T1, so that task is assigned to processor 2. At time 7, processor 1 becomes free, but no task becomes ready until time 13.
Thus, processor 1 stays idle from time 7 to time 13. At this time, because T2 is the first ready task on the list not already scheduled, it is assigned to processor 1. Processor 2, however, stays idle because no other ready task is available at this time. The remainder of the scheduling shown in Figure 3.2 is completed in this manner.