Exercises related to dependent tasks

NPP and Unnecessary Blocking

Exercice 1

NPP is simple to implement and it avoids deadlock. But it introduces unnecessary blocking, meaning that a task with higher priority that does not require access to the critical section can be blocked. Illustrate a scenario with 3 tasks where NPP introduces unnecessary blocking.

Maximum Blocking Time Using PIP

Exercice 2

Consider a system with 3 tasks \(\tau_1\), \(\tau_2\), and \(\tau_3\), with decreasing priority. The tasks share 3 resources \(A\), \(B\), and \(C\). Assume that the system is implementing PIP and compute the maximum blocking time \(B_i\) for each task, knowing that the longest access duration of task \(\tau_i\) on resource \(A\), \(B\), and \(C\) is defined as:

Task	\(A\)	\(B\)	\(C\)
\(\tau_{1}\)	3	0	3
\(\tau_{2}\)	3	4	0
\(\tau_{3}\)	4	3	6

Hint: recall the following points:

Using PIP, a task \(\tau_i\) can be blocked at most once for each lower priority task, i.e. at most for one critical section that can be owned by each lower priority task.
A task \(\tau_i\) can be blocked
- through direct blocking: a lower priority task that shares a critical section with \(\tau_i\) owns the critical section.
- through push-through blocking: a medium-priority task is blocked by a low priority task that has inherited a higher priority. It can happen only if a critical section is accessed both by a task with lower priority and by a task with higher priority.

Situation for Maximum Blocking Time Using PIP

Exercice 3

For the task set described in the previous exercise, illustrate the situation in which task \(\tau_2\) experiences its maximum blocking time, when using RM and PIP.

Hint: you must first compute the maximum blocking time of task \(\tau_2\) and reproduce the corresponding situation

Blocking Time Upper Bound using PIP

Exercice 3

The computation of the blocking time upper bound under PIP can be computed with the following algorithm:

Input: Durations \(\delta_{i,k}\) for each task \(\tau_{i}\) and each mutex \(M_{k}\)
Output: \(B_{i}\) for each task \(\tau_{i}\)

Notation: \(Ceiling(M_{k})\) is the priority ceiling of mutex \(M_{k}\).
Notation: \(P_{i}\) is the priority of task \(i\).
Notation: \(\delta_{j,k}\) is the duration of the longest critical section of task \(\tau_{i}\) guarded by mutex \(M_{k}\).

// Assumes tasks are ordered by decreasing priorities
(1) begin
(2) for i := 1 to n − 1 do // for each task
(3) \(B^{l}_{i}\) := 0;
(4) for j := i + 1 to n do // for each lower priority task
(5) \(D_{max}\) := 0;
(6) for k := 1 to m do // for each semaphore
(7) if (\(Ceiling(M_{k})\) ≥ \(P_{i}\)) and (\(\delta_{j,k}\) > \(D_{max}\)) do
(8) \(D_{max}\) := \(\delta_{j,k}\);
(9) end
(10) end
(11) if (\(D_{max}\) > 0) do
(11) \(B^{l}_{i}\) := \(B^{l}_{i}\) + \(D_{max}\);
(12) end
(12) end
(13) \(B^{s}_{i}\) := 0;
(14) for k := 1 to m do // for each semaphore
(15) \(D_{max}\) := 0;
(16) for j := i + 1 to n do // for each lower priority task
(17) if (\(Ceiling(M_{k})\) ≥ \(P_{i}\)) and (\(\delta_{j,k}\) > \(D_{max}\)) do
(18) \(D_{max}\) := \(\delta_{j,k}\);
(19) end
(20) end
(11) if (\(D_{max}\) > 0) do
(21) \(B^{s}_{i}\) := \(B^{s}_{i}\) + \(D_{max}\);
(12) end
(22) end
(23) \(B_{i}\) := min(\(B^{l}_{i}\), \(B^{s}_{i}\));
(24) end
(25) \(B_{n}\) := 0;
(26) end

Given four tasks \(\tau_{i}\) that share three mutexes \(M_{k}\) with durations \(\delta_{i,k}\),

Task	\(\delta_{i,1}\)	\(\delta_{i,2}\)	\(\delta_{i,3}\)
\(\tau_{1}\)	1	2	0
\(\tau_{2}\)	0	9	3
\(\tau_{3}\)	8	7	0
\(\tau_{4}\)	6	5	4

and the corresponding priority ceiling for each mutex,

Semaphore	Priority ceiling
\(M_{1}\)	\(p_{1}\)
\(M_{2}\)	\(p_{1}\)
\(M_{3}\)	\(p_{2}\)

compute the upper bound of the blocking time \(B_{i}\) for each task \(\tau_{i}\).
Note that a value of \(0\) in the table above means that the corresponding task is not using the mutex.

Schedulability Analysis for dependent tasks

Exercice 4

Consider the following task set with their computing time, period and blocking time:

Task	\(C_{i}\)	\(T_{i}\)	\(B_{i}\)
\(\tau_{1}\)	4	10	5
\(\tau_{2}\)	3	15	3
\(\tau_{3}\)	3	20	0

Note that the blocking time of the task with the lowest priority is 0 in all cases. Using the generalized schedulability test, validate the schedulability of this task set.

PIP Implementation in Zephyr RTOS: data structures

Exercice 5

To implement the Priority Inheritance Protocol, the following changes are required in the kernel:

The nominal/original and active priority of each thread must be stored.
Inheritance: Each mutex keeps track of the thread holding the mutex.
Transitivity: Each thread keeps track of the mutex in which it is blocked.

The k_thread and k_mutex data structures are defined in the zephyr/include/zephyr/kernel.h file. Examine the data structures and document how the support for PIP is implemented.

PIP Implementation in Zephyr RTOS: Mutex lock and unlock

Exercice 6

Implementation of z_impl_k_mutex_lock() to support PIP:

If the mutex is free upon lock, it becomes locked and the mutex keeps track of the thread locking the mutex.
If the mutex is locked upon lock, the priority of the thread locking it is changed to the priority of the task calling lock.
PIP can be disabled by setting CONFIG_PRIORITY_CEILING to the lowest possible priority.

The z_impl_k_mutex_lock() function is defined in the zephyr/kernel/mutex.c file. Examine the code and document how the support for PIP is implemented.

Exercice 7

Implementation of z_impl_k_mutex_unlock() to support PIP:

If no thread is blocked on the mutex, then simply unlock the Mutex.
If one or more threads are blocked on the mutex, then the highest-priority thread is awakened and is stored as owner of the mutex. The priority of the thread unlocking the mutex is updated.

The z_impl_k_mutex_unlock() function is defined in the zephyr/kernel/mutex.c file. Examine the code and document how the support for PIP is implemented.