linux - Linux2.6の内部完全に公正なスケジューラ

Question

このリンクhttp://www.ibm.com/developerworks/linux/library/l-completely-fair-schedulerでRED-BLACK_TREEデータ構造を使用するCFSのスケジューリングアルゴリズムについて研究していました 。

私の質問は：CFSで赤黒木を使用する目的は何ですか、なぜAVL木を使用できないのですか？

Answer 1

注：私は純粋にアルゴリズムの観点（実際の基本的な検索ツリー操作のパフォーマンス）からこれに答えていますが、Linux開発者がRBツリーを選択する他の内部的な理由があるかどうかはわかりません（特定のAVLを実行できる可能性があります）木はしません）。

一般に、この2つは互換性があり、機能に関する限り、基本的な検索ツリー、treap、スプレーツリーなどとも互換性があります。すべてのバランスの取れた検索ツリー（AVLツリーとRBツリーの両方がバランスが取れている）は同じ理論上のパフォーマンスを持っているため、違いは実際のパフォーマンスにあります。

2つのデータ構造（ AVL、RB ）のwikiページによると、AVLツリーはクエリのパフォーマンスが高く、挿入と削除のパフォーマンスが低くなっています。実装を見ると、これは非常に簡単にわかります。AVLツリーのバランスを取ることはより複雑であり、実際にはパフォーマンスが低下します。

だから私の推測では、彼らはAVLツリーを使用できます（RBツリーが持つ構造プロパティを利用し、AVLツリーが利用しない場合を除きます）が、クエリのパフォーマンスよりも挿入と削除のパフォーマンスを重視するため、代わりにRB。

また、C ++、Java、および.NETの組み込みデータ構造の多くは、おそらくすべての操作で同様のパフォーマンスが得られるため、実装に赤黒木を使用していることにも言及する価値があります。

Answer 2

CFS Linuxスケジューラーは、実際にはカスタマイズされたRBツリー（linux/rbtree.h）を使用します。ただし、ここで重要なのは、CFSは基本的に次にどのタスクを選択するかを知りたいということです。これは、ツリーから左端のノードを選択することで実現されます（スライス時間が短いノードになるため）。ただし、CFSで使用されるRBTには、便宜上、そのようなノードへのポインターもあります。

この時点で、AVLツリーは同等の複雑さで同じタスクを実行できると言えます。一方、タスクエントリを追加または削除するときは、RBTのバランスを取り直してトラバースする必要があります。ここで、私は理解していますが、RBTがAVLよりも仕事に適しているところです。

Answer 3

RB TREEは自己平衡型であるため、ツリー内のパスは他のパスの2倍の長さになりません。これは、ツリーの自己平衡型であるため、すべての操作がO（log n）になり、挿入と削除が行われます。ツリーからのタスクは迅速で非常に効率的に実行できます。