什么是优先倒置？

Question

关于操作系统的开发,我听过"优先级倒置"这个短语.

什么是优先倒置？

它要解决的问题是什么,它是如何解决的？

Answer 1

想象一下三(3)个不同优先级的任务:tLow,tMed和tHigh.tLow和tHigh在不同时间访问相同的关键资源; tMed做了自己的事.

1. tLow正在运行,tMed和tHigh目前被阻止(但不在关键部分).
2. tLow出现并进入关键部分.
3. t高解除阻塞,因为它是系统中最高优先级的任务,所以它会运行.
4. tHigh然后尝试进入关键资源,但阻止为tLow在那里.
5. tMed取消阻塞,因为它现在是系统中最高优先级的任务,它运行.

tLow放弃资源后才能运行.t在tMed阻塞或结束之前不能运行.任务的优先级已被颠倒; 虽然它具有最高优先级,但它位于执行链的底部.

要"解决"优先级倒置,必须将tLow的优先级提高到至少与tHigh一样高.有些人可能会优先考虑最高优先级.与提高tLow的优先级一样重要的是在适当的时间降低tLow的优先级.不同的系统将采用不同的方法.

何时放弃t的优先级...

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

方法#2是对方法#1的改进,因为它缩短了tLow优先级被提升的时间长度.请注意,在此期间,其优先级保持在tHigh的优先级.

方法#3允许tLow的优先级在必要时以增量递减,而不是在一个全有或全无步骤中.

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

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

希望这可以帮助.

Answer 2

优先级倒置是一个问题,而不是解决方案.典型示例是低优先级进程获取高优先级进程所需的资源,然后被中优先级进程抢占,因此高优先级进程在资源上被阻止,而中优先级进程完成(有效地执行优先级较低).

一个相当着名的例子是火星探路者漫游车遇到的问题:http://www.cs.duke.edu/~carla/mars.html,这是一个非常有趣的读物.

Answer 3

这是问题而不是解决方案.

它描述了这样的情况:当低优先级线程在工作期间获得锁定时,高优先级线程将不得不等待它们完成(这可能需要特别长的时间,因为它们是低优先级的).这里的反转是高优先级线程在低优先级线程之前不能继续,所以实际上它现在也具有低优先级.

一个常见的解决方案是让低优先级线程暂时继承等待其持有的锁的每个人的高优先级.

Answer 4

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

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

我们假设线程1和线程3共享相同的临界区代码

线程1和线程2在示例的开头处处于休眠或阻塞状态.线程3运行并进入关键部分.

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

稍后,线程1开始运行,抢占线程2.线程1尝试进入线程3拥有的关键部分,但由于它由另一个线程拥有,因此线程1阻塞,等待临界区.

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

因此,系统中的最高优先级线程(线程1)将被阻塞,等待较低优先级的线程运行.

Answer 5

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

LP 正在执行临界区。在进入临界区时，LP 一定已经获得了某个对象的锁，比如 OBJ。LP 现在位于临界区中。

同时，HP 被创建。由于更高的优先级，CPU 执行上下文切换，并且 HP 现在正在执行（不是同一个临界区，而是一些其他代码）。在 HP 执行过程中的某个时刻，它需要对同一个 OBJ 的锁（可能在也可能不在同一个临界区上），但是 OBJ 上的锁仍然由 LP 持有，因为它在执行临界区时被抢占. LP 现在不能放弃，因为进程处于 READY 状态，而不是 RUNNING 状态。现在 HP 移动到 BLOCKED / WAITING 状态。

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

因此，实际上这意味着在 MP 完成之前，LP 无法执行，因此 HP 无法执行。因此，看起来 HP 正在等待 MP，即使它们没有通过任何 OBJ 锁直接相关。->优先级反转。

优先级反转的解决方案是优先级继承-

将进程 (A) 的优先级增加到等待 A 拥有资源锁的任何资源的任何其他进程的最大优先级。