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添加某种handeling.

编辑:如果你有一个读写器,单个编写器无锁队列,你只需要锁定mtQueuePush,以防止多个同时写入者.

这是一个单个读取器/写入器无锁队列的nubmer,大多数都是作为c ++模板类实现的.然而,谷歌搜索,如果需要解决如何在普通C中重写它们.

Answer 3

https://www.liblfds.org

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

有玛莎百货排队。