在实时系统中，经常要讨论优先级反转问题带来的影响，本文主要讨论这个。

什么是优先级反转问题

当两个进程在竞争同一个共享资源时，高优先级的任务可能因为低优先级任务正在持有此共享资源从而放弃CPU，这种情况下，必须等到低优先级先运行，而高优先级等到低优先级释放此共享资源之后才得以运行，这种情况下说发生了优先级反转问题。

在其他非实时要求的系统中，如通用Linux内核，这种优先级反转经常发生，因为任务总会得到响应，所以它并不会视为对系统有害的。

有界优先级反转和无界优先级反转

在讨论优先级反转时，我们需要先了解有界优先级反转(通常无害)和无界优先级反转(可能有害)两个问题。

解释含义

场景一：

当系统存在两个优先级任务L和H，低优先级任务L获取了共享资源锁，而高优先级任务H在执行时必须被迫等待任务L完成关键任务并释放共享资源锁之后才能得以运行。

此时高优先级任务H的最坏等待时间实际上是等于低优先级任务L的持有锁时间。

• 高优先级任务H最坏等待时间 = 低优先级任务L的持有锁时间

因为只要任务L在有限的时间完成，这种有限优先级反转其实不会影响和损害应用程序。我们将这种情况称之为有界优先级反转。

场景二：

当系统存在两个优先级任务L和H，任务L获取了共享资源的锁，而任务H必须等到任务L释放锁才得以运行，假设此时出现优先级高于任务L并低于任务H的任务M，它能够有效的抢占任务L，使得任务M运行，直到它放弃对CPU的控制。只有当任务M完成任务时间后，任务L才能得以运行持有锁内的任务。而当任务L完成持有锁内的所有任务，任务H才得以条件获取资源并恢复执行。

此时任务H的最坏等待时间实际上是等于任务M抢占L的运行时间与任务L的持有锁时间之和。

• 高优先级任务H最坏等待时间 = 低优先级任务L的持有锁时间 + 中优先级任务M抢占L后运行的时间

这里可能任务M可能会无限期运行，也有可能会有多个任务M一直抢占任务L的运行，从而导致任务L和任务H都没有机会恢复运行。那么此时任务H的最坏等待时间是不确定的，这种情况下我们称之为无界优先级反转。

在具有实时性要求的系统中，有界优先级反转通常不会产生任何影响，因为其执行时间是固定的，但无界优先级反转可能会给实时任务带来致命错误。

所以需要采取一定的措施解决无界优先级反转问题。

无界优先级反转无害举例

下面举例说明无害的无界优先级反转问题，此例子中可能发生在通用linux中，所以是不会产生实际危害的：

• T0时刻，优先级为10的Task10开始运行；
• T1时刻，Task10申请并获得了锁M，进入临界区；
• T2时刻，优先级为90的任务Task90抢占Task10，开始运行；
• T3时刻，Task90也要申请锁M，准备进入临界区操作，但由于该锁被Task10所持有，Task90被迫放弃CPU，Task10继续运行；
• T4时刻，优先级为50的任务Task50抢占了Task10的CPU，开始运行，此时的状况是，Task90在等Task10，而Task10在等Task50；
• T5时刻，Task50完成任务，释放CPU，Task10继续运行；
• T6时刻，Task10释放锁M，离开临界区，Task90立刻抢占，继续运行。

可以看到，Task90和Task10造成了资源竞争，而Task90与Task50没有竞争关系，但Task50和Task10在这种情况下比Task90优先得到调度，其最坏影响时间是Task10的持有锁时间加上Task50完成抢占的任务时间，因为Task50的任务实际上是不确定的，这就发生了无界优先级反转问题，但如果Task50没有明确的实时确定性要求(deadline)，那么此时的优先级反转问题是无害的，因为它必将完成，只是推迟。

无界优先级反转有害举例

这里再举一个例子，其无界优先级反转导致实时任务错过了deadline，这种情况在实时系统中是有害的。

如上图所示，条件如下：

1. 优先级排序如下 T2 < T1 < T0
2. T0,T1,T2都是实时任务，其确定性由Deadline决定

其运行情况如下：

• t1时刻，任务T2得以运行，此时它获取共享资源锁
• t2时刻，任务T0得以运行，但是因为任务T2持有共享资源锁，所以阻塞
• t4时刻，任务T2恢复执行
• t5时刻，任务T1因为其优先级高于T2，抢占任务T2，任务T1开始运行。
• t9时刻，任务T0错过了截止时间
• t11时刻，任务T1完成，但此时任务T0已经错过了截止时间，任务T2恢复执行
• t12时刻，任务T2执行完成，释放共享资源锁，任务T0得以执行

