Python 3 Round Robin Priority queues – Avoiding starvation

In the post (Python 3 avoid starvation in Priority Queues) I explained the starvation problem you face front when using Python priority queues. In this post I’m going to reimplement a queue that avoid the problem using round robin, while in the post Python 3 priority queues with aging I used the aging to avoid the same problem.

In Round Robin, what I want to do is:
1. Most of the time, the more important items are fetched.
2. However, we guarantee that some of the time, the less important items are fetched.

To reach 1. goal we can use the priority queue.
To reach 2. goal we have to define when the queue should return higher priority items and when the queue should return lower priority items.

we can do this providing to the queue a roundrobin list for example
round_robin = [0, 0, 1, 0, 0, 2, 0, 0, 1]
The meaning of the list is:
For the first and second fetches, take items with priority = 0
For the third fetch, take the first item with priority = 1
For the fourth and fifth fetches, take items with priority = 0
For the sixth fetch, take an item with priority = 2
For the seventh and eighth fetches, take items with priority = 0
For the nineth fetch, take the first item with priority = 1

If items are not available take the first item in the prio order.

In this way we guarantee that each 9 times:
6 times the fetched item have priority 0

2 times the fetched item have priority 1
1 time the fetched item have priority 2

To implement the new queue class I’ll use a list a tuple with two elements: the data item and the priority of the item.

The enqueue method is very simple, it just appends the item to the list and sorts the list itself.

The dequeue method fetches the next item in the queue for which the priority matches the priority declared in the round robin list

Both enqueue and dequeue methods, to be thread safe, need the synchro decorator I described in the post (Python decorators in the real world)
Last we can add a print method to the class:

Here you are a simple main program to use the queue with round robin class:

It’s output is self explanatory, anyway let’s give a look:

The first print_queue() returns an “empty queue message”
Then we add four items and print the content of the queue, since the queue is ordered we can see the item “gigi2” as the last element.
Then we begin dequeueing the items, since we passed the rr_list=[0, 0, 1] the third dequeue call will fetch the gigi2 item.

Related Posts

1 thought on “Python 3 Round Robin Priority queues – Avoiding starvation

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.