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.

Solution

In this example, task 2 is unnecessarly blocked by task 3 (because task 3 is set to the highest priority). Task 1 is also blocked at arrival and not at the time that it tries to acquire the critical section, which can also create 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.

Solution

• In the notation below, \(Z_{j,k}\) denotes the longest critical section of task \(\tau_j\) to access resource \(k\) and \(\delta_{j,k}\) denotes its duration.
• Task \(\tau_1\) can only experience direct blocking since it is the task with the highest priority. The critical sections that can block \(\tau_1\) are \({Z_{2,A}, Z_{3,A}, Z_{3,C}}\). Task \(\tau_1\) can only be blocked once by each lower priority task. The maximum blocking time \(B_1\) is thus \(B_1 = (\delta_{2,A} - 1) + (\delta_{3,C} - 1) = 2 + 5 = 7\).
• Task \(\tau_2\) can be blocked through direct blocking on \({Z_{3,A}, Z_{3,B}}\) and through push-through blocking on \({Z_{3,A}, Z_{3,C}}\). The set of critical sections is thus \({Z_{3,A}, Z_{3,B}, Z_{3,C}}\). Since \(\tau_2\) can only be blocked once by \(\tau_3\), \(B_2 = (\delta_{3,C} - 1) = 5\).
• Task \(\tau_3\) cannot be blocked since it is the task with the lowest priority, hence we have \(B_3 = 0\).

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

Solution

The maximum blocking time for \(\tau_2\) corresponds to a push-through blocking on \(Z_{3,C}\).
Push-through blocking means that task \(\tau_2\) is blocked by task \(\tau_3\), that has inherited priority of \(\tau_1\) (when \(\tau_1\) accesses resource \(C\)). This situation is illustrated below:

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.

Solution

(2) i := 1
(3) \(B^{l}_{1}\) := 0
(4) j := 2
(5) \(D_{max}\) := 0
(6) k := 1
(7) Ceiling(\(M_{1}\)) == \(p_{1}\), \(\delta_{2,1}\) == 0
(6) k := 2
(7) Ceiling(\(M_{2}\)) == \(p_{1}\), \(\delta_{2,2}\) == 9
(8) \(D_{max}\) := 9
(6) k := 3
(7) Ceiling(\(M_{3}\)) == \(p_{2}\), \(\delta_{2,3}\) == 3
(11) \(B^{l}_{1}\) := 0 + 9 - 1 := 8
(4) j := 3
(5) \(D_{max}\) := 0
(6) k := 1
(7) Ceiling(\(M_{1}\)) == \(p_{1}\), \(\delta_{3,1}\) == 8
(8) \(D_{max}\) := 8
(6) k := 2
(7) Ceiling(\(M_{2}\)) == \(p_{1}\), \(\delta_{3,2}\) == 7
(6) k := 3
(7) Ceiling(\(M_{3}\)) == \(p_{2}\), \(\delta_{3,3}\) == 3
(11) \(B^{l}_{1}\) := 8 + 8 - 1 := 15
(4) j := 4
(5) \(D_{max}\) := 0
(6) k := 1
(7) Ceiling(\(M_{1}\)) == \(p_{1}\), \(\delta_{4,1}\) == 6
(8) \(D_{max}\) := 6
(6) k := 2
(7) Ceiling(\(M_{2}\)) == \(p_{1}\), \(\delta_{4,2}\) == 5
(6) k := 3
(7) Ceiling(\(M_{3}\)) == \(p_{2}\), \(\delta_{4,3}\) == 4
(11) \(B^{l}_{1}\) := 15 + 6 - 1 := 20
(13) \(B^{s}_{i}\) := 0
(14) k := 1
(15) \(D_{max}\) := 0
(16) j := 2
(17) Ceiling(\(M_{1}\)) == \(p_{1}\), \(\delta_{2,1}\) == 0
(16) j := 3
(17) Ceiling(\(M_{1}\)) == \(p_{1}\), \(\delta_{3,1}\) == 8
(18) \(D_{max}\) := 8
(16) j := 4
(17) Ceiling(\(M_{1}\)) == \(p_{1}\), \(\delta_{4,1}\) == 6
(21) \(B^{s}_{1}\) := 0 + 8 - 1 := 7
(14) k := 2
(15) \(D_{max}\) := 0
(16) j := 2
(17) Ceiling(\(M_{2}\)) == \(p_{1}\), \(\delta_{2,2}\) == 9
(18) \(D_{max}\) := 9
(16) j := 3
(17) Ceiling(\(M_{2}\)) == \(p_{1}\), \(\delta_{3,2}\) == 7
(16) j := 4
(17) Ceiling(\(M_{2}\)) == \(p_{1}\), \(\delta_{4,2}\) == 5
(21) \(B^{s}_{1}\) := 7 + 9 - 1 := 15
(14) k := 3
(15) \(D_{max}\) := 0
(17) Ceiling(\(M_{3}\)) == \(p_{2}\) so \(D_{max}\) := 0
(23) \(B_{1}\) := min(\(B^{l}_{1}\), \(B^{s}_{1}\)) := 15

