Priority Inversion in Linux Kernel

Introduction

Priority inversion is a classic scheduling problem in real-time and concurrent systems.

It occurs when a high-priority task is forced to wait for a lower-priority task, while a medium-priority task can continue executing.

The basic model uses three tasks:

Task	Conceptual Priority	Role
HIGH	80	Needs the shared resource
MEDIUM	50	Performs unrelated work
LOW	10	Owns the shared resource

The important distinction is:

Priority inversion is the problem. Priority inheritance is one mechanism used to mitigate it.

This article explores the concept from a Linux kernel perspective using kernel threads and the Linux rt_mutex mechanism.

1. What Is Priority Inversion?

Suppose a low-priority task obtains a mutex.

A high-priority task subsequently needs the same mutex.

The high-priority task cannot continue because the resource is currently owned by LOW.

The situation becomes problematic when MEDIUM gets CPU time while LOW is unable to finish its critical section.

The logical sequence is:

LOW acquires the mutex.
HIGH attempts to acquire the mutex.
HIGH blocks.
MEDIUM performs unrelated work.
LOW is delayed.
HIGH remains blocked.
LOW eventually releases the mutex.
HIGH can finally continue.

The surprising part is that HIGH has a higher priority than MEDIUM and LOW, yet MEDIUM can indirectly contribute to HIGH's delay.

That is the essence of priority inversion.

2. Priority Inversion vs Priority Inheritance

These two terms should not be confused.

Concept	Meaning
Priority inversion	A scheduling problem
Priority inheritance	A technique for mitigating that problem
HIGH	The task waiting for the resource
LOW	The task currently owning the resource
MEDIUM	A competing task that can contribute to the delay
`rt_mutex`	Linux kernel synchronization primitive associated with PI

The important relationship is:

Priority inversion = problem
Priority inheritance = mitigation

3. The Classic Example

Consider:

HIGH    = 80
MEDIUM  = 50
LOW     = 10

LOW acquires a shared resource first.

HIGH later needs the same resource.

HIGH therefore blocks.

If MEDIUM can execute while LOW is waiting for CPU time, HIGH's effective waiting time can increase.

Conceptually:

LOW owns resource
        ↓
HIGH needs resource
        ↓
HIGH blocks
        ↓
MEDIUM executes
        ↓
LOW is delayed
        ↓
HIGH remains blocked

This is why priority inversion matters in systems where predictable response time is important.

4. What Is Priority Inheritance?

Priority inheritance addresses the dependency between the waiting task and the lock owner.

If HIGH is waiting for a mutex owned by LOW, LOW can temporarily inherit HIGH's priority.

Conceptually:

LOW priority: 10
        ↓
HIGH waits
        ↓
LOW temporarily inherits HIGH's priority
        ↓
LOW completes critical section
        ↓
LOW releases mutex
        ↓
HIGH continues
        ↓
LOW returns to its original priority

The goal is straightforward:

Allow the lower-priority lock owner to finish the critical section sooner so that the higher-priority waiter can proceed.

5. Why `rt_mutex` Matters in Linux

The Linux kernel provides rt_mutex as a real-time mutex implementation with priority-inheritance support.

A simplified example is:

static struct rt_mutex lock;

rt_mutex_init(&lock);

rt_mutex_lock(&lock);

/* critical section */

rt_mutex_unlock(&lock);

The important API calls are:

rt_mutex_init()
rt_mutex_lock()
rt_mutex_unlock()

In the demonstration module, the shared lock is declared as:

static struct rt_mutex pi_lock;

and initialized during module loading.

6. Kernel Threads

The demonstration uses Linux kernel threads rather than ordinary user-space processes.

The three conceptual participants are:

LOW
HIGH
MEDIUM

Kernel threads can be created using APIs such as:

kthread_run(low_thread, NULL, "pi_low");

The returned task_struct pointer allows the module to retain a reference to the created kernel thread.

For example:

static struct task_struct *low_task;

The same approach is used for HIGH and MEDIUM.

7. The LOW Thread

LOW is responsible for acquiring the rt_mutex.

The important operation is:

rt_mutex_lock(&pi_lock);

After acquiring the lock, LOW enters its critical section.

The demonstration deliberately keeps LOW holding the mutex for some time so that HIGH can attempt to acquire it.

The important relationship is therefore:

LOW owns the resource while HIGH needs it.

The module also prints scheduling information before and during the interaction.

8. The HIGH Thread

HIGH attempts to acquire the same mutex:

rt_mutex_lock(&pi_lock);

If LOW already owns the mutex, HIGH blocks.

The conceptual state is:

HIGH
  ↓
waiting for mutex
  ↓
LOW owns mutex

This is the critical point at which priority inheritance becomes relevant.

After LOW releases the mutex, HIGH can acquire it and continue.

9. The MEDIUM Thread

MEDIUM represents independent work.

