线程安全的优先队列

Question

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

曾经有一个想法是实现带有并发提取的二叉堆（每个元素都有自己的自旋锁，并且有一个全局的shared_mutex，在更改堆大小时进行写锁定，在堆化节点时进行读锁定，并且在交换和比较节点时锁定它们的自旋锁），但存在许多潜在的死锁可能性，我仍然不知道如何避免它们。

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

- DuXeN0N

Answer 1

你应该尽可能实现最简单的东西，用锁来保护它，在应用程序中进行测试。除非你每秒钟要访问它数千次，否则锁的开销几乎肯定对应用程序的性能没有影响，特别是如果你的队列相对较小。 我的建议是从std::priority_queue开始，用锁包装它，然后试试。 如果你真的认为你需要一个无锁的并发优先级队列，请查看Concurrent mutable priority queue。

- Jim Mischel

Answer 2

不要过快地假设无锁优先队列比互斥锁更快。正如您所见，任何复杂的无锁结构都往往非常复杂，涉及大量的原子操作。而在现代处理器上，由于需要保持内存视图在众多核心CPU上的一致性，这些原子操作变得相对越来越慢。

在这种情况下，我会感到非常惊讶，如果一个简单的自旋锁围绕着一个简单的二叉堆，不管争用级别如何，都不会比无锁堆实现快得多。

- Sneftel

---

我不想使它无锁，而是让它更简单。也许有一些好的方法可以使它阻塞，但要细粒度控制。 - DuXeN0N

@DuXeN0N 连续的 pop-first 操作将争夺几乎相同的插槽，有效地使它们串行化，无论锁有多细粒度。选择是抓取一个锁，还是抓取多个锁。 - Sneftel