多线程无锁双向链表使用free-list

Question

我想要一个像单链表一样工作的并发数据结构，只需要 append 和 remove_iterator 操作。最后，一个线程将 iterate 所有节点。根据我的研究，我得到了 implementation that has append, remove_value and search_value operations with singly-linked lists. It is based on Harris' algorithm.

问题是在Harris的算法中，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 的实现。通过添加一个空闲列表（使用无锁堆栈实现）进行修改，我得到了一些工作代码。

存储库位于 dev 分支中的 https://github.com/buszk/ConcLinkedList. And the implementation is in this link。

Answer 2

当谈到无锁和无等待数据结构时，与其尝试重新发明轮子或修复某些东西并花费很长时间试图证明它是正确的，尽可能使用经过验证的现有实现.

众所周知，无锁实现很难正确，也很难证明是正确的。在一个 CPU 架构上是正确的，在另一个架构上可能是错误的。

在实践中，出于性能原因我们不得不使用它们的地方，它们可以一直使用，然后有一天会崩溃。我们从这里改编的实现取得了很好的成功

http://www.1024cores.net

他还引用了其他库，并提供了对并发编程的深刻见解。值得一读。

多线程无锁双向链表使用free-list

Multi-threaded lock-free doubly linked list using free-list

c

multithreading

atomic

lock-free

compare-and-swap