CODEWITHSUNDEEP
linuxalgorithmdata-structures
Anil Arya
Anil Arya

Reputation: 3110

Inside the Linux 2.6 Completely Fair Scheduler

I was studying about scheduling algorithm of CFS which uses RED-BLACK_TREE data structure on this link http://www.ibm.com/developerworks/linux/library/l-completely-fair-scheduler

My question is :What is the purpose of using red-black-tree in CFS ,why cannot use AVL tree.?

Upvotes: 2

Views: 1547

Answers (3)

KUMAR HARSH
KUMAR HARSH

Reputation: 103

Because an RB TREE is self balancing so no path in the tree will be twice as long as any other path because of the self balancing nature of the tree and due to this, all operations will be O (log n), thus inserting and deleting tasks from the tree can be quick and done very efficiently.

Upvotes: 0

rudygodoy
rudygodoy

Reputation: 478

The CFS Linux scheduler actually uses a customised RB Tree (linux/rbtree.h). But the key here is that CFS basically wants to know which task to pick next. This is achieved picking the left-most node from the tree (since it will be the one with minor slice time). However, the RBT used by CFS also has a pointer to such node for convenience.

At this point you could say that AVL tree could do the same task with equivalent complexity. In the other hand you have to rebalance and traverse the RBT when adding or removing task entries. Here, I understand, is where RBT suits better for the job than AVL.

Upvotes: 1

IVlad
IVlad

Reputation: 43507

Note: I am answering this from a purely algorithmic point of view (performance of the basic search tree operations in practice), I have no idea if the Linux devs have other inside reasons for choosing RB trees (it might let them do certain things AVL trees don't).

Generally, the two are interchangeable, and they are also interchangeable with basic search trees, treaps, splay trees etc. as far as functionality is concerned. The difference is in practical performance, as all balanced search trees (AVL and RB trees are both balanced) have the same theoretical performance.

According to the wiki pages for the two data structures (AVL, RB), AVL trees perform better for querying and worse for insertion and removal. This is pretty easy to notice if you look at an implementation: balancing the AVL tree is more involved, leading to slower performance in practice.

So my guess is, they CAN use AVL trees (unless they make use of a structural property RB trees have and AVL trees don't, which is unlikely), but they care more about insertion and removal performance than query performance, so they chose RB instead.

It's also worth mentioning that a lot of the built in data structures in C++, Java and .NET use red-black trees in their implementation, probably also because of their similar performance for all operations.

Upvotes: 2

Related Questions