What is Priority Inversion in RTOS?

Abstract: In the development of real-time operating systems, Priority Inversion is a classic problem that cannot be ignored. This article uses the lightweight kernel dumyOS to illustrate the causes of priority inversion through examples, introduces commonly used solutions in the industry (such as priority inheritance and priority ceiling protocols), and finally provides implementation points based on engineering practices.

What is Priority Inversion?

A typical scenario of priority inversion:

A high-priority task H needs to access a mutex.
The lock is currently held by a low-priority task L.
At this moment, a medium-priority task M appears, which does not depend on the lock but has a higher priority than L, thus preempting the CPU.
The result is: The originally most urgent H is blocked by an unrelated M. In other words:

The waiting time of the high-priority task is instead “extended” by the low and medium-priority tasks.

If not addressed, this phenomenon can severely disrupt the determinism of real-time systems and even lead to task timeout failures.

Reproduction Case in dumyOS

In dumyOS (a preemptive, priority-based micro RTOS), only three tasks are needed to reproduce the scenario:

Task L (low priority): Holds the mutex and executes a critical section for 5ms.
Task H (high priority): Periodically accesses this lock.
Task M (medium priority): Compute-intensive, does not use the lock, but has a long runtime.

Timeline:

L acquires the lock first.
H arrives, requests the lock → blocked.
M arrives, has a higher priority than L → preempts execution.
L has no chance to release the lock, and H is stuck in the waiting queue.

This is classic priority inversion. In the scheduling log of dumyOS, it can be intuitively seen that H’s response time is much greater than the critical section itself.

Three Common Solutions in Engineering

1. Priority Inheritance (PI)

Idea: When a low-priority task L holds the lock and a high-priority task H is waiting, temporarily raise L’s priority to H’s level to allow L to finish executing and release the lock as soon as possible.

Characteristics:

Simple and practical, suitable for most embedded systems.
The downside is the need to maintain a “chain inheritance,” which adds some complexity to the implementation. In dumyOS, the logic for raising the priority of the “current owner” can be added to the mutex control block, triggering a switch each time a high-priority task enters the waiting queue.

2. Priority Ceiling Protocol (PCP)

Idea: Assign a ceiling priority to each lock (the highest priority among all tasks that will access that resource). When a task acquires the lock, its priority is immediately raised to the ceiling, thus avoiding being preempted by medium-priority tasks.

Characteristics:

Can fundamentally avoid inversion.
Requires prior analysis of the relationship between tasks and resources, which has a higher configuration cost.
Commonly used in strong real-time scenarios such as aviation and industrial control.

3. Non-preemptive Critical Sections

In certain very short critical sections, directly prohibit scheduling or disable interrupts.

Advantages: Simple and thorough.
Disadvantages: Only suitable for code segments of a few microseconds; otherwise, it will sacrifice system responsiveness.

Implementation in dumyOS

dumyOS implements priority inheritance to solve the priority inversion problem

Core code

// Priority inheritance helper functions
static void raise_task_priority(int32_t task_id, uint8_t new_priority) {
  if (task_id < 0 || task_id >= OS_MAX_TASKS)
    return;
  if (tasks[task_id].priority <= new_priority)
    return; // Already higher or equal priority

  tasks[task_id].priority = new_priority;

  // If task is ready, move it to new priority queue
  if (tasks[task_id].state == TASK_STATE_READY) {
    set_ready(new_priority, task_id);
  }
}

static void restore_task_priority(int32_t task_id) {
  if (task_id < 0 || task_id >= OS_MAX_TASKS)
    return;

  uint8_t highest_needed = tasks[task_id].original_priority;

  // Check if any task is blocked on a mutex owned by this task
  for (int i = 1; i < task_count; i++) {
    if (tasks[i].blocked_on_mutex != NULL) {
      os_mutex_t *mutex = (os_mutex_t *)tasks[i].blocked_on_mutex;
      if (mutex->owner == task_id && tasks[i].priority < highest_needed) {
        highest_needed = tasks[i].priority;
      }
    }
  }

  if (tasks[task_id].priority != highest_needed) {
    tasks[task_id].priority = highest_needed;
    if (tasks[task_id].state == TASK_STATE_READY) {
      set_ready(highest_needed, task_id);
    }
  }
}

Conclusion

Priority inversion is an unavoidable issue in real-time systems.
Priority inheritance is the most cost-effective solution, while the priority ceiling protocol is suitable for high-safety scenarios.
When implementing in engineering, it is essential to combine kernel mechanisms with application requirements to choose the appropriate solution.
In addition to the aforementioned system-level solutions, program design also needs to reasonably control resource granularity and lock scope to improve system stability and real-time performance.

In summary:

Real-time kernels are not without bugs; rather, you must actively design mechanisms to ensure control even in the worst-case scenarios.

References

https://www.cnblogs.com/tangliMeiMei/p/13217172.html
https://en.wikipedia.org/wiki/Priority_inversion

Previous contentWriting an RTOS from scratch – Unveiling the full context switch process on Cortex-M3Creating a minimalist Bootloader for STM32