为什么比较和交换 (CAS) 算法是无锁同步的好选择？
Why is compare-and-swap (CAS) algorithm a good choice for lock-free synchronization?
CAS 属于读取-修改-写入 (RMW) 系列，这是一组允许您以原子方式执行复杂事务的算法。
具体来说，维基百科说
CAS is used to implement synchronization primitives like semaphores and mutexes, as well as more sophisticated lock-free and wait-free algorithms. [...] CAS can implement more of these algorithms than atomic read, write, or fetch-and-add, and assuming a fairly large amount of memory, [...] it can implement all of them.
https://en.wikipedia.org/wiki/Compare-and-swap#Overview
所以 CAS 算法似乎是其类别的 "one size fits all" 产品。为什么？其他 RMW 算法缺少什么？如果 CAS 是最好的工具，那么其他算法有什么用？
CAS 属于 class 个名为 "consensus objects" 的对象，每个对象都有一个共识编号；给定共识对象可以解决共识问题的最大线程数。
共识问题是这样的：对于一定数量的线程 n，提出一些值 p 并决定其中一个建议值 d 使得 n 线程同意 d。
CAS是最"powerful"的共识对象，因为它的共识数是无限的。也就是说，CAS可以用来解决理论上无限多个线程之间的共识问题。 它甚至以 wait-free 的方式进行。
这不能用原子寄存器、test-and-set、fetch-add、堆栈来完成，因为它们都有有限的共识数。这些共识数字有证据，但那是另一回事...
所有这一切的意义在于，可以证明存在 wait-free 使用共识的 n 个线程的对象实现共识数至少为 n 的对象。 CAS 特别强大，因为您可以使用它为任意数量的线程实现 wait-free 对象。
至于为什么其他RMW操作有用？多处理中的一些问题并不真正涉及解决任意数量线程的共识问题。例如，可以使用功能较弱的 RMW 操作来解决互斥，例如 test-and-set（简单的 TAS 锁）、fetch-add（票证锁）或原子交换（CLH 锁）。
维基百科共识 (computer_science) 部分有关共享内存共识的更多信息：In_shared-memory_systems
此外，我强烈推荐 Herlihy 和 Shavit 的 多处理器编程艺术 (WorldCat) 中有一整章是关于共识和通用构造的。
CAS 属于读取-修改-写入 (RMW) 系列，这是一组允许您以原子方式执行复杂事务的算法。
具体来说，维基百科说
CAS is used to implement synchronization primitives like semaphores and mutexes, as well as more sophisticated lock-free and wait-free algorithms. [...] CAS can implement more of these algorithms than atomic read, write, or fetch-and-add, and assuming a fairly large amount of memory, [...] it can implement all of them.
https://en.wikipedia.org/wiki/Compare-and-swap#Overview
所以 CAS 算法似乎是其类别的 "one size fits all" 产品。为什么？其他 RMW 算法缺少什么？如果 CAS 是最好的工具，那么其他算法有什么用？
CAS 属于 class 个名为 "consensus objects" 的对象，每个对象都有一个共识编号；给定共识对象可以解决共识问题的最大线程数。
共识问题是这样的：对于一定数量的线程 n，提出一些值 p 并决定其中一个建议值 d 使得 n 线程同意 d。
CAS是最"powerful"的共识对象，因为它的共识数是无限的。也就是说，CAS可以用来解决理论上无限多个线程之间的共识问题。 它甚至以 wait-free 的方式进行。
这不能用原子寄存器、test-and-set、fetch-add、堆栈来完成，因为它们都有有限的共识数。这些共识数字有证据，但那是另一回事...
所有这一切的意义在于，可以证明存在 wait-free 使用共识的 n 个线程的对象实现共识数至少为 n 的对象。 CAS 特别强大，因为您可以使用它为任意数量的线程实现 wait-free 对象。
至于为什么其他RMW操作有用？多处理中的一些问题并不真正涉及解决任意数量线程的共识问题。例如，可以使用功能较弱的 RMW 操作来解决互斥，例如 test-and-set（简单的 TAS 锁）、fetch-add（票证锁）或原子交换（CLH 锁）。
维基百科共识 (computer_science) 部分有关共享内存共识的更多信息：In_shared-memory_systems
此外，我强烈推荐 Herlihy 和 Shavit 的 多处理器编程艺术 (WorldCat) 中有一整章是关于共识和通用构造的。