C无锁队列内存管理

Question

为了提高我的C技能，我实现了一个线程安全且无锁的队列。该算法来自Maurice Herlihy和Nir Shavit的“多处理器编程艺术”一书的第10.5章，顺便说一下，这本书是一本很好的书。

到目前为止，一切正常，但我需要帮助解决以下问题：

问题

行free(first)在lfq_deq()方法中被注释掉，因为如果队列被多个dequeuers使用它会导致段错误。如果线程T1和T2出队并且T1释放节点而T2仍然使用它，则T2将产生段错误。

什么是释放这种记忆的优雅方式？由于我不重用节点，我不应该有ABA问题，对吧？或者您认为，重用节点并为ABA问题实施已知解决方案更容易？

lfq.h

标题提供了一种简单的主要测试方法。

#pragma once
#include <stdlib.h>

typedef struct Node {
    void* data;
    struct Node* next;
} lfq_node_t;

typedef struct Queue {
    lfq_node_t* head;
    lfq_node_t* tail;
} lfq_t;

lfq_t* lfq_new();
void lfq_free(lfq_t* q);
void lfq_enq(lfq_t* q, void* data);
void* lfq_deq(lfq_t* q);

lfq.c

#include "lfq.h"
#include <pthread.h>
#include <stdio.h>

#define CAS(a, b, c) __sync_bool_compare_and_swap(a, b, c)

lfq_t* lfq_new() {
    lfq_t* q = malloc(sizeof(*q));
    lfq_node_t* sentinel = malloc(sizeof(*sentinel));
    sentinel->data = sentinel->next = NULL;
    q->head = q->tail = sentinel;

    return q;
}

void lfq_free(lfq_t* q) {
    lfq_node_t *next, *node = q->head;
    while (node != NULL) {
        next = node->next;
        free(node);
        node = next;
    }
    free(q);
}

void lfq_enq(lfq_t* q, void* data) {
    lfq_node_t *node, *last, *next;

    node = malloc(sizeof(*node));
    node->data = data;
    node->next = NULL;

    while (1) {
        last = q->tail;
        next = last->next;
        if (last == q->tail) {
            if (next == NULL) {
                if (CAS(&(last->next), next, node)) {
                    CAS(&(q->tail), last, node);
                    return;
                }
            } else {
                CAS(&(q->tail), last, next);
            }
        }
    }
}

void* lfq_deq(lfq_t* q) {
    lfq_node_t *first, *last, *next;
    while (1) {
        first = q->head;
        last = q->tail;
        next = first->next;

        if (first == q->head) {
            if (first == last) {
                if (next == NULL) return NULL;
                CAS(&(q->tail), last, next);
            } else {
                void* data = first->next->data;
                if (CAS(&(q->head), first, next)) {
                    // free(first);
                    return data;
                }
            }
        }
    }
}

main.c中

测试队列的简单主要方法：

#include "lfq.h"
#include <stdio.h>

int main() {
    int values[] = {1, 2, 3, 4, 5};
    lfq_t* q = lfq_new();
    for (int i = 0; i < 5; ++i) {
        printf("ENQ %i\n", values[i]);
        lfq_enq(q, &values[i]);
    }
    for (int i = 0; i < 5; ++i) printf("DEQ %i\n", *(int*)lfq_deq(q));
    lfq_free(q);
    return 0;
}

Answer 1

这看起来像迈克尔和斯科特队列。

节点无法释放，我不记得究竟为什么随便（显然因为它们仍然可以引用 - 但确切地说我忘记了在哪里和如何）。它们只能放在空闲列表中。

我没有密切关注你的实现的正确性，但我可以看到没有内存障碍，这意味着实现是错误的。

您需要发现并阅读并理解内存障碍，然后使用它们。

我写过一篇文章，可以帮助你入门。

https://www.liblfds.org/mediawiki/index.php?title=Article:Memory_Barriers_%28part_1%29

https://www.liblfds.org/mediawiki/index.php?title=Article:Memory_Barriers_%28part_2%29

Answer 2

正如Peter Cordes在评论中指出的那样，我刚刚发现了内存回收问题：

相比之下，内存回收是无锁数据结构设计中最具挑战性的方面之一。无锁算法（也称为非阻塞算法）保证只要某个进程继续采取步骤，最终某个进程将完成一个操作。为无锁数据结构执行内存回收的主要困难是进程可以在保持指向即将被释放的对象的指针的同时休眠。因此，不小心释放对象可能导致休眠进程在唤醒，崩溃程序或产生细微错误时访问释放的内存。由于节点未被锁定，因此进程必须协调以让对方知道哪些节点可以安全回收，哪些节点仍然可以被访问。

引自奥地利科学技术研究所Trevor Brown的“为无锁数据结构回收记忆：必须有更好的方法”

here可以找到一个很好的答案（与堆栈相关但基本相同）。