Exercises related to scheduling of periodic tasks

Time-Triggered Cyclic Executive Scheduling

Background for Time-Triggered Cyclic Executive Scheduling

In a task set $\Gamma$ of periodic tasks, each task $\tau_i$ is defined by:

its period $T_i$
its deadline $D_i$
its worst-case computation time $C_i$
its phase $\Phi_i$

Let’s define the following:

$\tau_{i,j}$ = the $j^{th}$ instance of task $\tau_i$ (called job)
$a_{i,j}$ = the arrival (release) time of job $\tau_{i,j}$
$d_{i,j}$ = the absolute deadline of job $\tau_{i,j}$
$D_i$ = the relative deadline of task $\tau_i$

If the period $T_i$ is constant, then:

$a_{i,j} = \Phi_i + (j - 1) T_i$
$d_{i,j} = \Phi_i + (j - 1) T_i + D_i$
if $T_i == D_i$, $d_{i,j} = \Phi_i + j * T_i$

In a Time-Triggered Cyclic Executive system, tasks will be run in an order computed offline and the following applies:

The system runs the tasks in a schedule that is repeated every major cycle $M$.
Each major cycle is divided into minor cycles of length $m$.

The following conditions apply to $M$ and $m$:

A task executes at most once within a minor cycle, $\forall \tau_i: m <= T_i$
Assuming that tasks cannot be split, all tasks start (but not all need to be started within the same cycle) and complete within a single minor cycle, $\forall \tau_i: m >= C_i$
$M$ is a multiple of $m$ (in other words, $m$ divides one of the task period)
There is at least one minor cycle $m$ between the arrival/release time and deadline of every task. Given that the largest possible time offset between the start of a minor cycle and the start of the period of $\tau_i$ is $m - gcd(T_i, m)$, this condition can be expressed as $\forall \tau_i: m + (m - gcd(T_i, m)) <= D_i$. Note that this condition subsumes the first condition.

A possible choice for $M$ and $m$ is:

$M = lcm(T_1,...,T_n)$
$m = gcd(T_1,...,T_n)$
$M$ being a multiple of each period and $m$ a divisor of each period, therefore $M$ is a multiple of $m$
$\forall \tau_i, gcd(T_i, m) >= m$ and thus $\forall \tau_i, m <= T_i$
Under the condition that tasks cannot be split, $\forall \tau_i: m >= C_i$ must still be met

It is important to note that $m$ is not necessarly as small as $gcd(T_1,...,T_n)$, nor is it sufficient that $\forall \tau_i: m <= T_i$

Given $M$ and $m$, the problem of finding a schedule that meets all task constraints is known to be NP-hard. Given that the schedule is computed off-line, algorithms and software exist for finding feasible schedules. If the set of tasks is sufficiently small, then a feasible schedule can often be found graphically. One possible method is to determine $M = lcm(T_1,...,T_n)$ and $m = gcd(T_1,...,T_n)$ and to start to schedule the tasks in increasing order of deadlines. If $m = gcd(T_1,...,T_n)$ does not meet the constraint, you must use another value of $m$. It is also possible that no solution exists for any $m$.

For verifying that a schedule meet all task constraints, the following algorithm can be applied:

Let $m_{i,j}$ be the minor cycle index in which job $\tau_{i,j}$ executes, starting at $1$.
For each task $\tau_{i}$, its phase $\Phi_i$ may be computed from the schedule as $\Phi_i = \min_{1<=j<=\frac{M}{T_i}} {((m_{i,j}-1) m - (j-1) T_i)}$
Note that if the phase is constrained to be $0$ for each task, then a feasible schedule is one where each computed $\Phi_i$ is $>= 0$
By choosing $\Phi_i$ as the minimum value, one guarantees that arrival/release times are respected, i.e. that a task is not scheduled before its arrival/release time.
The deadline must also be respected for each $\tau_{i,j}$: $\forall{\tau_i}, 1<=j<=\frac{M}{T_i}, (j-1) T_i + \Phi_i + D_i >= m_{i,j} m$

Exercise 1

Given the following set of tasks:

Task	T	D	C	$\Phi$
1	4	3	2	0
2	6	3	?	0

what is the largest possible value of $C_2$ such that a feasible schedule exists?

Solution

