考虑更普遍的问题:如果有多个活动硬件线程,x86 是否保证每个线程都能向前推进,而不管其他线程做什么?您提出的问题似乎专门针对每个线程同时对重叠内存位置执行原子指令的情况。如果答案是肯定的,那么 x86 可谓“免等待”。 (该术语通常仅用于描述线程同步算法,但无论如何。)
我认为从架构或其实现的角度定义“向前进展”的含义很重要。我不喜欢在定义中使用术语“步骤”,因为不清楚什么是步骤,什么不是步骤。相反,我将使用以下定义:当活动硬件线程按程序顺序完成下一个动态指令时,通过将其退出或在出现错误情况下切换到异常处理程序来向前推进。如果每个活动的硬件线程都可以在有限的时间内取得进展,而不管其他线程做什么,也不管每个线程正在执行什么指令,只要它们不会导致线程变得不活动,那么 x86 就会等待 -自由的。 (请注意,中断处理程序不是在硬件线程上执行的程序的一部分,因此处理中断并不意味着线程正在向前推进。)
每个 CPU 都能保证在有限的步骤中取得进展吗
或者可能是一个或多个 CPU 资源不足并且可能
可能无限期推迟?
您可能会想到,如果有两个核心不断尝试获取对同一位置的原子 RMW 访问,则其中一个总是会成功,而另一个总是会失败,因为尝试执行相同的原子指令而没有取得任何进展,因此陷入困境它是程序顺序中的下一条指令。
这实际上是计算机体系结构中的一个传统问题。我想考虑更普遍的问题的原因是,除了获取锁之外,多个硬件线程或代理之间还存在许多可能的争用点。考虑一下你所说的:
CPU 硬件在保持状态时永远不会休眠或做其他事情
缓存锁(中断发生在原子 RMW 之前或之后,而不是
期间),数量有一个有限(且很小)的上限
释放缓存行之前的步骤。
...
我猜它至少是无锁的;如果存在争用,则至少有一个 CPU 会取得进展。
Intel和AMD从未声明过“释放缓存线之前的步数有一个有限的上限”。这种推理几乎可以应用于指令执行的任何阶段。如果私有缓存中的提取丢失,提取指令的步骤数是否存在有限上限?从共享缓存读取值的步骤数是否存在有限上限?对于超线程,几乎在执行任何类型指令的每个阶段都存在潜在的争用。你可以对他们每个人问同样的问题。原子访问争用并不特殊。人们还可以提出其他问题,例如核心是否有可能任意进入睡眠状态并且永远不会醒来。
从根本上讲,如果不通过设计在架构级别确保每个核心只要处于活动状态(根据上面的定义)就始终能够取得进展,那么拥有多个核心是没有意义的。否则,无法充分利用实施。每个实际的 ISA 都必须提供最小的前向进度保证,即任何操作都需要有限的时间来完成,并且在全局(或多代理)操作顺序中先于有限数量的其他操作。一些 ISA(例如 RISC-V)确实明确声明了这一点。
有很多例子,英特尔在 SDM 手册和许多其他文档中明确指出,共享结构的设计是为了保证公平性,这是比最小前进进度更强大的受让人。 (出于性能或其他原因,这可能并不总是准确的,因为某些类型的请求可能总是具有更高或最高的优先级。也许更好的说法是通常保证公平性并且总体上保证前进,或者类似的东西。)这些例子包括以下内容(来自我的脑海):
- 在 Nehalem 之前的多核处理器和多核 Atom 品牌处理器上,L2 超级队列(包括 L2 控制器)被设计为(通常)公平,并保证与其交互的所有代理的进度。
- 前端总线(在具有 FSB 的系统上)和 APIC 总线(在具有单独 APIC 总线的系统上)都被设计为公平的。
- 同一内核上的硬件线程之间的大多数仲裁点都被设计为公平的。一个例外是具有统一 RS 的微架构上的 uop 调度程序,或者具有分布式 RS 的微架构上的 uop 调度程序,它们使用先就绪伪 FIFO 算法。
- 在使用交叉互连的处理器上,L3 全局队列的公平性得到保证。
- 在具有环互连的处理器上,在某些环停止处保证公平性,而在其他环停止处仅保证前进进度。
因此,如果两个核心尝试获取对同一位置的原子 RMW 访问,则保证原子指令能够通过每个核心的管道和内存层次结构,并且每个核心的读锁定请求最终将轮到得到服务。所以,是的,根据上面的定义,x86 是免等待的。但值得注意的是,大多数或所有英特尔处理器都很少出现导致所有或部分处理器无限期挂起的错误。
一个有趣的考虑是,是否可以保证核心的进程不会因连续处理中断而无限期地受阻。我认为这主要取决于中断处理程序的设计,因此系统软件必须保证这一点。