3

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

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

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

4

1 回答 1

2

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

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

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