1. Introduction
The core objective of real-time systems is to ensure that tasks are completed at the correct times and within specified time limits.
In the design of real-time systems, not only is functional correctness required, but when to start and when to finish are also important considerations.
To achieve this goal, compared to general computing systems, real-time systems require some special designs, such as task scheduling, resource sharing, and synchronization. “Priority inversion” is one of the most common and critical issues.
Sometimes, a high-priority task can be blocked by a low-priority task. This can lead to delays in executing high-priority tasks and may even cause the entire system to enter an unpredictable state.
To address this issue, programmers in the last century proposed the Priority Inheritance Protocol (PIP). This method allows low-priority tasks that block high-priority tasks to temporarily inherit higher priority to ensure the system operates normally.
This article will analyze the implementation of the priority inversion problem in real-time systems gradually. We will also introduce an interesting case: the Mars Pathfinder, which encountered a system reset issue due to priority inversion after launch. This article will use Zephyr RTOS as an example to illustrate the implementation of the priority inheritance mechanism.
2. Overview of Priority Inversion Problem
Priority inversion is a common problem in the design of complex real-time systems. Suppose a high-priority task is blocked because it is occupied by a low-priority task accessing shared resources (for example, the low-priority task has acquired the mutex first). If this low-priority task is then preempted by a medium-priority task, a priority inversion situation occurs.
For example, suppose there are three tasks: Task A (highest priority), Task C (medium priority), and Task B (lowest priority). Task A needs to access a shared resource but is occupied by Task B. Task B is preempted by Task C, which also needs to access this resource. At this point, Task A will be blocked by Task C, resulting in a priority inversion:
3. Case Study: Mars Pathfinder
Some readers may not have experience in designing complex real-time systems or may not have encountered such problems and might wonder if this situation is merely a figment of the author’s imagination.
This section will use a real case that occurred: the system reboot issue encountered by the Mars Pathfinder after landing to illustrate the problem of Priority Inversion.
[Strange Reboots]
Shortly after landing on Mars, the Mars Pathfinder began encountering a strange problem: every few days, the Pathfinder would suddenly reboot. Each reboot severely affected scientific data collection.
After investigation, NASA engineers discovered that this was due to a priority inversion problem in the VxWorks real-time operating system used by the Pathfinder.
[System Architecture]
Similar to the real-time systems we design today, the software system of the Pathfinder used a preemptive, fixed-priority kernel scheduling strategy to manage the execution of multiple tasks.
The software system of the Pathfinder had the following tasks:
– “bc_sched”: The highest priority task, responsible for scheduling bus communication, triggered by the watchdog timer at a frequency of 8Hz.
– “bc_dist”: The second highest priority task, responsible for distributing bus communication data.
– “communication_task”: A medium-priority task responsible for communication with Earth.
– “ASI/MET_task”: A low-priority task responsible for collecting meteorological data.
Among these, ASI/MET_task and bc_dist share a protected shared resource (Pipe) by a Mutex, similar to Unix’s Pipe, which is also a communication channel between tasks.
[Root Cause]
The sequence of events leading to priority inversion is as follows:
-
The low-priority ASI/MET_task acquires the Mutex and attempts to update shared data.
-
However, before releasing the mutex, this task is preempted by the higher-priority bc_dist task, which also needs to access the mutex.
-
However, since the mutex is still held by ASI/MET_task, bc_dist is blocked.
-
To make matters worse, some medium-priority tasks (such as communication_task) may also preempt ASI/MET_task, delaying the release of the mutex.
-
Until the moment shown in the diagram at time t4, the highest priority bc_sched is awakened by the watchdog and finds that bc_dist has not completed execution, thus performing a reset action, resetting the entire system.
This problem was ultimately resolved by using a Priority Inheritance Mutex. In fact, the VxWorks operating system already provides such a mechanism, but the NASA team chose to disable this feature to enhance performance.
Through this case, we should realize how important it is to understand real-time scheduling and deduce corner cases in the design of real-time systems.
4. PIP Protocol Implementation – Using Zephyr RTOS as an Example
Before introducing the implementation of Zephyr, let’s look at how PIP is implemented:
-
The low-priority task acquires a mutex to access shared resources.
-
The high-priority task requests the same mutex but is blocked because it is held by the low-priority task.
-
The low-priority task inherits the priority of the high-priority task, allowing it to execute with elevated priority.
-
The medium-priority task cannot preempt the low-priority task while it holds the mutex.
-
Once the low-priority task releases the mutex, it will revert to its original priority, and the high-priority task will continue.
Zephyr OS Mutex Implementation – `z_impl_k_mutex_lock` Function
Branch 1 – Successfully Acquire Control
This branch is not the focus of this section. If the mutex can be locked (no other task has locked it), the calling thread (cur_thread) becomes the owner (lock_owner) and continues execution:
Branch 2 – Lock Acquisition Failed
If the lock acquisition fails, the calling thread will be added to the mutex’s waiting queue and trigger the priority inheritance logic (new_prio_for_inheritance) to determine the priority of the currently locked thread:
Let’s analyze line by line:
new_prio = new_prio_for_inheritance(arch_current_thread()->base.prio, mutex->owner->base.prio);Here `new_prio_for_inheritance` compares the priorities of the lock_owner thread and cur_thread, returning the higher priority. It is worth mentioning that Zephyr provides the PRIORITY_CEILING mechanism to limit the “magnitude” of priority elevation by low-priority threads. Pseudocode:
return (LOWER_PRIO(CONFIG_PRIORITY_CEILING, HIGHER_PRIO(lock_owner_prior, cur_thread_prior)))If a priority change is detected, the priority of the lock_owner thread needs to be adjusted:
if (z_is_prio_higher(new_prio, mutex->owner->base.prio)) { resched = adjust_owner_prio(mutex, new_prio); }When the lock_owner thread is in the ready state, the `resched` flag is set to true, which will re-initiate scheduling at the end of the function.
The priority is given to the lock_owner thread, and we need to add cur_thread to the waiting queue:
int got_mutex = z_pend_curr(&lock, key, &mutex->wait_q, timeout);