linux RT-Preempt -- 优先级继承实现

一、什么是优先级继承

优先级继承是解决优先级反转的一种手段。了解优先级继承需要先明白优先级反转。

1、优先级反转

如下图所示：3个进程的优先级H>M>L。假设低优先级的进程L和高优先级进程H竞争共享资源 

1. 低优先级的进程开始运行
2. 进程L获得共享资源
3. 高优先级的进程H抢占了进程L
4. 中等优先级的进程M运行，但由于H进程还在运行，所以M进程进入等待
5. H进程开始尝试获得共享资源，但是此时被L持有，所以进度阻塞
6. M进程执行完成，H进程由于等资源，L进程开始执行
7. L进程释放资源，H进程开始执行，并获得资源
8. L进程执行结束

在时刻5到时刻6之间，M优先级<H，但是由于H在等资源，所以反而M先执行。这就导致了优先级反转。

为了解决优先级反转，有两种方法：优先级天花板（priority ceiling，PC）和优先级继承（priority inheritance，PI）。

优先级天花板（priority ceiling）：将申请某资源的任务的优先级提升到可能访问该资源的所有任务中最高优先级任务的优先级。

优先级继承（priority inheritance）：将低优先级进程L的优先级临时提升到与高优先级进程一样的级别，使得低优先级进程能更快地运行，从而更快地释放临界资源。低优先级进程离开临界区后，其优先级恢复至原本的值。

2、优先级继承

时刻5，进程H需要获取共享资源时，L会继承H的优先级。这样M就无法抢占L。从而L可以尽快执行完成，以释放资源。

时刻6进程L释放资源后，L的优先级恢复到之前。进程H获得资源开始执行。

时刻7，H执行完成。M开始执行

时刻8，M执行完成后，L开始执行

一点思考：如果有一个比H进程更高优先级的进程H2，在时刻5-时刻6优先级继承期间请求调度，会怎样？

当优先级继承机制生效时，低优先级的任务会暂时继承高优先级任务的优先级，以确保高优先级任务能够尽快完成其工作并释放资源。如果在优先级继承期间，有一个更高优先级的进程试图打断当前的执行，系统会根据以下规则进行处理：

1. 优先级调度：Linux内核会根据进程的优先级进行调度。更高优先级的进程会优先获得CPU时间片。因此，如果有一个更高优先级的进程出现，它将会打断当前的执行，获得CPU的控制权。

2. 优先级继承的影响：在优先级继承期间，低优先级的任务已经继承了高优先级任务的优先级。如果有一个更高优先级的进程出现，它将会打断当前的执行，但这不会影响优先级继承机制本身。低优先级任务仍然会保持继承的高优先级，直到它完成了关键的工作并释放了资源。

3. 调度策略：Linux内核使用不同的调度策略（如CFS、实时调度等）来管理进程的优先级和调度。如果更高优先级的进程属于实时调度类（如SCHED_FIFO或SCHED_RR），它将会立即获得CPU的控制权。如果是普通的CFS调度类进程，调度器会根据公平性原则进行调度。

总结来说，当有更高优先级的进程出现时，它会打断当前的执行并获得CPU的控制权，但这不会影响优先级继承机制的正常运行。优先级继承机制会继续确保高优先级任务能够尽快完成其工作。

一个更加复杂的例子：

在真实环境中，往往是多个信号量、多个任务，下图为多个任务与多个互斥信号量交互的示例：

① 低优先级为10的任务t3获取信号量s1;

② 任务t3获取信号量s2;

③ 任务t2（优先级为30）抢占运行后尝试获取信号量s1时阻塞；

④ 任务t3继承t2的优先级30继续执行；

⑤ 优先级为90的t1抢占t3;

⑥ 任务t1尝试获取信号量s2阻塞；

⑦ 任务t3继承t1的优先级90继续执行；

⑧ 任务t3释放信号量s1，优先级继续保持为90；

⑨ 任务t3释放信号量s2，并恢复优先级10；

⑩ 任务t1获取信号量s2抢占运行。

上述实例中，进程t3的优先级进行了多次提升。

二、优先级继承原理

为了实现优先级继承，内核引入了新的一些结构体成员。

1. 关键数据结构

struct rt_mutex：在struct rt_mutex中，owner记录了当前被哪个进程持有，waiters使用红黑树实现，按优先级记录了所有被该锁阻塞的进程，优先级最高的那一个叫top waiter。

rtmutex.h - include/linux/rtmutex.h - Linux source code v5.4.90 - Bootlin Elixir Cross Referencer

