3

众所周知,优先级队列可以以最简单的形式为较低优先级的项目造成饥饿。例如,假设我们在优先级队列中有以下项目以优先级顺序递增:

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。这将防止不同项目类型的饥饿。

这是一个简单的方法,但我想知道是否有其他著名的算法来解决这个问题。有更好的算法或解决方案的想法吗?

4

0 回答 0