为什么比较交换（CAS）算法是无锁同步的一个好选择？

Question

9

CAS属于读取-修改-写入(RMW)算法族，这是一组允许您原子性地执行复杂事务的算法。

具体来说，维基百科表示：

CAS用于实现同步原语，如信号量和互斥锁，以及更复杂的无锁和无等待算法。[...] CAS可以实现比原子读取、写入或获取-添加更多的这些算法，并且假设有相当大量的内存，[...]它可以实现所有这些算法。

看起来CAS算法是其类别中的“一刀切”产品。为什么会这样？其他RMW算法缺少什么？如果CAS是最好的工具，那么其他算法是什么？

- Ignorant

1

CAS通常在处理器本身上实现，因此处理器保证原子性。这使得它相当高效，但也更容易，因为程序员不必关心它是如何实现的，只要处理器做好了工作就可以了。 - Willem Van Onsem

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eric · Accepted Answer

CAS属于一类被称为“共识对象”的物体，每个共识对象都有共识数。即可解决共识问题的给定共识对象所能支持的最大线程数。

共识问题如下：对于一些线程数量n，提议某个值p并决定其中一个提议值d，使得n个线程都同意d。

CAS是最“强大”的共识对象，因为它的共识数是无限的。也就是说，CAS可用于在理论上无限数量的线程之间解决共识问题。甚至以等待自由(wait-free)的方式实现它。

原子寄存器、测试和设置(test-and-set)、加法获取(fetch-add)、栈这些工具都有有限的共识数，因此无法完成该任务。虽然这些共识数字有证明，但这又是另一回事...

所有这些的重要性在于可以证明存在一个等待自由的对象实现，使用共识对象的共识数至少为n。CAS特别强大，因为您可以使用它来实现任意数量线程的等待自由对象。

关于为什么其他RMW操作是有用的？在多进程中，一些问题并不涉及解决任意数量线程的共识问题。例如，互斥可以使用比test-and-set（一个简单的TAS锁），fetch-add（票据锁）或atomic swap（CLH锁）更弱的RMW操作来解决。

更多关于共享内存共识的信息，请参考维基百科“共识（计算机科学）”部分：In_shared-memory_systems 此外，在Herlihy和Shavit的多处理器编程的艺术（WorldCat）中，有关共识和通用构造的整章内容，强烈推荐阅读。