Exercises related to scheduling of periodic tasks

Timeline 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 for each task, 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\).
Tasks that are released at the beginning of a minor cycle can be assigned to this minor cycle.

The following conditions apply for the choice of \(M\) and \(m\):

A task executes at most once within a minor cycle, so the minor cycle cannot be longer than any task’s period: \(\forall \tau_i: m <= T_i\)
\(M\) is a multiple of \(m\). In other words, \(m\) divides one of the task period and \(M\) is a common multiple of all tasks periods.
Each task starts and completes within a single minor cycle, \(\forall \tau_i: m >= C_i\)
There is at least one minor cycle \(m\) between the arrival/release time and deadline of every task, so that each job can run completely. 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 released 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 conditions must be verified:

Are \(M\) and \(m\) valid? \(M\) must be a common multiple of all periods and a multiple of \(m\).
Is each minor cycle long enough?
- Let \(m_{i,j}\) be the minor cycle index in which job \(\tau_{i,j}\) executes, starting at \(1\), with \(\tau_{i,j}\) being the \(j^th\) instance of job \(\tau_i\) in the major cycle.
- For every minor cycle with index \(k\), the sum of \(C_i\) of all jobs assigned to it must be \(<= m\). This can be expressed as \(\sum_{i | m_{i,j} = k}{C_i} <= m, \forall{1 <= k <= \frac{M}{m}}\)
Are release/arrival times respected?
- A job can’t run before it is released. For each task \(\tau_{i}\), choose the phase \(\Phi_i\) as \(\Phi_i = \min_{1<=j<=\frac{M}{T_i}} {((m_{i,j}-1) m - (j-1) T_i)}\).
- Choosing this phase or any smaller one guarantees that every job starts at or after its release.
- Note that if the phase is constrained to be \(0\) for each task, then a feasible schedule is one where each bound computed for \(\Phi_i\) is \(>= 0\)
Are deadlines 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 (BikeComputer tasks, values divided by \(100\)). We assume \(D==T\) and \(\Phi==0\) for every task. The Display task can be split into two subtasks.

Task	T	C
1 - Speed	4	2
2 - Gear	8	1
3 - Reset	8	1
4 - Temperature	16	1
5 - Display	16	3

demonstrate that this set of tasks is schedulable using a Time-Triggered Cyclic Executive algorithmks. Draw a full major cycle of the task schedule

Exercise 2

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 3

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 4

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 5

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 6

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 7

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 8

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 9

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	40	10
3	100	100	5

Exercise 10

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.