可以看到，这种场景下，高优先级任务T0出现了延期执行(错过deadline)，而任务T0本身是实时任务，它需要具备确定性的特点。延期执行明显违反了实时任务的确定性特点，所以可能会给实际任务带来致命影响，假设是一次导弹的发射，那么可能就炸膛了~

优先级继承

优先级继承是解决无界优先级反转的一种办法，它的基本思路是：

当低优先级任务获取共享资源后，如果高优先级任务请求同一个共享资源时，此时动态的将低优先级任务的优先级提升到此高优先级任务优先级上。这样，低优先级任务就不容易被其他任务抢占，从而运行持有共享资源的关键部分，直到运行完成并释放资源。当共享资源得到释放之后，低优先级任务会自动回到原始低优先级上，从而系统正常运行其他高优先级任务。

举一个例子，它通过优先级继承解决了优先级反转问题：

如上图所示，其运行情况如下：

• t1时刻，任务T2得以运行，此时它获取共享资源锁
• t2时刻，任务T0得以运行，但是因为任务T2持有共享资源锁，所以阻塞
• t4时刻，任务T2恢复执行，此时会继承T0的优先级
• t5时刻，任务T1因为其优先级低于此时任务T2，不能抢占任务T2，任务T2继续运行。
• t6时刻，任务T2完成运行，并释放资源，并恢复优先级为原始优先级，此时任务T0优先级最高，得以执行
• t9时刻，任务T0得以在截止时间内完成，此时任务T1得以运行

可以看到，这种场景下，任务T2在恢复运行时将优先级继承了同样持有锁的高优先级任务T0，使得任务T2能够优于任务T1运行，从而快速释放共享资源，保证了T0任务在截止时间之前完成。它解决了无界优先级反转导致高优先级错过截止时间的问题。

但是没有这么简单，如果存在嵌套的共享资源锁，那么优先级继承会明显的增加高优先级的等待时间，如果等待时间过长，或截止时间太短。就仍会导致实时任务错过截止时间，从而破坏了实时任务的确定性。

下面举一个例子，它表述了共享资源嵌套导致实时任务仍错过了截止时间的问题：

如上图所示，其运行情况如下：

• t1时刻，任务T2得以运行，此时它获取共享资源锁2
• t2时刻，任务T1得以运行，它抢占了任务T2，此时T1获取了共享资源锁1
• t3时刻，任务T0得以运行，但是其依赖共享资源锁1，但任务T1持有共享资源锁1，所以任务T1继承任务T0的优先级。同时，任务T1依赖共享资源锁2，但任务T2持有共享资源锁2，所以任务T2继承了任务T0的优先级。此时任务T0，T1，T2的优先级都是任务T0的最高优先级。因为资源嵌套问题，任务T2得到执行
• t4时刻，任务T2完成持有锁2的关键任务，释放共享资源锁2，此时任为任务T2优先级返回原始优先级，同时任务T1因共享资源锁2释放，得以占用共享资源锁2执行持有锁2的关键任务
• t6时刻，任务T1完成持有锁2的关键任务，释放共享资源锁2，此时因为任务T0需要等待共享资源锁1，而任务T1正持有共享资源1，故任务T1继续运行。
• t7时刻，任务T1完成持有锁1的关键任务，释放共享资源1，此时任务T1优先级返回原始优先级，同时任务T0因共享资源锁1释放，得以占用共享资源锁1执行持有锁1的关键任务
• t11时刻，任务T0的截止时间到达，但任务T0正在运行
• t13时刻，任务T0完成，但已经错过了截止时间

可以看到，这种场景下，任务T2占用锁2，任务T1占用锁1，而任务T0需要等待锁1才能运行，所以需要等待任务T1释放锁1，而任务T1需要等待锁2才能运行，所以需要等待任务T2释放锁2。此时，即使通过优先级继承能够缓解优先级反转的等待时间，但最后任务T0仍错过了截止时间。

所以，通过这种场景可以发现，优先级继承并不能完全解决优先级反转导致的实时任务被破坏的问题。

优先级天花板

