Question 3.55

25.

  1. Can all the processors being used to schedule tasks be simultaneously idle at a time before the completion time of a collection of tasks scheduled using the list-processing algorithm?
  2. Explain why the list-processing algorithm cannot yield the schedule below, regardless of what priority list was used to schedule the tasks on the three processors.
    image
  3. Construct an order-requirement digraph and a priority list that will yield the following schedule on two processors.
image

25.

(a) No

(b) If T5 could be started on Machine 3 and Machine 2 was also free at the same time, proper use of the list-processing algorithm should have assigned this task to Machine 2.

(c) Use the digraph with no edges and the list T2, T5, T4, T3, T1.