Task Dependencies and Priority Inversion

Introduction

In the various codelabs dealing with scheduling, you learned how to schedule a hybrid set of tasks consisting of both periodic and aperiodic tasks. In these codelabs, the tasks were assumed to be independent and no task could block any other task.

In this codelab, we address the problem of dependencies among tasks and of priority inversion. In multitasking programs, tasks often need to share resources, which must be protected against concurrent access. Such protections are usually implemented using mutexes and Zephyr RTOS is no exception.

In this codelab, you will also experience a situation similar to one that occurred on the Mars Rover Pathfinder in 1997 (see image below). Although you will experience it from a much more comfortable seat than the engineers did in 1997, this example illustrates the need to implement resource access protocols, such as PIP in Zephyr RTOS, to mitigate priority inversion problems.

Source: https://upload.wikimedia.org/wikipedia/commons/7/7f/Mars_Pathfinder_Lander_preparations.jpg

What you’ll build

In this codelab, you will add task dependencies to your CarSystem application. You will create critical sections that are accessed concurrently by several tasks and learn how access to these sections impacts the program and can lead to unexpected behaviors.

What you’ll learn

• How to use Zephyr RTOS mutexes.
• How to create protect critical sections with properly configured mutexes.
• How to configure the PIP mechanism in Zephyr RTOS.

What you’ll need

• You need to have finished the Digging into Zephyr RTOS.
• You need to have completed the Scheduling of periodic tasks codelab and Scheduling of a hybrid set of tasks codelabs.
• You need to have completed the Robust Development Methodologies (I) codelab and the Robust Development Methodologies (II) codelab.

Configuration Parameters

As documented in the preceding codelab, to deliver the different phases of the project, you must use configuration parameters that correspond to the features to be implemented in each phase. This codelab relates to the phase C of the project for which the priority inversion phenomenom must be implemented and documented. The CONFIG_PRIORITY_INVERSION=y option must be used to enable this feature.

Configuration Parameters

To facilitate the comprehension of task dependencies, you must compile your application with the configuration parameters CONFIG_PERIODIC_TASKS=y and CONFIG_PRIORITY_INVERSION=y. Ensure the exclusion of aperiodic tasks generation and servers (e.g., without CONFIG_APERIODIC_TASKS=y). Thus, your application must compile and behave correctly with dependent periodic tasks only. The prj.conf file must thus contain the following configuration parameters:

car_system/prj.conf

# disable time slicing (IRQ 37)
CONFIG_TIMESLICING=n
# build system with periodic tasks
CONFIG_PERIODIC_TASKS=y
# do not build system with aperiodic tasks
# CONFIG_APERIODIC_TASKS=y
# build system for priority inversion
CONFIG_PRIORITY_INVERSION=y
# do not use system watchdog
CONFIG_APP_WATCHDOG=n

Periodic Tasks Configuration

In this codelab, we will use the same set of periodic tasks as in the project and in the preceding codelab. As documented below, we will modify some task parameters to demonstrate the priority phenomenom.

Add Tasks Dependencies

In the preceding codelab, dependencies have been introduced between the “Engine” and “Display” tasks that implement a producer-consumer mechanism. For simplicity and reproducibility, this codelab introduces a simpler dependency mechanism based exclusively on a mutex. We establish dependencies among tasks by incorporating critical sections protected by mutexes into subsections of code, as depicted below. This allows us to demonstrate the priority inversion mechanism in a reproducible way.

Figure 1: Shared Resource Scenario

Modify the Existing CarSystem Implementation

To reproduce this pattern programmatically, a simple way is to modify the PeriodicTaskInfo structure used in the preceding codelabs as follows:

src/periodic_task_info.hpp

#if CONFIG_PRIORITY_INVERSION
struct SubtaskComputationInfo {
  std::chrono::milliseconds _computationTime;
  zpp_lib::Mutex* _pMutex;
};
static constexpr uint8_t NbrOfSubTasks = 3;
#endif  // CONFIG_PRIORITY_INVERSION

