2

我一直试图了解两者之间的区别,因为它们适用于用于选择要在某些 CPU 调度程序中运行的任务的不同算法。

将所需时间最短的进程放在左侧并从左侧选择节点运行的 RB 树与将它们放在最短作业第一顺序的队列之间有什么区别?

4

1 回答 1

2

单个队列在搜索时具有 O(1) 的时间复杂度[ 1 ],因为它可以弹出下一个进程执行。插入也有 O(1),因为它将新项目放在队列的末尾。这种循环调度器曾在早期的 Linux 内核中使用过。缺点是所有任务每次都以相同的顺序执行。

为了解决这个问题,一个简单的改进是继续以 O(1) 弹出队列的头部,并在插入时按优先级和/或时间要求在队列中搜索合适的槽,因此具有 O(n)。一些调度程序保留多个队列(甚至是优先级队列),这些队列的操作时间取决于实现和需求。

另一方面,红黑树的时间复杂度为 O(log n) 以获取下一个进程插入。红黑树的基本思想是,它使自己与每个操作保持平衡,从而在没有任何进一步优化操作的情况下保持高效。优先级队列也可以在内部使用红黑树来实现。

关于 (Linux) 调度程序的一个很好的起点是 IBM 站点上的CFS 文章,其中也有一组很好的参考资料。

于 2010-11-11T07:57:33.850 回答