1

优先级倒置是一个常见且有些古老的问题。处理过 OS 进程调度的人，特别是有实时性要求的人，对它很熟悉。这个问题几乎没有众所周知的解决方案，每个都有其优点和缺点：

  • 禁用所有中断以保护关键部分
  • 优先上限
  • 优先继承
  • 随机提升

选择哪种方法来处理优先级倒置并不重要；鉴于应用程序使用定义良好的接口来同步共享资源，所有这些都相对容易在 OS 内核中实现。例如，如果一个进程使用，例如，锁定一个互斥锁，pthread_mutex_lock操作系统很清楚这一事实，因为这个函数在深处执行系统调用（即futex在 Linux 上）。当内核处理这个请求时，它对谁在等待什么有一个完整而清晰的画面，并且可以决定如何最好地处理优先级反转。

现在，假设内核不知道进程何时锁定/解锁互斥锁。例如，如果使用原子 CPU 指令来实现互斥锁（如“无锁”算法），就会发生这种情况。然后，低优先级的进程可能会因为更高优先级的任务而获得锁并暂停执行。然后，当安排更高优先级的任务时，它会简单地烧毁 CPU，试图锁定“自旋锁”。像这样的死锁会使整个系统变得毫无用处。

鉴于上述情况以及我们无法更改程序以不使用原子操作来同步对共享资源的访问这一事实，问题归结为检测代码何时尝试这样做。

我有一些有点模糊的启发式想法，这些想法既难以实施，又可能会产生误报。他们来了：

  1. 不时查看程序计数器寄存器并尝试检测代码只是在紧密循环中烧毁 CPU。如果代码在该位置被发现 N 次，则暂停该进程并让其他优先级较低的进程有机会运行并解锁互斥锁。这种方法离理想太远了，可能会产生太多误报。
  2. 对进程可以运行的时间有硬性限制。这会立即降低调度程序的硬实时功能，但它可以工作。然而，问题在于，在“死锁”情况下，高优先级进程将浪费其所有时间窗口来尝试获取繁忙的资源。
  3. 我不知道这是否可能，但另一个想法是拦截/插入原子 CPU 指令，让调度程序知道锁定/解锁尝试。换句话说，本质上是将原子 CPU 操作转换为某种系统调用。当 MMU 发出页面错误信号时，它的机制与创建虚拟页面映射的方式有些接近。

你怎么看上面的想法？您还能想到哪些其他检测此类代码的方法？

4

2 回答 2

1

我认为您的选项 1 可能比您认为的更有价值。我假设您有几个可能需要监视的进程，并且您不知道自旋锁的目标地址。

与随机外部采样相比，您可能会发现此时挂钩调度程序入口点并收集您的统计数据更容易，优势是您在进程地址空间中并且缓存很热。我对linux调度程序了解不多，但过去在OpenVMS上做过这种事情。调度程序通常有两个入口点，自愿的（等待 IO 等）和非自愿的，自旋锁问题几乎总是非自愿的，因此这应该会降低您的工作率。

显然，此时您拥有中断的 PC，但似乎英特尔芯片也有一些您可以使用的性能监控计数器、BTS（分支跟踪存储）和 PEBS，但这些在性能方面可能是“非免费的”。诸如分支跟踪之类的信息会很快显示出紧密的循环，然后您可以使用它来检查导致循环的实际指令（同样，已经在缓存中）并查看它是条件原子指令还是“正常”工作，例如对数组求和.

如果您没有编写代码，则始终可能以某种方式使用了非互锁指令，希望不会！

虽然我认为一些片上监控功能在这里真的可以提供帮助，但您也可以简单地检查电脑在最后 M 个计划周期结束时是否大致相同，并强制它跳过一个周期，非常简单但没有针对性。

虽然您可以将所有这些作为第二个进程进行查看，但它可能不像基于调度程序的方法那样响应迅速，尽管可能更安全且系统崩溃的可能性更小。无论如何，您仍然需要从调度程序中获取最后一台 PC，并且第二个进程的优先级必须高于或等于受监视进程的优先级。

于 2013-06-09T06:16:20.063 回答
1

虽然我仍然质疑您的设置（请参阅评论），但我认为您的第三种方法是最有希望的，因为它提供了最精确的信息。我可以想出两种遵循主要思想的机制：

  1. 假设：你知道锁的地址。您可以通过检查系统中典型自旋锁模式的二进制文件来找到它们，例如loop: CMPXCHG <adr>, JRZ loop.
    然后，您标记<adr>为“丢失”或“不可访问”并挂钩 MMU 服务例程。
  2. 假设：您还可以更改二进制文件的文本段。
    然后，您可以通过调用常规互斥锁或一些自己的记账例程（在实际锁定旁边）来交换关键自旋锁。

作为策略，您应该更喜欢优先级上限而不是优先级继承，因为它可以避免死锁作为副作用。您可以应用它，因为无论如何您都知道线程的（潜在）锁。

对于更详细的解决方案，需要有关硬件、操作系统和工具链的更多信息。

另外请注意，使用 atomar 用户级自旋锁的基本方法可能不适用于当今的几种内存一致性模型。

于 2013-06-03T13:09:52.387 回答