c# - 是否可以使用无锁(等待)双向链表？

Question

用C#标签问这个问题，但如果可以的话，用任何语言都应该可以。

是否可以使用互锁操作实现双向链表以提供无等待锁定？我希望无需等待即可插入、添加和删除以及清除。

Answer 1

是的，这是可能的，这是我对类似 STL 的实现 Lock-Free Doubly-Linked List在 C++ 中。

Sample code that spawns threads to randomly perform ops on a list

它需要 64 位比较和交换才能在没有 ABA 问题的情况下运行。此列表仅可能是因为 lock-free memory manager .

查看 benchmarks on page 12 .随着竞争的增加，列表的性能与线程数成线性关系。该算法支持不相交访问的并行性，因此随着列表大小的增加，争用可以减少。