c++ - 比较和交换如何用于任何共享数据结构的无等待互斥？

Question

作为多线程和互斥体的新手，我正在浏览维基百科以了解初学者。我遇到了这部分:

CAS can be used to achieve wait-free mutual exclusion for any shared data structure by creating a linked list where each node represents the desired operation to be performed. CAS is then used to change the pointers in the linked list during the insertion of a new node. Only one process can be successful in its CAS; all other processes attempting to add a node at the same time will have to try again. Each process can then keep a local copy of the data structure, and upon traversing the linked list, can perform each operation from the list on its local copy.

现在我了解了 CAS 的基本概念，我们基本上使用原子操作将一个值与预定值进行比较，如果匹配则交换它们。但是我无法理解这里的“所需操作的链接列表”是什么意思？为什么所有进程都遵循相同的操作链表？

Answer 1

链表保存对共享数据结构的操作。

例如，如果我有一个堆栈，它将通过压入和弹出来操作。链接列表将是伪共享堆栈上的一组推送和弹出。共享该堆栈的每个线程实际上都有一个本地拷贝，为了到达当前共享状态，它将遍历操作链表，并按顺序将每个操作应用于堆栈的本地拷贝。当它到达链表的末尾时，它的本地拷贝保持当前状态(当然，它随时可能变得陈旧)。

在传统模型中，每次按下和弹出都会有某种锁定。每个线程都将等待获取锁，然后执行推送或弹出操作，然后释放锁。

在这个模型中，每个线程都有一个堆栈的本地快照，它通过应用链表中的操作与其他线程的堆栈 View 保持同步。当它想要操纵堆栈时，它根本不会尝试直接操纵它。相反，它只是将其推送或弹出操作添加到链表中，因此所有其他线程都可以/将会看到该操作，并且它们都可以保持同步。然后，当然，它应用链接列表中的操作，并且当(例如)有弹出时，它检查哪个线程请求弹出。当且仅当它是请求此特定弹出的线程时，它才使用弹出的项目。