什么是优先倒置？

我已经听说过关于操作系统开发的“优先倒置”这个短语。

什么是优先倒置？

它意味着要解决什么问题？它是如何解决的？

Answer 1

优先倒置是一个问题，而不是一个解决scheme。 典型的例子是获取高优先级进程需要的资源的低优先级进程，然后被中等优先级进程抢占，因此高优先级进程在资源上被阻塞，而中等优先级进程结束（有效地用低优先级）。

一个比较有名的例子就是火星探路者漫游者遇到的问题： http : //www.cs.duke.edu/~carla/mars.html ，这是一个非常有趣的阅读。

Answer 2

设想三个不同优先级的任务：tLow，tMed和tHigh。 tLow和tHigh不同时间访问相同的关键资源; tMed做它自己的事情。

1. tLow正在运行，tMed和tHigh目前被阻止（但不在关键部分）。
2. tLow进入临界区。
3. 由于它是系统中最高优先级的任务，因此运行非常畅通无阻。
4. 然后尝试进入关键资源，但是因为tLow在那里而被阻塞。
5. tMed解锁并且由于它现在是系统中最高优先级的任务，所以它运行。

tLow放弃资源之前无法运行。 tLow不能运行，直到tMed块或结束。 任务的优先性被颠倒过来; 尽pipe它的优先级最高，但却处于执行链的最底层。

为了“解决”优先倒置，tLow的优先级必须至less高达tHigh。 有些可能会将其优先级提高到最高优先级。 与提高tLow的优先级一样重要，就是在合适的时间（s）降低tLow的优先级。 不同的系统将采取不同的方法。

何时放弃tLow的优先权…

1. 没有任何其他任务在tLow所拥有的任何资源上被阻塞。 这可能是由于超时或释放资源。
2. 没有其他任何有助于提高tLow的优先级的任务在tLow所具有的资源上被阻止。 这可能是由于超时或释放资源。
3. 当任务等待资源发生变化时，删除tLow的优先级以匹配在其资源上阻塞的最高优先级任务的优先级。

方法＃2比方法＃1有所改进，因为它缩短了tLow优先级颠簸的时间长度。 请注意，在此期间，其优先级保持在tHigh的优先级。

方法＃3允许tLow的优先级在必要时以递增的方式递减，而不是在一个全有或全无的步骤中。

不同的系统将根据他们认为重要的因素实施不同的方法。

• 内存占用
• 复杂
• 实时响应
• 开发者知识

希望这可以帮助。

Answer 3

优先级反转问题：
让我们考虑一个例子：任务：
高优先级（H）
中等优先（M）
低优先级（L）

和一个锁X，可能是semaphore_lock（X）。

场景：
1. L运行并获取X.
2.然后H尝试访问X而L有它，因为信号量，H睡觉。
3. M到达，抢先L并运行。 实际上，H＆M是两个等待运行的进程，但是M运行，因为H正在等待locking，不能运行 。
4. M完成，H不能进入，因为L有锁，所以L运行。
5. L完成，放弃locking。 现在H获得锁并执行。

H具有最高的优先级，但在优先级较低的进程运行之后运行。 这是优先倒置。

现在解决优先倒置。
当低优先级进程正在运行并且具有locking时，并且如果高优先级进程试图获取locking，则将低优先级进程的优先级提高到高优先级进程的优先级。 也就是说，如果L正在运行并且有锁，当H试图获得它的时候，在L持有锁的期间，L的优先级将提高到H的优先级。 这样，M就不能先占。 L完成后，H运行并获取locking。 H完成后，M运行保持优先顺序。

Answer 4

这是问题，而不是解决scheme。

它描述了当低优先级的线程在其工作期间获得锁的情况下，高优先级线程将不得不等待它们完成（这可能需要特别长的时间，因为它们是低优先级的）。 这里的反转是高优先级线程不能继续，直到低优先级线程执行，所以实际上它现在也具有低优先级。

一个常见的解决scheme是让低优先级的线程临时inheritance正在等待锁的每个人的高优先级。

Answer 5

假设一个应用程序有三个线程：

 Thread 1 has high priority. Thread 2 has medium priority. Thread 3 has low priority. 

假设线程1和线程3共享相同的关键部分代码

在示例的开始处，线程1和线程2正在hibernate或阻塞。 线程3运行并进入关键部分。

此时，线程2开始运行，抢占线程3，因为线程2具有更高的优先级。 所以，线程3继续拥有一个关键部分。

稍后，线程1开始运行，抢占线程2.线程1尝试进入线程3拥有的临界区，但是由于它由另一个线程拥有，线程1阻塞，正在等待临界区。

此时，线程2开始运行，因为它具有比线程3更高的优先级，并且线程1没有运行。 线程3从不释放线程1正在等待的关键部分，因为线程2继续运行。

因此，系统中最高优先级的线程（线程1）被阻塞，等待较低优先级的线程运行。

Answer 6

[假设，低进程= LP，中进程= MP，高进程= HP]

LP正在执行关键部分。 在进入关键部分时，LP必须获得对某个对象的locking，比如OBJ。 LP现在在临界区域内。

同时，惠普创build。 由于更高的优先级，CPU执行上下文切换，并且HP正在执行（不是相同的关键部分，而是一些其他代码）。 在HP执行期间的某个时刻，它需要locking同一个OBJ（可能或不在同一个关键部分），但是OBJ上的锁仍然由LP保存，因为它在执行临界区时被预占。 LP现在不能放弃，因为进程处于READY状态，而不是RUNNING。 现在HP转移到BLOCKED / WAITING状态。

