As everyone knows, a priority queue can create starvation for lower priority items in its simplest form. For example, assume that we have following items in a priority queue in increasing priority order:
Item Priority
--------------------
Item A 0 //Lowest priority
Item B 1
Item C 2
Item D 3
Item E 4 //Highest priority
Now if we receive a consistent flow of items with higher priority in our priority queue(B-E), we may never handle lower priority packets(A). I wonder what algorithms are there to handle this problem?
A simple approach that comes to my mind is limiting processing of different item types based on priority. For example, we limit packet processing of each type to 2 ^ priority. So for table above, after handing 16 items of Item E type, we will handle up to 8 items of type Item D, up to 4 of Item C, up to 2 of Item B and up to 1 of Item A before starting to handle Item E again. This will prevent starvation for different item types.
This is a simple method, but I wonder if there are other famous algorithms to tackle this problem. Any idea for better algorithms or solutions?
