首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >一个锁(等待)自由的双向链表可能吗?

问一个锁(等待)自由的双向链表可能吗?
EN

Stack Overflow用户
提问于 2009-05-11 19:57:41
回答 9查看 10.1K关注 0票数 10

使用C#标签询问这个问题,但如果可能的话,它应该可以在任何语言中使用。

是否有可能使用互锁操作来实现双向链表以提供无等待锁定?我想要插入、添加和删除,并且不需要等待就可以清除。

EN

回答 9

Stack Overflow用户

回答已采纳

发布于 2009-05-11 20:06:04

一个简单的谷歌搜索将显示许多无锁的双向链表文件。

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

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

http://www.albahari.com/threading/part4.aspx

对于读写32位字段,C#操作只能保证是原子的。没有提到CAS。

票数 11
EN

Stack Overflow用户

发布于 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。随着争用的增加,列表的性能随着线程数量的增加而线性扩展。该算法支持不相交访问的并行性,因此随着列表大小的增加,争用可以减少。

票数 16
EN

Stack Overflow用户

发布于 2009-05-29 11:08:33

这是一个描述无锁双向链表的paper。

我们提出了一种高效而实用的并发双队列的无锁实现,它是不相交的-并行访问的,并使用现代计算机系统中可用的原子原语。先前已知的deques的无锁算法或者基于不可用的原子同步原语,仅实现功能的子集,或者不被设计用于分离访问。我们的算法是基于双向链表的,并且只需要单字比较和交换...

Ross Bencina有一些非常好的链接,我刚刚找到了大量关于"Some notes on lock-free and wait-free algorithms“的论文和源代码示例。

票数 4
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/849786

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档