差分

Linux 2.6系におけるスケジュラーは以前26系におけるスケジューラーは以前2.4系で使われていたスケジュラーからみると画期的に性能がいいO4系で使われていたスケジューラーからみると画期的に性能がいいO(1)スケジュラ(Order one scheduler)に変更されました。さらにLinux 2.6.23からO(1)スケジュラからCFS(Completely Fair Scheduler)に変更されました。

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