使用自由列表的多线程无锁定双链表

Question

我想要一个并发数据结构，其工作方式类似于单链列表，并且仅需要append和remove_iterator操作。最后，一个线程将iterate所有节点。从我的研究中，我得到了一个implementation，它具有带有单链接列表的append，remove_value和search_value操作。它基于Harris' algorithm。

问题是，在哈里斯算法中，remove_value仅标记逻辑删除的节点，而没有实际删除它。 search_value实际上完成了删除逻辑上已删除的节点的工作。但是由于我的用例没有search操作。我保留了很长的列表，其中包含许多被逻辑删除的节点。对于多线程来说，这样做只是效率不高，因为删除节点的所有工作都放在单个线程的iterate操作中。

我想知道是否还有其他适合我需要的实现。任何建议表示赞赏。

如果不是，我想知道我是否可以使用带有无锁堆栈实现的free-list来为这种特殊情况实现某些功能。在这种情况下，append操作将成为pop空闲列表，将值放入节点，如果为空则追加到我们的列表。 remove_iterator操作将标记为已逻辑删除节点，并且push节点为指向空闲列表的指针。

我认为无锁堆栈相当容易实现。我可以在线使用一些implementations。

---

记住一些代码。

struct node_t {
    node_t *next;
    int deleted;
    val_t val;
};
struct list_t {
    node_t *head;
};
struct fl_node_t {
    node_t *padding_1;
    int padding_2;
    fl_node_t *next; // assume sizeof(val_t) >= sizeof(fl_node_t*);
};

struct free_list_t {
    fl_node_t * head;
};

void append(val_t val) {
    fl_node_t *fl_head;
    fl_node_t *fl_next;
    node_t *head;
    node_t *new_node
    /* Try insert to one of the node in free-list */
    if (free_list.head) {
        do {
            fl_head = free_list.head;
            next = fl_head->next;
        } while(!CAS(&free_list.head, fl_head, fl_next)); 
        if (fl_head) {
           fl_head->node->val = val; 
           return;
        }
    }
    /* Append to head */
    new_node = malloc(sizeof(node_t));
    new_node.val = val;
    new_node.deleted = 0;
    do {
        head = list.head;
        new_node.next = head;
    } while(!CAS(&list.head, head, new_node));

}

void remove(node_t *node) {
    fl_node_t *fl_node;
    fl_node_t *fl_head;

    /* Mark logically deleted */
    node->deleted = 1;
    fl_node = (fl_node_t*) node;

    /* Add to free-list */
    do {
        fl_head = free_list.head;
        fl_node->next =fl_head;
    } while(!CAS(&free_list.head, fl_head, fl_node)); 
}

---

Answer 1

我在github上找到了gavra0的实现。通过添加自由列表的修改（使用无锁堆栈实现），我得到了一些有效的代码。

存储库为https://github.com/buszk/ConcLinkedList。实现是在link分支的此dev中。

Answer 2

关于释放锁定和等待释放的数据结构，而不是尝试重新发明轮子或修复某些问题，并花了很长时间尝试证明它是正确的，如果可能的话，请使用一个经过验证的现有实现。

无锁实现很难正确实现，很难证明正确。在实践中，出于性能原因，我们不得不使用它们，因为它们可以反复移动，然后有一天爆炸。从这里改编的实现取得了很大的成功]

http://www.1024cores.net

他还参考了其他库，并提供了对并发编程的深入了解。非常值得一读。