Run the same for \(B_{2}\)
(2) i := 2
(11) \(B^{l}_{2}\) := 7 + 5 := 12
(21) \(B^{s}_{2}\) := 7 + 6 + 3 := 16
(23) \(B_{2}\) := min(\(B^{l}_{2}\), \(B^{s}_{2}\)) := 12

Run the same for \(B_{3}\)
(2) i := 3
(11) \(B^{l}_{3}\) := 5 := 5
(21) \(B^{s}_{3}\) := 5 + 4 + 3 := 12
(23) \(B_{3}\) := min(\(B^{l}_{3}\), \(B^{s}_{3}\)) := 5

And we have \(B_{4}\) := 0 // the task with the lowest priority cannot be blocked

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.

Solution

The generalized schedulability test is \(\forall i\), \(1 <= i <= n\), \(\sum_{k=1}^{i-1}\frac{C_{k}}{T_{k}} + \frac{C_{i} + B_{i}}{T_{i}} <= i(2^{\frac{1}{i}} - 1)\)
\(i=1\), \(\frac{C_{1} + B_{1}}{T_{1}} = \frac{9}{10} < 1\)
\(i=2\), \(\frac{C_{1}}{T_{1}} + \frac{C_{2} + B_{2}}{T_{2}} = \frac{4}{10} + \frac{6}{15} = \frac{4}{5} < 0.83\)
\(i=3\), \(\frac{C_{1}}{T_{1}} + \frac{C_{2}}{T_{2}} + \frac{C_{3} + B_{3}}{T_{3}} = \frac{4}{10} + \frac{3}{15} + \frac{3}{20} = \frac{3}{4} < 0.77\)
Since this condition is sufficient, we can conclude that the set of tasks is schedulable.
For the sake of demonstration, we can also apply the generalized hyperbolic test.
The generalized hyperbolic test is \(\forall i\), \(1 <= i <= n\), \(\prod_{k=1}^{i-1}(\frac{C_{k}}{T_{k}} + 1)(\frac{C_{i} + B_{i}}{T_{i}} + 1) <= 2\)
\(i=1\), \((\frac{C_{1} + B_{1}}{T_{1}} + 1) = \frac{9}{10} + 1 < 2\)
\(i=2\), \((\frac{C_{1}}{T_{1}} + 1)(\frac{C_{2} + B_{2}}{T_{2}} + 1) = (\frac{14}{10})(\frac{21}{15}) = \frac{294}{150} < 2\)
\(i=3\), \((\frac{C_{1}}{T_{1}} + 1)(\frac{C_{2}}{T_{2}} + 1)(\frac{C_{3} + B_{3}}{T_{3}} + 1) = (\frac{14}{10})(\frac{18}{15})(\frac{23}{20}) = \frac{5796}{3000} < 2\)
Since this condition is sufficient, we can conclude as expected that the set of tasks is schedulable.

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.

