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

Question

CAS属于读-修改-写（RMW）系列，这是一组算法，可让您自动执行复杂的事务。

具体来说，维基百科说

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

因此，似乎CAS算法就是其同类产品的“一刀切”。为什么？其他RMW算法缺少什么？如果CAS是最好的工具，那么其他算法还有什么用呢？

Answer 1

CAS属于一类称为“共识对象”的对象，每个对象都有一个共识编号。给定共识对象可以解决共识问题的最大线程数。

共识问题是这样的：对于一定数量的线程n，请提出一些值，p然后确定所提议的值之一，以d使n线程同意d。

CAS是最“强大”的共识对象，因为它的共识数是无限的。也就是说，CAS可用于解决理论上无限数量的线程之间的共识问题。它甚至以无等待的方式进行操作。

这不能用原子寄存器，测试设置，获取添加，堆栈来完成，因为它们都具有有限的共识数。这些共识数字有证据，但这是另一回事了。

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

至于为什么其他RMW操作有用？多处理中的某些问题实际上并不涉及解决任意数量线程的共识问题。例如，可以使用功能较弱的RMW操作（例如测试设置（简单的TAS锁定），访存（票证锁定）或原子交换（CLH锁定））解决互斥问题。

有关共享内存共识的更多信息，请参见 Wikipedia Consensus（computer_science）部分：In_shared-memory_systems

另外，我强烈建议在Herlihy和Shavit的“多处理器编程的艺术（WorldCat）”中有一章完整地讨论共识和通用结构。