struct PeriodicTaskInfo {
#if CONFIG_PRIORITY_INVERSION
  SubtaskComputationInfo _subTasks[NbrOfSubTasks];
#else   // CONFIG_PRIORITY_INVERSION
  std::chrono::milliseconds _computationTime;
#endif  // CONFIG_PRIORITY_INVERSION
  std::chrono::milliseconds _period;
  zpp_lib::PreemptableThreadPriority _priority;
  const char* _szTaskName;
};

This modified structure allows you to easily define multiple code sections, some of which can be protected by a mutex:

• First, modify the initialization of the _taskInfos attribute of the CarSystem class.
• Next, modify the implementation of the CarSystem::task_method() so that it executes each code section, with or without a critical section.
• Initially, use the same task parameters as before, with only one subtask and without a critical section to reproduce the same results.

Adapt the Tasks Parameters to Better Visualize Blocking

The project’s periodic task parameters result in relatively low CPU utilization. These parameters were chosen to facilitate the introduction of sporadic tasks, servers, and background scheduling. However, the low utilization factor makes it difficult to visualize task dependencies.

To more easily visualize the blocking and priority inversion phenomenon, modify the task parameters as follows:

Task	Function	WCET [ms]	Period [ms]	\(\Phi\)
Engine	Performs car engine checks periodically	20	50	0
Display	Displays car information	20	125	0
Tire	Performs tire pressure checks	10	200	0
Rain	Performs rain detection	50	250	0

Note that the task periods remain unchanged, but the computation times have increased to bring the utilization factor closer to the upper bound. With the new task parameters, you should observe the following task behaviors:

Figure 2: Time diagram without shared resource

The project task parameters remain unchanged for other configurations

The task parameters must remain unchanged when CONFIG_PRIORITY_INVERSION is disabled. This means that the code delivered for phase C of the project must still execute as expected when the configuration parameters correspond to Phases A and B.

Note that some of the deliverables of Phase C of the project are related to demonstrating the blocking and priority inversion phenomenon. Be sure to read the related deliverables carefully while working on this codelab.

Add Critical Sections with Mutual Exclusion

You can create dependencies among tasks by declaring a mutex and defining subtasks for those that share this mutex. If these tasks share the same critical section, they are dependent on each other and one could block the other. In this codelab, we will create a dependency between the Engine and Rain tasks using the following parameters:

