What's the difference between a red black tree and a single runqueue?

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 di开发者_如何学Pythonfference 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?

---

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.