Question 3.59

29. Consider the following order-requirement digraph. Suppose one plans to schedule these tasks on two identical processors.

image
  1. How many different priority lists can be used to schedule the tasks?
  2. Can all these priority lists lead to different schedules? If not, why not?
  3. Can an optimal schedule have no idle time? Can you give two different reasons why an optimal schedule must have some idle time?
  4. Is there any list that produces a schedule where the second processor has no idle time?

29.

(a) 120

(b) No; T1 must be assigned to the first machine at time 0.

(c) No; when 2 divides 31, there is a remainder of 1.

(d) No