c - 处理高争用、高频情况的锁

Question

我正在寻找一种锁实现，它可以在您有两个线程以非常高的频率不断尝试释放和重新获取同一锁的情况下优雅地降级。

当然，在这种情况下，两个线程显然不会并行进行。从理论上讲，最好的结果是运行整个线程 1，然后运行整个线程 2，而不进行任何切换——因为切换只会在这里产生大量开销。因此，我正在寻找一种锁实现，它可以通过在切换之前让同一个线程运行一段时间而不是不断切换来优雅地处理这种情况。

问题的长版

因为我自己很想用“你的程序坏了，不要那样做”来回答这个问题，这里有一些关于为什么我们最终会陷入这种情况的理由。

该锁是“单一全局锁”，即非常粗糙的锁。 (它是 PyPy 内部的全局解释器锁(GIL)，但问题是关于一般情况下如何做到这一点，假设你有一个 C 程序。)

我们有以下情况:

• 争论不断。在这种情况下这是预期的:锁是一个全局锁，大多数线程都需要获取它才能进行。所以我们预计他们中的很大一部分正在等待锁。这些线程中只有一个可以进行。

• 持有锁的线程有时可能会突然释放短时间。一个典型的例子是如果这个线程重复调用“外部的东西”，例如许多简短的写入文件。这些写入中的每一个通常都很快完成。仍然必须释放锁，以防万一这个外部事物花费的时间比预期的要长(例如，如果写入实际上需要等待磁盘 I/O)，以便另一个线程可以在这种情况下获取锁。

如果我们为锁使用一些标准的互斥量，那么锁通常会在所有者释放锁后立即切换到另一个线程。但问题是，如果程序运行多个线程，每个线程都想进行长时间的短释放。该程序最终花费大部分时间在 CPU 之间切换锁。

在切换之前运行同一个线程一段时间要快得多，至少只要在很短的时间内释放锁。 (例如，在 Linux/pthread 上，紧接着获取的释放有时会立即重新获取锁，即使还有其他等待线程也是如此；但我们希望在大多数情况下都能得到这种结果，而不仅仅是有时。)

当然，一旦锁被释放了更长的时间，那么将锁的所有权转移到不同的线程就成了一个好主意。

所以我正在寻找关于如何做到这一点的一般想法。我想它应该已经存在于某个地方——在论文中，或者在一些多线程库中？

作为引用，PyPy 尝试通过轮询来实现类似的东西:锁只是一个全局变量，具有同步比较和交换但没有操作系统调用；其中一个等待线程被赋予“窃取者”的角色； “窃取者”线程每 100 微秒唤醒一次以检查变量。这并不是非常糟糕(除了正在运行的线程消耗的 100% 的 CPU 时间之外，它可能花费 1-2% 的 CPU 时间)。这实际上实现了我在这里的要求，但问题是这是一个不能完全支持更传统的锁情况的 hack:例如，如果线程 1 尝试向线程 2 发送消息并等待答案是，两个线程切换平均每次需要 100 微秒——如果消息处理得很快，这就太多了。

Answer 1

作为引用，让我描述一下我们最终是如何实现它的。我对此不确定，因为它仍然感觉像是一个 hack，但它似乎在实践中适用于 PyPy 的用例。

我们按照问题的最后一段中的描述做了它，增加了一个:“窃取者”线程，每 100 微秒检查一些全局变量，通过调用 pthread_cond_timedwait 或 WaitForSingleObject 具有系统提供的常规互斥锁，超时为 100 微秒。这为全局变量和常规互斥锁提供了一个“复合锁”。如果“窃取者”注意到值 0 是全局变量(每 100 微秒)，则“窃取者”将成功窃取“锁”，或如果另一个线程释放了常规互斥锁。 p>

接下来就是根据具体情况选择如何释放复合锁的问题。大多数外部函数(写入文件等)通常会很快完成，因此我们通过写入全局变量来释放并重新获取复合锁。只有在一些特定的函数情况下——比如 sleep() 或 lock_acquire()——我们希望调用线程经常阻塞；围绕这些函数，我们通过实际释放互斥锁来释放复合锁。