multithreading - 线程安全的优先队列

Question

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

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

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

Answer 1

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

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

如果您真的认为您需要一个无锁并发优先级队列，请查看 Concurrent mutable priority queue .