13

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

我需要以下东西:

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

编辑:读取线程不应该在空队列上旋转,因为可能有几分钟没有写入的时间,大量写入的短脉冲。

4

4 回答 4

19

当然,有无锁队列。但是,根据您在评论中所说的,这里的性能并不重要,因为无论如何您都是在每次写入时创建一个线程。

因此,这是条件变量的标准用例。让自己成为一个包含互斥体、条件变量、链表(或循环缓冲区,如果你愿意)和取消标志的结构:

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

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

编辑:如果取消您将“信号”更改为“广播”,您还可以支持多个阅读器(没有可移植保证哪个人获得给定事件)。尽管您不需要它,但它也并不真正花费任何费用。

于 2009-07-31T14:32:04.777 回答
5

如果你不需要一个无锁队列,那么你可以只用一个锁来包装一个现有的队列。

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 重写它们。

于 2009-07-31T14:18:48.963 回答
4

http://www.liblfds.org

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

有 M&S 队列。

于 2012-05-23T18:44:44.783 回答
1

我会选择多个单写队列(每个写线程一个)。然后,您可以检查如何让单个阅读器阅读各种队列。

于 2009-07-31T13:53:01.813 回答