CLock-FreeQueue内存管理

Question

为了提高我的 C 技能，我实现了 thread-safe 和 lock-free queue。该算法来自 Maurice Herlihy 和 Nir Shavit 的书 "The Art of Multiprocessor Programming" 的第 10.5 章，顺便说一句，这是一本很棒的书。

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

问题

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

释放内存的优雅方式是什么？由于我不重用节点，所以我应该不会出现 ABA 问题，对吧？还是您认为，重用节点并实施 ABA 问题的已知解决方案更容易？

lfq.h

header提供了一个简单的主要测试方法。

#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

测试queue的简单主要方法：

#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

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

In contrast, memory reclamation is one of the most challenging aspects of lock-free data structure design. Lock-free algorithms (also called non-blocking algorithms) guarantee that as long as some process continues to take steps, eventually some process will complete an operation. The main difficulty in performing memory reclamation for a lock-free data structure is that a process can be sleeping while holding a pointer to an object that is about to be freed. Thus, carelessly freeing an object can cause a sleeping process to access freed memory when it wakes up, crashing the program or producing subtle errors. Since nodes are not locked, processes must coordinate to let each other know which nodes are safe to reclaim, and which might still be accessed.

Cited from "Reclaiming Memory for Lock-Free Data Structures: There has to be a Better Way" by Trevor Brown, Institute of Science and Technology, Austria

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

Answer 2

这看起来像 Michael 和 Scott 队列。

无法释放节点，我不记得确切的原因（显然是因为它们仍然可以被引用 - 但具体位置和方式我忘记了）。它们只能放在空闲列表中。

我没有仔细检查你的实现是否正确，但我可以看到没有内存障碍，这意味着实现是错误的。

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

我写了两篇文章，可以帮助您入门。

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

CLock-FreeQueue内存管理

C Lock-Free Queue Memory Management

c

multithreading

memory-leaks

memory-management

lock-free

问题

lfq.h

lfq.c

main.c