开发者社区> ali清英> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

并发数据结构-1.5 链表

简介:
+关注继续查看

原文链接译文链接,译者:huavben,校对:周可人

考虑支持插入,删除和查找操作的并发数据结构实现。如果这些操作只处理键值(译者注:而不处理具体值),这样的数据结构会是一个集合。如果一个数据值与每一个键关联起来,我们就得到了一部数据字典。由于他们都是密切相关的数据结构,一个并发的集合通常能够经过适当修改来实现一部字典。在接下来的三个小节中,我们将专注于利用linked lists,hash tables,和trees这三种不同的数据结构来实现集合。

试想我们使用一个linked list去实现集合。除了锁住整个linked list来避免并发操作以外,最普遍的实现基于锁的linked lists的方式是hand-over-hand-locking(有时也叫lock coupling)。在这种方式下,每个节点都有一个关联的锁。一个正在遍历Linked list的线程只有在获取到了下一个节点的锁时才会释放上一个节点的锁,这样就避免了overtaking现象:可能导致线程未察觉节点被其他线程删除。这种方式减小了锁的粒度,但是由于插入和删除操作在链表的不同位置可能相互阻碍,而限制了并发性.

一种解决这个问题的途径就是设计出一个无锁的 linked lists。实现出这样一个无锁的有序linked lists的困难在于要确保在插入或者删除操作期间,相邻的节点仍然是有效的,即他们仍然存在于列表当中并且是相邻的。正如1.4节中图1.6展现的一样,设计出这样一个无锁的链表不是一件轻松的活。

Concurrent Data Structure Linked-list

图1.6:基于CAS的链表操作是复杂的。在图中的两个例子(这两个例子都滥用了CAS操作)中,P从链表中将b元素删除。在上面的例子中,Q尝试将c元素插入到链表中,在下面的例子中,Q元素尝试将c元素从链表中删除。圆圈标记的位置代表了CAS操作的目标地址,叉号标记的链接代表在CAS成功之前链接。

第一个基于CAS的无锁链表是Valois 提出来的,他在每个普通节点之前使用了一个特殊的辅助节点来防止在图1.6中发生的非期望现象。Valois的算法在结合了Michael和Scott的内存管理方案之后是正确的,但是这种解决方式并不实用。Harris提出了一种使用了特殊的,带有被原子访问的“删除”标记位的无锁链表,用来标记该节点是否已经被删除,然而此方案只有在垃圾收集环境下才是适用的。Michael 通过修改Harris的算法使其兼容内存回收方法,弥补了这个缺陷。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
数据结构-跳表
跳表这种数据结构对你来说,可能会比较陌生,因为一般的数据结构和算法书籍里都不怎么会讲。但是它确实是一种各方面性能都比较优秀的动态数据结构,可以支持快速地插入、删除、查找操作,写起来也不复杂,甚至可以替代红黑树(Red-black tree)。 Redis 中的有序集合(Sorted Set)就是用跳表来实现的。如果你有一定基础,应该知道红黑树也可以实现快速地插入、删除和查找操作。那 Redis 为什么会选择用跳表来实现有序集合呢? 为什么不用红黑树呢?学完今天的内容,你就知道答案了。
15 0
数据结构——单向链表
数据结构——单向链表
35 0
数据结构——链表
数据结构——链表
101 0
【数据结构5】树
树的定义 树的遍历 前序遍历 中序遍历 后序遍历 二叉搜索树 树的定义 typedef struct node { int data; struct node * left, *right, *parent;...
673 0
数据结构:双向链表
原创:转载请注明 在前面介绍了单项链表, http://blog.itpub.net/7728585/viewspace-2125007/ 在实际的应用中双向链表应用也是非常多的,因为我本生是一名DBA,我知道的在数据库中双向链表应用非常广泛,在双向链表中 我们多了一个*prior 指向前一个节点,那么这样如果我们已知一个节点的指针要求得上一个节点的指针就变得非常简单了, 时间复杂度由O(n)下降到一个常数O(1),关于这个实现函数我觉得没必要写了太简单了。
553 0
数据结构之二叉树
二叉树的定义: 二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。     二叉树(BinaryTree)是n(n≥0)个结点的有限集,它或者是空集(n=0),或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。    
1165 0
+关注
ali清英
方腾飞,花名清英,英文名kiral,并发编程网创始人,支付宝技术专家,《Java并发编程的艺术》作者。
614
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载