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 Keil RTX5: data structures

Exercice 5

For implementing the Priority Inheritance Protocol, the following changes are required in the kernel:

Each thread must store its nominal and active priority
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 osRtxThread_t and osRtxMutex_t data structures are defined in the “rtx_os.h” file. Examine the data structures and document how the required changes for PIP are implemented.

PIP Implementation in Keil RTX5: Mutex lock and unlock

Exercice 6

Changes in the Mutex lock for implementing PIP:

If Mutex is free, it becomes locked and the mutex keeps track of the thread locking the mutex.
If Mutex is locked, the priority of the thread locking it is changed to the priority of the task calling lock.

The osMutexAcquire/svcRtxMutexAcquire function is defined in the “rtx_mutex.c” file. Examine the code and document how the required changes for PIP are implemented.

Exercice 7

Changes in the Mutex unlock for implementing 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 osMutexRelease/svcRtxMutexRelease function is defined in the “rtx_mutex.c” file. Examine the code and document how the required changes for PIP are implemented.