差分

それまでの Linux のスケジューラーは、タスクを管理するキューをもち、その中で処理をしていました。CFSでは平衡2分探索木の一種である赤黒木というデータ構造を使いタスクを管理します。タスクは仮想実行時間という値を持ち、タスクが実行されるとこの値は増えます。タスク管理のツリーに戻される時、この仮想実行時間の値によってツリー中の適切な位置に置かれます。このツリーの中で最も値の小さいものが次に実行されるべきタスクとなります。こうすることによってCFSはのスケジューラーは、タスクを管理するキューをもち、その中で処理をしていました。CFSでは平衡2分探索木の一種である赤黒木<ref>赤黒木がどう生成され管理されるかビジュアルで示してくれるサイトです。挿入(insert)、削除(delete)、検索(find)の操作をすると、どうRed/Black Treeが作られるか/操作されるかがビジュアルでわかります。https://www.cs.usfca.edu/~galles/visualization/RedBlack.html</ref>というデータ構造を使いタスクを管理します。タスクは仮想実行時間という値を持ち、タスクが実行されるとこの値は増えます。タスク管理のツリーに戻される時、この仮想実行時間の値によってツリー中の適切な位置に置かれます。このツリーの中で最も値の小さいものが次に実行されるべきタスクとなります。こうすることによってCFSは[[計算量]]はO(log n)で、適切なタスクを選ぶという操作が可能になっています。