C语言中的多写者线程安全队列

13

我正在使用pthread开发一个多线程的C语言应用程序。其中一个线程将数据写入数据库(数据库库只能在单个线程中安全使用),而其他几个线程则收集数据、处理数据,然后需要将结果发送给数据库线程进行存储。我看到有人提到在C语言中可以实现“多写者安全队列”,但每次看到这样的提及时都说“对于这个示例来说太复杂了”,并且只是演示一个“单写者安全队列”。

我需要以下内容:

  • 高效的插入和删除。我认为像其他任何队列一样,O(1)的入队和出队是可能的。
  • 动态分配内存,即链式结构。我需要不受大小限制的队列,因此数组并不是我要找的东西。

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


1
当你说“多个写入者”时,你是指你希望队列支持来自多个线程的push()和pop()吗? - Matt Ball
2
你是否正在寻找无锁实现? - Karl Voigtland
你是指一个队列,其中两个或更多的写入线程同时添加到队列中,还是一个队列具有多个可能的写入线程,但只有一个线程可以同时写入到队列中? - anon
  • 多个写入者意味着多个push()线程。
  • 无锁并不是必须的,但如果有的话会很好。
  • 并发写入完全是可能的,虽然不太可能。 (即没有隐含保证不会有并发写入,但如果一个或多个阻塞直到其中一个完成,那也不是一个大问题。)
- Edward
顺便说一句,人们没有发布实现的一个原因是这种类型的代码虽然在C语言中编写不太困难,但很繁琐。 用C++编写要简单得多。 如果你不是完全依赖于C语言,我建议你改变编程语言。 - anon
@Neil:在项目的这个阶段,我完全依赖C语言。我想看看无锁队列会是什么样子,因为正如onebyone所提到的,我的代码可能需要它。虽然我认为它不需要,但我还没有测试过它的性能。 - Edward
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

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

编辑:如果在取消操作中将“signal”更改为“broadcast”,则还可以支持多个读取器(对于哪个读取器获取给定事件没有可移植的保证)。虽然你不需要它,但这样做也不会产生额外的代价。


1
我能看到一个问题: 当我决定关闭应用程序时,我需要停止等待在条件变量上的读取线程。我该怎么做? - Edward
内存可以被任意数量的执行线程同时读取。因此,读操作不需要互斥锁。 - Misguided
1
@Julian:虽然在这个上下文中我们称其为“读取”操作,但它实际上是从队列中移除一个项目。它绝对需要锁来完成这个操作,并且当然也需要锁来等待条件变量。 - Steve Jessop

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语言实现。


虽然有可能这样做,但如果队列中有多个元素的情况下,我希望读取器可以在写入器将元素推入队列尾部时,同时从队列头部弹出元素。在这种情况下,不需要进行互斥操作。 - Edward
也就是说,虽然我不反对在设计中使用互斥锁,但我宁愿不要将整个东西都包装在其中。 - Edward
2
这样做不行。当队列中有读取器等待项目时,它会持有锁定,从而防止任何写入者向队列添加项目(假设queueFront()/queuePop()是阻塞的)。如果queueFront()/queuePop()不是阻塞的,则没有办法让读取器等待项目而不进行轮询。 - mhagger

5

不错的回答,这个库看起来很有趣,虽然比较匿名,在网络上关于它的信息并不多。但是它的源代码量还是可控的,所以应该适合进行代码审查 :) - Rob11311

1
我会选择多个单写队列(每个写线程一个队列)。然后,您可以查看this以了解如何让单个读取器读取各个队列。

不幸的是,这并不是一个可行的选择,因为许多线程正在生成、完成它们的任务,然后将结果写入队列,由单个数据库工作线程处理。因此,每个队列只会被写入一次,从而打败了整个目的。 - Edward
好的。所以每个线程的工作量很大,最后只有一个写入队列?那么队列并不是真正的性能问题。那么用互斥锁保护push方法如何? - Bahbar

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接