Priority Queues and Async Tasks

I started playing with Priority Queues last week, they are very simple to use. Create a queue, add an element, assign a priority to that element.

PriorityQueue<string, int> myQueue = new PriorityQueue<string, int>();

myQueue.Enqueue("middle", 2);
myQueue.Enqueue("first", 1);
myQueue.Enqueue("last", 3);

As you might guess, when dequeuing these they will come out in the order of “first”, “middle”, and “last”. Very nice, very easy.

Running async tasks based on their priority

In the past month, I’ve written a few blogs about using WhenAny and wanted to see if I could combine what I was doing there with priority queues. Here is the contrived example that resulted.

I don’t have a practical use for this, but I’m guessing that someone out there does.

I have three async methods MakeBigWidget, MakeMediumWidget, and MakeSmallWidget that all include a random delay, but usually, the the big one takes the longest, and the small one takes the shortest amount of time.

Into the priority queue I put the three Func<Task>, setting the big one as the highest priority, and the small one as the lowest priority (lines 5-9).

Then I loop over the priority queue, dequeuing the highest priority item, run task, and add to a List<Task> (lines 13-18).

Finally, I wait for each task to complete and remove the task from the List<Task> (lines 21-28).

There it is, hopefully this will solve a real problem someone has.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class PriorityQueueForAsyncTasks
{
    public static async Task Main()
    {
        PriorityQueue<Func<Task>, int> widgetPriorityQueue = new PriorityQueue<Func<Task>, int>();

        widgetPriorityQueue.Enqueue(MakeSmallWidget, 3);
        widgetPriorityQueue.Enqueue(MakeMediumWidget, 2);
        widgetPriorityQueue.Enqueue(MakeBigWidget, 1);

        List<Task> widgetsBeingPrepared = new List<Task>();

        while(widgetPriorityQueue.Count > 0)
        {
            var widgetToStartOn = widgetPriorityQueue.Dequeue();
            Console.WriteLine($"Starting on {widgetToStartOn.Method.Name}");
            
            widgetsBeingPrepared.Add(Task.Run(() => widgetToStartOn()));
        }

        while(widgetsBeingPrepared.Any())
        {
            var widgetThatIsReady = await Task.WhenAny(widgetsBeingPrepared);

            await widgetThatIsReady;
            
            widgetsBeingPrepared.Remove(widgetThatIsReady);
        }
    }

    public static async Task MakeSmallWidget()
    {
        await Task.Delay(random.Next(100, 400));
        Console.WriteLine("Small widget is ready");
    }
    
    public static async Task MakeMediumWidget()
    {
        await Task.Delay(random.Next(200, 400));
        Console.WriteLine("Medium widget is ready");
    }

    public static async Task MakeBigWidget()
    {
        await Task.Delay(random.Next(300, 600));
        Console.WriteLine("Big widget is ready");
    }
    static Random random = new Random();
}
comments powered by Disqus

Related