我正在尝试了解 x86/x64 上 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
正如我们所知，可能会发生活锁，其中每个线程都会阻止其他线程前进。
我最初的想法（现在我认为是错误的）是 CAS 干扰了 CAS。我的意思是，如果 CAS 指令同时发生，那么它们本身就会与另一个 CAS 发生破坏性冲突。两者都会失败。 （可能是因为我在心里想着以太网）。
这“显然”解释了结果 - 所有这些 CAS 指令同时运行，很少有机会在被破坏性中断之前完全执行。
再想一想，我现在认为不可能是这样。 CAS 指令实际上没有故障模式。它会告诉您目的地等于或不等于比较数。就这样。它不会回来说“哦，对不起，撞到了别人”。
破坏性干扰正在发生，但它发生在更高的层次上，发生在数据结构算法本身中。当我们从空闲列表中推送或弹出时，我们实际上是在尝试交换。我们需要目的地稳定足够长的时间，以便我们可以读取它，做我们需要做的任何工作，然后发现它不变，这样我们就可以完成我们的推送/弹出。
如果其他线程保持 CASing，则目标不稳定 - 它不断变化 - 并且我们必须不断重试我们的操作。
但现在我很困惑。
我们看到，单个线程执行大约 3000 万次入栈/出栈操作。目的地必须在其中一项操作期间保持稳定，操作才能成功，因此我们看到有 3000 万个“槽位”。如果我们有两个线程，那么我们可以拥有的最大理论性能是每个线程 1500 万次操作；每个线程使用一半的插槽。
现在让我们回到 CAS。 CAS没有故障模式。那么，当另一个线程已经在进行 CAS 操作而第二个线程尝试进行 CAS 操作时，会发生什么情况呢？好吧，第二个线程将在数据结构级别失败，因为交换无法发生，因此它将重试交换。
但现在想象我们有很多线程。开始 CAS 的第一个线程将成功（假设每个 CAS 花费完全相同的时间 - 不正确，但该假设不会改变任何基本内容，因此可以推理）。所有其他人都会失败。
但是，一旦第一个线程完成，下一个读取新目标值的线程将使其 CAS 成功（而所有其他线程，仍在执行其 CAS 或现在开始新的 CAS，将失败）。
那么为什么我们没有看到完美的缩放呢？因为每个“槽”都应该被使用！
因此我认为我没有正确理解 CAS。
阅读 Intel 的架构软件开发人员手册，我发现如果所有数据都存在于缓存中（我感兴趣的情况），则缓存一致性协议会负责 CAS。
Drepper 在他的白皮书中描述了 LL/SC 以及它如何使用 MESI 工作。
在我看来，CAS 以类似的方式运作是合理的。
让我们考虑两个线程的情况。第一个线程开始其 CAS。具有目标的缓存行位于其缓存中并标记为独占。
第二个线程开始 CAS。第一个核心将其缓存行发送到第二个核心，并且两个核心都将该缓存行标记为共享。
第一个线程完成 CAS 并写入缓存行（写入始终发生在 x86/x64 上，即使比较为 false；它只写入原始值）。
写入行为将缓存行标记为已修改；发生 RFO，导致第二个核心将其缓存行标记为无效。
第二个线程完成其 CAS 并注意到其缓存行无效......然后，怎么办？我发现很难相信该指令在 CPU 内部循环直到它成功 - 尽管我想知道，因为 ARM 上的 LL/SC 需要you在你的程序集中执行此循环。但CAS指令知道destination的值已经改变，所以它的比较结果无效。但 CAS 不可能出错；它总是返回 true 或 false 进行比较。但即使指令确实循环直到完成，我仍然期望完美的缩放。每个“插槽”仍应使用。
那么会发生什么呢？什么is发生在 CAS 上吗？
我所看到的是，随着线程数的增加，完成的工作越来越少 - 所有可用的“插槽”肯定都没有被使用。有什么原因导致了这种情况。 CAS指令之间是否存在破坏性干扰？或者是大量RFO占用了CPU->北桥总线？
我非常感兴趣地注意到，同一物理核心上的两个线程完美地扩展。在这种情况下，会发生一些特殊且不同的情况 - 单独物理核心上的两个线程也会缩放一半。但这还不足以解释这一切。
