scheduling - 红黑树和单个运行队列有什么区别？

Question

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

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

Answer 1

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

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

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

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