CFSメモ

Linuxのスケジューラ、CFSの解説。

http://www.ibm.com/developerworks/jp/linux/library/l-completely-fair-scheduler/?ca=drs-jp

ちょっと古いが、勉強になる。

応答性とスケーラビリティのトレードオフのために、コア技術としてRed-Black Treeを使っている。単なるBinary Search Treeと違い、Tree構造が高々１段差にしかならないことが特徴。

これが日本のWikipediaだとさっぱりわからなかった。

英語のほうをみたら、ちゃんとサンプルつきで書かれていた。

http://ja.wikipedia.org/wiki/%E8%B5%A4%E9%BB%92%E6%9C%A8

http://en.wikipedia.org/wiki/Red_black_tree

Linuxではプロセスごとに優先度が決められていてプロセスの数が増えても問題ないようにこのような特殊なデータ構造を使っているようだ。

ちなみにCFSでは一度リグレッション（性能劣化）が発生していて、今のバージョンではそれなりに直っている。

http://www.atmarkit.co.jp/flinux/rensai/watch2009/watch09b.html