Solution

• Each thread must store its nominal and active priority
  The osRtxThread_t data structure contains two fields:

  int8_t priority;  ///< Thread Priority
  int8_t priority_base;  ///< Base Priority
  

• Inheritance: Each mutex keeps track of the thread holding the mutex The osRtxMutex_t data structure contains one field for storing the owner field:

  osRtxThread_t         *owner_thread;  ///< Owner Thread
  

• Transitivity: Each thread keeps track of the mutex in which it is blocked The osRtxThread_t data structure contains a list of owned Mutexes:

  struct osRtxMutex_s     *mutex_list;  ///< Link pointer to list of owned Mutexes
  

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.

Solution

• When the mutex is free, it becomes locked and the mutex keeps track of the thread locking the mutex.

  // Check if Mutex is not locked
  if (mutex->lock == 0U) {
    // Acquire Mutex
    mutex->owner_thread = thread;
    mutex->owner_prev   = NULL;
    mutex->owner_next   = thread->mutex_list;
    if (thread->mutex_list != NULL) {
      thread->mutex_list->owner_prev = mutex;
    }
    thread->mutex_list = mutex;
    mutex->lock = 1U;
    ...
  }
  

• When the mutex is locked, the priority of the owner thread is changed to the one of the calling thread

  // Check if Priority inheritance protocol is enabled
  if ((mutex->attr & osMutexPrioInherit) != 0U) {
    // Raise priority of owner Thread if lower than priority of running Thread
    if (mutex->owner_thread->priority < thread->priority) {
      mutex->owner_thread->priority = thread->priority;
      osRtxThreadListSort(mutex->owner_thread);
    }
  }
  

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.

Solution

• Since the Mutex implementation may be reentrant/recursive, the lock count is first decremented

  mutex->lock--;
  

• If the lock count is 0, it means that this thread releases the Mutex. The thread must be removed from the Mutex owner list:

  if (mutex->lock == 0U) {
    // Remove Mutex from Thread owner list
    if (mutex->owner_next != NULL) {
      mutex->owner_next->owner_prev = mutex->owner_prev;
    }
    if (mutex->owner_prev != NULL) {
      mutex->owner_prev->owner_next = mutex->owner_next;
    } else {
      thread->mutex_list = mutex->owner_next;
    }
    ...
  }
  

• Upon releasing the Mutex, the priority of the thread unlocking the Mutex is updated. The new priority is either the nominal priority or - in the case that this thread still owns other mutexes - the highest priority among owned mutexes

  // Restore running Thread priority
  priority = thread->priority_base;
  mutex0   = thread->mutex_list;
  // Check mutexes owned by running Thread
  while (mutex0 != NULL) {
    if ((mutex0->attr & osMutexPrioInherit) != 0U) {
      if ((mutex0->thread_list != NULL) && (mutex0->thread_list->priority > priority)) {
        // Higher priority Thread is waiting for Mutex
        priority = mutex0->thread_list->priority;
      }
    }
    mutex0 = mutex0->owner_next;
  }
  thread->priority = priority;
  

• Upon releasing the Mutex, when other threads are blocked on this Mutex, then the highest-priority thread is awakened and is stored as owner of the Mutex

  // Check if Thread is waiting for a Mutex
  if (mutex->thread_list != NULL) {
    // Wakeup waiting Thread with highest Priority
    thread = osRtxThreadListGet(osRtxObject(mutex));
    osRtxThreadWaitExit(thread, (uint32_t)osOK, FALSE);
    // Thread is the new Mutex owner
    mutex->owner_thread = thread;
    mutex->owner_prev   = NULL;
    mutex->owner_next   = thread->mutex_list;
    if (thread->mutex_list != NULL) {
      thread->mutex_list->owner_prev = mutex;
    }
    thread->mutex_list = mutex;
    mutex->lock = 1U;
    ...
  }