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?

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?

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

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

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

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

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.

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

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.

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.