C 中的多写入器线程安全队列

Question

我正在使用 pthreads 开发多线程 C 应用程序。我有一个写入数据库的线程（数据库库只能安全地在单个线程中使用），还有几个线程正在收集数据，处理数据，然后需要将结果发送到数据库线程进行存储。我在提到的内容中提到，用 C 语言创建一个多写入器安全队列是“可能”的，但是我看到提到的每个地方都只是说它“对于这个例子来说太复杂了”，并且仅仅演示了一个单写入器安全队列.

我需要以下东西：

• 高效插入和移除。我假设像任何其他队列一样，O(1) 入队和出队是可能的。
• 动态分配的内存，即链接结构。我不需要对队列的大小进行任意限制，因此数组确实不是我想要的。

编辑： 读取线程不应在空队列上旋转，因为可能有几分钟的时间没有写入，并且有大量写入的短突发。

Answer 1

当然，有无锁队列。不过，根据您在评论中所说的内容，这里的性能一点也不重要，因为无论如何您都会为每次写入创建一个线程。

因此，这是条件变量的标准用例。为自己创建一个包含互斥锁、条件变量、链表（或循环缓冲区，如果您愿意）和取消标志的结构：

write:
    lock the mutex
    (optionally - check the cancel flag to prevent leaks of stuff on the list)
    add the event to the list
    signal the condition variable
    unlock the mutex

read:
   lock the mutex
   while (list is empty AND cancel is false):
       wait on the condition variable with the mutex
   if cancel is false:  // or "if list non-empty", depending on cancel semantics
       remove an event from the list
   unlock the mutex
   return event if we have one, else NULL meaning "cancelled"

cancel:
   lock the mutex
   set the cancel flag
   (optionally - dispose of anything on the list, since the reader will quit)
   signal the condition variable
   unlock the mutex

如果您使用带有外部节点的列表，那么您可能希望在互斥锁之外分配内存，只是为了减少其持有时间。但如果您使用侵入式列表节点设计事件，这可能是最简单的。

编辑：如果在取消中将“信号”更改为“广播”，您还可以支持多个读取器（没有可移植的保证哪个读取器获得给定事件）。虽然你不需要它，但也不需要花费任何费用。

Answer 2

如果您不需要无锁队列，那么您可以用锁包装现有队列。

Mutex myQueueLock;
Queue myQueue; 
void mtQueuePush(int value)
{
    lock(myQueueLock);
    queuePush(myQueue, value);
    unlock(myQueueLock);
}
int mtQueueNext()
{
    lock(myQueueLock);
    int value = queueFront(myQueue);
    queuePop(myQueue);
    unlock(myQueueLock);
    return value;
}

之后唯一的事情就是在队列为空时为 mtQueueNext 添加某种处理。

编辑： 如果你有一个单一的读者、单一的写入者无锁队列，你只需要在 mtQueuePush 周围有一个锁，以防止多个同时写入者。

有许多单读/写无锁队列，但其中大多数都是作为 C++ 模板类实现的。不过，请进行谷歌搜索，如果需要的话，可以找出如何用纯 C 重写它们。

Answer 3

https://www.liblfds.org

用C编写的无锁数据结构库。

有M&S队列。

Answer 4

我会选择多个单写入器队列（每个写入器线程一个）。然后你可以检查this以了解如何让单个读取器读取各个队列。