红黑树和单个runqueue有什么区别？

Question

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

在左边放置最低时间需求进程并选择从左边运行的节点的RB树和将它们放置在最短作业第一级的队列之间有什么区别？

Answer 1

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

为了解决这个问题，一个简单的改进是保持用O（1）弹出队列首部，并根据优先级和/或时间要求在插入队列中搜索合适的插槽，从而具有O（n）。有些调度程序保留多个队列（甚至是一个优先队列），这些队列的运行时间因实施和需求而异。

另一方面，红黑树的时间复杂度为O（log n），以便插入时获得下一个进程和。红黑树的原理是，它保持与每一个操作的平衡，从而保持高效率，而不需要进一步的优化操作。优先级队列也可以在内部使用红黑树来实现。

（Linux）调度程序的一个很好的起点是IBM站点上的CFS article，它也有一组很好的引用。