1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The biggest question in my mind is actually if we can truly sort things in two dimensions - first sort by priority level, then sort by age. Not even sure if that's possible or how to do it! $\endgroup$ – Alexander Mills Jan 11 '17 at 0:07
  • $\begingroup$ The only problem/achilles heel I see for this algorithm is the sorting part - I have to make sure that the sorting which happens on two dimensions (priority and age of an item in the queue) does not consistently relegate certain items to the back of the subset of 20. So perhaps it's much better to put more weight on age and less weight on priority. $\endgroup$ – Alexander Mills Jan 11 '17 at 8:36
  • 2
    $\begingroup$ I believe you should clarify what you are trying to achieve. From what you wrote, I gather you imply some form of liveness property, but I'm not exactly sure what it is and what the exact constraints are. Regarding the sorting, I don't see why you wouldn't be able to. You can certainly sort according to any order relation of your choice, that's what sorting algorithms do. $\endgroup$ – quicksort Jan 11 '17 at 8:56
  • $\begingroup$ well, re: the question of the sort, please see: stackoverflow.com/questions/41586024/… $\endgroup$ – Alexander Mills Jan 11 '17 at 9:02
  • $\begingroup$ AFAICT you can't have it both ways, you have to choose one sorting dimension over another dimension. and like I was saying, I think it's more important to eliminate starvation (liveness?), and less important to get high priority items off the queue quickly. $\endgroup$ – Alexander Mills Jan 11 '17 at 9:05
2
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ very nice analysis, I will have to read several times to grok it, will get back to you with questions if I have any. AFAICT, your analysis looks like at least you understand the algorithm that I conveyed. I implemented it before i even wrote the question, so maybe some tests can back up your analysis. $\endgroup$ – Alexander Mills Jan 14 '17 at 0:54
  • $\begingroup$ if I ever write this up, will call it headzone instead of endzone, thanks again for your help $\endgroup$ – Alexander Mills Jan 15 '17 at 9:50
  • $\begingroup$ I wonder what this algorithm is called, I know I didn't invent it. It's a simple case of putting everything in one list, and then picking the first N and sorting them by priority. I am not even sure the mod operation part is even necessary. $\endgroup$ – Alexander Mills Feb 3 at 4:58
  • $\begingroup$ The mod part makes more sense if you put each priority level in a different queue. In retrospect, seems like I was mixing and matching techniques. Either mod or pick the first N and sort. Not sure if both makes any sense at all. $\endgroup$ – Alexander Mills Feb 3 at 5:14
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thanks for the info - assuming it's true, I am not sure I care for the strict definition of a priority queue :) This is a priority queue, but I believe you that it may not meet the strict definition :) thanks for your answer and feedback, will definitely look into process schedulers to see if one of those algorithms more closely matches this one. $\endgroup$ – Alexander Mills Jan 13 '17 at 19:31
  • $\begingroup$ WRT to correctness, maybe I should have made that more clear - correctness would mean that priority items are indeed processed more quickly on average; but more importantly correctness means that starvation cannot happen for any item at any priority. Maybe I could add that to the question. $\endgroup$ – Alexander Mills Jan 13 '17 at 20:08
  • $\begingroup$ Cool. Yup! Adding a definition of what counts as correctness for you sounds like a great thing to add to the question. When you say "on average", what are you averaging over? $\endgroup$ – D.W. Jan 13 '17 at 20:21
  • $\begingroup$ Re: "average", you would have to collect statistics over time, and for an item in the same position in the queue with two different priorities, the average number of steps (dequeue events) for the higher priority item to come off the queue would be statistically significantly fewer than the number of steps for a lower priority item. does that make sense? I guess you could do this mathematically, but that's quite difficult, and not necessarily possible. Of course two different items can't be in the same position in the same queue, we are just looking at things statistically. $\endgroup$ – Alexander Mills Jan 14 '17 at 0:57
  • $\begingroup$ just curious, you created two answers to the OP, how is that possible? I thought with StackExchange only 1 answer per user per post? $\endgroup$ – Alexander Mills Jul 3 '17 at 8:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.