3

在此处输入图像描述 在此处输入图像描述

我也在做一个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;
 }

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

  • 代码会是什么样子？
4

5 回答 5

2

您的伪代码可能（并且很可能确实）受到ABA 问题的影响，因为只检查了指针，而不是随附的唯一标记，您会发现在这方面使用的这篇论文并作为锁定的一般指南-自由队列实现，有它的陷阱。

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

于 2011-05-22T16:05:00.240 回答
2

还有最近关于这个主题的 boost'con 讨论： https ://github.com/boostcon/2011_presentations/raw/master/wed/lockfree_2011_slides.pdf

于 2011-05-22T18:46:21.287 回答
2

前段时间，我找到了一个很好的解决这个问题的方法。我相信它是迄今为止发现的最小的。

存储库有一个示例，说明如何使用它创建 N 个线程（读取器和写入器），然后共享一个席位。

我在测试示例上做了一些基准测试，得到了以下结果（以百万次操作/秒为单位）：

按缓冲区大小

吞吐量

按线程数

在此处输入图像描述

请注意线程数如何不改变吞吐量。

我认为这是这个问题的最终解决方案。它的工作原理令人难以置信的快速和简单。即使有数百个线程和单个位置的队列。它可以用作线程之间的管道，在队列内分配空间。

该存储库有一些用 C# 和 pascal 编写的早期版本。我正在努力使一些东西更加完善，以展示其真正的力量。

我希望你们中的一些人可以验证这项工作或提供一些想法。或者至少，你能打破它吗？

于 2020-01-06T19:33:49.113 回答
0

（暂时将其留在这里，但请参阅编辑。）

你知道 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);

编辑：

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

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

我还不确定如何解决这个问题，但我会（希望）在我弄清楚后更新它。暂时先不管这个。

于 2011-05-22T18:08:32.613 回答
0

你可以试试这个库，它是用 c native 构建的。队列

例如

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);
于 2018-09-04T13:39:26.680 回答