线程安全的优先队列

Question

有一个目标是使线程池支持优先任务。所以我需要写一些数据结构来支持线程安全的优先级队列。当然，我们可以写大锁，使用 std::priority_queue。但这并不是那么有效。

有一个想法用并发提取来实现二进制堆（每个元素都有自己的自旋锁，并且有一个全局 shared_mutex，当我们改变堆大小时写锁定，堆化节点时读锁定，当我们交换和比较节点时我们锁定了他们的自旋锁），但是有很多潜在的死锁能力，我仍然不知道如何避免它们。

有没有什么好的数据结构可以更容易地成为线程安全的？或者是否有任何已经实施的堆我可以调查？

Answer 1

你真的应该实现你能找到的最简单的东西，用锁保护它，并在你的应用程序中测试它。除非您每秒执行数千次，否则锁的开销几乎肯定与应用程序的性能无关。如果您的队列相对较小，则尤其如此。

我的建议是从 开始std::priority_queue，在它周围锁上一把锁，然后试一试。

如果您真的认为您需要一个无锁的并发优先级队列，请查看并发可变优先级队列。