It does not need the shared mutex.

Its purpose is to model the classic third participant in a priority-inversion scenario.

The simplified model is:

Task	Needs mutex?	Role
LOW	Yes	Owns resource
HIGH	Yes	Waits for resource
MEDIUM	No	Performs unrelated work

MEDIUM is therefore important because it illustrates how a task that has no direct relationship with the shared resource can still affect HIGH's waiting time.

10. A Linux 5.15 Constraint

There is an important implementation detail in this particular experiment.

The target environment is Ubuntu Linux 5.15.x.

An earlier version attempted to use:

sched_setscheduler_nocheck()

to assign arbitrary scheduler priorities.

However, that scheduler interface was not exported for use by the external loadable module in the target Ubuntu kernel.

As a result, the module cannot simply depend on that internal scheduler interface.

The implementation therefore uses exported helpers such as:

sched_set_fifo_low(low_task);
sched_set_fifo(high_task);

This is an important Linux kernel development lesson:

An API existing somewhere inside the kernel source does not automatically mean an out-of-tree module can call it.

11. Theoretical Priorities vs Actual Scheduler State

The textbook example commonly uses:

LOW    = 10
MEDIUM = 50
HIGH   = 80

However, those numbers should not be confused with the actual scheduler state of this module.

The current implementation uses the scheduler helpers available to the external module.

Therefore, the project deliberately distinguishes between:

Conceptual model

LOW    = 10
MEDIUM = 50
HIGH   = 80

Actual implementation

LOW    → sched_set_fifo_low()
HIGH   → sched_set_fifo()
MEDIUM  → normal kernel thread

The module prints actual scheduling fields such as:

current->pid
current->policy
current->prio
current->normal_prio

This is preferable to assuming that a theoretical priority value is the actual runtime value.

12. Standard Ubuntu Kernel vs PREEMPT_RT

Another important limitation is kernel configuration.

The target environment is a standard/non-PREEMPT_RT Ubuntu kernel.

That means this project should primarily be viewed as a Linux kernel rt_mutex and priority-inheritance learning experiment, rather than a deterministic real-time benchmark.

The exact timing and scheduling behavior can depend on:

Kernel configuration
Scheduler behavior
CPU topology
System load
Preemption configuration
Timing of msleep()
Scheduling policy

For a strict textbook real-time demonstration with controlled priorities such as 10 / 50 / 80, a PREEMPT_RT kernel or an appropriately designed user-space POSIX experiment can be a better environment.

13. Why `msleep()` Is Used

The demonstration uses delays such as:

msleep(1000);

These delays are not intended to provide precise real-time scheduling.

Their purpose is to create enough temporal separation for the demonstration:

LOW gets time to start.
HIGH gets time to start.
LOW obtains the mutex.
HIGH subsequently attempts the mutex.
MEDIUM begins its work.

Therefore, msleep() should be understood as a demonstration timing mechanism, not a real-time synchronization mechanism.

14. Module Lifecycle

A kernel module has an important lifecycle:

Build
  ↓
Load
  ↓
Initialize
  ↓
Create kernel threads
  ↓
Run demonstration
  ↓
Synchronize completion
  ↓
Stop threads
  ↓
Unload

The module entry point is:

static int __init pi_demo_init(void)

The module exit point is:

static void __exit pi_demo_exit(void)

These are connected using:

module_init(pi_demo_init);
module_exit(pi_demo_exit);

15. Why Module Cleanup Matters

Kernel thread lifecycle management is especially important.

An earlier version of the project experienced a kernel Oops during:

sudo rmmod pi_demo

The reported instruction pointer was associated with:

kthread_stop()

This highlighted an important kernel-programming rule:

Creating a kernel thread is only half of the problem. You must also correctly manage its entire lifecycle.

A module must carefully handle:

Thread creation
Thread execution
Thread blocking
Thread termination
kthread_stop()
Module removal

16. Using Completion for Safe Cleanup

The current design uses a kernel completion object:

static DECLARE_COMPLETION(demo_done);

HIGH signals completion after the actual demonstration:

complete(&demo_done);

The module cleanup path waits for that event:

wait_for_completion(&demo_done);

This gives the module a clear synchronization point before it proceeds with cleanup.

The lifecycle is therefore:

Start demonstration.
HIGH reaches completion.
HIGH signals demo_done.
Module cleanup waits for completion.
Cleanup stops the threads.
Module is unloaded.

This is safer than blindly stopping threads without considering their current state.

17. `task_struct` and Scheduler Information

The module stores thread references using:

struct task_struct *

The current executing task can be accessed through:

current

The demonstration prints scheduler-related information from the current task.

For example:

pr_info("PID=%d policy=%d prio=%d normal_prio=%d\n",
        current->pid,
        current->policy,
        current->prio,
        current->normal_prio);

