haskell - STM缺乏公平性，为什么阻塞的线程不能按照先进先出的顺序被唤醒？

Question

我正在重温 Marlow's book 的 STM 章节.那里指出:

When multiple threads block on an MVar, they are guaranteed to be woken up in FIFO order

但是，在 STM 情况下不能这样做:

A transaction can block on an arbitrary condition, so the runtime doesn't know whether any individual transaction will be able to make progress after the TVar is changed; it must run the transaction to find out. Hence, when there are multiple transactions that might be unblocked, we have to run them all; after all, they might all be able to continue now.

我不明白为什么从这里可以得出结论

Because the runtime has to run all the blocked transactions, there is no guarantee that threads will be unblocked in FIFO order ...

我希望即使我们必须在 STM block 中运行所有事务，我们仍然可以按 FIFO 顺序唤醒线程。所以我想我遗漏了一些重要的细节。

Answer 1

STM 的重点是推测:我们尝试运行所有事务，希望它们不会相互冲突(或执行重试)。当我们确实发现冲突时，我们允许一些事务提交，同时让冲突的事务回滚。

我们可以只运行一个事务，等待它完成或阻塞，然后运行另一个，等等，但这样做相当于使用一个“全局锁”，使计算完全顺序。

从技术上讲，当线程等待 MVar 时，这些线程将在一个非常简单的条件下继续:MVar 变为非空。唤醒时，线程将获取该值，使其为空。因此，最多一个线程可以执行 take，唤醒多个线程没有意义。

相比之下，当线程因为STM而等待时，情况要复杂得多。假设他们正在等待，因为他们之前执行了一次 retry，所以他们正在等待一些之前读取的 TVar 被更改。当这种情况发生时，我们无法真正知道哪个线程会再次阻塞，除非我们重新运行它的事务。与 MVar 不同，现在将它们全部唤醒可能会导致它们全部完成而不会发生冲突，因此我们尝试这样做。这样做我们希望许多(如果不是全部)完成，并准备为那些没有完成的再次回滚。

考虑这个具体的 STM 示例:

Thread 1:
read X
if X is zero, retry
compute f(X)
write Y = f(X)

Thread 2:
read X
if X is zero, retry
compute g(X)
write Z = g(X)

假设一开始我们有“X=Y=Z=0”。我们运行两个线程，但它们重试。然后第三个线程写入 X=1。我们可以唤醒两者，按 FIFO 顺序这样做没有意义，因为两者都会完成。我们可以而且应该并行计算 f(X) 和 g(X)。

现在，如果线程 2 最后写入 Y 而不是 Z，就会发生冲突。在这种情况下，按顺序运行事务会更有效率(否则我们会计算 f(X) 或 g(X) 两次)。但是，在一般情况下，很难预测是否会发生冲突。 STM 不尝试，留给程序员优化他们的代码。