Delphi的线程安全优先队列？

Question

我正在寻找一个在Delphi中实现的优先队列，能够在多线程环境下很好地工作。

最好是无锁实现，或者是为多线程插入/删除设计的，而不是一个单线程实现的加锁包装（这已经有了）。

具体要求是，在正常操作中，只有添加、删除和通知顶部（最高优先级项）更改时，而“弹出”最高优先级项的操作应该非常不频繁。

它将用于监视任务的看门狗/超时线程，在其他线程中执行这些任务，大部分时间会正常终止，因此它们只需要从队列中添加/删除。超时线程基本上会等待下一个超时事件，因此需要在顶部优先级事件发生更改时进行通知。

这些任务由脚本处理，可以随时安全终止。

如果有比优先队列更好的算法，也可以作为好的答案!

编辑：根据Martin James的说法，另一个特点是超时值相对较少，对于每个超时值，问题变成了FIFO队列的问题。

- Eric Grange

---

@Pol：这还不够好，因为我已经有一个了（正如帖子中所说）。 - Eric Grange

@David：任何时候都可能启动和停止大量任务，包括非常短的任务。我的基准测试使用锁定解决方案显示它是超过10-12个任务线程的扩展瓶颈，因为所有任务最终都会两次锁定优先级队列，一次用于添加，一次用于删除。理想情况下，我希望它能够扩展到32到48个任务线程。 - Eric Grange

有时候无锁解决方案当然也可能更糟。 - David Heffernan

好的，一个建议 - 不要从列表中删除它们，只需在某个内部状态枚举中将它们标记为“待删除”。最终，超时线程会处理它们并在那时删除它们。 - Martin James

@EricGrange - 当项目被添加时，它们总是以相同的超时值添加，因此始终添加到队列的末尾，还是超时间隔变化很大？ - Martin James

Answer 1

最近，《Delphi算法和数据结构》的作者Julian Bucknall宣布发布了Delphi XE版本的EZDSL（一个Delphi结构库），你可以在他的博客中获取相关信息。

不幸的是，EZDSLPQu.PAS实现的TThreadsafePriorityQueue是基于锁的。

我想分享这个好消息，并希望他能为回答问题做出贡献。

- menjaraz

---

我一直使用我自己移植的EZDSL，如果我需要一个基础来开始，我会信任EZDSL。 - Warren P

Answer 2

我的框架架构完全建立在优先级线程队列上 - 这是我使用的唯一线程模型（http://www.csinnovations.com/framework_overview.htm）。学习曲线陡峭，但可能会给你一些启示。

- Misha

Answer 3

你可以使用每个优先级一个队列，而不是单个队列。

OmnithreadLibrary 包含线程安全队列： http://code.google.com/p/omnithreadlibrary/

http://code.google.com/p/omnithreadlibrary/

- BennyBechDk

---

多个单优先级队列并不是真正的解决方案。所有“弹出”操作都会变得非常复杂。（反之，“推入”操作很简单。）在我的中期计划中有一个待办事项，上面写着“检查无锁优先级队列的可能性”，但这在接下来的几个月内不会发生。 - gabr