RTOS 优先级倒置

问题背景

在多任务实时操作系统（Real Time Multitask Operating System，简称multi-task RTOS）中，为实现多线程同时运行，OS需要实现一种多个任务之间的切换，即任务调度算法（或策略）。RTOS中，常见调度算法是优先级调度：每个任务（线程）分配一个优先级，按任务紧急状况来划分，一般优先级数值越小，优先级越高，先被OS调度执行。

而多任务ROTS中，经常出现多个任务同时访问同一资源的情况。为避免多个任务同时访问同一资源（如串口、网络等），引入同步原语中等互斥体（mutex，也可翻译成互斥量）。被互斥体保护的代码段，称为“临界区”（critical section）。当一个任务进入临界区前，必须获取（acquire）与此区域相关联的互斥体所有权。如果已经有一个任务获取进入临界区的互斥体，其他任务就不能再进入该临界区，而必须等待持有互斥体的任务释放（release）互斥体的所有权。

关于互斥体概念和用法，详见Linux 自旋锁，互斥量（互斥锁），读写锁

优先级倒置概念

引入互斥体后，也带来了其他问题，即优先级倒置（Priority Inversion），也称优先级反转。

为方便解释，现假设有3个任务：A，B，C（优先级数值3，2，1,），优先级顺序：A < B < C，其中A和C需要访问共享资源。

如果低优先级任务A已占用mutex，且正访问共享资源时，被中等优先级任务B抢占，此时B运行，A就绪；如果高优先级任务C除了需要共享资源外、其他条件都满足，但依然无法运行。看起来任务C被更低优先级的任务B阻塞了。这样，系统的实时性无法得到保证。
—— 这就是优先级倒置问题。

产生原因

为什么会产生优先级倒置问题？
可抢占式的优先级调度策略 + 不同优先级线程对共享资源访问的同步机制。高优先级线程C和低优先级A要访问共享资源，中等优先级B不访问共享资源。当A访问共享资源时（已经获得mutex），C等到（A释放mutex），但A被B抢占了，导致B运行。最终结果是，B运行，A、C等待。也就是说，高优先级C被阻塞，中等优先级B运行。

解决办法

有3种：
1）将代码进行适当组织安排，如确保mutex不被处于不同优先级线程共享，避免优先级倒置发生；
2）优先级置顶协议（Priority Ceiling Protocol）：获得mutex的线程运行时的优先级，比其他获取该mutex的线程的优先级都要高。即每个mutex都被分配一个优先级，该优先级通常与所有可以拥有该互斥体的线程中等最高优先级相对应。当优先级较低的线程占用mutex后，就被提升到mutex的优先级。相当于临时提升线程优先级到最高的mutex优先级。
3）优先级继承协议（Priority Inheritance Protocol）：将占有mutex的线程优先级提升到所有正在等待该mutex的线程优先级的最高值。

参考

优先级倒置（Priority inversion） | CSDN