Skip to content

Exercises related to scheduling of hybrid set of tasks (periodic and aperiodic)

Background Scheduling

Consider two periodic tasks defined as (\(C_{1} = 1\), \(T_{1} = 5\)) and (\(C_{2} = 2\), \(T_{2} = 6\)). Consider that the Rate Monotonic Algorithm is applied for scheduling this set of tasks.

Given that the aperiodic tasks is made of two tasks defined as \(C_{3} = 3\) and \(C_{4} = 1\), draw the schedule for the following aperiodic arrival times using background scheduling:

  • task \(3\) at arrival time \(= 2\)
  • task \(4\) at arrival time \(= 7\)
  • task \(4\) at arrival time \(= 17\)
  • task \(3\) at arrival time \(= 21\)
Solution

The schedule is illustrated here:

Polling Server

Consider the same two periodic tasks defined as (\(C_{1} = 1\), \(T_{1} = 5\)) and (\(C_{2} = 2\), \(T_{2} = 6\)). Consider that the Rate Monotonic Algorithm is applied for scheduling this set of tasks.

This system has to be extended for handling aperiodic tasks, using a Polling Server.

Exercice 1

Determine:

  1. the period and
  2. computation time

of the Polling Server task, for maximum utilization and high priority (thus responsiveness).

Solution

First of all, we may check that the set of periodic tasks is schedulable:

\(U = \frac{1}{5} + \frac{2}{6} \approx 0.533\), thus \(U < 2 (2^{\frac{1}{2}} - 1) \approx 0.828\).

Given the bound \(U_{S} <= \frac{2-P}{P}\), with \(P = \prod_{i=1}^{2}{(U_{i} + 1)} = \frac{6}{5} * \frac{4}{3} = \frac{8}{5}\), \(U_{S} <= \frac{\frac{2}{5}}{\frac{8}{5}} = \frac{1}{4}\).

If we set \(T_{S} = 4\) (as high priority), we get \(C_{S} = 1\).

Exercice 2

Given that the aperiodic tasks are composed by two tasks defined as \(C_{3} = 3\) and \(C_{4} = 1\), draw the schedule for the following aperiodic arrival times:

  • task \(3\) at arrival time \(= 2\)
  • task \(4\) at arrival time \(= 7\)
  • task \(4\) at arrival time \(= 17\)
  • task \(3\) at arrival time \(= 21\)

Note that in the case of an intermediate priority, the computation time of task \(3\) exceeds the server budget allocated for each server period. From this example, explain the specific requirements for a scheduler that would allow an execution of aperiodic tasks without exceeding the server budget.

Solution

The schedule is illustrated here:

From the schedule, you may observe that: - at time \(t = 4\), although task \(1\) has a lower priority than task \(3\), task \(3\) must stop its execution because the budget for the server is entirely consumed. This cannot be implemented with a standard priority-based preemption scheme since task \(1\) has a lower priority than the preempted task. The scheduler should implement a budget base behavior in this particular case. - at time \(t = 8\), task \(3\) resumes and stops again when the budget of the server is gone.

Polling Server (accounting for aperiodic task maximum computation time)

Given the same configuration as in the previous exercice, choose a value of \(C_{S}\) so that it exceeds \(C_{i}\) of all aperiodic tasks. Also assume that no aperiodic task starts its execution if the budget is not available for executing the entire task.

Exercice 3

Determine:

  1. the period and
  2. computation time
Solution

We have again \(U_{S} = \frac{1}{4}\).

We need to have \(C_{S} >= 3\), so we get \(C_{S} = 3\) and \(T_{S} = 12\). The task for serving aperiodic tasks gets a lower priority and the average response time will increase.

The schedule is illustrated here:

From the schedule, you may observe that it correspond to a priority-based preemptive scheme. We also observe that the response time of aperiodic tasks is larger than the ones obtained with a lower period for \(T_{S}\).

Deferrable Server

Given the same configuration as in the previous exercice, implement a solution with a Deferrable Server instead of a Polling Server.

Exercice 4

Determine:

  1. the period and
  2. computation time
  3. the graph of the schedule
Solution

Given the hyperbolic bound, the schedulability is guaranteed if \(U_{S} <= \frac{2 - P}{2P - 1}\), with \(P = \prod_{i=1}^{2}{(U_{i} + 1)} = \frac{6}{5} * \frac{4}{3} = \frac{8}{5}\).

The condition is thus \(U_{S} <= \frac{\frac{2}{5}}{\frac{11}{5}} = \frac{2}{11}\).

As for the previous exercice, we may choose \(C_{S} = 3\) and \(T_{S} = 18\), with \(T_{S} = \frac{1}{6} <= \frac{2}{11}\).

The difference as compared to the polling server is that there is no polling time and that the server budget is available for the entire period.

The schedule is illustrated here:

From the schedule, you may observe that it correspond to a priority-based preemptive scheme. We also observe that the response time of aperiodic tasks is smaller than the ones obtained with a similar polling server.