76

我听说过有关操作系统开发的“优先级反转”一词。

究竟什么是优先级反转？

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

4

11 回答 11

74

想象三 (3) 个不同优先级的任务：tLow、tMed 和 tHigh。tLow 和 tHigh 在不同时间访问同一个关键资源；tMed 做自己的事。

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

在 tLow 放弃资源之前，tHigh 无法运行。tLow 无法运行，直到 tMed 阻塞或结束。任务的优先级已倒置；tHigh 尽管它具有最高优先级，但它位于执行链的底部。

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

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

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

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

方法#3 允许 tLow 的优先级在必要时逐步降低，而不是在一个全有或全无的步骤中。

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

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

希望这可以帮助。

于 2010-11-23T15:22:43.983 回答
64

优先级反转是一个问题，而不是解决方案。典型的例子是低优先级进程获取高优先级进程需要的资源，然后被中优先级进程抢占，所以高优先级进程在资源上阻塞，而中优先级进程完成（实际上是用较低的优先级）。

一个相当著名的例子是火星探路者火星车遇到的问题：http ://www.cs.duke.edu/~carla/mars.html ，读起来很有趣。

于 2010-11-23T02:31:45.407 回答
22

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

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，被阻塞等待低优先级的线程运行。

于 2013-10-01T22:45:18.577 回答
18

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

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

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

于 2010-11-23T02:27:42.703 回答
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 具有资源锁的任何资源的任何其他进程的最大优先级。

于 2014-12-16T06:19:00.927 回答
3

让我说得非常简单明了。（此答案基于上述答案，但以清晰的方式呈现）。

假设有一个资源R和 3 个进程。L, M, H. where p(L) < p(M) < p(H)（p(X)优先级在哪里X）。

说

  • L首先开始执行并 catch 保持R。（独家访问R）
  • H来晚了，也想独占访问R，既然L是持有它，H只好等待。
  • M紧随其后H，它不需要R。既然M已经得到了它想要执行的一切，它就会被迫L离开，因为它与L. 但H不能这样做，因为它有一个资源锁定L它需要执行。

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

对于解决方案，请参阅上述答案:)

于 2017-09-02T04:56:38.793 回答
2

优先级反转是低优先级进程获得高优先级进程所需的资源，阻止高优先级进程继续进行，直到资源被释放。

eg: FileA 需要被 Proc1 和 Proc2 访问。Proc 1 的优先级高于 Proc2，但 Proc2 设法首先打开 FileA。

通常，Proc1 的运行频率可能是 Proc2 的 10 倍，但由于 Proc2 正在保存文件，因此无法执行任何操作。

所以最终发生的事情是 Proc1 阻塞，直到 Proc2 完成 FileA，本质上它们的优先级是“反转的”，而 Proc2 持有 FileA 的句柄。

就“解决问题”而言，如果优先级倒置不断发生，它本身就是一个问题。最坏的情况（尽管大多数操作系统不会让这种情况发生）是如果 Proc2 在 Proc1 之前不允许运行。这将导致系统锁定，因为 Proc1 将继续获得分配的 CPU 时间，而 Proc2 将永远不会获得 CPU 时间，因此永远不会释放文件。

于 2010-11-23T02:24:54.147 回答
1

优先级倒置是这样发生的：给定进程 H、M 和 L，其中名称代表高、中和低优先级，只有 H 和 L 共享一个公共资源。

比如说，L 首先获取资源并开始运行。由于 H 也需要该资源，因此它进入等待队列。M 不共享资源并且可以开始运行，因此它确实如此。当 L 被任何方式中断时，M 进入运行状态，因为它具有更高的优先级，并且在中断发生的瞬间运行。虽然 H 的优先级比 M 高，但由于它在等待队列中，所以它无法获取资源，这意味着比 M 还要低的优先级。在 M 完成后，L 将再次接管 CPU，导致 H 一直等待。

于 2013-11-04T22:12:37.387 回答
0

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

于 2015-07-28T16:34:22.997 回答
0

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

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

于 2017-08-20T08:20:46.110 回答
0

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

于 2016-03-05T10:22:14.537 回答