考虑一个更一般的问题:如果有多个活动的硬件线程,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 是无等待的。不过值得注意的是,大多数或所有英特尔处理器都很少出现导致所有或部分处理器无限期挂起的错误。
一个有趣的考虑是,是否保证内核的进程不会因为中断的连续处理而无限期地阻塞。我认为这主要取决于中断处理程序的设计,因此系统软件必须保证这一点。