红黑树和单个运行队列有什么区别？
我一直试图理解两者之间的区别，因为它们适用于选择在某些 CPU 调度程序中运行的任务的不同算法。
将所需时间最短的进程放置在左侧并从左侧选择节点运行的 RB 树与将它们放置在最短作业优先顺序的队列之间有什么区别？
I have been trying to understand the difference between the two as they apply to different algorithms used to choose tasks to run in some CPU schedulers.
What is the difference between an RB tree that places lowest time needed process on the left and chooses nodes from the left to run, and a queue that places them in a shortest job first order?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
单个队列的时间复杂度[1]为 O(1)在搜索上，因为它可以弹出下一个进程来执行。插入也具有 O(1)，因为它将新项目放置在队列末尾。这种循环调度程序曾在早期的 Linux 内核中使用过。缺点是所有任务每次都以相同的顺序执行。
为了解决这个问题，一个简单的改进是继续以 O(1) 的方式弹出队列的头部，并在插入时按优先级和/或时间要求在队列中搜索合适的槽位，从而具有 O(n) 的时间复杂度。一些调度程序保留多个队列（甚至优先级队列），这些队列的操作时间根据实现和需求而变化。
另一方面，红黑树在插入时获取下一个进程的时间复杂度为 O(log n)。和。红黑树的基本思想是它在每个操作中保持自身平衡，从而保持高效而无需任何进一步的优化操作。优先级队列也可以在内部使用红黑树来实现。
关于 (Linux) 调度程序的一个很好的起点是 CFS 文章< /a> 在 IBM 的网站上，该网站也有一组很好的参考资料。
A single queue has time complexity[1] of O(1) on search because it can just pop the next process to execution. Insertion has also O(1) as it places the new item at the end of the queue. This kind of round-robin scheduler was used e.g. in early Linux kernel. The downside was that all tasks were executed every time in the same order.
To fix this, a simple improvement is to keep popping the head of the queue with O(1) and search a suitable slot in the queue on insert by priority and/or time requirements thus having O(n). Some schedulers keep multiple queues (or even a priority queue), that have varying operation times depending from the implementation and needs.
Red-black tree, on the other hand, has time complexity of O(log n) to get the next process and on insert. The principle idea of a red-black tree is that it keeps itself balanced with every operation thus remaining efficient without any further optimization operations. A priority queue can also be implemented using a red-black tree internally.
A good starting point on (Linux) schedulers is the CFS article on IBM's site, which has a nice set of references, as well.