Linuxのスケジューリング

linux2.4のスケジューラ

ランキューが単純なリスト構造
線形探索
ランキューひとつ

その後
優勢順位別のリスト
単純に優先順位の高いのから実行
実行頻度が偏る
直すための調整->実装の複雑化

2.6以降？

CPUごとにランキュー
CPU間でのプロセス数の偏りが起こる
Reb-Black Tree使う（2分木みたいの
プロセス多くても時間がそんなに変わらない
参照しているところがほぼ左端
:vruntime
|CPU時間の合計と優先度の重み付けした値
:CFS（Completey　Fair　Scheduler)
|CPU時間をできるだけ公平にする

対話型は応答速度が大切
カーネルから対話型、バッチ型を判断できないので
単位時間当たりの実行時間が少ないやつを対話型と仮定して優先度上げる

優先度には固定と変動優先度がある

---

参考

• SoftwareDesign2009/12
• Linuxカーネル解読室