11 concurrency assembly multithreading x86-64 lock-free
我试图理解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碰撞,如果它们同时发生的话.两者都会失败.(推荐,因为我在脑海中思考以太网).
这"显然"解释了结果 - 所有CAS指令同时运行,很少有机会在被破坏性中断之前完全执行.
考虑到这一点后,我相信现在情况并非如此.CAS指令实际上并不具有故障模式.它会告诉你目的地等于或不等于比较.就这样.它没有回来说"哦,对不起,碰到别人".
破坏性干扰正在发生,但它发生在数据结构算法本身的更高层次.当我们从空闲列表推送或弹出时,我们实际上正在尝试交换.我们需要目标稳定足够长的时间以便我们可以阅读它,做我们需要做的任何工作,然后找到它不变,这样我们就可以完成我们的推/弹.
如果其他线程保持CASing,目标不稳定 - 它会不断变化 - 我们不得不重试我们的操作.
但现在我很困惑.
我们看到的是单个线程执行大约3000万次推/弹操作.目的地必须在其中一个操作期间保持稳定,以使操作成功,因此我们看到有3000万个"插槽".如果我们有两个线程,那么我们可以拥有的最大理论性能是每个线程1500万个操作; 每个线程使用一半的插槽.
现在让我们回到CAS.CAS没有故障模式.那么当另一个线程已经进行CASing时,第二个线程尝试CAS时会发生什么？好吧,第二个线程将在数据结构级别失败,因为交换不会发生,因此它将重试交换.
但现在想象我们有很多线程.开始CAS的第一个线程将成功(假设每个CAS花费完全相同的时间 - 不是真的,但是这个假设不会改变任何基本的,所以可以推理).所有其他人都会失败.
但是,一旦第一个线程完成,读取新目标值的下一个线程将使其CAS成功(并且所有其他线程,仍在执行其CAS或现在开始新的CAS,将失败).
那么为什么我们看不到完美的缩放？因为每个"槽"都应该被使用!
因此我认为我不理解CAS.
阅读英特尔架构软件开发人员手册,我发现如果所有数据都存在于缓存中(我感兴趣的情况),缓存一致性协议负责CAS.
Drepper在他的白皮书中描述了LL/SC及其如何使用MESI.
CAS以类似方式运作似乎是合理的.
让我们考虑两个线程案例.第一个线程开始它的CAS.具有目标的高速缓存行位于其高速缓存中并标记为独占.
第二个线程开始CAS.第一个核心将其缓存线路发送到第二个核心,两个核心都将该缓存线标记为共享.
第一个线程完成CAS并写入高速缓存行(写入始终发生在x86/x64上,即使比较为假;它只是写入原始值).
写入操作将缓存行标记为已修改; 发生RFO,导致第二个核心将其缓存行标记为无效.
第二个线程来完成它的CAS并注意到它的缓存行无效......然后,什么？我发现很难相信指令在CPU内部循环直到成功 - 虽然我不知道,因为ARM上的LL/SC要求你在程序集中执行此循环.但CAS指令知道目标的值已更改,因此其比较结果无效.但是CAS没有错误; 它总是为比较返回true或false.但即使指令循环完成,我仍然希望完美缩放.仍应使用每个"槽".
那会发生什么？什么是与CAS发生了什么？
我所看到的是,随着线程数量的增加,工作量越来越少 - 所有可用的"插槽"肯定都没有被使用.有什么事情导致这种情况.是CAS指令之间的破坏性干扰吗？或者是大量的RFO占用CPU->北桥总线？
我非常感兴趣地注意到,同一物理核心上的两个线程完美地扩展.在这种情况下会发生一些特殊和不同的事情 - 在不同的物理内核上的两个线程也会缩小一半.但这还不足以解释一切.
您在这里看到的是在两个物理核心的 L1 缓存之间移动数据的成本。当仅使用一个核心时，数据位于 L1 缓存中，并且每个 CAS 以缓存中的数据全速运行。另一方面，当有两个核心处于活动状态时，每次一个核心成功写入数据时，都会使另一个缓存失效，这将导致在另一个核心可以执行任何操作之前需要在缓存之间复制数据（一般会在CAS完成之前阻塞等待加载）。这比实际的 CAS 昂贵得多（它至少需要将数据移动到 L3 缓存，然后返回到另一个 L1 缓存），并且会导致您看到的速度减慢，因为数据最终会出现乒乓球效应在两个 L1 缓存之间来回