Question 3.38

8. Consider the order-requirement digraph below:

image
  1. Find the length of the critical path.
  2. Schedule these seven tasks on two processors using the list algorithm and the lists:
    1. T1, T2, T3, T4, T5, T6, T7
    2. T2, T1, T3, T6, T5, T4, T7
  3. Does either list lead to a completion time that equals the length of the critical path?
  4. Show that no list can ever lead to a completion time equal to the length of the critical path (providing the schedule uses two processors).