How to classify simple priority queue algorithm

Question

I have a simple priority queue algorithm that I implemented, and I doubt it's new but I haven't been able to classify it. Wondering if I could get some help with classifying it! Once I classify it I can read more about how to implement it properly, etc.

Assuming the implementation is sound, I am also trying to figure out how to prove certain aspects of the queue, namely to determine if the maximum amount of time (or steps) for an item to come off the queue is deterministic. Ideally we could figure out how long that would be as a function of some variables and initial state, or what not.

Here is the basic algorithm:

Setup/background/assumptions:

• We have a FIFO queue, and each item in the queue has a priority of 1, 2, or 3 (generically, we could make it 1 -X where those are all integers). By FIFO we mean that, in general, items that are enqueued first get dequeued first, but with a priority queue that is not exactly the case (that should be pretty obvious).

• 3 is highest priority, 1 is lowest priority, the higher the number the higher the priority.

• Let's assume a single server for simplicity, but the concept should be similar enough for multiple servers.

• Assume we only take one item off the queue at a time, but this same algo should work if we pop off multiple items.

Algorithm:

(Note that the only question at hand is: What item do we pop off the queue next? That is what the algorithm is trying to solve).

Step 1: For all your priority levels, determine a number of cycles for each level. Higher priority levels should have more cycles - so let's say priority 3 has 10 cycles, priority 2 has 6 cycles and priority 1 has 2 cycles.

Step 2: Instead of looking at the whole queue, look at only the first Y items, for example the first 20 items. This makes things faster (O(20) instead of O(n)), and easier to prove that the implementation is working as expected. Most importantly, setting this cap should prevent starvation for the lower priority levels. Because eventually the 20 items will be filled with lower priority items, and then they will start seeing some attention.

Step 3: Every time you dequeue an item, increment an integer. Then mod this integer against the total number of cycles (10 + 6 + 2) = 18. This will determine which priority cycle you are in, for any given dequeue event.

Step 4: Take the value from the mod operation, determine what cycle you are in by comparing the value to an accumulated cycle value, e.g.:

Priority     Cycles      Accumulated

3            10           10

2            6            16

1            2            18

In that way if the mod result of our incremented integer is in the range 0 - 10 we are in priority 3 mode, if the mod result is in the range 11-16 we are in priority 2 land and if the mod result is in the range 17-18 we are in priority 1 realm.

Step 5: Sort the first 20 items in the head of the queue, first by priority level, then by age, oldest to the front. Given the priority level found from step 4, look through the sorted list find the first one that is at the priority level or below. So if we are at priority 3 we will look at all items. If we are at priority 2, we look at items with priority 2 and below, etc etc.

Step 6: If no items can be found with priorty Z and below, then cycle to the highest priority again, in this case 3, which will always yield something off the queue.

Done.

The basic idea is that our priority system is is based off of the number of cycles given to each priority, where more cycles are given to higher priority items. This should make things more deterministic.

But like I said, I am most interested in (a) proving this actually works somehow and (b) determining some value for maximum time (or steps) for an item to come off the queue.

Answer 1

You asked about starvation. Starvation is impossible in your scheme: every item will eventually come off the queue, after finitely many dequeue operations.

Consider an arbitrary priority-1 item, call it T. I'll prove that T will eventually be removed from the queue. Let $M$ denote the number of items that are older than T (i.e., were enqueued before T). This number must be finite. Let's call the first-20 items of the queue the endzone, so we have a concise name for it.

Lemma 1. T will reach the endzone after at most $M-19$ dequeue operations.

Proof: If T isn't among the endzone, then a dequeue operation will move it one position closer to the endzone. As long as T isn't among the endzone, no enqueue operation can jump a younger item ahead of T. There are initially $M$ items ahead of T, and as long as T stays out of the endzone this number decreases by one for each dequeue operation, so after $M-19$ operations, there are only 19 items ahead of T, i.e., T is in the endzone.

Lemma 2. Once T reaches the endzone, it will stay in the endzone until it is dequeued.

Proof: Follows by inspection of the algorithm. The only way for an item to be removed from the endzone is if it is selected to be returned by the dequeue operation.

Lemma 3. Let $N$ denote the number of priority-1 items that are ahead of T when it first enters the endzone. Then T will be dequeued after at most $18 \lfloor N/2 \rfloor + 18$ dequeue operations.

Proof: Consider the set of priority-1 items that are ahead of T, starting from the time when T first enters the endzone. Once T enters the endzone, this set can only shrink -- no new priority-1 item can jump ahead of T. (Any other priority-1 item will be tied with T for priority, and will be younger, so the sorting operation won't jump it ahead of T.) Moreover, after every 18 dequeue operations, we'll have dequeued at least 2 priority-1 items, so this set will shrink by at least 2. This can happen at most $\lfloor N/2 \rfloor$ times before this set has size at most 1. When the set has size at most 1, T will be removed after at most 18 more dequeue operations. Thus, T will be removed after a total of at most $18 \lfloor N/2 \rfloor + 18$ dequeue operations.

Theorem. T will be dequeued after at most $M+161$ dequeue operations.

Proof: By Lemma 1, T will enter the endzone after at most $M-19$ dequeue operations. Then we will have $N \le 19$ (since there can be at most 19 items ahead of T, when it is the endzone). By Lemmas 2 and 3, T will be dequeued after at most $18 \times \lfloor 19/2 \rfloor + 18 = 180$ more dequeue operations. Consequently, after at most $M-19 + 180 = M+161$ dequeue operations, T will have been removed.

It follows that every priority-1 item will be removed after at most finitely many dequeue operations; indeed, the latency (compared to a priority-less FIFO queue) is at most 161 extra dequeue operations. A similar argument can be applied to priority-2 items (adjusting Lemma 3 so $N$ counts the number of priority-1-or-2 items ahead of T) and to priority-3 items (adjusting Lemma 3 so $N$ counts the number of items ahead of T). We deduce that every item will be dequeued after at most finitely many dequeue operations, i.e., starvation is impossible.

Answer 2

You can't prove an algorithm is correct without a specification what correctness means.

This algorithm isn't a priority queue. A priority queue has two properties: pop always removes the highest-priority item; and it resolves ties (in priority) in a FIFO fashion. Your algorithm doesn't do that; if the first 20 items in the last are all low priority, but there's a high-priority item elsewhere, a priority queue would return the high-priority item, but your algorithm returns a low-priority item.

A true priority queue is easy to implement if you only have three priority levels: you just have three ordinary queues, one for each priority level. When pushing an item, push it onto the corresponding queue. When popping an item, first look at the level-3 queue and pop off of it if it is non-empty; otherwise check the level-2 queue and pop from it if it is non-empty; otherwise pop from the level-1 queue if the other two queues are empty. This achieves $O(1)$ time for all priority queue operations.

Possibly you are looking for information on process schedulers; this is studied in the operating systems area.