可以锁定(等待)免费双向链表吗？

Question

用C#标签提出这个问题,但是如果可能的话,应该可以使用任何语言.

是否可以使用Interlocked操作实现双向链表以提供无等待锁定？我想插入,添加和删除,并清除,而不是等待.

Answer 1

是的,这是可能的,这是我在C++中实现类似STL的无锁双链表.

它需要64位比较和交换才能在没有ABA问题的情况下运行.此列表仅可用于无锁内存管理器.

查看第12页的基准测试.随着争用的增加,列表的性能与线程数呈线性关系.该算法支持不相交访问的并行性,因此随着列表大小的增加,争用可能会减少.

Answer 2

一个简单的谷歌搜索将揭示许多无锁双链表.

但是,它们基于原子CAS(比较和交换).

我不知道C#中的操作是多么原子,但根据这个网站

C#操作只能保证读取和写入32位字段的原子性.没有提到CAS.

C#(.NET)绝对有一个原子比较和交换.它被称为Interlocked.CompareExchange.http://msdn.microsoft.com/en-us/library/system.threading.interlocked.compareexchange.aspx (13认同)