1

我在 C 中实现了一个无锁链表，类似于 linux 内核 llist.h 中可用的内容。我正在使用“__sync_bool_compare_and_swap”的原子操作。

这是代码片段：

    struct llist_head {
    struct llist_node *head;
    struct llist_node *tail;
};

struct llist_node {
    struct llist_node *next;
    int mm_ref;
};

#define LLIST_HEAD_INIT(name)   { NULL, NULL }
#define LLIST_HEAD(name)    struct llist_head name = LLIST_HEAD_INIT(name)

void llist_insert_tail(struct llist_head *head, struct llist_node *new)
{
    volatile struct llist_node *last;
    new->mm_ref = 0;

    mb();
    new->next = NULL;
    do {
        last = head->tail;
        if (last)
            last->next = new;
    } while(!CAS(&(head->tail), last, new));
    CAS(&(head->head), NULL, new);
    mb();
}

struct llist_node *llist_remove_head(struct llist_head *head)
{
    volatile struct llist_node *first, *next;

    do {
        first = head->head;
        if (first != head->head)
            continue;
        if (first == NULL)
            return 0;
        next = first->next;
        printf("%s: tid=%lx first=%p next=%p first->next=%p\n", 
              __func__, pthread_self(), first, next, first->next);
    } while(!CAS(&(head->head), first, next));
    return first;
}

我有一个小型多线程测试程序，只有 1 个生产者线程将节点插入尾部列表，两个消费者线程从列表头部删除节点。插入/删除功能如下所示：

    void *list_insert(void *data)
{
    int i;
    printf("producer: id=%lx\n", pthread_self());

    for ( i = 0 ; i < 10 ; i++) {
        struct my_list_node *e = malloc(sizeof(struct my_list_node));
        e->a = SOMEID;
        llist_insert_tail(&global_list, &(e_array[i]->list));
        printf("new node p=%p next=%p\n", e_array[i], e_array[i]->list.next);
        ATOMIC_ADD64(&cn_added, 1);
    }
    ATOMIC_SUB(&cn_producer, 1);
    printf("Producer thread [%lx] exited! Still %d running...\n",pthread_self(), cn_producer);
    return 0;
}

void *list_remove(void *data)
{
    struct llist_node *pos = NULL;
    printf("consumer: id=%lx\n", pthread_self());
    while(cn_producer || !llist_empty(&global_list)) {
        struct my_list_node *e;
        pos = llist_remove_head(&global_list);
        if (pos) {
            e = llist_entry(pos, struct my_list_node, list);
            printf("tid=%lx removed %p\n", pthread_self(), pos);
            if (e->a != SOMEID) {
                printf("data wrong!!\n");
                exit(1);
            }
            ATOMIC_ADD64(&cn_deleted, 1);
        } else {
            sched_yield();
        }
    }
    printf("Consumer thread [%lx] exited %d\n", pthread_self(), cn_producer);
    return 0;
}

测试显示一致的失败，例如生产者插入了 10 个节点，但消费者只弹出了 1/2 或 3 个节点，我得到的典型输出之一如下所示：

consumer: id=7f4d469e8700
consumer: id=7f4d461e7700
producer: id=7f4d459e6700
new node p=0x7f4d400008c0 next=(nil)
new node p=0x7f4d400008e0 next=(nil)
new node p=0x7f4d40000900 next=(nil)
new node p=0x7f4d40000920 next=(nil)
new node p=0x7f4d40000940 next=(nil)
new node p=0x7f4d40000960 next=(nil)
new node p=0x7f4d40000980 next=(nil)
new node p=0x7f4d400009a0 next=(nil)
new node p=0x7f4d400009c0 next=(nil)
new node p=0x7f4d400009e0 next=(nil)
Producer thread [7f4d459e6700] exited! Still 0 running...
llist_remove_head: tid=7f4d469e8700 first=0x7f4d400008c0 next=(nil) first->next=(nil)
llist_remove_head: tid=7f4d469e8700 head=(nil)
tid=7f4d469e8700 removed 0x7f4d400008c0
Consumer thread [7f4d469e8700] exited 0
llist_remove_head: tid=7f4d461e7700 first=0x7f4d400008c0 next=(nil) first->next=(nil)
Consumer thread [7f4d461e7700] exited 0

可以看出，生产者线程首先退出，并切换到消费者线程，但是，这一行： llist_remove_head: tid=7f4d469e8700 first=0x7f4d400008c0 next=(nil) first->next=(nil) 表明一个消费者线程正在尝试删除第一个节点，但它的下一个指针指向NULL，这不应该是case 因为到目前为止，列表已完全填充（有 10 个节点）。因此存在竞争条件，由于这是无锁列表，因此假设会发生这种情况，但是我挠头，无法弄清楚哪种竞争条件会导致此输出。此实现类似于https://github.com/darkautism/lfqueue 但我无法弄清楚为什么我的版本不起作用。

4

1 回答 1

1

你可以试试lfqueue

使用简单，圆形设计无锁

    int *ret;

    lfqueue_t results;

    lfqueue_init(&results);

    /** Wrap This scope in multithread testing **/
    int_data = (int*) malloc(sizeof(int));
    assert(int_data != NULL);
    *int_data = i++;
    /*Enqueue*/
    while (lfqueue_enq(&results, int_data) != 1) ;

    /*Dequeue*/
    while ( (ret = lfqueue_deq(&results)) == NULL);

    // printf("%d\n", *(int*) ret );
    free(ret);
    /** End **/

    lfqueue_clear(&results);

有一个lfstack与同一个开发人员一起出现。

于 2018-07-25T02:33:08.193 回答