并发链表

Question

我试图在c ++中设计一个允许并发访问的链表.显然,对于该列表使用单个锁是非常低效的,因为可以并行更新不相交的区域.现在除了每个节点存储一个锁之外,还有什么选择？

另外,在这种情况下,非阻塞版本会更好吗？任何相关链接,任何人？

编辑:感谢您的回复.我想补充一些事情:

1. 如何为每个M节点存储N个锁而不是1:1锁:节点比？有些线程会等待,但这是一种权衡.你怎么看？
2. 如果我打算在这个链表中找到一些节点,看起来需要锁定所有互斥锁.这是一个问题,因为锁定和解锁所有互斥锁都很耗时.有没有人有更好的选择？
3. 我对非阻塞算法持开放态度.但是如何在不使用汇编的情况下在旧的C++中使用CAS？我听说gcc有一些__sync属性做类似的工作,但不确定.
4. 使用非阻塞方法,如何在链表上进行查找？

Answer 1

可以使用互锁函数实现非阻塞单链表：

互锁单链表

我认为没有互锁比较和交换 (CAS) 的非阻塞双向链表是不可能实现的，这不是广泛可用的。