tabateeの日記： CFS

LinuxのスケジューラがCFS(Completely Fair Scheduler、kerneltrap.orgの解説記事)に変更されそうな雰囲気なので、紹介を書いてみます。
昔のLinuxのスケジューラは教科書的なものを適当に実装したような感じでしたが、負荷に弱く、SMPのスケーラビリティも悪かったため(8CPUのベンチマークで延べ実行時間の半分以上がスケジューラというのを見たことがあります)現在のO(1)スケジューラに取り替えられました。
O(1)スケジューラは名前のとおりプロセス選択の処理は最速だったんですが、複雑な負荷分散や ユーザインタフェースの反応を良くするためのハックを入れて複雑化し、それでも様々なコーナーケースが残るということが問題となっていたようです。
そんな状況で、Con Kolivas氏がO(1)スケジューラを基にして、各プロセスが平等(Fair)に実行されるスケジューラRSDLをリリースします。さらに、それにinspireされたIngo Molnar氏(O(1)スケジューラの作者)が開発したのがCFSでした。
CFSでは各プロセスの実行された時間と待たされた時間を元に各プロセスをいつから実行するかを計算し、その時間をキーとするRB-treeに格納します。スケジューリングの際にはRB-treeの一番左のプロセスが選択され、他のプロセスの時間がくるか待ちが発生するまで走行します。
こんな感じの説明とコードを見る限り、サーバプロセスが多数走って高負荷な状態でもコーディング中のエディタのように休み休み動くプロセスが共存できそうな感じです。また、時間を測定して平等にスケジューリングというやり方が出てきたことも興味深いです。