美文网首页
CAS操作引起链表删除的问题

CAS操作引起链表删除的问题

作者: 祝方泽 | 来源:发表于2018-09-17 11:27 被阅读0次

如果要删除p->next节点,一种简单的方式是使用原子操作更改p->next值。但是,如果其它线程正在修改p->next节点,会导致链表进入错误状态,如下图:

list_cas_delete_problem.png
如果一个线程删除节点B,同时另一个线程通过节点B,删除节点C,随后将C delete掉,整个链表进入错误状态。
维基百科上Harris's solution给出了另一种错误状态:
https://en.wikipedia.org/wiki/Non-blocking_linked_list

相关文章

  • CAS操作引起链表删除的问题

    如果要删除p->next节点,一种简单的方式是使用原子操作更改p->next值。但是,如果其它线程正在修改p->n...

  • 删除链表的倒数第N个节点

    链表类的操作首先要知道链表的数据类型结构、链表的插入和删除以及链表的求表长的问题。 19.删除链表的倒数的第N个节...

  • 单链表的删除操作

    单链表的删除操作

  • 线性表的链式存储-单链表

    单链表操作 [x] 单链表的创建(尾插法、头插法) [x] 单链表的查找操作 [x] 单链表的删除操作 [x] 单...

  • 链表

    文章结构 链表的定义 链表的插入和删除操作 链表的特性 常见的链表结构 自定义链表 链表的经典操作 使用链表实现L...

  • [Leetcode] [Tag 链表] Python 刷题总结

    链表的结构 链表的题不难,多在于考察对链表操作的熟练度,问题常常在于链表是单向的,需要对链表的删除、反转、获取第n...

  • 1.数据结构-链表问题

    链表相关问题 删除节点 链表去重 有环链表 反转链表 链表排序 链表相交 其他问题 面试题 02.03. 删除中间...

  • Leetcode总结 -- 链表

    目录 链表的基本操作 改/遍历:while(?) 查: 返回倒数K个节点 增/删除:反转链表,删除链表中的重复节点...

  • 删除链表中重复的元素解法分析

    链表的操作非常常见,也是面试中经常会被问道的问题。对于链表重复元素的删除,有两个变体,现在总结如下。链表代码如下:...

  • 数据结构之链表及其栈和队列的实现

    链表的基本操作 定义 从链表头部插入元素 从链表头部删除元素 从链表尾部插入元素 从中间插入和删除结点 栈和对列的...

网友评论

      本文标题:CAS操作引起链表删除的问题

      本文链接:https://www.haomeiwen.com/subject/pcvknftx.html