c - 如何提高用 C 编写的阻塞队列的性能？

Question

我用 C 语言编写了一个阻塞队列，与 Java 的 BlockingQueue 类提供的阻塞队列非常相似。队列基本上提供了以下 API:

void blocking_queue_add(Blocking_Queue* bq, void* element);
void* blocking_queue_get(Blocking_Queue* bq);

并具有以下属性:

它有一个固定的大小。

如果 blocking_queue_add当队列满时调用，调用者被阻塞，直到队列有空间。

如果 blocking_queue_get当队列为空时调用，调用者被阻塞，直到有数据要获取。

如果多个调用者被阻止等待 blocking_queue_add或 blocking_queue_get ，他们需要服务订购 (先进先出)。

我很难实现一个满足最后一点的队列，同时保持可接受的性能。我正在使用 pthreads进行同步，为了满足 FIFO 要求，我依赖 pthread_cond_wait和 pthread_cond_broadcast职能。整个想法是所有被阻止的调用者都将等待一个条件。一旦它们中的一个可以被服务，就会发出一个广播信号并且它们都被唤醒。此时，他们可以根据内部 FIFO 状态轻松检查谁是被选中的人。其他人通过调用 pthread_cond_wait 自愿阻止自己。再次等待轮到他们。
这个实现似乎工作正常，队列本身似乎工作。但是，当消费者多于生产者时，我的性能会大幅下降，反之亦然。问题是当我遇到这种不平衡时，总会有很多被阻塞的调用者，所以通过调用 pthread_cond_broadcast 唤醒所有调用者的开销每次都变得无法接受。
我正在寻找有关如何解决此问题的提示。我将我的队列与 Java 的实现进行了比较，它在处理小工作负载时更快，但是当我测试一个工作负载很大且完全不平衡的场景时，我的实现是一场灾难，Java 的实现似乎只是线性地慢。事实上，如果我从我的实现中删除所有与队列相关的代码，只更改两个 blocking_queue_add和 blocking_queue_get仅具有条件/广播逻辑的功能，这已经是一场灾难。
任何输入表示赞赏，谢谢。

Brandon 的想法大大提高了性能。现在的性能似乎比 Java 实现好 2 倍以上。
对于任何对 future 感兴趣的人，我将源代码开源:
https://github.com/felipeek/c-fifo-blocking-queue

Answer 1

'm having a hard time implementing a queue that satisfies the last point while keeping acceptable performance. I'm using pthreads to do the synchronization and, in order to satisfy the FIFO requirement, I am relying on pthread_cond_wait and pthread_cond_broadcast functions.

在这种情况下，当一个线程添加到队列中时，它会执行 pthread_cond_broadcast()并唤醒所有被阻塞等待从空队列中获取数据的线程；并且(如果有很多线程被阻塞等待)这会导致大量 CPU 时间被线程切换和调度程序开销浪费掉；因为每个等待线程解除阻塞，尝试获取互斥锁(并且可能在尝试获取互斥锁时再次阻塞和解除阻塞)然后检查它是否是下一个，如果不是下一个则再次阻塞。
解决这个问题；每个线程都需要自己独立的条件变量。当一个线程开始等待来自空队列的数据时，它会将其条件变量放在“等待读者的队列”中；当一个线程将数据添加到队列中时，它会从“等待读者队列”中获取第一个条件变量，并且(如果有服务员)执行一个 pthread_cond_signal() (而不是广播)，以便只有一个等待线程被解除阻塞。
注意“等待读者条件变量队列”可以是“struct waiter { struct waiter * next; pthread_cond_t condVar; }”结构的链表；并且这些结构可以在创建线程时创建和初始化，然后不断回收(直到线程终止)。
对于“多个作者”来说，使用相同的解决方案本质上是相同的问题(并且可以重复使用创建线程时创建的相同“struct waiter”)。当一个线程需要等待将数据添加到队列中时，它会将其条件变量添加到“等待写入者的链接列表”中，当一个线程完成从队列中删除数据时，它会执行 pthread_cond_signal()解锁下一个等待的作家。
请注意，当它处于高争用状态(大量等待的读者或大量等待的写入者)时，这应该会显着提高性能；但是管理“服务员队列”的额外开销也可能会降低低争用下的性能(最坏的情况是通常只有一个等待线程，这是您当前使用 pthread_cond_broadcast 方法的最佳情况)。