Linux Kernel Development第四章のスケジューリング問題の記述

柴田芳樹さんが主催する勉強会(http://yshibata.blog.so-net.ne.jp/2010-07-23)の準備で「Linux Kernel Development 3rd edition」を読んでいる。

第三章までは比較的すらすら読めたが、第四章で読みづらかった部分(P47,48)があった。
後々忘れるといけないので、メモっておく。

Process Scheduling in Unix Systems
最近のプロセススケジューラには二つの概念がある。
1.プロセス優先度
2.タイムスライス

優先度の高いプロセスがより頻繁に、より長いタイムスライスを得ることができる。

優先度はnice値の形をとってユーザ空間に公開している。実際にはこのことが問題を引き起こす。

問題1.nice値が低いプロセスと高いプロセスのある種の組み合わせによる挙動
それぞれのnice値に割り当てるタイムスライスの絶対値は何かを決める必要がある。これは次善のスイッチングの振る舞いを導く。
例えばnice値が0でタイムスライスが100msのプロセスAとnice値が+20でタイムスライスが5msのプロセスBが居るとする。
確かにプロセスAとプロセスBが一つずつ居る場合は問題にならないが、プロセスBが二つ居る場合、5msごとに一度頻繁なスイッチングが発生し、プロセスAが二つだと100msに一度スイッチングが発生する。
優先度が高いプロセスがフォアグラウンドで、低いプロセスはバックグラウンドで動くことを考えると、この振る舞いは理想から遠い。

問題2.nice値の「価値」について
相対的なnice値とタイムスライスの割り当てについて。
例えば、nice値が0と1の場合、タイムスライスの割り当ては100msと95ms。
しかし、nice値が18と19の場合は10msと5ms。
nice値が1違うだけなのに、タイムスライスの絶対値の「価値」が異なってしまう。
(nice値が18と19の場合、タイムスライスが倍の差となってしまう。)

問題3.タイムスライス値の単位
nice値とタイムスライスの割り当てをするにあたり、カーネルが測定できる指標と結びつける必要がある。
通常、タイマティック値の整数倍の値と結びつけることになる。
（要は、「タイムスライス値」はタイマティック値を単位として扱わないといけないということである。)
ところがLinuxの場合、タイムスライス値の単位が1msの場合と10msの場合があり、粒度が異なるため、単純にティック単位で扱うとまずいことになる。

4.インタラクティブなプロセスに対する不公平なスケジューリング
インタラクティブな性質のプロセス向けに最適化された優先度ベースのスケジューラではタイムスライスを使い果たしてもすぐに実行対象として選ばれる。このことはインタラクティブな性質のプロセスの反応は大抵よくなるが、他のプロセスに実行権がまわらなくなり不公平なスケジューリングとなる。

これらの問題(2,3)については例えばタイムスライスとnice値の割り当て方法を変えたり、タイマティック値に応じた計算をするという手もある。
しかし、結局真の問題(恒常的なスイッチングと「気まぐれな」公平さ、つまりスイッチングがバカスカ起きるだけで公平なスケジューリングが実現できない)は解決できていない。

そこで、CFSスケジューラのご登場となるわけだ。
CFSスケジューラがこうした問題をどう解決しているのか、ここから先の記述が楽しみだ。
あと、BSDのスケジューラなどと何が違うのか、この点も楽しみである。