Both tasks have a phase $0$ and have to finish execution by time $3$. Since $C_1 = 2$, then $C_2 <= 1$.

Exercise 2

Given the following set of tasks:

Task	T	D	C
1	14	14	1
2	20	20	2
3	22	22	3

what are the values of $m$ that meet the requirements?

Solution

$\forall \tau_i: m <= T_i$: $1 <= m <= 14
$\forall \tau_i: m >= C_i$: $3 <= m <= 14
$m$ divides one of the task periods $14$, $20$ or $22$: $m=4,5,7,10,11,14$
$\forall \tau_i: m + (m - gcd(T_i, m)) <= D_i$: $m=4,5,7$

Exercise 3

Given the following set of tasks and values of with $M=20$ and $m=1$:

Task	T	D	C
1	4	3	2
2	5	4	2

what are the conditions for a feasible Time-Triggered Cyclic Executive schedule that are violated?

A task executes at most once within a frame
$M$ is a multiple of $m$
Assuming that tasks cannot be split, all tasks start and complete within a single frame
There is at least one frame between the arrival/release time and deadline of every task

Solution

$\forall \tau_i: m >= C_i$ is not respected, therefore tasks cannot start and finish within a single frame. In this case, $m = gcd(T_1, T_2)$ and $M = lcm(T_1, T_2)$ is not a valid solution.

Exercise 4

Given the following set of tasks and values of with $M=20$ and $m=3$:

Task	T	D	C
1	4	3	2
2	5	4	2

what are the conditions for a feasible Time-Triggered Cyclic Executive schedule that are violated?

A task executes at most once within a frame
$M$ is a multiple of $m$
Assuming that tasks cannot be split, all tasks start and complete within a single frame
There is at least one frame between the arrival/release time and deadline of every task

Solution

$M$ is not a multiple of $m$. $\forall \tau_i: 2m - gcd(T_i, m) <= D_i$ is not respected.

Exercise 5

Given the following set of tasks and values of with $M=20$ and $m=4$:

Task	T	D	C
1	4	3	2
2	5	4	2

what are the conditions for a feasible Time-Triggered Cyclic Executive schedule that are violated?

A task executes at most once within a frame
$M$ is a multiple of $m$
Assuming that tasks cannot be split, all tasks start and complete within a single frame
There is at least one frame between the arrival/release time and deadline of every task

Solution

$\forall \tau_i: 2m - gcd(T_i, m) <= D_i$ is not respected.

Exercise 6

Given the following set of tasks and values of with $M=20$ and $m=2$:

Task	T	D	C
1	4	3	2
2	5	4	2

what are the conditions for a feasible Time-Triggered Cyclic Executive schedule that are violated?

A task executes at most once within a frame
$M$ is a multiple of $m$
Assuming that tasks cannot be split, all tasks start and complete within a single frame
There is at least one frame between the arrival/release time and deadline of every task

Solution

All conditions are met.

Exercise 7

Given the following set of tasks:

Task	T	D	C
1	25	25	15
2	50	50	10
3	100	100	5

determine a feasible Time-Triggered Cyclic Executive schedule. Note that all phases are required to be $0$. The solution is simple enough for verifying graphically that arrival/release times and deadlines are respected.

Solution

