id:syuu1228 さんのLinuxのしくみを学ぶ - プロセス管理とスケジューリング がとてもわかりやすかった。ここまで分かりやすさと深さを両立した説明は初めて読んだ。プロセススケジューラの自分用の備忘録です。
- タイマ割込みのタイミングでプロセスの切り替えが起こる
- Linux 2.4 のランキューは単純なリスト構造で線形探索になるので探索コストがO(n)
- O(1)スケジューラは優先度ごとのプロセスリストの配列になっているので計算量はO(1)
- CFSではプロセスが使用したCPU時間と優先度による重み付けをして昇順に並べて先頭のプロセスを実行する。赤黒木が効率が良いので使われている。
- 赤黒木はO(log n)だが、プロセス数が多くなるとO(1)との差がわずかになる
- スケジューラのアルゴリズム上ほとんど左端しか参照しないので、ノードのポインタをキャッシュすることでさらに高速化している
- Linux 2.4 ではランキューは一つだったが現在はCPUごとにある。定期的に偏りをなくしたり、新しいプロセスは短いランキューに繋いだりして、偏りが起きないようにしている。
