无锁队列

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

但不确定如何使用队列和出队函数继续...

• 代码会是什么样子？

- edgarmtze

---

Compare&Swap和Fetch&Add是CPU的扩展函数，可能已经内置于您的编译器/库中。 - Jonas Bötel

我正在进行CompareAndExchange的实现，请查看我的更新。 - edgarmtze

无锁队列就像独角兽一样稀有，你必须使用运行时或操作系统提供的低锁原语。在示例算法中使用FetchAndAdd、CompareAndSwap。这就是问题所在，你没有记录下运行时环境。 - Hans Passant

@darkcminor：你知道吗，你正在使用一个“锁”来实现你的队列的一个基本实用函数，因此它不是一个“无锁”队列！ - Jonas Bötel

你可以使用GCC的原子内置函数来进行比较和交换以及获取和添加操作：http://gcc.gnu.org/onlinedocs/gcc/Atomic-Builtins.html - Alexey Kukanov

Answer 1

我曾经发现了一个不错的解决方案，用于解决这个问题。我相信这是目前为止找到的最小的解决方案。

该代码库具有如何使用它创建N个线程（读者和写者），并使它们共享单个位置的示例。

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

按缓冲区大小划分

按线程数排序

请注意，线程数量不会改变吞吐量。

我认为这是解决这个问题的终极方案。它能够快速、简单地工作，即使有数百个线程和一个长度为一的队列。它可以用作线程之间的管道，在队列内分配空间。

该存储库中有一些早期版本是用C#和Pascal编写的。我正在努力制作更完整、更精细的版本，以展示其真正的能力。

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

- bittnkr

Answer 2

您的伪代码可能（很可能）存在ABA问题，因为只检查指针，而没有附带的唯一标记。在这方面，您会发现这篇论文非常有用，它是锁定自由队列实现及其陷阱的通用指南。

在处理无锁编程时，阅读Herb Sutter的作品也是一个好主意，因为他对所需的内容、为什么需要以及其潜在的弱点给出了良好而深入的解释（尽管要注意，他的一些旧出版物/文章被发现包含一些隐藏/未预料到的问题）。

- Necrolis

---

有时候ABA问题并不重要，如果一个对象的地址是其固定标识符。例如，我曾经尝试在堆管理器中使用无锁队列，其中对象的位置（堆上的空闲块）就是其唯一标识。同样的道理也适用于长期存在的其他类型的对象，这些对象仅会在不同列表之间移动，而不会被释放或分配。 - R.. GitHub STOP HELPING ICE

Answer 3

同时，最近关于这个主题的"boost'con"演讲也提出了一些观点: https://github.com/boostcon/2011_presentations/raw/master/wed/lockfree_2011_slides.pdf

- Joel Falcou

Answer 4

（暂时保留此处，但请参见编辑。）

你知道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 指出的那样，如果在检查 null 和交换之间，tmp 被弹出、释放、重新分配并再次放入队列中，则 queue_pop 可能会失败：

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

我还不确定如何解决这个问题，但一旦我想出来了我会（希望）更新这个内容。暂时先不用考虑。

- David X

---

单线程代码使用无锁队列有什么意义？在多线程代码中，由于ABA问题，它会出现故障。 - Alexey Kukanov

@Alexey Kukanov，它的设计（不一定是实现，但是设计）是不需要关心“A”后面是什么，只要有“A”，它就应该正确地工作，即使“A”后面的数据已经改变。不过我确实需要仔细检查并验证这是否属实。 - David X

Joel Falcou回答中提到的幻灯片解释了为什么您的queue_pop会遭受ABA问题。在读取tmp->next和CAS之间存在时间窗口；无论多小，它都足以使您读取的值过时。 - Alexey Kukanov

如果您总是向列表中添加新项目，则没有ABA问题。只有在删除然后重新添加相同项目时才会出现此问题。 - johnnycrash

我们总是将项目添加到列表的头部，而不是尾部。实际上，我们没有尾部指针。因此，您只需要一个CAS，就不会出现数据竞争问题。 - johnnycrash

Answer 5

你可以尝试这个库，它是用C语言编写的原生库。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);

- Oktaheta