Question 3.43

13.

  1. Use the accompanying order-requirement digraph to schedule the 6 tasks T1, T2, T3, T4, T5, T6 on two processors with the priority lists:
    1. T1, T2, T3, T4, T5, T6
    2. T1, T6, T3, T5, T4, T2
  2. Are either of the schedules produced from these lists optimal? If not, can you find a priority list that will result in an optimal schedule?
  3. Find the critical path and its length. Explain why no schedule has an earliest completion time equal to the length of the critical path.
image

13.

(a) (i) Processor 1: T1 from 0 to 13, T3 from 13 to 25, T6 from 25 to 45; Processor 2: T2 from 0 to 18, T4 from 18 to 27, T5 from 27 to 35, idle from 35 to 45 (ii) Processor 1: T1 from 0 to 13, T3 from 13 to 25, T4 from 25 to 34, T5 from 34 to 42; Processor 2: T2 from 0 to 18, T6 from 18 to 38, idle from 38 to 42

(b) Yes

(c) , and 38; sum of the task times divided by 2 is 40.