使用C#标签询问这个问题,但如果可能的话,它应该可以在任何语言中使用。
是否有可能使用互锁操作来实现双向链表以提供无等待锁定?我想要插入、添加和删除,并且不需要等待就可以清除。
发布于 2009-05-11 20:06:04
一个简单的谷歌搜索将显示许多无锁的双向链表文件。
但是,它们是基于原子CAS (比较和交换)的。
我不知道C#中的操作有多原子,但根据这个网站
http://www.albahari.com/threading/part4.aspx
对于读写32位字段,C#操作只能保证是原子的。没有提到CAS。
发布于 2011-07-07 04:04:07
是的,这是可能的,这是我在C++中实现的一个类似STL的Lock-Free Doubly-Linked List。
Sample code that spawns threads to randomly perform ops on a list
它需要64位比较和交换才能正常运行,而不会出现ABA问题。此列表只有在lock-free memory manager的作用下才有可能。
查看benchmarks on page 12。随着争用的增加,列表的性能随着线程数量的增加而线性扩展。该算法支持不相交访问的并行性,因此随着列表大小的增加,争用可以减少。
发布于 2009-05-29 11:08:33
这是一个描述无锁双向链表的paper。
我们提出了一种高效而实用的并发双队列的无锁实现,它是不相交的-并行访问的,并使用现代计算机系统中可用的原子原语。先前已知的deques的无锁算法或者基于不可用的原子同步原语,仅实现功能的子集,或者不被设计用于分离访问。我们的算法是基于双向链表的,并且只需要单字比较和交换...
Ross Bencina有一些非常好的链接,我刚刚找到了大量关于"Some notes on lock-free and wait-free algorithms“的论文和源代码示例。
https://stackoverflow.com/questions/849786
复制相似问题