【连载】嵌入式OS入门笔记-以RTX为案例（九）：关于优先度-翻转，继承和天花板

RaymondKwan

当调度涉及优先度的时候，会出现不少问题，本文关于优先度调度的主要问题和一些应付的策略。主要有以下几个概念：优先度翻转（priority  inversion），优先度继承（priority inheritance）策略和优先度天花板（priority ceiling）策略。

1.优先度翻转（priority inversion）

    大部分的RTOS都支持给不同进程分配优先度，一定程度上能够让调度和时间管理灵活性更大。但是当涉及到一些代码临界区（critical section）的时候，可能就会出现问题。优先度翻转就是这样一个典型的问题。为了解释这个概念，我们先来看一个实际例子：

    首先我们考虑三个进程，T1，T2，T3。T3的优先度大于T2，T2的优先度大于T1，采用的调度算法是优先度高的可以打断优先度低的进程，临界区等待可以阻断高优先度的进程。 考虑在一个时间轴上，以下事件依次发生：

       

• T1被创造       
  
• T1要求进入资源R临界区       
  
• T2被创建       
  
• T3被创建       
  
• T3要求进入资源R临界区
  

    光看文字可能会比较抽象，我们把每个事件都画在下图：  

请先按照时间顺序从左到右看一下所有事件，有没有觉得有什么不妥的？

    如果没有觉得不妥的，我们再按照每个进程来看。进程1首先被创建，然后进入了临界区执行，然后被阻断，然后重新进入临界区执行。中间的阻断时间是三个进程最长的。进程2第二被创建，一创建就打断了进程1，直到被阻断，然后恢复正常执行直到进程消灭。进程3最后被创建，一创建就打断了进程2，直到要求进入临界区被阻断，然后再恢复临界区执行，阻断时间是三个进程中第二长的。

    问题恰恰出现在这里：进程3被什么阻断了？进程3因为要求资源R的临界区，而此时资源R临界区被进程1占用，理想状态我们应该让进程1尽快执行尽早退出临界区，以便进程3（当前最高优先度）能够及早运行。可实际上，因为进程1被进程2阻断（进程2优先度比进程1优先度高），所以进程2阻断了希望继续在临界区执行的进程1，直到进程2完成！

    所以，进程3实际上是被进程2阻断了，低优先度的进程阻断了高优先度的进程，这就是优先度翻转问题。（临界区执行阻断不属于优先级阻断，而是资源阻断。）上面这个例子，如果我们把进程2的执行时间无限延长的话，进程3就完全没有办法继续执行了。也就是说，理想情况下，我们希望高优先度的进程的最大阻断时间受限于低优先度进程的临界区执行时间之和，实际上在这种最简单的设定下，高优先度的最大阻断时间是低优先度进程临界区执行时间之和加上优先度高于临界区执行进程的进程的执行时间之和。

    一个简单的解决方案，就是在临界区时禁止中断，尽管这个确实能够解决优先度翻转问题，但我们如果考虑如下的情况：

    这相当于无条件地阻断了进程2和进程3，显然不是我们想要的结果。

2.优先度继承（priority inheritance）

    一个比较好的解决办法就是优先度继承。优先度继承的意思是，将临界区内的进程的优先度提高为该进程阻断的进程里的优先级最高进程的优先级。这么说可能还是很绕，我们看一下这个办法具体怎样解决我们上面提到的例子的：

当进程3要求进入R临界区执行时，因为被进程1阻断了，进程1此时在临界区内，而且它阻断的是进程3，那么此时它的优先度就会提升为进程3的优先度，也就是说继承了进程3的优先度。当退出临界执行区后，进程1优先度又会降为原先的优先度。

    这就很好地解决了高优先度进程被无条件阻断的问题，上面这个例子里面，进程3的阻断时间其实只是进程1临界区执行的时间。

    但这也会引起死锁的问题，我们看下面这个例子：

       

• T1被创造       
  
• T1要求进入资源A临界区       
  
• T2被创建       
  
• T2要讲求进入资源B临界区       
  
• T2要求进入资源A临界区       
  
• T1要求进入资源B临界区
  

当进程2要求资源A临界区时，因为进程1正在资源A临界区内，所以其优先级继承了进程2的优先级，但进程1执行了一段时间后又要求进入资源B临界区以完成当前任务，退出临界区A。两个进程此时都在等待对方退出临界区，而自己却不会主动退出自己占有的临界区，所以死锁。

3.优先度天花板（priority ceiling）

    这个策略就是为了解决优先度继承的死锁问题。具体说来就是，为每个资源定义优先度天花板，资源的优先度天花板是所有可能要互斥使用该资源的进程的最高优先度。这种策略只允许满足一个条件的进程去进入临界区，而这个条件就是，该进程的优先度要大于（等于不足够），所有其他进程占用的资源的优先度天花板的最高优先度。同时保留优先度继承策略。 我们看一下上面这个例子，优先度天花板会怎样处理：

    当进程2想进入资源B临界区时，被阻断了，因为它优先度并不大于其他进程（进程1）占用资源（A）的优先度天花板（进程2的优先度），被进程1阻断，与此同时，进程1的优先度提升为进程2的优先度，继续执行，直到退出两个临界区。

4.小结

RTX的互斥锁和信号量有内嵌的优先度继承策略，但是没有内嵌的优先度天花板策略，所以如果你的代码涉及了2个以上独占资源，请留心避免死锁。