How to avoid starvation in a priority queue

Question

I am trying to create a queue that avoids having elements in the queue for too long. I am using a linked list. The way I want to implement it is that if a greater priority is added, the ones that are pushed backed have 0.4 added to them. I also need to implement a sort for the linked list but that makes some sense already. I do not really understand how I am supposed to add this 0.4 to the priority's that have been displaced.

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self,):
        self.head = Node()

    def append(self, data):
        new_node = Node(data)
        current = self.head
        while current.next is not None:
            current = current.next
        current.next = new_node

    def __str__(self):
        data = []
        current = self.head
        while current is not None:
            data.append(current.data)
            current = current.next
        return "[%s]" %(', '.join(str(i) for i in data))

    def __repr__(self):
        return self.__str__()

    def length(self):
        current = self.head
        total = 0
        while current.next is not None:
            total += 1
            current = current.next
        return total

    def display(self):
        elements = []
        current_node = self.head
        while current_node.next is not None:
            current_node = current_node.next
            elements.append(current_node.data)
        print("Elements ", elements)

    def get(self, index):
        if index >= self.length():
            print("Error: Index is out of range!")
            return None
        current_index = 0
        current_node = self.head
        while True:
            current_node = current_node.next
            if current_index == index:
                return current_node.data
            current_index += 1

    def remove(self):
        current = self.head
        if current is not None:
            self.head = current.next
        else:
            print("Queue is empty!")

def main():
    queue = LinkedList()
    queue.append(5)
    queue.append(2)
    queue.display()


main()

Write a function, call it `get_true_priority(base_priority, age)` such that it produces useful output that "avoids starvation" (there are probably some other rules that should be honored, such as being monotonic wrt age?). This function *can be plotted on a graph* and I would probably start by drawing the graph of how I'd "expect" it work and then work that back to code. — user2864740, Aug 24 '18 at 23:57
You don't need a linked list, Python `list` is just fine. You need 2 structures in your class: one that keeps items sorted or heapified by current priorities, and the other - by time left "till it gets another 0.4 added". Update list positions of items whose priorities get updated. — Victor Sergienko, Aug 25 '18 at 00:31

score 0 · Answer 1 · answered Aug 25 '18 at 16:03

I'd suggest using python's heapq rather than a linked list. Because you're doing a custom comparison, you'll probably want to implement something like what's described in heapq with custom compare predicate.

In addition to the priority, add a field that contains the time when the item was added to the heap. Then, your actual priority is a function of the assigned priority and the length of time the item has been in the heap. For example, the priority could be something like:

elapsed_time = current_time - added_time;
real_priority = assigned_priority * elapsed_time;

You might want to make the multiplier some fraction of the elapsed time.

Another possibility is if you want to make sure that something doesn't stay in the queue longer than some set time. For example, if you want to make sure things don't stay for more than 5 minutes, you could add dequeue_time field. Your comparison then becomes something like:

// assume items a and b are being compared
if (a.dequeue_time < current_time) {
    if (b.dequeue_time < a.dequeue_time) {
        // b sorts before a
    }
    else if (b.dequeue_time > a.dequeue_time) {
        // return a sorts before b
    }
    else { // dequeue times are equal
        return result of comparing a.priority to b.priority
    }
}
else {
    // here, return result of comparing a.priority and b.priority
}

heapq is going to be much more efficient than your linked list, especially as the number of items in your queue increases. Plus, it's already written and known working. All you have to do is provide the comparison function.

How to avoid starvation in a priority queue

1 Answers1