现在MP进来了，执行自己的代码。 MP不需要在OBJ上locking，所以它保持正常执行。 HP等待LP释放locking，LP等待MP完成执行，以便LP可以回到RUNNING状态（..并执行并释放locking）。 只有在LP释放锁后，HP才能回到READY状态（然后通过预占低优先级任务进入RUNNING状态）。

所以，这实际上意味着，在MP完成之前，LP不能执行，因此HP不能执行。 所以，似乎惠普正在等待MP，即使它们不是通过任何OBJ锁直接相关的。 – > 优先倒置 。

优先级反转的解决scheme是优先级inheritance –

将进程（A）的优先级提高到等待其中有资源锁的资源的任何其他进程的最大优先级。

Answer 7

优先级倒置是指优先级较低的进程获取优先级较高的进程所需的资源，阻止优先级较高的进程继续进行，直到资源被释放。

例如：FileA需要被Proc1和Proc2访问。 Proc 1比Proc2具有更高的优先级，但是Proc2首先打开FileA。

通常Proc1运行的次数可能是Proc2的10倍，但是由于Proc2持有文件，所以无法执行任何操作。

所以最终发生的事情是，Proc1阻塞，直到Proc2完成与FileA，本质上他们的优先事项是“倒置”，而Proc2持有FileA的处理。

就“解决问题”而言，优先倒置本身就是一个问题。 最坏的情况（大多数操作系统不会让这种情况发生）是否Proc2不允许运行，直到Proc1有。 这会导致系统locking，因为Proc1会一直分配CPU时间，而Proc2永远不会获得CPU时间，所以文件永远不会被释放。

Answer 8

优先级反转发生如下：给定进程H，M和L，其中名称代表高，中，低优先级，只有H和L共享公共资源。

假设L首先获取资源并开始运行。 由于H也需要这个资源，它进入等待队列。 M不共享资源，并可以开始运行，因此它。 当L被任何手段中断时，M就会处于运行状态，因为它具有更高的优先级，并且在发生中断的瞬间运行。 虽然H比M有更高的优先级，但由于处于等待队列，所以不能获取资源，这意味着比M更低的优先级.M完成后，L再次接pipeCPU，导致H等待整个时间。

Answer 9

如果被阻塞的高优先级线程将其高优先级转移到保持在资源上的低优先级线程，则可以避免优先级反转。

Answer 10

当较高优先级的进程需要读取或修改当前由较低优先级进程或一系列较低优先级进程访问的内核数据时，会产生调度挑战。 由于内核数据通常使用锁保护，因此优先级较高的进程将不得不等待较低优先级的进程使用该资源。 如果较低优先级的进程被优先权较高的另一进程抢占，情况会变得更加复杂。 作为一个例子，假设我们有三个进程-L，M和H，它们的优先级遵循L <M <H的顺序。假设进程H需要资源R，目前进程L正在访问资源R.通常，进程H将等待L使用资源R完成。但是，现在假设进程M变为可运行的，从而抢占进程L.间接地，具有较低优先级进程M的进程已经影响进程H必须等待L放弃资源R的时间这个问题被称为优先级倒置，它只发生在具有两个以上优先级的系统中，所以一个解决scheme只有两个优先级。然而这对于大多数通用操作系统是不够的。 通常这些系统通过实施优先权inheritance协议来解决问题。 根据这个协议，所有正在访问优先级较高的进程所需资源的进程都会inheritance更高的优先级，直到它们完成所讨论的资源。完成后，它们的优先级会恢复到原来的值。 在上面的例子中，优先级inheritance协议将允许进程L临时inheritance进程H的优先级，从而防止进程M抢占其执行。 当进程L使用资源R完成时，它将从H中放弃其inheritance的优先级，并假定它的原始优先级。由于资源R现在可用，所以进程H（而不是M）将接下来运行。 参考：ABRAHAM SILBERSCHATZ

Answer 11

考虑一个有两个进程的系统， H高优先级， L低优先级。 调度规则是这样的： H由于其高优先级而处于就绪状态时运行。 在某一时刻，当L处于临界区域时， H就准备运行（例如，I / O操作完成）。 H现在开始忙于等待，但是因为L在H运行时从不安排，所以L从来没有机会离开关键部分。 所以H永远循环。

这种情况被称为Priority Inversion 。 因为较高优先级的进程正在等待较低优先级进程。

Answer 12

让我说得很简单明了。 （这个答案是基于上面的答案，但以清晰的方式呈现）。

说有一个资源R和3个进程。 L ， M ， H 。 其中p(L) < p(M) < p(H) （其中p(X)是X优先级）。

说

• L开始执行，并抓住R （独家访问R ）
• H来得晚，也想要独家访问R ，因为L拿着它， H必须等待。
• M在H之后， 不需要R 而且，由于M已经得到了它想要执行的所有内容，所以迫使L离开，因为它与L相比具有高优先级。 但H不能做到这一点，因为它有一个资源locking的L ，它需要执行。

现在让问题更清楚了，实际上M应该等待H完成，因为p(H) > p(M)没有发生，这本身就是问题。 如果有许多进程（如M出现，并且不允许L执行并释放锁，则H将永远不会执行。 哪些在时间关键的应用中可能是危险的

对于解决scheme，请参阅上面的答案:)