0%

Harris' Non-Blocking Linked-Lists

specification

  • ordered(ascending)
  • no duplicated key

features

  • non-blocking
  • linearizable
  • compare-and-swap based

仅使用一个cas的缺陷

  • insert

  • delete

对于只有一个insert或者一个delete的情况,没有问题会出现。

  • insert and delete

但是如果一个insert和一个delete同时进行,问题就会出现。删除30的时候,一个cas无法保证,也不能避免10和30之间的修改。

解决方法:用两个cas

基本思想

  • stage 1

    用一个cas mark将要被删除结点的next field(logically deleted);

  • stage 2

    另一个cas来进行删除结点(physically deleted)。

stage 1结束以后,list的结构保持不变,mark以后的结点,避免了新节点insert到该结点的后面。

algorithm

marked and unmarked

A node is marked if and only if its next field is marked.

这句话是关键:论文中的mark,实际上是mark了要被删除结点的next指针,而不是要被删除的结点本身。
我觉得从另一个视角来看,mark的效果是,不允许改变要被删除结点的后继结点。这点从避免前文提到的问题的角度来说,也应该是正确的理解。

get_marked_referenceget_unmarked_reference是以copy的形式传入reference,mark或者unmark以后的并不是reference本身。

数据结构

1
2
3
4
5
6
7
8
9
struct Node {
key_type key;
node *next;
}

struct list {
node *head;
node *tail;
}

满足这么几个要求:

  • left_node.key < search_key <= right_node.key
  • left_node and right_node are unmarked
  • right_node is immediate successor(直接后继) of left_node

有这么几个步骤:

  • 找到left_node和right_node
  • 检查是不是直接后继
    • 是,直接返回
  • 移除left_node and right_node之间的一个或多个marked结点

insert

  • 找到left_node和right_node
  • cas插入

delete

如前文解决方法中描述的,分两个阶段:

  • stage 1:
    • 找到left_node和right_node
    • logically delete
  • stage 2:
    • physically delete
      • cas删除
      • 或者search中删除

find

  • 找到left_node和right_node
  • right_node == search_key

Reference

  1. A Pragmatic Implementation of Non-Blocking Linked-lists, Timothy L. Harris.