众所周知,优先级队列可以以最简单的形式为较低优先级的项目造成饥饿。例如,假设我们在优先级队列中有以下项目以优先级顺序递增:
Item Priority
--------------------
Item A 0 //Lowest priority
Item B 1
Item C 2
Item D 3
Item E 4 //Highest priority
现在,如果我们在优先级队列(BE)中接收到具有较高优先级的项目的一致流,我们可能永远不会处理较低优先级的数据包(A)。我想知道有什么算法可以解决这个问题?
我想到的一个简单方法是根据优先级限制对不同项目类型的处理。例如,我们将每种类型的数据包处理限制为2 ^ priority
. 所以对于上表,在处理完 16 种Item E
类型后,我们将处理最多 8 种类型Item D
,最多 4 种Item C
,最多 2 种Item B
,最多 1 种,Item A
然后再开始处理Item E
。这将防止不同项目类型的饥饿。
这是一个简单的方法,但我想知道是否有其他著名的算法来解决这个问题。有更好的算法或解决方案的想法吗?