scheduling - 赤黒いツリーと単一のランキューの違いは何ですか?

Question

一部のCPUスケジューラで実行するタスクを選択するために使用されるさまざまなアルゴリズムに適用されるため、2つの違いを理解しようとしています。

所要時間が最も短いプロセスを左側に配置し、左側から実行するノードを選択する RB ツリーと、それらを最短のジョブから順に配置するキューの違いは何ですか?

Answer 1

単一のキューは、検索時に O(1) の時間計算量^{[ 1 ]}を持ちます。これは、次のプロセスを実行にポップするだけだからです。挿入は、新しいアイテムをキューの最後に配置するため、O(1) も持ちます。この種のラウンドロビン スケジューラは、初期の Linux カーネルなどで使用されていました。欠点は、すべてのタスクが毎回同じ順序で実行されることでした。

これを修正するための簡単な改善は、キューの先頭を O(1) でポップし続け、優先度および/または時間要件によって挿入時にキュー内の適切なスロットを検索し、O(n) を持つことです。一部のスケジューラは複数のキュー (または優先キュー) を保持し、実装とニーズに応じて操作時間が異なります。

一方、赤黒木は、次のプロセスを取得して挿入するまでに O(log n) の時間の複雑さがあります。赤黒ツリーの基本的な考え方は、すべての操作でバランスを保ち、それ以上の最適化操作なしで効率を維持することです。プライオリティ キューは、内部で赤黒ツリーを使用して実装することもできます。

(Linux) スケジューラーの出発点としては、IBM のサイトにあるCFS の記事を参考にしてください。この記事にも参考文献がたくさんあります。