/**
 * The rt_mutex structure
 *
 * @wait_lock:	spinlock to protect the structure
 * @waiters:	rbtree root to enqueue waiters in priority order;
 *              caches top-waiter (leftmost node).
 * @owner:	the mutex owner
 */
struct rt_mutex {
	raw_spinlock_t		wait_lock;
	struct rb_root_cached   waiters;
	struct task_struct	*owner;
};

struct rt_mutex_waiter：用来链接rt_mutex和task_struct的数据结构，保存了waiter是哪个进程（task_struct）在等待哪个lock（rt_mutex）

rtmutex_common.h - kernel/locking/rtmutex_common.h - Linux source code v5.4.90 - Bootlin Elixir Cross Referencer

/*
 * This is the control structure for tasks blocked on a rt_mutex,
 * which is allocated on the kernel stack on of the blocked task.
 *
 * @tree_entry:		pi node to enqueue into the mutex waiters tree
 * @pi_tree_entry:	pi node to enqueue into the mutex owner waiters tree
 * @task:		task reference to the blocked task
 */
struct rt_mutex_waiter {
	struct rb_node          tree_entry;
	struct rb_node          pi_tree_entry;
	struct task_struct	*task;
	struct rt_mutex		*lock;
	int prio;
	u64 deadline;
};

• Tree Entry (struct rb_node tree_entry):这个字段用于将等待者插入到rt_mutex的主等待队列中。红黑树根据任务的优先级对这些等待者进行排序，以确保高优先级任务能够优先获取锁。
• PI Tree Entry (struct rb_node pi_tree_entry):这个字段用于优先级继承（Priority Inheritance）机制。pi_tree_entry用于管理这种优先级继承关系。
• Task (struct task_struct *task):指向正在等待锁的任务的指针。这个字段使得内核能够在锁可用时唤醒正确的任务。
• Priority (int prio):记录任务的优先级。红黑树会根据这个优先级字段对等待者进行排序。
• Lock Pointer (struct rt_mutex *lock):指向该等待者正在等待的互斥锁。

 struct task_struct：有一个pi_waiters列表，使用红黑树实现，pi_waiters中包含此进程持有所有rt_mutex的top waiter，称作top pi waiter。

struct task_struct {
.....
#ifdef CONFIG_RT_MUTEXES
	/* PI waiters blocked on a rt_mutex held by this task: */
	struct rb_root_cached		pi_waiters;
	/* Updated under owner's pi_lock and rq lock */
	struct task_struct		*pi_top_task;
	/* Deadlock detection and priority inheritance handling: */
	struct rt_mutex_waiter		*pi_blocked_on;
#endif
.....
	/* Protection of the PI data structures: */
	raw_spinlock_t			pi_lock;
}

/*
 * Leftmost-cached rbtrees.
 *
 * We do not cache the rightmost node based on footprint
 * size vs number of potential users that could benefit
 * from O(1) rb_last(). Just not worth it, users that want
 * this feature can always implement the logic explicitly.
 * Furthermore, users that want to cache both pointers may
 * find it a bit asymmetric, but that's ok.
 */
struct rb_root_cached {
	struct rb_root rb_root;
	struct rb_node *rb_leftmost;
};

2. 内核实现关键原理

从rt mutex的视角看任务：

rt_mutex_waiter用来抽象一个阻塞在rt mutex的任务：task成员指向这个任务，lock成员指向对应的rt mutex对象，tree_entry是挂入blocker红黑树的节点。

rt mutex对象的waiters成员就是这颗红黑树的根节点（wait_lock成员用来保护红黑树的操作）。而owner则指向持锁的任务。需要特别说明的是waiters这个红黑树是按照任务优先级排序的，left most节点就是对应该锁的top waiter。

从任务的视角来看rt mutex：

为了支持rt mutex，task struct也增加了若干的成员，最重要的就是pi_waiters。

pi_waiters:由于一个任务可以持有多把锁，每把锁都有top waiter，因此和一个任务关联的top waiter也有非常多，这些top waiter形成了一个红黑树（同样也是按照优先级排序），pi_waiters成员就是这颗红黑树的根节点。这颗红黑树的left most的任务优先级就是实现优先级继承协议中规定要临时提升的优先级。

pi_top_task成员指向了left most节点对应的任务对象，我们称之top pi waiter。

Task struct的pi_blocked_on成员则指向其阻塞的rt_mutex_waiter对象。

有了上面的基本概念之后，我们讲一下PI chain的概念。首先看看任务和锁的基本关系，如下图所示：

在上面的图片中，task 1持有了Lock A和Lock B，阻塞在Lock C上。一个任务只能阻塞在一个锁上，所以红色箭头只能是从任务到锁，不能分叉。由于一个任务可以持有多把锁，所以黑色箭头会有多个锁指向一个任务，即多把锁汇聚于任务。有了这个基本的关系图之后，我们可以形成更加复杂的任务和锁的逻辑图，如下：

