只是好奇想知道哪些CPU架构支持比较和交换原语？
10个回答
13
Powerpc拥有更强大的原语可用: "lwarx"和"stwcx"
lwarx从内存加载一个值但记住位置。任何其他线程或CPU触及该位置将导致"stwcx"(条件存储指令)失败。
因此，lwarx / stwcx组合允许您实现原子递增/递减、比较和交换以及更强大的原子操作，如"原子递增循环缓冲区索引"。
- Jeff Koftinoff
12
5使用load-store-exclusive的另一个好处是它们不会遭受ABA问题的困扰，而该问题可能会使使用compare-exchange或compare-and-store的一些算法变得复杂。如果在load和store-exclusive之间有任何东西涉及到一个位置，即使该位置被重写为原始值，store-exclusive也会“知道”。 - supercat
1@mP：使用数据库类比，想象一下一个数据库，每次修改任何内容都会增加一个64位的更新计数器。Load-linked读取记录的状态以及更新计数器；store-conditional仅在更新计数器保持特定值时才写入记录。如果所有想要更新数据库的人都通过执行load-linked并非常快地执行store-conditional来进行操作，那么其中许多操作将成功，但由于对不感兴趣的记录进行的更新，有些操作将失败。load-linked和store-conditional之间的时间越长... - supercat
@supercat 溢出实际上对于无限处理来说是必要的，重要的是确保溢出在一个合理的时间内不会发生，以避免 ABA 问题。 - JAB
@JAB: 在某些情况下，与其处理溢出，不如设计事物的方式使得发生溢出所需的时间显著超过计数器相关的时间。即使一个64位计数器每秒递增10亿次，它也需要544年才能溢出; 我认为假设系统不会连续使用544年是合理的（波音因其发电机控制器在...而受到了一些嘲笑）。 - supercat
连续运行 248 天的唯一维护措施要求发电机每 120 天至少关闭一次，但是如果跳过了许多其他安全和维护程序，那么即使发电机可以运行一个月，也只有这种情况。虽然应该更好地记录发电机控制器必须每八个月重置一次的要求，但从工程角度来看，没有理由处理定时器溢出，除了指定需要定期重新启动之外，因为已经出于其他原因需要这样做了。 - supercat
显示剩余7条评论
10
很抱歉，这里有很多字母。:(
x86指令集中的几乎所有指令（除了所谓的字符串指令和可能还有其他一些指令）在unicore CPU的上下文中都是原子性的。这是因为按照x86架构的规定，在每个指令执行完成后CPU会检查是否有中断到达，并且永远不会在中途检查。因此，只有在执行两个连续指令之间的边界时才可以检测到中断请求并启动处理。由于这种行为对于单核和多核CPU都是普遍的，因此CPU在执行单个指令期间获取的所有内存引用都是被隔离的，并且无法与任何其他活动交错。但是，如果在unicore CPU的上下文中只有系统的一个单元执行对内存的访问，那么在multicore CPU的上下文中就有多个系统单元同时执行对内存的访问。在这种环境中，指令隔离是不足以保证一致性的，因为在同一时间内由不同CPU进行的内存访问可能会交错。因此，必须对数据更改协议应用附加的保护层。对于x86而言，这个层是lock前缀，它在系统总线上发起原子事务。
总结：如果您确信此指令访问的数据只能由一个核心访问，则使用无lock前缀的同步指令（如CMPXCHG、XADD、BTS等）是安全且成本较低的。如果您对此不确定，则应用lock前缀来提供安全性，以换取性能。
CPU支持硬件同步的两种主要方法：
- 基于原子事务的方法。
- 基于高速缓存一致性协议的方法。
没有银弹。这两种方法都有其优点和缺点。
基于原子事务的方法依赖于内存总线上特殊类型的事务支持。在这种事务期间，只有连接到总线的一个代理（CPU核心）有资格访问内存。结果是，在一方面，由总线所有者在原子事务期间进行的所有内存引用都保证作为单个不可中断的事务进行。另一方面，所有其他总线代理（CPU核心）都将被强制等待原子事务完成，以恢复访问内存的能力。无论他们想要访问哪些内存单元，即使他们想要访问在原子事务期间没有被总线所有者引用的内存区域。因此，广泛使用lock前缀指令会显著减慢系统的速度。另一方面，由于总线仲裁器根据轮廓调度为每个总线代理提供对总线的访问，因此保证了每个总线代理将相对公平地访问内存，并且所有代理都能够以相同的速度取得进展。此外，在原子事务的情况下，ABA问题成为其中的一部分，因为由于其本质，原子事务非常短（单个指令进行的少量内存引用），并且事务期间对内存所采取的所有操作仅依赖于内存区域的值，而不考虑在两个事务之间是否由其他人访问了该内存区域。基于原子事务的同步支持的一个很好的例子是x86架构，在其中lock前缀指令强制CPU以原子事务执行它们。
基于缓存一致性协议的方法依赖于内存行只能在某一时刻的一个L1缓存中缓存。缓存一致性系统中的内存访问协议类似于下面的操作序列：
- 当CPU A将内存行X存储在L1缓存中时，同时CPU B希望访问内存行X。(X-->CPU A L1)
- CPU B在总线上发出内存行X访问事务。(X-->CPU A L1)
- 所有总线代理(CPU核)都有一个所谓的嗅探代理，它监听总线上的所有事务，并检查事务请求的内存行是否存储在其所有者CPU的L1缓存中。因此，CPU A的嗅探代理检测到CPU A拥有CPU B请求的内存行。(X-->CPU A L1)
- CPU A暂停了CPU B发出的内存访问事务。(X-->CPU A L1)
- CPU A从其L1缓存中刷新CPU B请求的内存行。(X-->memory)
- CPU A恢复之前暂停的事务。(X-->memory)
- CPU B从内存中获取内存行X。(X-->CPU B L1)
由于该协议，CPU核总是访问内存中的实际数据，并且对内存的访问按严格顺序进行串行化，一次只能访问一个。基于缓存一致性协议的同步支持依赖于这样一个事实，即CPU可以轻松地检测到在两个时间点之间访问了特定的内存行。在第一次访问X行内存时，必须打开交易，CPU可以标记L1缓存中的内存行必须由嗅探代理控制。反过来，嗅探代理可以在缓存行刷新期间执行检查，以确定该行是否已标记为受控，并在控制行刷新时提高内部标志。结果，如果CPU在关闭事务的内存访问期间检查内部标志，它将知道受控内存行是否能够被其他人更改，并得出交易必须成功完成或必须视为失败的结论。这是LL\SC指令类实现的方式。与原子事务相比，这种方法更简单，并且在同步方面提供了更多的灵活性，因为可以基于此构建更多不同的同步原语。这种方法更具可伸缩性和效率，因为它不会阻塞其他系统部件对内存的访问。并且正如您所看到的，它解决了ABA问题，因为它基于内存区域访问检测的事实，而不是内存区域变化检测的值。任何参与正在进行的事务的内存区域的访问都将被视为交易失败。这既有好处也有坏处，因为特定算法可能仅关心内存区域的值，并且不考虑该位置是否被某个人在中间访问过，直到该访问改变了内存。在这种情况下，对内存值的读取将导致假负事务失败。此外，这种方法可能会导致控制流程的巨大性能降低，这些控制流程争夺同一内存行，并且通过这种方式相互阻止完成交易成功。这是一个非常重要的问题，因为在极端情况下，它可能会使系统处于死锁状态。缓存一致性协议基于同步支持通常用于RISC CPU，因为它简单而灵活。但必须注意的是，英特尔决定支持x86体
- ZarathustrA
1
哇，感谢您从微观角度进行的解释。 - Piyush Katariya
8
回答这个问题的另一种更简单的方法可能是列出不支持比较和交换（或可用于编写比较和交换的加载-链接/存储条件）的多处理器平台。
我知道的唯一一个是PARISC，它只有一个原子清除字指令。这可以用于构建互斥锁（前提是将字对齐到16字节边界）。这个架构上没有CAS（与x86、ia64、ppc、sparc、mips、s390等不同）。
- Peeter Joot
1
1旧版 ARM 是第二个没有完整 CAS（Compare-And-Swap）指令集的平台: http：//gcc.gnu.org/wiki/Atomic 上提到，ARM、PA（PA-RISC）、SH 都没有本地原子操作指令，但是 Linux 内核提供了对软件原子操作的支持。 - osgx
7
几个人评论/询问在x86/x64中是否需要“lock”前缀用于cmpxchg。对于多核机器来说，答案是肯定的。该指令对单核心机器没有锁就是完全原子性的。
我已经很久没有深入研究这些东西了，但我似乎记得这条指令在技术上是可重启的——如果它还没有产生任何副作用，它可以在中途停止指令以避免过长时间延迟中断处理。
我已经很久没有深入研究这些东西了，但我似乎记得这条指令在技术上是可重启的——如果它还没有产生任何副作用，它可以在中途停止指令以避免过长时间延迟中断处理。
- Doug65536
5
从ARMv6架构开始，ARM具有LDREX / STREX指令，可用于实现原子比较交换操作。
- Mike B
2
ARM的LDREX/STREX和PPC的LWARX/STWCX相似吗？ - oz10
我相信是这样的 - ARM技术参考手册对LDREX/STREX的解释相当复杂（而对于PowerPC，我正在使用Jeff Koftinoff的解释），因此细节上可能会有一些差异。 - Michael Burr
5
英特尔x86平台支持此功能。IBM在其《Solaris到Linux移植指南》中给出了以下示例:
bool_t My_CompareAndSwap(IN int *ptr, IN int old, IN int new)
{
unsigned char ret;
/* Note that sete sets a 'byte' not the word */
__asm__ __volatile__ (
" lock\n"
" cmpxchgl %2,%1\n"
" sete %0\n"
: "=q" (ret), "=m" (*ptr)
: "r" (new), "m" (*ptr), "a" (old)
: "memory");
return ret;
}
- mat_geek
1
1你能进一步解释一下吗？你为什么使用
lock 指令？cmpxchg 本身是原子性的吗？上面的代码只涉及一个内存位置，还是实现了内存栅栏并触发全局缓存一致性协议？ - axel224
为了完整列出清单，MIPS有Load Linked (ll)和Store Conditional (sc)指令，它们从内存中加载一个值，如果没有其他CPU访问该位置，则稍后有条件地存储。的确，您可以使用这些指令执行交换、递增和其他操作。但是缺点是，如果大量的CPU非常频繁地锁定，您将陷入活锁状态：条件存储将经常失败并需要另一个循环来重试，这将失败，以此类推。
如果认为这些情况很重要，软件mutex_lock实现可能会变得非常复杂，尝试实现指数回退。在我工作过的一个具有128个核心的系统中，它们确实是很重要的。
如果认为这些情况很重要，软件mutex_lock实现可能会变得非常复杂，尝试实现指数回退。在我工作过的一个具有128个核心的系统中，它们确实是很重要的。
- Denton Gentry
1
我同意，锁争用是在使用非锁定数据结构（通常使用CAS）时必须非常小心的事情。感谢您的提醒。 - oz10
3
比较并交换（Compare and swap）于1973年被添加到IBM大型机中。它（以及比较双精度和交换）仍然存在于IBM大型机上（以及更近期的多处理器函数，如PLO-执行锁定操作）。
- s.holton
1
2据说CAS（Compare And Swap）是发明该指令的人“查理”姓名的缩写。 - Krazy Glew
3
x86和Itanium都具有CMPXCHG（比较和交换）指令。
- Darksider
4
请注意，这条指令直到i486才被添加，对于老式硬件黑客可能需要特别留意。 - Brian Knoblauch
那是给年轻黑客的提示，不是吗？ - Peeter Joot
1CMPXCHG是原子操作吗，还是必须使用LOCK？ - axel22
CMPXCHG在单个CPU内对抢占是原子的，但添加LOCK后，它将针对跨多个CPU是原子的。这是因为“lock”实际上锁定了所有CPU的内存总线访问。http://heather.cs.ucdavis.edu/~matloff/50/PLN/lock.pdf - Peter Teoh
2
Sparc v9有一个cas指令。SPARC v9 架构手册在附录J中讨论了CAS指令的使用，特别是要看一下J.11和J.12的例子。
我认为指令的名字实际上是"casa"，因为它可以访问当前地址空间或备用地址空间。 "cas"是一个汇编宏，它访问当前ASI。
还有一篇关于developers.sun.com的文章，讨论了多年来Sparc处理器实现的各种原子指令，包括cas。
我认为指令的名字实际上是"casa"，因为它可以访问当前地址空间或备用地址空间。 "cas"是一个汇编宏，它访问当前ASI。
还有一篇关于developers.sun.com的文章，讨论了多年来Sparc处理器实现的各种原子指令，包括cas。
- Denton Gentry
3
这是什么？你能给一个链接吗？ - oz10
1请注意，x86具有双字CAS，而其他非SPARC CPU具有ll/cs - 两者都使用计数器解决ABA问题。单字CAS不允许使用计数器解决ABA问题，因此与其他体系结构相比，SPARC处于劣势。 - user82238
Sparc v8或Sparc v7怎么样？ - osgx
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接