在条件变量中实现一个优先级队列C

Question

我当前对条件变量的理解是所有被阻塞的（等待的）线程都被插入到一个基本的FIFO队列中，当signal（）被调用时，第一个队列被唤醒。

有没有什么办法可以修改这个队列（或创建一个新的结构）来执行优先级队列呢？我一直在考虑这个问题，但大多数解决方案最终都受到C.V.和互斥体固有的队列结构的阻碍。

谢谢！

Answer 1

我认为你应该重新考虑你想要做的事情。如果你试图优化你的表现，你可能会吼出错误的树。

pthread_cond_signal()甚至不保证准确解锁一个线程 - 它保证疏通至少一个线程，因此能够处理多个线程畅通，同时这种情况你的代码更好。执行此操作的典型方法是，每个线程在解锁后重新检查条件，如果为false，则返回到等待。

你可以实现某种方案，让你保持自己的线程优先级队列在等待，并且每个线程在它开始等待之前立即将自己添加到该队列中，然后在解除阻塞时检查队列，但是这样做会增加很多复杂性和很大的潜在严重问题（比赛条件，死锁等）。这也增加了一笔不小的开销。

此外，如果优先级更高的线程在条件变量被发送信号的同时开始等待条件变量，会发生什么情况？谁获得畅通，新到达的高优先级线程或以前的最高优先级线程？

线程得到解锁的顺序完全取决于内核的线程调度程序，所以你是在仁慈的。我甚至不会承担FIFO排序。

Answer 2

由于条件变量基本上只是一个障碍，您无法控制等待线程的队列，因此没有真正的方法来应用优先级。假设等待的线程以FIFO的方式工作是无效的。

利用原子，附加条件变量和预先知道的线程/优先级，您可以构建一个解决方案，其中一个信号线程将重新发信号通知主CV，然后重新阻塞优先级CV，但它当然不会是一个通用的解决方案。这也是我的头顶，所以也可能有其他缺陷。

Answer 3

调度程序确定哪个线程将运行。您可以查看pthread_setschedparam和pthread_getschedparam，并查看策略（SCHED_OTHER,SCHED_FIFO或SCHED_RR）和优先级。但它可能不会让你到我怀疑你想去的地方。

听起来好像你想从固有的非确定性中做出某些可预测的事情。正如Andrew所说，你可能会破解一些东西，但我的猜测是，这会导致心痛或者很多代码，你会在六个月（或两者）中讨厌自己编写代码。