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:
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.
(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.
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.