CODEWITHSUNDEEP
.netalgorithmqueueproducer-consumer
bmt22033
bmt22033

Reputation: 7240

Algorithm for .NET consumer thread processing of two queues (based on priority)

I have a C# 4.0 app with "high priority" and "low priority" queues implemented as such:

BlockingCollection highPriority = new BlockingCollection(1000); BlockingCollection lowPriority = new BlockingCollection(1000);

Any data produced in highPriority should be consumed before any data produced in lowPriority. The twist here is that data may be produced to either of the two queues at any time. So after I've consumed all of the data in highPriority, I will then being consuming any data that might be in lowPriority. If new data is produced in highPriority while I'm consuming data in lowPriority, I want to finish consuming the current item in lowPriority and then switch back and process the data in highPriority.

Can anyone suggest an algorithm to help with this? Pseudo code is fine. Thanks very much.

Upvotes: 5

Views: 609

Answers (3)

eSniff
eSniff

Reputation: 5875

I would do this with a single priority queue. This would allow you to add a 3rd priority later, with very little code change.

I've written one before using a lockFree-SkipList, But here's a project for one which uses a normal skip-list (http://www.codeproject.com/KB/recipes/PriorityQueueSkipList.aspx). I used a skip-list because they preform well under concurrency and are pretty simple to implement (minus the lock-free version).

Ive also seen a priority queue on CodePlex which use a Red-Black Tree, but I can't find it right now. UPDATE : The priority queue implementation I was thinking of was part of the NGenerics project: http://code.google.com/p/ngenerics/

Upvotes: 1

Jim Mischel
Jim Mischel

Reputation: 133995

You'll want to wrap this into a single object if you can, as @Kevin Brock suggested, and have that object implement IProducerConsumerCollection. Otherwise your code that calls TryDequeue will have do do a busy wait loop. That is, with two queues, you have to write something like:

WorkItem item = null;
do
{
    if (!hpQueue.TryDequeue(out item))
    {
        lpQueue.TryDequeue(out item);
    }
while (item != null);

If you use your own class, then you can use events (EventWaitHandle, etc.) to prevent the busy waiting.

In truth, you'd probably be better off using a priority queue. It would be pretty easy to make a priority queue thread-safe and implement IProducerConsumerCollection, and then you can use it with BlockingCollection. A good place to start would be Julian Bucknall's Priority Queue in C#.

Upvotes: 1

Carra
Carra

Reputation: 17964

How about this:

while(true)
{
    workitem = highQueue.dequeue();

    if(workitem == null)
        workitem = lowQueueu.dequeue()

    process(workitem)
}

Upvotes: 3

Related Questions