This is useful because kernel experiments should distinguish between:

what the source code intends,
what the scheduler interface requests,
and what the kernel actually reports.

18. Observing the Experiment with `dmesg`

Kernel modules normally use kernel logging APIs rather than printf().

The demonstration uses messages such as:

pr_info("PI-DEMO: HIGH trying to acquire rt_mutex\n");

You can filter the kernel log with:

sudo dmesg | grep PI-DEMO

For live output:

sudo dmesg -w

This allows the experiment to be observed while the kernel threads execute.

19. Useful Commands

Build

make

Check the module

ls -lh pi_demo.ko

Load

sudo insmod ./pi_demo.ko

Inspect output

sudo dmesg | grep PI-DEMO

Follow output live

sudo dmesg -w

Remove

sudo rmmod pi_demo

Check whether it is loaded

lsmod | grep pi_demo

Inspect recent messages

sudo dmesg | tail -30

Inspect the complete PI demonstration

sudo dmesg | grep -A80 -B20 "PI-DEMO"

Search for kernel problems

sudo dmesg | grep -E "BUG:|Oops:|WARNING:|PI-DEMO|kthread_stop" | tail -100

20. Recommended Laboratory Workflow

A clean experiment can follow this sequence:

Step 1 — Build

make

Step 2 — Verify the module

ls -lh pi_demo.ko

Step 3 — Load it

sudo insmod ./pi_demo.ko

Step 4 — Observe the output

sudo dmesg | grep PI-DEMO

or:

sudo dmesg -w

Step 5 — Remove it after completion

sudo rmmod pi_demo

Step 6 — Verify cleanup

sudo dmesg | tail -30

Step 7 — Verify module state

lsmod | grep pi_demo

21. What This Project Teaches

This relatively small module touches several important Linux kernel concepts.

Kernel modules

module_init()
module_exit()
MODULE_LICENSE()
MODULE_AUTHOR()
MODULE_DESCRIPTION()
MODULE_VERSION()

Kernel threads

kthread_run()
kthread_stop()
kthread_should_stop()
struct task_struct

Synchronization

rt_mutex
rt_mutex_init()
rt_mutex_lock()
rt_mutex_unlock()

Completion

DECLARE_COMPLETION()
complete()
wait_for_completion()

Scheduling

sched_set_fifo()
sched_set_fifo_low()
current->policy
current->prio
current->normal_prio

Debugging

pr_info()
pr_err()
dmesg
Kernel Oops
Kernel warnings
Thread cleanup

22. Common Conceptual Mistakes

Mistake 1: Priority inversion means LOW always runs before HIGH

Not exactly.

The problem is the resource dependency.

HIGH is blocked because LOW owns a resource that HIGH needs.

Mistake 2: Priority inheritance means LOW permanently becomes HIGH priority

No.

The inheritance is temporary and associated with the lock dependency.

After the relevant resource is released, the inherited priority can be removed.

Mistake 3: `rt_mutex` makes the entire system real-time

No.

Using rt_mutex does not automatically transform a standard Ubuntu kernel into a deterministic real-time operating system.

Kernel configuration and scheduling behavior still matter.

Mistake 4: `sched_set_fifo()` lets an external module select any priority number

No.

The exported helper does not provide arbitrary numeric priority assignment such as:

10
50
80

That was one of the important constraints encountered during development.

Mistake 5: If the code compiles, `rmmod` is automatically safe

No.

Module cleanup is part of kernel correctness.

Thread lifecycle bugs can surface only during module removal.

23. Priority Inheritance in One Sentence

Priority inheritance temporarily raises the effective priority of a lower-priority task holding a resource needed by a higher-priority task, helping the lock owner finish and release the resource sooner.

24. Final Takeaway

Priority inversion demonstrates why synchronization and scheduling cannot be studied completely independently.

A mutex determines who can access a resource.

The scheduler determines which runnable task gets CPU time.

Priority inheritance connects these two concerns when a high-priority task is blocked by a lower-priority lock owner.

In Linux, rt_mutex provides the kernel mechanism used for priority inheritance.

This project combines:

Area	Linux concept
Module	`.ko`, `module_init()`, `module_exit()`
Threads	`kthread_run()`, `kthread_stop()`
Synchronization	`rt_mutex`
Priority inheritance	PI behavior associated with `rt_mutex`
Scheduling	FIFO scheduler helpers
Synchronization lifecycle	Completion
Diagnostics	`pr_info()`, `dmesg`
Debugging	Oops, warnings, cleanup analysis

The most important lesson is not simply how to call rt_mutex_lock().

It is understanding the complete relationship between:

task → scheduler → resource → mutex → blocking → priority inheritance → critical section → unlock → task lifecycle → module cleanup.

GitHub Repository

Priority Inheritance Repository: 👉 priority_inheritance

Explore the complete source code, build files, and module implementation.

Command Palette