Aks*_*235 6 c++ multithreading compare-and-swap
作为多线程和互斥体的新手,我正在浏览维基百科.我遇到了这个部分:
通过创建链接列表,CAS可用于实现任何共享数据结构的无等待互斥,其中每个节点表示要执行的所需操作.然后,在插入新节点期间,CAS用于更改链表中的指针.只有一个过程可以在CAS中成功; 尝试同时添加节点的所有其他进程将不得不再次尝试.然后,每个进程可以保留数据结构的本地副本,并且在遍历链接列表时,可以从其本地副本上的列表执行每个操作.
现在我理解CAS的基本概念,其中我们基本上使用原子操作将值与预定值进行比较,如果匹配则我们交换它们.但我无法遵循"所需操作链表"的含义？为什么所有流程都遵循相同的链接操作列表？
链表保存对共享数据结构的操作.
例如,如果我有一个堆栈,它将被推送和弹出操作.链表将是伪共享堆栈上的一组推送和弹出.共享该堆栈的每个线程实际上都有一个本地副本,并且为了进入当前的共享状态,它将遍历链接的操作列表,并将每个操作应用于其堆栈的本地副本.当它到达链表的末尾时,其本地副本保持当前状态(当然,它随时会变得陈旧).
在传统模型中,每个push和pop都会有一些锁定.每个线程都会等待获取锁定,然后执行推送或弹出,然后释放锁定.
在此模型中,每个线程都有一个堆栈的本地快照,它通过应用链接列表中的操作与其他线程的堆栈视图保持同步.当它想要操纵堆栈时,它根本不会尝试直接操作它.相反,它只是将其推送或弹出操作添加到链接列表,因此所有其他线程可以/将看到该操作,并且它们都可以保持同步.然后,当然,它应用链接列表中的操作,并且当(例如)有弹出时,它检查哪个线程要求弹出.它使用弹出的项目,当且仅当它是请求此特定弹出的线程时.