STM缺乏公平性，为什么阻塞的线程不能按照先进先出的顺序被唤醒？
Lack of fairness in STM, why can't blocked threads be woken up in FIFO order?
我正在重温 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 块中的所有事务，我们仍然可以按 FIFO 顺序唤醒线程。所以我想我遗漏了一些重要的细节。
STM 的重点是推测：我们尝试 运行 处理所有交易，希望它们不会相互冲突（或执行 retry）。当我们确实发现冲突时，我们允许一些事务提交，同时让冲突的事务回滚。
我们可以 运行 只有一个事务，等待它完成或阻塞，然后 运行 另一个事务，依此类推，但这样做相当于使用一个单一的“全局锁”，使计算完全按顺序进行。
从技术上讲，当线程等待 MVar 时，这些线程将在一个非常简单的条件下进行：MVar 变为非空。唤醒时，线程将获取该值，使其为空。所以，最多一个线程可以执行 take，唤醒多个线程是没有意义的。
相比之下，当线程因为STM而等待时，情况要复杂得多。假设他们正在等待，因为他们之前执行了一个 retry，所以他们正在等待一些之前读取的 TVar 被更改。当这种情况发生时，我们无法真正知道哪个线程会再次阻塞，除非我们重新[=38=]它的事务。与 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 不尝试，留给程序员优化他们的代码。
当一堆线程正在等待从 MVar 中获取并且有人填充它时，只有一个等待线程可以 运行。这就是重点。唤醒的线程在完成任务后（大概）会再唤醒一个线程并依次填充 MVar。因此，有一个明确的顺序让服务员轮到他们是有道理的。
TVar 不是 MVar。他们没有 empty/reserved 与 full/available 的二分法。它们只是可以通过交易访问 and/or 更改的值。线程不会“阻塞等待 TVar”；他们只是读取 TVar 的当前值，然后决定他们无法使用该值取得进展（因此 retry）。
运行时间系统知道线程访问了哪个 TVars，因此它知道不会再次唤醒该线程，除非至少有一个 TVars 发生变化；通过纯计算，线程决定是否 retry 应该是它读取的所有 TVar 的纯函数，所以我们知道它不能取得进展，直到其中一个改变。
但是当你有一堆线程在 retry 中等待，它们都读取相同的 TVar 并且它发生变化时，运行时间系统不想只是唤醒一个。没有理由相信只有其中一个能够在新价值上取得进步。 STM 事务应该 乐观地并行运行。我们想唤醒他们 所有 并让他们尝试 运行。如果它们发生冲突，我们稍后会通过检测 STM 事务之间争用的正常方法发现；我们不能从他们都想阅读相同的 TVar.
的事实中看出这一点
我们可能会同时唤醒它们，并且（如果可用计算单元太多）尝试确保调度程序运行以 FIFO 顺序启动它们。也许这已经完成了；我不知道。但我猜想它们的处理方式与任何其他可用于调度的线程完全相同，并且不会采取任何特殊操作。它们“应该”都是 运行 并行的，所以哪个先出门应该无关紧要。
我正在重温 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
TVaris 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 块中的所有事务，我们仍然可以按 FIFO 顺序唤醒线程。所以我想我遗漏了一些重要的细节。
STM 的重点是推测：我们尝试 运行 处理所有交易，希望它们不会相互冲突（或执行 retry）。当我们确实发现冲突时，我们允许一些事务提交，同时让冲突的事务回滚。
我们可以 运行 只有一个事务，等待它完成或阻塞，然后 运行 另一个事务，依此类推，但这样做相当于使用一个单一的“全局锁”，使计算完全按顺序进行。
从技术上讲，当线程等待 MVar 时，这些线程将在一个非常简单的条件下进行：MVar 变为非空。唤醒时，线程将获取该值，使其为空。所以，最多一个线程可以执行 take，唤醒多个线程是没有意义的。
相比之下，当线程因为STM而等待时，情况要复杂得多。假设他们正在等待，因为他们之前执行了一个 retry，所以他们正在等待一些之前读取的 TVar 被更改。当这种情况发生时，我们无法真正知道哪个线程会再次阻塞，除非我们重新[=38=]它的事务。与 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 不尝试，留给程序员优化他们的代码。
当一堆线程正在等待从 MVar 中获取并且有人填充它时，只有一个等待线程可以 运行。这就是重点。唤醒的线程在完成任务后（大概）会再唤醒一个线程并依次填充 MVar。因此，有一个明确的顺序让服务员轮到他们是有道理的。
TVar 不是 MVar。他们没有 empty/reserved 与 full/available 的二分法。它们只是可以通过交易访问 and/or 更改的值。线程不会“阻塞等待 TVar”；他们只是读取 TVar 的当前值，然后决定他们无法使用该值取得进展（因此 retry）。
运行时间系统知道线程访问了哪个 TVars，因此它知道不会再次唤醒该线程，除非至少有一个 TVars 发生变化；通过纯计算，线程决定是否 retry 应该是它读取的所有 TVar 的纯函数，所以我们知道它不能取得进展，直到其中一个改变。
但是当你有一堆线程在 retry 中等待，它们都读取相同的 TVar 并且它发生变化时，运行时间系统不想只是唤醒一个。没有理由相信只有其中一个能够在新价值上取得进步。 STM 事务应该 乐观地并行运行。我们想唤醒他们 所有 并让他们尝试 运行。如果它们发生冲突，我们稍后会通过检测 STM 事务之间争用的正常方法发现；我们不能从他们都想阅读相同的 TVar.
我们可能会同时唤醒它们，并且（如果可用计算单元太多）尝试确保调度程序运行以 FIFO 顺序启动它们。也许这已经完成了；我不知道。但我猜想它们的处理方式与任何其他可用于调度的线程完全相同，并且不会采取任何特殊操作。它们“应该”都是 运行 并行的，所以哪个先出门应该无关紧要。