为了解决上述因为嵌套的资源锁问题导致实时任务不确定的问题，另一种解决无界优先级反转的办法出现了，就是优先级天花板。其原理是先为每个共享资源预设优先级上限，当任务获取这个共享资源时，直接将该任务设置为优先级上限，从而确保拥有共享资源的任务不会被尝试访问同一资源的任何其他任务抢占，当提升的任务释放共享资源时，又将其恢复成原始优先级。这种方法能够很好的解决共享资源嵌套时出现的破坏实时任务确定性的问题。

下面举一个例子，它表述了优先级天花板良好处理共享资源嵌套的场景：

如上图所示，其运行情况如下：

• t1时刻，任务T2得以运行，此时它获取共享资源锁2，此时任务T2的优先级提升到资源的上限，即大于任务T1的优先级
• t2时刻，原计划运行的任务T1被任务T2阻止，任务T2继续运行，任务T1阻塞等待
• t3时刻，任务T0得以运行，此时它获取共享资源锁1，并持续运行直到释放资源锁1
• t9时刻，任务T1得以运行，此时共享资源锁1没有被占用，程序得以运行，同样的，共享资源锁2也没有被占用，程序同样得以运行

可以看到，这种场景下，任务T2在获取共享资源锁2的时候，立马改变优先级为最高，此时没有其他任务可以阻塞它运行，同样的任务T0在获取共享资源锁1的时候，也立马改变优先级为最高，此时没有其他任务阻塞它运行。其最终结果是任务T0不会错过其截止时间。

优先级天花板良好的解决了共享资源嵌套导致的破坏实时任务确定性的问题。

优先级继承和优先级天花板的优劣势

根据上面的分析，我们知道优先级天花板很好的解决共享资源嵌套问题，但其也是存在缺点的，那么它有哪些缺点呢。

优先级天花板的缺点

1. 无争用情况下开销大

任务在获取共享资源锁的时候，会立马提升优先级为预设最高值，也就意味着，系统中即使是没有争用的情况下，也会错误的将任务优先级提升最高，其对整体系统来说，开销很大。

2. 阻塞中等优先级任务运行

立马提升优先级为预设最高值，那么意味着系统中低于此优先级的大量中等优先级任务会被错误的阻塞，从而带来整体性能的下降。

3. 平均情况响应时间变差

每次获取共享资源时，都必须立即将该任务设置为优先级上限，而每次释放资源时，都必须立即将该任务降低至原始优先级。这种行为的开销会导致所有相关任务响应时间变差。

可以看到，如果使用优先级天花板协议，那么就将承受共享资源无争用时开销偏大(1)， 系统常规优先级任务整体性能偏低(2)， 所有需要访问共享资源的任务响应时间集体变差 (3) 三个性能问题。

优先级继承的缺点

那么我们如果选择优先级继承解决优先级反转问题，需要注意什么呢？

1. 上下文切换时间可能大于关键任务执行时间

因为优先级继承会将低优先级任务继承高优先级任务的优先级，如果在极端场景下，假设高优先级任务整体优先级并不高，而系统负载较高，那么就容易出现上下文切换时间大于关键任务执行时间的问题。此时上下文切换时间在极端情况下的优化至关重要。

2. 共享资源嵌套问题

优先级继承的共享资源嵌套问题无法从代码设计上解决，因为其最坏情况下的耗时比优先级天花板最坏情况下耗时差很多。同样的，优先级天花板的设计可能会将资源嵌套中可能死锁的场景更容易暴露出来。所以需要程序员自行去避免此问题的出现。

由于实时系统中，应用程序在实际场景下大多数共享资源时是没有争用的，因此优先级继承协议具备常规情况下的最好性能。故它成为了PREEMPT_RT的解决优先级反转的默认策略。

参考文献

Implementation and Evaluation of the Synchronization Protocol Immediate Priority Ceiling in PREEMPT-RT Linux

总结

根据上面的讨论，我们可以知道，在实时系统中，我们需要关注优先级反转问题，它有两种解决办法，优先级天花板和优先级继承，这两种解决办法都有优缺点，如果系统共享资源争用强度高，那么优先级天花板能够非常良好的应用，如果更注重性能和普遍场景下，那么优先级天花板更适用。
但是，如果使用优先级继承，那么共享资源嵌套的问题实际上是交给了程序员自己解决。

而支持PREEMPT_RT的linux内核，默认只支持优先级继承，也就意味着，在实际场景中，如果遇到优先级继承带来的死锁，错过deadline等问题，需要有经验的程序员自行解决。