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\)

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).

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.

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 anew:

  1. the period and
  2. computation time

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