无锁队列

Question

此外，我正在做一个c实现，目前有队列的结构：

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;
 }

但不确定如何继续，有队列和出队功能......

• 代码怎么样？

Answer 1

您的伪代码可以（并且很可能确实）受到ABA problem的影响，因为只检查指针，而不是附带的唯一标记，您将找到在这方面使用的this paper以及作为无锁队列的一般指南实施，有其陷阱。

在处理无锁编程时，阅读Herb Sutter的作品也是一个好主意，因为他对所需的内容，为什么需要及其潜在的弱点提供了很好的，有见地的解释（尽管要注意他的一些旧版出版物/文章）在哪里发现包含一些隐藏/未发现的问题）。

Answer 2

还有最近的提升'谈论这个主题：https://github.com/boostcon/2011_presentations/raw/master/wed/lockfree_2011_slides.pdf

Answer 3

（暂时离开这里，但请看编辑。）

你知道C中无锁队列的实现吗？

我最近写了无锁队列（http://www.ideone.com/l2QRp）。我实际上无法保证它正常工作，但我找不到任何错误，我已经在几个单线程程序中使用它没有任何问题，所以它没有太明显的错误。

琐碎的用法示例：

queue_t queue;
int val = 42;
queue_init(&queue,sizeof val);
queue_put(&queue,&val);
val = 0; 
queue_pop(&queue,&val);
printf("%i\n",val); // 42
queue_destroy(&queue);

Edit:

正如@Alexey Kukanov指出的那样，如果tmp被弹出，释放，再次分配，并且在检查null和交换之间再次放置，则queue_pop可能会失败：

    if(!tmp->next) return errno = ENODATA;
    /* can fail here */
    } while(!sync_swap(q->head,tmp,tmp->next));

我还不确定如何解决这个问题，但是一旦我搞清楚，我（希望）会更新这个。现在，无视这一点。

Answer 4

您可以尝试使用本机构建的库。 lfqueue

例如

int* int_data;
lfqueue_t my_queue;

if (lfqueue_init(&my_queue) == -1)
    return -1;

/** Wrap This scope in other threads **/
int_data = (int*) malloc(sizeof(int));
assert(int_data != NULL);
*int_data = i++;
/*Enqueue*/
 while (lfqueue_enq(&my_queue, int_data) == -1) {
    printf("ENQ Full ?\n");
}

/** Wrap This scope in other threads **/
/*Dequeue*/
while  ( (int_data = lfqueue_deq(&my_queue)) == NULL) {
    printf("DEQ EMPTY ..\n");
}

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

lfqueue_destroy(&my_queue);