Question 3.57

27.

  1. Making use of the order-requirement digraph below, determine at time 0 which tasks are ready.
    image
  2. What is special about tasks T1 and T6?
  3. What is the critical path, and what is its length?
  4. Schedule the tasks on three processors with the priority list T1, …, T6.
  5. Is the schedule found in part (d) optimal?
  6. Schedule the tasks on three processors using the priority list T6, …, T1.
  7. Is the schedule found in part (f) optimal?
  8. Can you find a priority list that yields an optimal schedule?

27.

(a) T1, T2, T3, and T6

(b) No tasks require that T1 and T6 be done before these other tasks can begin.

(c) T6

(d) Processor 1: T1, T6; Processor 2: T2, T4, idle from 18 to 30; Processor 3: T3, T5, idle from 12 to 30

(e) No

(f) Processor 1: T6, idle from 20 to 22; Processor 2: T3, T5, T1; Processor 3: T2, T4, idle from 18 to 22

(g) Yes

(h) Yes