优先级倒置

在计算机科学中，优先权倒置是调度中的一种情况，即一个高优先级的任务被一个低优先级的任务间接取代，有效地倒置了任务的分配优先权。这违反了优先级模型，该模型指出高优先级任务只能被高优先级任务阻止运行。当低优先级任务出现资源争夺，然后被中优先级任务抢占时，就会发生倒置。

考虑两个任务H {displaystyle H}和L {displaystyle L}，分别为高优先级和低优先级。高优先级和低优先级的任务，其中任何一个都可以独占访问共享资源R { {displaystyle R}。如果H {{displaystyle H}在L {{displaystyle L}获得R {{displaystyle R}之后试图获得它，那么H {{displaystyle H}就会被阻止，直到L {{displaystyle L}放弃该资源。在一个设计良好的系统中，共享一个独占资源（在本例中是R {displaystyle R}）通常需要L {displaystyle L}及时放弃R {displaystyle R}，这样H {displaystyle H}（一个优先级更高的任务）就不会阻塞太长时间。尽管有良好的设计，但在L {displaystyle L}期间，有可能有第三个中等优先级的任务M {displaystyle M}使用R {displaystyle M}运行。

在某些情况下，优先级倒置可以在不造成直接伤害的情况下发生--高优先级任务的延迟执行不被注意，最终低优先级任务释放了共享资源。然而，也有很多情况下，优先级倒置会导致严重的问题。如果一个高优先级的任务没有得到资源，它可能会导致系统故障或触发预定的纠正措施，如看门狗定时器重置整个系统。1997年火星探路者登陆器遇到的麻烦是实时系统中优先级倒置引起的问题的一个典型例子。

优先级倒置也会降低系统的感知性能。低优先级的任务通常具有低优先级，因为及时完成它们并不重要（例如，它们可能是一个批处理作业或其他非交互式活动）。同样，高优先级的任务具有高优先级，因为它更有可能受到严格的时间限制--它可能是向交互式用户提供数据，或者是一个受实时响应保证的行动。因为优先级倒置的结果是低优先级任务的执行阻碍了高优先级任务的执行，它可能导致系统响应能力的降低，甚至违反响应时间保证。

一个类似的问题，称为截止日期交换，发生在最早的截止日期优先调度（EDF）。

这个问题的存在在20世纪70年代就被知道了，Lampson和Redell发表了最早的论文之一，指出了优先级倒置问题。UNIX内核等系统已经用splx()原语解决了这个问题。没有万无一失的方法来预测这种情况。然而，有一些现有的解决方案，其中最常见的是。

禁用所有中断以保护关键部分 当禁用中断被用来防止优先级倒置时，只有两个优先级：可抢占和禁用中断。如果没有第三个优先级，倒置是不可能的。由于只有一块锁数据（中断使能位），错误的锁是不可能的，所以死锁不会发生。

由于关键区域总是运行到完成，挂起也不会发生。请注意，这只有在所有中断被禁用的情况下才有效。如果只有一个特定的硬件设备/的中断被禁用，优先级倒置就会由硬件/的中断优先级重新引入。在UNIX的早期版本中，有一系列名为splx(0)的中断......splx(7)的中断原语禁用了给定优先级之前的所有中断。优先级倒置的问题可以通过正确选择曾经进入关键部分的任何中断的最高优先级来解决，而不必锁定所有中断。一个简单的变体，即单一共享标志锁，被用于多CPU系统中。这个方案在共享内存中提供了一个单一的标志，被所有的CPU用来锁定所有处理器间的关键部分的繁忙等待。