Scheduling

  1. (from Lee Shia's book, with adaptation)  This problem studies fixed-priority scheduling. Consider two tasks to be executed periodically on a single processor, where task 1 has period p1 = 4 and task 2 has period p2 = 6.
    1. Let the execution time of task 1 be e1 = 1. Find the maximum value for the execution time e2 of task 2 such that the RM schedule is feasible.
    2. Again let the execution time of task 1 be e1 = 1. Let non-RMS be a fixed-priority schedule that is not an RM schedule and gives higher priority to task 2. Find the maximum value for the execution time e2 of task 2 such that non-RMS is feasible.
    3. For the previous solutions to (a), (b)  and (c) above, find the processor utilization. Which is/are better?
    4. For RM scheduling, are there any value e1 and e2 that yield 100% utilization? If so, give and example.
  2. (from Lee Shia's book) This problem studies dynamic-priority scheduling. Consider two tasks to be executed periodically on a single processor, where task 1 has period p1 = 4 and task 2 has period p2 = 6. Let the deadlines for each invocation of the tasks be the end of their period. That is, the first invocation of task 1 has deadline 4, the second invocation of task 1 has deadline 8, and so on.
    1. Let the execution time of task 1 be e1 = 1. Find the maximum value for the execution time e2 of task 2 such that EDF is feasible.
    2. For the value of e2 that you found in (a), compare the EDF schedule against the RM schedule from Exercise 1 (a). Which schedule has less preemption? Which schedule has better utilization?
  3. (from Lee Shia's book)  This problem compares RM and EDF schedules. Consider two tasks with periods p1 = 2 and p2 = 3 and execution times e1 = e2 = 1. Assume that the deadline for each execution is the end of the period.
    1. Give the RM schedule for this task set and find the processor utilization. How does this utilization compare to the Liu and Layland utilization bound given by \( \mu \leq n(2^{1/n} -1) \)?
    2. Show that any increase in e1 or e2 makes the RM schedule infeasible.
    3. If you hold e1 = e2 = 1 and p2 = 3 constant, is it possible to reduce p1 below 2 and still get a feasible schedule? By how much?
    4. If you hold e1 = e2 = 1 and p1 = 2 constant, is it possible to reduce p2 below 3 and still get a feasible schedule? By how much?
    5. Increase the execution time of task 2 to be e2 = 1.5, and give an EDF schedule. Is it feasible? What is the processor utilization?
Última alteração: terça, 8 de junho de 2021 às 20:15