multithreading - CAS 碰撞的 CPU 内部特性是什么？

Question

我正在尝试了解 x86/x64 上 CAS 的低级机制，我非常感谢一些帮助/见解。

我一直在思考这个问题的原因是我试图对指数退避进行推理，并在原则上弄清楚退避延迟的正确单个单位应该是什么。

如果我查看一个没有指数退避的无锁 freelist 基准测试，我会看到随着线程数量的增加，性能会迅速下降。

Release 7 Lock-Free Freelist Benchmark #1

   M
   N
   S
  L3U
L2U L2U
L1D L1D
L1I L1I
 P   P
L L L L total ops,mean ops/sec per thread,standard deviation,scalability
0 0 0 1 310134488,31013449,0,1.00
0 1 0 1 136313300,6815665,38365,0.22

0 1 0 1 136401284,6820064,50706,0.22
1 1 1 1 111134328,2778358,23851,0.09

0 0 1 1 334747444,16737372,2421,0.54
1 1 1 1 111105898,2777647,40399,0.09

正如我们所知，活锁可能发生，其中每个线程阻止其他线程进行。

我原来的——我相信现在是错误的——认为 CAS 正在干扰 CAS。我的意思是，如果它们同时发生，CAS 指令本身会与另一个 CAS 发生破坏性冲突。两者都会失败。 (Prolly 因为我一直在考虑以太网)。

这“显然”解释了结果——所有这些 CAS 指令同时运行，很少有机会在被破坏性中断之前完全执行。

想了想，现在觉得不可能了。 CAS 指令实际上没有故障模式。它会告诉您目的地是否等于比较对象。就这样。它不会回来说“哦，对不起，撞到了别人”。

破坏性干扰正在发生，但它发生在数据结构算法本身的更高级别。当我们从/向空闲列表推送或弹出时，我们实际上是在尝试交换。我们需要目的地稳定足够长的时间，以便我们可以读取它，做我们需要做的任何工作，然后发现它没有变化，这样我们就可以完成我们的推送/弹出。

如果其他线程保持 CASing，则目的地不稳定 - 它一直在变化 - 我们必须不断重试我们的操作。

但现在我很困惑。

我们看到的是单个线程执行大约 3000 万次 push/pop 操作。目标必须在这些操作之一的持续时间内保持稳定，操作才能成功，所以我们看到有 3000 万个“插槽”。如果我们有两个线程，那么我们可以拥有的最大理论性能是每个线程 1500 万次操作；每个线程使用一半的插槽。

现在让我们回到CAS。 CAS 没有故障模式。那么当另一个线程已经在 CASing 时，第二个线程尝试 CAS 时会发生什么？好吧，第二个线程将在数据结构级别失败，因为交换无法发生，因此它将重试交换。

但是现在想象一下我们有很多线程。开始 CAS 的第一个线程将成功(假设每个 CAS 花费的时间完全相同 - 不正确，但该假设不会改变任何基本的东西，因此可以推理)。所有其他人都会失败。

但是一旦第一个线程完成，下一个读取新目标值的线程就会成功执行他的 CAS(而所有其他线程，仍在执行它们的 CAS 或现在开始新的 CAS，将失败)。

那么为什么我们看不到完美的缩放呢？因为每个“插槽”都应该被使用!

我认为因此我不能正确理解 CAS。

阅读英特尔的架构软件开发人员手册，我发现如果所有数据都存在于缓存中(我感兴趣的情况)，缓存一致性协议(protocol)会处理 CAS。

Drepper 在他的白皮书中描述了 LL/SC 以及它如何使用 MESI。

在我看来，CAS 以类似的方式运行是合理的。

让我们考虑两个线程的情况。第一个线程开始它的 CAS。具有目的地的缓存行在其缓存中并标记为独占。

第二个线程开始CAS。第一个内核将其缓存行发送到第二个内核，并且两个内核都将该缓存行标记为共享。

第一个线程完成 CAS 并写入缓存行(写入总是发生在 x86/x64 上，即使比较结果为假；它只写入原始值)。

写入行为将缓存行标记为已修改；发生 RFO，导致第二个内核将其缓存行标记为无效。

第二个线程完成它的 CAS 并注意到它的缓存行无效......然后，怎么办？我发现很难相信指令在 CPU 内部循环直到它成功 - 虽然我想知道，因为 ARM 上的 LL/SC 要求你在你的程序集中执行这个循环。但是CAS指令知道destination的值发生了变化，所以它的比较结果是无效的。但是 CAS 不可能出错；它总是为比较返回真或假。但即使指令循环直到完成，我仍然期望完美的缩放。每个“插槽”仍应使用。

那么会发生什么？ CAS发生了什么？

我所看到的是，随着线程数的增加，完成的工作越来越少——所有可用的“插槽”肯定都没有被使用。有什么东西导致了这种情况。 CAS指令之间是破坏性干扰吗？还是大量的 RFO 占用了 CPU-> 北桥总线？

我非常感兴趣地注意到，同一物理核心上的两个线程可以完美地扩展。在这种情况下发生了一些特殊和不同的事情 - 不同物理内核上的两个线程也可以扩展一半。但这还不足以解释这一切。

Answer 1

您在这里看到的是在两个物理内核的 L1 缓存之间移动数据的成本。当仅使用一个内核时，数据位于该 L1 缓存中，每个 CAS 都以缓存中的数据全速运行。另一方面，当有两个内核处于事件状态时，每次一个内核成功写入数据时，都会使另一个缓存失效，这将导致数据需要在另一个内核之间进行复制，然后另一个内核才能执行任何操作(一般情况下，它会在CAS完成之前阻塞等待加载)。这比实际的 CAS 昂贵得多(它至少需要将数据向上移动到 L3 缓存，然后再向下移动到另一个 L1 缓存)，并导致您看到的速度变慢，因为数据最终是乒乓在两个 L1 缓存之间来回