优先级反转

简介

优先级反转 英文名叫做 Priority Inversion，一句话概括它的意思：低优先级任务要比高优先级任务先执行。

先明白一些背景知识

• 1.操作系统是多任务的
• 2.任务之间谁都可以得到执行，是通过任务调度来完成
• 3.任务调度有多种算法，常见的有：
  • 罗宾环调度算法：Round-robin scheduling algorithm
  • 基于优先级的调度算法：Priority-controlled scheduling algorithm
• 4.一般操作系统用的就是优先级调度算法，根据优先级别高低去调度，也就是优先级高的先执行，优先级低的后执行；
  • 任务调度器，总是先去激活所有任务中优先级别最高的任务，且该任务处于就绪状态，然后让它执行
  • 任务有多种状态：就绪，挂起，执行等；常见的如：需要某种资源时被别的任务占用了，那么当前任务就不得不挂起，先让被占用资源的任务执行
• 5.任务一般被称为：进程，或者粒度更小的线程

详细解释下为什么

假设有以下条件

• 1.任务A （低优先级）
• 2.任务B （中优先级）
• 3.任务C （高优先级）
• 4.资源

步骤

• 1.已知任务调度器总是去激活所有任务中优先级最高的，且处于就绪状态的任务，去执行；但是当某个最高优先级的任务A，由于其所需要的某个资源被低优先级任务C所占用，而且还没有释放，那么高优先级任务A就被阻塞了。
• 2.按照调度规则：
  • 此高优先级任务A，必须等到低优先级任务C把自己占用的资源释放后，才能继续运行；
  • 但是要等到低优先级任务C释放其所占用的资源的话，则很明显，必须要让低优先级任务C 先去执行，然后等低优先级任务C执行完毕并释放资源后，高优先级任务A就能得到的那个资源了；
  • 但是，问题就是：在高优先级任务A执行的这段时间内，某个中优先级任务B已经处于就绪状态了，所以当高优先级任务A，由于所需要的资源被占用而挂起，然后中优先级任务B，由于比低优先级任务C的优先级高，所以被调度执行，然后中优先级任务B就一直执行，知道结束。
• 3.这种情况就是：一个中等优先级任务B，却比一个高更优先级的任务A 先执行，这就叫做优先级反转

问题：
本来应该是优先级最高的任务A先执行的，结果却变成了，比高优先级任务A要低一些的中优先级任务B先执行了。
优先级反转如名字一样，就是他们的优先级别互换了一下（反转了一下）。

有的朋友会问了，反转就反转了呗😄，有什么大不了的，程序还不是照样运行吗？

优先级反转的有和危害

实话说，当我刚学习计算机的时候，对计算机的概念都真的只是个概念，背后的技术和逻辑学的也是云里云雾的，而慢慢的成长，就会发现以前不理解的知识，现在看起来很重要很重要，而且也容易理解些了。

对于实时系统，最重要的指标就是：确保任务执行时间是可预测的，即涉及到最后时间点等
比如：
要确保，某个时刻在执行某个任务，都不能超过某个时间等

危害一

• 由于优先级反转，造成任务调度时，时间的不确定性。
  • 时间的不确定，破坏了实时系统的实时性
    • 严重时可能导致系统崩溃

危害二

• 由于本身基于优先级设计的任务，每个优先级不同的任务，往往都对应着实际的现实中执行的任务
  • 由于优先级反转，导致了低优先级比高优先级先执行了
    • 直接导致任务错乱，逻辑错乱了
      • 程序可能也就异常了
        • 数据可能也会错误的

现实中最有名也是第一例

当年的火星探路者号（Mars Pathfinder）就由于优先级反转问题而导致火星探路者号内部程序的执行逻辑出错。
在1997年7月4号发射后，在开始搜集气象数据之后没几天，系统就（无故）重启了。
后来，被相关技术人员找到了问题根源，就是优先级反转所导致的，然后他们就发送了一个简单的C程序到火星探路者上，以修复。
可以看这里：http://blog.jobbole.com/42802/

如何解决或避免优先级反转的问题了？

既然危害那么大，也发生了那么多年，肯定早就解决了。
解决方法就是：

• 对于占了高优先级任务A的某种所需资源的低优先级任务C，赋予给低优先级任务C和高优先级任务A相同的优先级;
• 所以执行顺序就是 高优先级任务A执行时被阻塞了 -> 执行高优先级任务C（原来是低优先级） -> 执行剩下的任务A -> 执行中优先级的任务B

看图

仔细对比这张图和上一张图的区别，Priority Inheritance （优先级继承）

Priority Celling（最高优先级）

由于临界区，mutex（互斥）了公用的资源部分，则赋予相同优先级。
由此，凡是想要用到临界区的资源的任务，要在进入临界区之前，都要将临界区的优先级赋予给该任务，从而使得该任务有了相同的优先级而不被打断，才可以保持继续运行，直到用过资源后，退出临界区，这样就避免了，被高优先级A发现某资源被低优先级C占用之类的问题了。

好了，就说到这里，相信读者应该很清晰明白了优先级反转的原因和解决方案了吧。😄