4

在 x86 上,像这样的原子 RMW 指令lock add dword [rdi], 1是使用现代 CPU 上的缓存锁定来实现的。因此,高速缓存行在指令期间被锁定。这是通过在读取值时获取行 EXCLUSIVE/MODIFIED 状态来完成的,并且 CPU 在指令完成之前不会响应来自其他 CPU 的 MESI 请求。

有两种并发进度条件,阻塞和非阻塞。原子 RMW 指令是非阻塞的。CPU 硬件在持有缓存锁时永远不会休眠或做其他事情(中断发生在原子 RMW 之前或之后,而不是期间),释放缓存行之前的步数有一个有限(且很小)的上限.

非阻塞算法在理论计算机科学中可以分为 3 种风格:

  1. 等待免费:所有线程将在有限的步骤中取得进展。

  2. 无锁:至少一个线程将在有限的步骤中取得进展

  3. 无阻塞:如果没有争用,线程将在有限的步数内取得进展

x86 提供什么样的保证?

我想它至少是无锁的;如果存在争用,至少有一个 CPU 会取得进展。

但是 x86 是否可以免费等待原子指令?是否每个 CPU 都能保证在有限数量的步骤中取得进展,或者可能是一个或多个 CPU 处于饥饿状态并可能无限期延迟?

那么当多个内核在同一个缓存行上进行原子操作时会发生什么?

4

2 回答 2

3

考虑一个更一般的问题:如果有多个活动的硬件线程,x86 是否保证每个线程都向前推进而不管其他线程做什么?您提出的问题似乎专门针对每个线程同时对重叠内存位置执行原子指令的情况。如果答案是肯定的,那么 x86 可以说是“免等待”。(该术语通常仅用于描述线程同步算法,但无论如何。)

我认为从架构或其实现的角度定义“向前进展”的含义很重要。我不喜欢在定义中使用“步骤”一词,因为不清楚什么是步骤,什么不是步骤。相反,我将使用以下定义:当一个活动的硬件线程完成程序顺序中的下一条动态指令时,它会向前推进,方法是退出它或在出现错误情况时切换到异常处理程序。如果每个活动的硬件线程可以在有限的时间内向前推进,而不管其他线程做什么,也不管每个线程正在执行什么指令,只要它们不会导致线程变为非活动状态,那么 x86 就是等待 -自由的。

是否每个 CPU 都能保证在有限数量的步骤中取得进展,或者可能是一个或多个 CPU 处于饥饿状态并可能无限期延迟?

您可能会想,如果有两个内核不断尝试获取对同一位置的原子 RMW 访问权,其中一个总是成功而另一个总是失败,在尝试执行相同的原子指令而没有取得任何进展时会卡住,因为这是程序顺序中的下一条指令。

这实际上是计算机体系结构中的一个传统问题。我想考虑更一般的问题的原因是,除了获取锁之外,多个硬件线程或代理之间可能存在许多争用点。想想你说的:

CPU 硬件在持有缓存锁时永远不会休眠或做其他事情(中断发生在原子 RMW 之前或之后,而不是期间),在释放缓存行之前的步数有一个有限(且很小)的上限.
...
我想它至少是无锁的;如果存在争用,至少有一个 CPU 会取得进展。

英特尔和 AMD 从未声明“在释放高速缓存行之前的步数有一个有限的上限”。这种推理几乎可以应用于指令执行的任何阶段。如果在私有缓存中丢失了获取指令,那么在获取指令的步数上是否存在有限的上限?从共享缓存中读取值的步骤数是否存在有限上限?使用超线程,几乎在执行任何类型指令的每个阶段都存在争用的可能性。你可以对他们每个人都问同样的问题。原子访问争用并不特殊。人们可以问其他问题,例如核心是否有可能任意进入睡眠状态并且永远不会醒来。

从根本上说,如果没有在架构级别通过设计确保每个核心始终能够向前推进,那么拥有多个核心是没有意义的,只要它处于活动状态(根据上面的定义)。否则,无法充分利用实施。每个实际的 ISA 都必须提供最小前向进度保证,即任何操作都需要有限的时间才能完成,并且在全局(或多代理)操作顺序中之前有有限数量的其他操作。一些 ISA,例如 RISC-V,确实明确说明了这一点。

