CODEWITHSUNDEEP
delphithread-safetypriority-queue
Eric Grange
Eric Grange

Reputation: 6211

Thread-safe Priority Queue for Delphi?

I'm looking for a priority queue implemented in Delphi that would work well in a multi-threaded environment.

Ideally lock-free, or designed for multi-threaded inserts/deletes with something better than a locked wrapper around a single-threaded implementation (which I already have).

The specificity is that in normal operation, there would be only adds, deletes, and notifications when the top (highest priority item) changes, while "pop" operations of the highest priority item should be very infrequent.

It would be used for a watchdog/timeout thread monitoring tasks, being executed in other threads, those task are expected to terminate normally most of the time, so they would just be added/removed from the queue. The timeout thread would essentially be waiting on the next timeout event, hence the need for notifications when the top-priority event changes.

The tasks are handled by scripts, which can be safely terminated at any time.

If there are better algorithms for this than a priority queue, they could be good answers too!

Edit: following a remark by Martin James, another specificity is that there are relatively few different timeout values, and for each timeout value, the problem becomes that of a FIFO queue.

Upvotes: 13

Views: 3627

Answers (3)

Misha
Misha

Reputation: 1826

My framework architecture is completely built around priority threaded queues - that's the only threading model I use (http://www.csinnovations.com/framework_overview.htm). A steep learning curve, but it might give you some ideas.

Upvotes: 1

menjaraz
menjaraz

Reputation: 7575

Julian Bucknall (Author of "Tomes of Delphi: Algorithms and Data Structures" ) has recently announced the release of a Delphi XE version of EZDSL(a Delphi Structures Library) in his Blog.

Unfortunately TThreadsafePriorityQueue (implemented in EZDSLPQu.PAS) is lock based.

I can't help sharing the good news and my other intent is a call for his contribution in answering the question.

Upvotes: 2

BennyBechDk
BennyBechDk

Reputation: 944

Instead of a single que you could use one queue for each priority.

The OmnithreadLibrary contains thread safe queues: http://code.google.com/p/omnithreadlibrary/

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

Upvotes: 0

Related Questions