根据上述场景，则 PI Chain 如下：

Task D->Lock 2->Task B->Lock 1->Task A;

Task E->Lock 2->Task B->Lock 1->Task A;

Task F->Lock 3->Task B->Lock 1->Task A;

Task G->Lock 3->Task B->Lock 1->Task A;

Task C->Lock 1->Task A;

为了维护优先级关系，处于 PI Chain 中右端任务的优先级必须大于等于 PI Chain 中左端的任务们；比如上述例子中：Task A 的优先级必须大于 Task B/C/D/E/F/G，Task B 的任务优先级必须大于 Task D/E/F/G；

三、优先级源码分析

优先级继承机制的实现主要在以下文件中：

• kernel/sched/core.c
• kernel/sched/rt.c

rt_mutex_slowlock() ----> __rt_mutex_slowlock() ---->

                 task_blocks_on_rt_mutex() ---->  __rt_mutex_adjust_prio()

                                                                   |--> rt_mutex_adjust_prio_chain()

          __rt_mutex_adjust_prio调整了当前持有锁的进程的动态优先级（继承自等待队列中所有进程的最高优先级），rt_mutex_adjust_prio_chain()如果被调整的动态优先级的进程也在等待某个资源，那么也要链式地调整相应进程的动态优先级。

rtmutex.c - kernel/locking/rtmutex.c - Linux source code v5.4.90 - Bootlin Elixir Cross Referencer

rt_mutex_adjust_prio_chain

这是处理优先级继承的核心函数。当一个高优先级任务被低优先级任务持有的锁阻塞时，低优先级任务的优先级会被提升到高优先级任务的优先级。

static int rt_mutex_adjust_prio_chain(struct task_struct *task, struct task_struct *owner, struct rt_mutex *lock, struct rt_mutex_waiter *waiter, struct rt_mutex_waiter *top_waiter, int *chainwalk)
{
    // 省略部分代码
    while (owner) {
        // 省略部分代码
        if (task->prio < owner->prio) {
            // 提升owner的优先级
            rt_mutex_setprio(owner, task->prio);
        }
        // 省略部分代码
    }
    // 省略部分代码
}

rt_mutex_setprio

这个函数用于设置任务的优先级，并处理优先级继承的逻辑。

static void rt_mutex_setprio(struct task_struct *p, int prio)
{
    // 省略部分代码
    if (p->prio != prio) {
        p->prio = prio;
        // 重新插入到调度队列中
        enqueue_task(p, rq, flags);
    }
    // 省略部分代码
}

3. 调度器中的优先级继承

在调度器中，当一个任务尝试获取一个被低优先级任务持有的锁时，会调用rt_mutex_adjust_prio_chain函数来调整持有锁的任务的优先级。

void rt_mutex_lock(struct rt_mutex *lock)
{
    struct task_struct *task = current;
    struct rt_mutex_waiter waiter;

    // 省略部分代码
    if (rt_mutex_adjust_prio_chain(task, owner, lock, &waiter, NULL, NULL)) {
        // 省略部分代码
    }
    // 省略部分代码
}

Linux内核同步机制RT-mutex_struct mutex中的rtmutex与mutex的区别-CSDN博客

rt-mutex/code_draft.md at master · apollo434/rt-mutex · GitHub

https://elixir.bootlin.com/linux/v5.4.90/source/Documentation/locking/rt-mutex-design.rst

ref：

我爱说实话 / proj62-Linux锁优先级传递 · GitLab

https://github.com/freelancer-leon/notes/blob/master/kernel/sched/sched_rt.md

RT-Patch 学习 - plus studio - StudyingLover

linux 之 mutex、rt_mutex、spinlock_t 的实时性补丁分析_linux rt补丁中断能达到多少-CSDN博客

Linux内核深度解析之内核互斥技术——实时互斥锁-CSDN博客

 Linux RT_MUTEX 图文详解释_linux rtmutex-CSDN博客

https://docs.kernel.org/locking/rt-mutex-design.html

Linux内核同步机制RT-mutex_struct mutex中的rtmutex与mutex的区别-CSDN博客

https://www.youtube.com/watch?v=NrjXEaTSyrw

https://www.youtube.com/watch?v=15-ZVimSHTshttps://www.youtube.com/watch?v=KWYzrvv-V2k&t=616s

https://www.youtube.com/watch?v=-J0y_usjYxo&t=666s

https://www.youtube.com/watch?v=aYdQ4AtNVro