CAS碰撞的CPU内部特征是什么？

Question

我正在尝试理解CAS在x86/x64上的低层次机制，我非常希望得到一些帮助/洞察力。

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

如果我看一个没有锁的自由职业者基准，没有指数退避，我看到随着线程数量的增加，性能快速平行线。

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指令本身就会与另一个CAS发生破坏性的碰撞。两者都会失败。(很明显是因为我在心里想着以太网)。

这“显然”解释了结果-所有的CAS指令同时运行，很少有机会充分执行之前，破坏性中断。

再想一想，我相信现在不可能是这样了。CAS指令实际上没有失败模式。它会告诉你目的地等于或不等于比较。就这样。它不会回来说“哦，对不起，撞到别人了”。

破坏性干扰正在发生，但在更高的层次上，在数据结构算法本身。当我们向自由职业者推送或弹出时，我们实际上是在尝试交换。我们需要目的地稳定足够长的时间，我们可以阅读它，做任何我们需要做的工作，然后找到它不变，这样我们就可以完成推送/弹出。

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

但现在我很困惑。

我们看到的是，一个线程执行大约3000万push/pop操作。目的地必须在其中一个操作期间是稳定的，这样操作才能成功，因此我们看到有3000万个“时隙”。如果我们有两个线程，那么我们可以拥有的最大理论性能是每个线程有1500万次操作；每个线程使用一半的插槽。

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

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

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

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

因此，我认为我对中科院的理解并不恰当。

阅读Intel的架构软件开发手册，我发现如果缓存中存在所有数据(我感兴趣的情况)，那么缓存一致性协议就会照顾CAS。

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

对我来说，中科院以类似的方式运作似乎是合理的。

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

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

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

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

第二个线程来完成它的CAS并注意到它的缓存行无效.然后呢？我很难相信指令在CPU内部循环，直到它成功--尽管我想知道，因为ARM上的LL/SC需要您在程序集中执行这个循环。但是CAS指令知道目的地的值已经改变，所以它的比较结果是无效的。但是CAS不可能出错；它总是为比较返回true或false。但是，即使指令一直循环到完成，我仍然期待完美的缩放。每个“插槽”仍应使用。

那会发生什么？中科院怎么了？

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

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

Answer 1

您在这里看到的是在两个物理核的L1缓存之间移动数据的成本。当只使用一个核心时，数据位于该L1缓存中，并且每个CAS都以全速运行，缓存中的数据。另一方面，当有两个核活动时，当一个核心成功地写入数据时，它将使另一个缓存无效，这将导致需要在缓存之间复制数据，然后另一个核心才能执行任何操作(通常，它会阻止等待负载等待CAS完成)。这比实际的CAS昂贵得多(它至少需要将数据移动到L3 cahce，然后返回到其他L1缓存)，并导致您所看到的减速，因为数据最终会在两个L1缓存之间来回切换。

Answer 2

根据CAS，我想你说的是锁

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

你似乎认为手术开始了，被打断了，继续着。相对于内存子系统，CAS是原子的。因此，它读取值，比较和写入在一次。一旦它收购了它，就不会有时间把它丢给另一个核心。那是怎么回事？它在指令执行过程中引发处理器锁信号，以便其他指令在存储器子系统上停止运行，直到证书再次可用为止。这就是为什么CMPXCHG指令上有一个锁前缀的原因。有关进一步的详细信息，您可以阅读锁描述。

因此，发生的大部分争论都发生在L1上，它试图获得cacheline的独占所有权，而这个信号几乎一直都在发出。如果L1已经具有cacheline (例如在同一核上有2个线程)，则唯一的争用是CAS本身的持续时间，不包括跨核的cacheline内存传输(因为它已经存在了)。而且速度快得多。

Answer 3

所以，我一直在想这些。

目前，我有两个不同的建议，如何处理CAS -‘缓存锁’和MESI。

这篇文章纯粹是关于缓存锁的。

缓存锁假设一个核心锁定给定的缓存行和试图在该缓存线上进行CAS的其他核心，但缓存仍被释放。

更重要的是，我也相信CAS总是在完成之前将其结果写回记忆。

根据这一理论，让我们看看基准，并尝试相互交换结果。

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

所以，首先是单线情况；

L L L L total ops,mean ops/sec per thread,standard deviation,scalability
0 0 0 1 310134488,31013449,0,1.00

这是我们最大的表现。每个“插槽”都是由单线程使用的。

现在，我们来到两个线程在同一核心；

L L L L total ops,mean ops/sec per thread,standard deviation,scalability
0 0 1 1 334747444,16737372,2421,0.54

当然，在这里，我们仍然有相同数量的“插槽”-- CAS所需的时间和时间一样长--但是我们看到它们在逻辑处理器之间分布均匀。这是有道理的；一个核心锁定缓存行，另一个暂停，第一个完成，第二个得到锁.他们轮流。目标仍然处于L1缓存中，缓存行处于修改状态；我们从来不需要从内存中重新读取目标，因此在这个意义上，我们就像一个线程的情况一样。

现在，我们来到两个不同的核心线；

L L L L total ops,mean ops/sec per thread,standard deviation,scalability
0 1 0 1 136401284,6820064,50706,0.22

这里我们看到了我们的第一个大减速。我们的最大理论标度是0.5，但我们在0.22。怎么会这样?嗯，每个线程都试图锁定相同的缓存行(当然，在自己的缓存中)，这很好--但问题是，当一个核心获得锁时，它将需要从内存中重新读取目标，因为它的缓存行将被修改其数据副本的另一个核心标记为无效。所以我们把速度降低到我们必须要做的记忆读取。

现在我们有四个线程，每个核心有两个线程。

L L L L total ops,mean ops/sec per thread,standard deviation,scalability
1 1 1 1 111105898,2777647,40399,0.09

在这里，我们可以看到，每个内核的操作系统总数实际上仅略少于一个线程，当然，扩展要糟糕得多，因为我们现在有四个线程，而不是两个线程。

在每个核心场景中的一个线程中，每个CAS以读取内存开始，因为另一个内核已使CASing核心缓存线失效。

在这种情况下，当核心完成CAS并释放缓存锁时，有三个线程在竞争锁，两个线程位于另一个内核上，一个线程位于同一核心上。因此，三分之二的时间我们需要在CAS开始时重新读取内存；三分之一的时间我们不需要。

所以我们应该更快一点。但事实上我们慢了一些。

0% memory re-reading gives 33,474,744.4 total ops per second (two threads, same core)
66% memory re-reading, gives 11,110,589.8 total ops per second (four threads, two per core)
100% memory re-reading, gives 13,640,128.4 total ops per second (two threads, one per core)

这让我很困惑。观察到的事实与理论不符。