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.

class PriorityQueueRR(object):
    """ Class implementing a priority queue with round robin.
    """
    def __init__(self, rr_list=[0, 0, 1], qsize=32):
        """ Initializes the Priority Queue with Round Robin

        Arguments:
            rr_list {List} -- The list of priorities for round robin

        Keyword Arguments:
            qsize {Integer} -- The max size for the queue (default: {32})
        """

        self.rr_list = [0, 0, 1]
        self.rr_len = len(rr_list)
        self.rr_index = 0
        self.queue = []
        self.queue_len = 0
        self.q_size = qsize

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

    @synchro(LOCK)
    def enqueue(self, data, item_prio=0):
        res = False
        if len(self.queue) == self.q_size:
            print("Queue Full!")
        else:
            self.queue.append((data, item_prio))
            self.queue = sorted(self.queue, key=itemgetter(1))
            self.queue_len = self.queue_len + 1
            res = True
        return res

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

    @synchro(LOCK)
    def dequeue(self):
        if self.queue_len == 0:
            print("Queue is Empty!")
            return False
        else:
            pos, the_tuple = self.__get_next_item()
            del self.queue[pos]
            self.rr_index = (self.rr_index + 1) % self.rr_len
            self.queue_len = self.queue_len - 1
            return the_tuple[0]

    def __get_next_item(self):
        """Finds the next item to be dequeued

        Returns:
            tuple -- A tuple containing the item and the position of the item inside the queue
        """
        for pos, the_tuple, in enumerate(self.queue):
            if the_tuple[1] == self.rr_list[self.rr_index]:
                return pos, the_tuple
        return 0, self.queue[0]

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:

    def print_queue(self):
        if self.queue_len == 0:
            print("Queue is empty")
        else:
            print(self.queue)

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

if __name__ == '__main__':
    RR_Q = PriorityQueueRR()
    RR_Q.print_queue()
    RR_Q.enqueue("gigi", 0)
    RR_Q.enqueue("gigi1", 0)
    RR_Q.enqueue("gigi2", 1)
    RR_Q.enqueue("gigi3", 0)

    RR_Q.print_queue()
    print(RR_Q.dequeue())
    RR_Q.print_queue()
    print(RR_Q.dequeue())
    RR_Q.print_queue()
    print(RR_Q.dequeue())
    RR_Q.print_queue()
    print(RR_Q.dequeue())

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

if __name__ == '__main__':
Queue is empty
[('gigi', 0), ('gigi1', 0), ('gigi3', 0), ('gigi2', 1)]
gigi
[('gigi1', 0), ('gigi3', 0), ('gigi2', 1)]
gigi1
[('gigi3', 0), ('gigi2', 1)]
gigi2
[('gigi3', 0)]
gigi3

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.