Major Cycle = ppmc($T_{1}$, $T_{2}$, $T_{3}$) = $100$
Possible values for $m$ are:
1. $\forall \tau_i: m <= T_i: 1 <= m <= 100$
2. $\forall \tau_i: m >= C_i: 15 <= m <= 100$
3. $m$ divides one of the task periods $25, 50, 100$: $m=20,25,50,100$
4. $\forall \tau_i: m + (m - gcd(T_i, m) <= D_i: m=25$
$m = 25$
One can easily verify that all arrival/release times and deadlines are respected.

Exercise 8

Given the Time-Triggered Cyclic Executive schedule developed in the previous exercice, consider the case where the period $T_{2}$ is modified from $50$ to $40$. Does the schedule require important changes? Are the Minor Cycle and Major Cycle values the same?

Can you draw a schedule without splitting a task into several sub-tasks?

Task	T	D	C
1	25	25	15
2	40	50	10
3	100	100	5

Solution

Major Cycle = ppmc($T_{1}$, $T_{2}$, $T_{3}$) = $200$
Possible values for $m$ are:
1. $\forall \tau_i: m <= T_i: 1 <= m <= 100$
2. $\forall \tau_i: m >= C_i: 15 <= m <= 100$
3. $m$ divides one of the task periods $25, 40, 100$: $m=20,25,50,100$
4. $\forall \tau_i: m + (m - gcd(T_i, m) <= D_i: m=25$
One can easily verify that all arrival/release times and deadlines are respected.

Time-Triggered Cyclic Executive Scheduling (for codelab)

Exercise 9

Given the following set of tasks:

Task	T	D	C
1	15	3	3
2	10	5	3
3	6	6	3

determine a feasible Time-Triggered Cyclic Executive schedule. Demonstrate that your schedule meets all arrivals and deadlines.

Solution

Choose $M = ppmc(T_{1}, T_{2}, T_{3}) = 30$
Possible values for $m$ are:
1. $\forall \tau_i: m <= T_i: 1 <= m <= 6$
2. $\forall \tau_i: m >= C_i: 3 <= m <= 6$
3. $m$ divides one of the task periods $15, 10, 6$: $m=3,5,6$
4. $\forall \tau_i: m + (m - gcd(T_i, m) <= D_i: m=3$
$m = 3$

The phase of each task for respecting arrival times is computed as $\Phi_i = \min_{1<=j<=\frac{M}{T_i}} {((m_{i,j}-1) m - (j-1) T_i)}$
1. $i = 1$: $\Phi_1 = \min(0, 0) = 0$
2. $i = 2$: $\Phi_2 = \min(3, 2, 4) = 2$
3. $i = 3$: $\Phi_3 = \min(6, 3, 6, 3, 3) = 3$
The deadline is met for each task, $\forall{\tau_i}, 1<=j<=\frac{M}{T_i}, (j-1) T_i + \Phi_i + D_i >= m_{i,j} m$
1. $i = 1$:
  1. $j=1, m_{1,1}=1: 0 + 3 = 3 >= 3$
  2. $j=2, m_{1,2}=6: 15 + 0 + 3 = 18 >= 18 = 6 \times 3$
2. $i = 2$:
  1. $j=1, m_{2,1}=2: 2 + 5 = 7 >= 6 = 2 \times 3$
  2. $j=2, m_{2,2}=5: 10 + 2 + 5 = 17 >= 15 = 5 \times 3$
  3. $j=3, m_{2,3}=9: 20 + 2 + 5 = 27 >= 27 = 9 \times 3$
3. $i = 3$:
  1. $j=1, m_{3,1}=3: 3 + 9 = 9 >= 9 = 3 \times 3$
  2. $j=2, m_{3,2}=4: 6 + 3 + 6 = 15 >= 12 = 4 \times 3$
  3. $j=3, m_{3,3}=7: 12 + 3 + 6 = 21 >= 21 = 7 \times 3$
  4. $j=4, m_{3,4}=8: 18 + 3 + 6 = 27 >= 24 = 8 \times 3$

Rate Monotonic Scheduling (for codelab)

Exercise 10

Given the task set of exercise 7, show that the set of tasks is schedulable using the Rate Monotonic scheduling algorithm. Draw the schedule that will be computed from the Rate Monotonic Algorithm.

Solution

Major Cycle = ppmc($T_{1}$, $T_{2}$, $T_{3}$,) = $100$
Upper bound is $3 * (2^{(\frac{1}{3})} - 1) \approx 0.7797$
$\sum_{1}^{3}(\frac{C_i}{T_i}) = \frac{15}{25} + \frac{10}{50} + \frac{5}{100} = 0.85$
This condition is not respected.
Test the hyperbolic bound: $\prod_{1}^{3}(U_{i} + 1) = 1. 6 * 1.2 * 1.05 = 2.016$.
It is $\gt{2}$, so this condition is not respected.
However, we notice that our tasks form an harmonic task set, since $T_{3} = 2 * T_{2} = 4 * T_{1}$.
In this case, we have one harmonic subset, so the upperbound can be relaxed to $1 * (2^{(\frac{1}{1})} - 1) = 1.0$.
This condition is respected and the task set is schedulable.
The same schedule as the one obtained for Time-Triggered Cyclic Executive scheduling matches the RMA rules.