Homework assignment #2: Fixed-priority preemptive scheduilng of periodic task systems (solutions)

Consider the following set of implicit-deadline periodic tasks.

1. Draw a Gantt chart of the non-preemptive rate-monotonic schedule for this set of tasks. (10 pt)

   

2. Draw a Gantt chart of the preemptive rate-monotonic schedule for this set of tasks. (10 pt)

   

3. Draw a Gantt chart of the non-preemptive earliest-deadline-first (EDF) schedule for this set of tasks. (10 pt)

   

4. Draw a Gantt chart of the preemptive EDF schedule for this set of tasks. (10 pt)

   

   Note that the schedules turned out to be the same for (1), (2), and (3) for this task set. In general, these four methods may produce four different schedules.

5. Use the method of Lemma 6.6 in Jane Liu's book (iterative computation of a least-fixed-point solution of the recurrence) to compute the worst-case response time of each of the tasks, under fixed-task-priority scheduling. (10 pt)

   • R_1,0 = e₁ = 2

   • R_2,0 = e₁ + e₂ = 2 + 3 = 5

     R_2,1 = e₁ * ⌈ R_2,0/p₁⌉ + e₂ = 2 * ⌈ 5 / 6 ⌉ + 3 = 5

   • R_3,0 = e₁ + e₂ + e₃ = 2 + 3 + 3 = 8

     R_3,1 = e₁ * ⌈ R_3,0/p₁⌉ + e₂ * ⌈ R_3,0/p₂⌉ + e₃ = 2 * ⌈ 8 / 6 ⌉ + 3 * ⌈ 8 / 8 ⌉ + 3 = 4 + 3 + 3 = 10

     R_3,2 = 2 * ⌈ 10 / 6 ⌉ + 3 * ⌈ 10 / 8 ⌉ + 3 = 4 + 6 + 3 = 13

     R_3,3 = 2 * ⌈ 13 / 6 ⌉ + 3 * ⌈ 13 / 8 ⌉ + 3 = 6 + 6 + 3 = 15

     R_3,4 = 2 * ⌈ 15 / 6 ⌉ + 3 * ⌈ 15 / 8 ⌉ + 3 = 6 + 6 + 3 = 15