// Engine subtasks
      {._subTasks = { { ._computationTime = 6ms, ._pMutex = nullptr },
                      { ._computationTime = 12ms, ._pMutex = &_mutex_ER },
                      { ._computationTime = 2ms, ._pMutex = nullptr } },
// Rain subtasks
      {._subTasks = { { ._computationTime = 25ms, ._pMutex = nullptr },
                      { ._computationTime = 23ms, ._pMutex = &_mutex_ER },
                      { ._computationTime = 2ms, ._pMutex = nullptr } },

Note that the sum of the subtask computation times correspond to the updated task computation time. The other two tasks remain independent from other tasks.

The _mutex_ER mutex can be created in your CarSystem class using zpp_lib::Mutex. If you prefer to use the Mutex API directly, then you need to adapt the SubtaskComputationInfo structure declaration.

Collect Tasks Statistics with the Modified Parameters

After modifying the CarSystem so that it executes the Engine and Rain subtasks, build your application using -S rtt-tracing and collect task statistics using SEGGER SystemView. You should then observe a similar behavior to that depicted below:

Figure 3: Time diagram with shared resource

As you can see, at the \(100\ ms\) mark, the Engine task preempts the Rain task. At \(106\ ms\), the Engine task attempts to lock the mutex owned by the Rain task, which blocks the Engine task. At this point, the Rain task inherits the priority of the Engine task and runs again. This demonstrates that the Priority Inheritance Protocol is in use.

Figure 4: With PIP, task Rain inherits priority

Later, at the \(125\ ms\) mark, the Rain task unlocks the mutex. Its original priority is restored, allowing the Engine task to preempts the Rain task again.

Figure 5: With PIP Rain task's priority is restored

This demonstrates how a higher-priority task can be blocked by a lower-priority task when they share resources. While the PIP mechanism prevents unbounded blocking, it is important to understand that no protocol can avoid blocking altogether.

Demonstrate Schedulability Under RM and PIP

Once event statistics has been collected, validate that no error is detected by running the Python script using a command similar to

python csv_marker_parser_with_preemption.py phase_c_mutex_pip.csv --marker 0 --task Engine --period-ms 50 --max-exec-ms 20.3 --marker 1 --task Display --period-ms 125 --max-exec-ms 20.3 --marker 2 --task Tire --period-ms 200 --max-exec-ms 10.2 --marker 3 --task Rain --period-ms 250 --max-exec-ms 50.6 --tolerance-period-start-ms 0.2

or a similar command.

You should not detect any error. Even though no error was detected, we still need to demonstrate that the maximum blocking time encountered by the Engine task will not cause it to miss its deadline, as required in the following exercise. Note that the solution of this exercise is part of the deliverables for project Phase C.

Exercise 1 (Deliverable for the Project - Phase C)

• Feasibility

  • Demonstrate that the set of periodic tasks with modified task computation times (but without dependencies) is schedulable under RM. You can demonstrate schedulability RM by applying the Liu-Layland or hyperbolic bounds.
  • Compute the maximum block time for all tasks with task dependencies.
  • Then, apply the generalized schedulability test to demonstrate schedulability under RM and PIP for tasks with dependencies.

• Experiments

  • Run your application and collect event statistics.
  • Take a snapshot of the time diagram like the one in Figure 3. Annotate the diagram to explain the priority inheritance mechanism.
  • Run the Python script to analyze the statistics and show that no violation is detected.
  • Both the annotated snapshot and the statistical analysis results must be added to the README.md file of your project.
  • Document the command used to produce the statistical results.

Demonstrate How a Lower-Priority Task Can Block a Higher-Priority Task without PIP

As demonstrated in the previous section, when a higher-priority task attempts to acquire a mutex owned by a lower-priority task, the lower-priority task inherits the higher-priority task’s priority. This follows the Inheritance Protocol mechanism, which is the default behavior for mutexes in Zephyr RTOS.

This behavior can be modified using the CONFIG_PRIORITY_CEILING configuration parameter. This parameter defines the minimum priority value that a thread will acquire as part of the priority inheritance protocol. Setting this value to a level equal to or lower than the idle thread’s priority level (i.e., the highest possible integer value) will disable the priority inheritance algorithm. By default, the idle thread’s priority is \(15\) and if you add the CONFIG_PRIORITY_CEILING=15 configuration parameter in your prj.conf file, this will disable the PIP mechanism.

After rebuilding and running your application, you should observe similar behavior to that depicted below. This demonstrates that without PIP, some task deadlines may be missed. This must be documented as described in the next exercise. Note that the solution of this exercise is part of the deliverables for project Phase C.

Figure 6: Time diagram with shared resource (without PIP)

Exercise 2 (Deliverable for the Project - Phase C)

• Run your application with PIP deactivated and collect event statistics.
• Take a snapshot of the time diagram like the one in Figure 6. Annotate the diagram to explain what task deadline is missed. Explain why this occurs without PIP.
• Run the Python script to analyze the statistics. Timing violations should be detected. Explain these violations, by comnmenting the statistical results together.
• Both the annotated snapshot and the statistical analysis results must be added to the README.md file of your project.
• Do not forget to document the command used to produce the statistical results.

Wrap-Up

By the end of this codelab, you should have completed the following steps:

• You modified the CarSystem application to handle multiple code sections that may be protected by a mutex.
• You adapted the task parameters for better visualization of the blocking mechanisms.
• You created dependencies between the Engine and Rain tasks.
• You computed the maximum blocking times for each task and validated that the set of tasks is schedulable under RM and PIP.
• You demonstrated how disabling the PIP mechanism can affect schedulability.
• You added the deliverables of your project for phase C, as documented in the codelab and in the project specification.