无锁队列 [英] Lock-free queue

问题描述

另外，我做了 C 执行情况和目前拥有的队列的结构：

Also I am doing a c implementation and currently have the structure of the queue:

typedef struct queueelem {
    queuedata_t data;
    struct queueelem *next;
} queueelem_t;

typedef struct queue {
    int capacity;
    int size;
    queueelem_t *head;
    queueelem_t *tail;
} queue_t;

queue_t *
queue_init(int capacity)
{
    queue_t *q = (queue_t *) malloc(sizeof(queue_t));
    q->head = q->tail = NULL;
    q->size = 0;
    q->capacity = capacity;
    return q;
}

int CompareAndExchange (void **a, void *comparand,void *new) {
    int success = 0;
    pthread_mutex_lock(&CE_MUTEX);
    if ((*a) != comparand) {
       (*a) = new;
       //return     TRUE
       success = 1;
    }
    pthread_mutex_unlock(&CE_MUTEX);     
   //return     FALSE
    return success;
 }

但不知道如何继续下去，队列和出列功能...

But not sure How to continue, with queue and dequeue functions...

• 将如何code是什么样子？

推荐答案

您伪code能（而且很可能不会）从的 ABA问题，因为只有指针被选中，而不是伴随独特的印记，你会发现的在这方面的作为一般指导使用本文以锁定无队列实现，其缺陷。

Your pseudo-code can (and most likely does) suffer from the ABA problem, as only the pointer is checked, and not an accompanying unique stamp, you'll find this paper of use in that regard and as a general guide to lock-free queue implementation, with its pitfalls.

在与锁自由编程处理，它也是一个不错的主意，在香草萨特的作品读了起来，因为他提供了良好的，有见地的解释什么要求，为什么需要它和它潜在的弱点（不过要小心他的一些旧的刊物/论文中，发现含有一些隐藏/不可预见的问题）。

When dealing with lock free programing, its also a good idea to read up on Herb Sutter's works, as He gives good, insightful explanations to whats required, why its required and its potential weak points (though beware that some of his older publications/articles where found to contain some hidden/unforseen problems).

这篇关于无锁队列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！