Scheduling: List Processing Algorithm Example

Example

Create the schedule on three processors using the following order requirement digraph and the priority list T3, T5, T1, T2, T7, T4, T6.

Solution

Priority List: T3, T5, T1, T2, T7, T4, T6.

We would like to schedule T3 on processor 1, but looking at the order requirement digraph we see we can't since it requires T1 to be complete. T5 cannot be scheduled either, but T1 can. The first step in our schedule looks like:

Priority List: T3, T5, T1, T2, T7, T4, T6.

We would like to schedule T3 on processor 2, but we can't. In fact, nothing else can be scheduled until T1 has finished! Every other task in our order requirement digraph depends on T1 being completed.

Therefore, the next task is scheduled in processor 1, after T1 has completed. Looking at our priority list, we would like to schedule T3 on processor 1, but looking at the order requirement digraph we see we can't since it requires T4 to be complete. T5, T2, T7 cannot be scheduled either, but T4 can. The second step in our schedule looks like:

Priority List: T3, T5, T1, T2, T7, T4, T6.

We would like to schedule T3 on processor 2, but we can't. We would like to schedule T5 on processor 2, but we can't. We would like to schedule T7 on processor 2, but we can't. We can't schedule any more jobs until after T4 completes. After T4 completes, we can schedule T3 on processor 1 and T7 on processor 2. The third step in our schedule looks like:

Priority List: T3, T5, T1, T2, T7, T4, T6.

After T3 completes, we can schedule T2 on processor 1. The fourth step in our schedule looks like:

Priority List: T3, T5, T1, T2, T7, T4, T6.

After T2 completes, we can schedule T5 on processor 1, and T6 on processor 2. The fifth step in our schedule looks like:

Notice that for this priority list we ended up scheduling nothing on processor 3! The tasks had too much interdependence to make the third processor useful. The total time to complete the job under this priority list is 36.