在许多示例中,英特尔在 SDM 手册和许多其他文档中明确指出,共享结构的设计是为了保证公平性,这比最小的前进进度更强大。(但是,出于性能或其他原因,这可能并不总是准确的,因为某些类型的请求可能总是具有更高或最高的优先级。也许最好说通常保证公平并且通常保证前进进度,或者类似的东西。)这些例子包括以下(从我的头顶):

  • 在 Nehalem 之前的多核处理器和多核 Atom 品牌的处理器上,L2 超级队列(包括 L2 控制器)被设计为(通常)公平并保证与之交互的所有代理的进度。
  • 前端总线(在具有 FSB 的系统上)和 APIC 总线(在具有单独 APIC 总线的系统上)都被设计为公平的。
  • 同一内核上的硬件线程之间的大多数仲裁点都设计为公平的。一个例外是 uop 调度程序,在具有统一 RS 的微架构上,或 uop 调度程序,在具有分布式 RS 的微架构上,使用先就绪伪 FIFO 算法。
  • 在使用交叉互连的处理器上,L3 全局队列保证公平性。
  • 在具有环形互连的处理器上,在某些环形停止处保证公平性,而在其他环形停止处只保证向前进展。

因此,如果两个内核尝试获取对同一位置的原子 RMW 访问,则保证原子指令通过每个内核的管道和内存层次结构,并且每个内核的读锁请求最终将得到服务。所以,是的,根据上面的定义,x86 是无等待的。不过值得注意的是,大多数或所有英特尔处理器都很少出现导致所有或部分处理器无限期挂起的错误。

一个有趣的考虑是,是否保证内核的进程不会因为中断的连续处理而无限期地阻塞。我认为这主要取决于中断处理程序的设计,因此系统软件必须保证这一点。

于 2020-07-30T22:25:53.990 回答
-1

当多个线程碰巧锁定同一个缓存行时,它们的执行是序列化的。这称为错误共享导致的写入争用

写原则源于此。与读取相反,写入不能同时执行。

原子读-修改-写指令本身的执行时间是固定的,不依赖于争用高速缓存行的线程数。因此,在 x86 上,它们是无等待的 population-oblivious

锁定争用高速缓存行所需时间的上限与高速缓存行所经历的争用程度成正比。

来自英特尔社区

在某些架构中,未选择先执行的操作将被停止(然后由硬件重试直到成功),而在其他架构中,它们将“失败”(基于软件的重试)。例如,在 Intel 处理器中,如果目标内存位置繁忙,硬件将重试锁定的 ADD 指令,而必须检查锁定的“比较和交换”操作是否成功(因此软件必须注意到失败并重试操作)。

由于缓存行锁定会不断重试,最终所有原子的读-修改-写操作都会成功(操作是指令加上硬件为锁定缓存行所做的重试)。
所以的,每个 CPU 都保证在有限数量的步骤中取得进展,并且 x86 上的原子读-修改-写操作作为一个整体是无等待有界的

通过相同的逻辑,x86 存储操作是无等待有界的,x86 存储指令是无等待人口不经意的,而 x86 加载始终是免等待人口不经意的。

虽然,正如有人建议的那样,一个 ucode 错误可能会导致锁永远保持不变,但我们在描述算法的风格时不考虑外部因素,而只考虑逻辑本身。


缓存行锁获取不公平。

选择一个线程来获取锁的概率与它与释放锁的线程的接近程度成正比。因此,同一个内核上的线程比共享 L2 缓存的线程更有可能获得锁,后者比共享 L3 缓存的线程更有可能。然后,较短 QPI/UPI/NUMA 节点路径上的线程比其他线程具有优势,依此类推。

这也适用于软件锁(自旋锁),因为当发布存储时,它以相同的方式传播。


我在英特尔 Q4'17 台式机 CPU 上运行了一个基准测试,确认了上述所有内容。
当连续lock xadd遍历相同的内存位置时......

  • 在 10 秒内,在不同内核上运行的 5 个线程中,最快的线程lock xadd比最慢的线程多 2.5 倍,在不同的双向超线程上运行的 10 个线程中,它比最慢的线程多 3 倍
  • 3 亿次,平均越来越小数量的lock xadds 花费越来越多的时间,5 个线程在不同内核上运行最多 1.1ms,10 个线程在不同双向超线程上运行最多 193ms

不同流程的运行之间的差异很大。

于 2020-07-11T11:40:50.827 回答