差分
/* CFS */
それまでの Linux のスケジュラーは、タスクを管理するキューをもち、その中で処理をしていました。CFSでは平衡2分探索木の一種である赤黒木というデータ構造を使いタスクを管理します。タスクは仮想実行時間という値を持ち、タスクが実行されるとこの値は増えます。タスク管理のツリーに戻される時、この仮想実行時間の値によってツリー中の適切な位置に置かれます。このツリーの中で最も値の小さいものが次に実行されるべきタスクとなります。こうすることによってCFSは計算量はOのスケジュラーは、タスクを管理するキューをもち、その中で処理をしていました。CFSでは平衡2分探索木の一種である赤黒木というデータ構造を使いタスクを管理します。タスクは仮想実行時間という値を持ち、タスクが実行されるとこの値は増えます。タスク管理のツリーに戻される時、この仮想実行時間の値によってツリー中の適切な位置に置かれます。このツリーの中で最も値の小さいものが次に実行されるべきタスクとなります。こうすることによってCFSは[[計算量]]はO(log n)で、適切なタスクを選ぶという操作が可能になっています。
匿名利用者
