3

如果两个线程具有相同的优先级,我正在寻找一种按优先级和先到先服务(FCFS)调度线程的方法。我正在考虑使用一堆队列或类似的东西。问题是,即使我实现了自己的优先级队列,更改优先级的能力也会破坏插入该队列的顺序。

为了解决这个问题,我可以节省每个线程的插入时间,并按插入时间对优先级队列进行排序(作为主要优先级参数的辅助参数),但我相信有一种数据结构的组合可以解决没有使用插入时间的问题。

复杂度应该是O(logN)(有一些O(N)复杂的天真的解决方案,例如有一个常规队列,并且每当我们必须弹出一个线程时迭代队列)。

4

1 回答 1

2

可能是我没有正确解决您的问题,但您可以为每个优先级设置一个单独的列表。
因此,每个线程都根据其优先级添加到相应的列表中。而且由于您总是在列表的末尾添加并从头部删除,您将拥有 FCFS 行为。

您还可以创建一个优先级队列来检索具有最低优先级的下一个线程(O(1) 来获取下一个线程和 O(logN) 来插入。为了比较,您可以使用每个节点的优先级和插入时间的组合。

于 2012-04-09T11:27:37.107 回答