9月版 帰ってきたCon Kolivas、大論争を呼ぶの巻
小崎資広
2009/10/14
本邦初？ あまり知られていないCFS概略
さて、ここでMikeの改善の解説に入る前に少し話を脱線して、CFSの概略について説明しましょう。CFSはドキュメントが非常に少なく（注5）、いきなり内部パラメータの解説をしても全然楽しくない記事になってしまうので、若干数式が多くなりますが、ご勘弁ください。
| 注5：かつカーネルに付属しているドキュメントはすでに古くなっていてうそまみれ。実はまともな解説としては、この記事が世界初かもしれません。 |
CFS（Complete Fair Scheduler）は、まず、以下のルールによってスケジューリング周期を求めます。
sched_latency = 20 msec × (1＋log2(ncpus)) [ncpusは論理CPU個数] |
この周期で全タスクが1回動作できるように、タスク数で割り算を行います。ただし、nice値によりボーナスを与える必要があるので、それぞれのタスクの重みを以下の計算式で求めます。
weight = 1.25 ^ (-nice) |
そして、それぞれのタスクのタイムスライス（注6）を、
slice = period × weight/total-wight |
によって求めることができます。タスクがI/Oなどにより動作する権利を自発的に放棄することにより、1周がperiodよりも短くなることはあるが、periodは全タスクが限界までCPUを使用した場合の1周にかかる時間になるので、これがスケジューラ・レイテンシの基準値となります。
別の視点から説明すると、CPUコア数とレイテンシ・ターゲット（sched_latency）との関係は、以下のようになります（CPUは1つと仮定します）。
single-core: 20 msecs |
このslice配分方式は、タスク数の増加と応答性に相関関係がないので優れたやり方ですが、タスク数が多くなると、際限なくスライスが短くなっていき、コンテキストスイッチコストがどんどん上がっていってしまいます。よって、CFSではスケジュール時間の最小値が決まっており、periodは以下の修正式を使います。
sched_min_granularity = 4 msec * (1 + log2(ncpus)) |
このように、CFSではタイムスライスがシステム負荷に応じて動的に変化します。これをもって「CFSにはタイムスライスがない」と表現しているドキュメントもあります。
割り当て時間が決まったら、次は割り当て順序です。CFSはここで「vruntime」という仮想的なタスク動作時間を導入します。vruntimeは動作時間にniceによる重みを加味したもので、
vruntime = 動作時間 × 1.25 ^ nice |
で表すことができます。これにより、vruntimeの小さい順にタスクをソートすることにより、nice値（注7）を加味したうえでの最も動作時間が短いタスクを選ぶことができます。CPU boundなタスクよりもインタラクティブタスクを優先するのは、スケジューラの基本ですね。
ここで、スケジューラはタスク起床時に、vruntimeに対して1つ調整を行います。vruntimeは走り続けているタスクにペナルティを与え、running状態だが実行待ちになっているタスクにボーナスを与える仕組みであって、寝続けているタスクにボーナスを与えるためのものではありません。このため、寝ていたタスクが起床したときは、そのタスクのvruntimeは、running状態のタスク群のvruntimeの最小値まで繰り上げられます。
これにより、常にvruntimeが最小値のタスクをスケジューリングするだけで、period時間に全タスクに動作権を1回以上回すことができるようになります（この調整がなければ、10分間寝ていたタスクは起床後10分間動作する権利を得てしまい、レイテンシ・ターゲットが台無しになってしまいます）。
また、この動作順序ルールには3つの例外があります。
（1）高速にwakeupとsleepを繰り返しているタスクが複数ある場合を考えてみます。素直にvruntime順に動作させようとすると、タスクがwakeupするたびにtask preemptionが動いてしまい、スケジューラが頻繁に動き過ぎて、コンテキストスイッチ・コストが大きくなり過ぎます。そこで、起床してきたタスクと現在走行中のタスクのvruntimeの差が、以下の式で表されるsched_wakeup_granularity以下の場合は、preemptionをしばらく遅延する仕組みが実装されています。
sched_wakeup_granularity = 5 msec * (1 + log2(ncpus)) |
（2）（1）の効果により、preemptに失敗したタスクは、次の走行タスク選定フェイズにおいて若干のボーナスを得ることができます。具体的には、最小のvruntimeを持つタスクのvruntime＋sched_wakeup_granularity×1.25 ^ niceより遅延タスクのvruntimeが小さいときは、vruntimeが最小でなくても優先して起床されます。これを「next-buddyルール」といったりもします。
（3）インタラクティブタスクがpreemptして、すぐさまsleepしたケースを考えます。このときの走行タスク選定ですが、単純にvruntime順に決定すべきでしょうか？ 答えはNoです。preemptされたタスク（1つ前に動作していたタスク）は、高い確率でまだキャッシュに残っています。キャッシュ・ホットなタスクに（レイテンシが許容する範囲で）若干のボーナスを与えることにより、スループットを向上させることができます。このボーナスにも前述のsched_wakeup_granularityが使われます。これを「last-buddyルール」といったりもします。
| 注6：タイムスライスとは、プロセスの走行時間の区切りとなる時間で、タイムスライスが100msのシステムでは、「プロセスAが100ms動いた後、プロセスBが100ms動き、その後、プロセスCが100ms動く」という動作になります。タイムスライスが短か過ぎるとコンテキストスイッチ・コストが大きくなり過ぎ、タイムスライスが長過ぎるとシステムの応答性が悪くなりもっさりした印象を与えてしまいます。使用するアプリケーションによって応答性とスループットの重要度が変わるため、例えばWindowsなどではサーバ向けとクライアント向けでタイムスライスを変えて出荷しています。 注7：nice値とは、niceコマンドによって設定されるプロセスの優先度を示し、−20（最高）から＋19（最低）までの40段階の優先度を表します。nice値を変えることによる影響はOSにより大きく異なっており、スケジューラの性格が表れる部分です。 |
| ■コラム スケジューラ・パラメータのチューニング | |
|
前述のように、これらのスケジューラ・パラメータは、/procの以下のエントリによって変更することができます。レイテンシとスループットの調整は有用ですので、覚えておくとよいでしょう。
|
さて、Mikeのパッチは何を変えたのか
ここまで書いてやっと、今回の改善点の説明に入れます（ぜーはー、ぜーはー）。前述のとおり、Mikeは4つの改善を提案しました。
- NEW_FAIR_SLEEPERSの廃止
- child_runs_firstの廃止
- デフォルト・レイテンシターゲット値の調整
- カーネルスレッドのnice値ボーナスの廃止
順に説明していきます。
■NEW_FAIR_SLEEPERSの廃止
NEW_FAIR_SLEEPERSとは、タスクの起床時にvruntimeを（最小vruntimeではなく）min_vruntime - sched_latencyに調整する仕組みです。つまり、起床直後はsched_latency分だけ余分に動作できるよう、ボーナスが受け取れるということです。これにより、CPU boundのタスクに対してインタラクティブタスクがボーナスを得ることができます。
ところが、よく考えてみるとこのボーナスは変です。インタラクティブタスクの実行中にバックグラウンドタスクが起床してきたときも、sched_latencyのボーナスを受け取るため、インタラクティブタスクはsched_latency時間分、動けなくなります。そして、20msecというのは、マウスカーソルの処理落ちを発生させるのに十分な時間です。よって、Mikeはこのfeatureを完全にOFFにした方が応答性が上がると指摘しました。
なお、この仕組みはv2.6.24で導入されていました。このパラメータは/sys/kernel/debug/sched_featuresで調整可能です（v2.6.32より名前がまた変わる予定なので注意が必要です）。
■child_runs_firstの廃止
child_runs_firstは、fork()実行時に、子プロセスが親プロセスよりも先に実行するようボーナスを与える仕組みです。Linuxにおいてfork()直後にexec()を呼ぶケースは非常に多いので、子プロセスを先に動かすことにより、親プロセスが無意味にCOW（Copy On Write）を発生させてしまうことを防げます。
ところで、上記の説明はCPUが1つしかないとの仮定に立ったものです。しかしSMP環境下においては、話はそう単純ではありません。親プロセスが走り続けていた方が、CPU間の負荷バランス処理によって子供が別CPUに移動し、両プロセスが同時に走行するという理想的な状態になりやすいからです。デスクトップでもSMPが普通になり、また、実際にカーネルコンパイルが高速化している以上（注8）、このデフォルト値を1のまま据え置く理由がないと指摘されました。
なお、このパラメータはv2.6.23では0がデフォルトだったのですが、bashのタイミング障害を引き起こしやすくなってしまうという問題があり、v2.6.24で変更されたという経緯があります。Linusは、「もう2年もたったんだし、大丈夫じゃないか？」との見解を示しました。このパラメータは、/proc/sys/kernel/sched_child_runs_firstにて調整可能です。
| 注8：カーネル開発者にとって、最も重要なベンチマークですね :-) |
■デフォルト・レイテンシターゲット値の調整
デフォルト・レイテンシターゲット値の変更では、前章にて解説した、レイテンシ関係のデフォルト値をそれぞれ以下の値に縮小しています。
sched_latency = 5 msec * (1 + log2(ncpus)) |
デフォルト値がCPU数のlogに比例していたのには、2つの理由がありました。1つはCPU数が増えれば、あるCPUでpreemptできなくても別CPUで動作できるので、ユーザーがレイテンシを体感できなくなること。もう1つは、CPUの個数とOSの利用用途には強い相関関係があるからです。100CPUのマシンをデスクトップ用途に使う人はいません。
ところが、近年の急激なマルチコア化の進展により「デスクトップは普通1CPU」という常識は過去のものとなってしまいました。このため、デフォルト値の再調整を図るべき、という提案がなされました。
■カーネルスレッドのnice値ボーナスの廃止
最後は、ちょっと異色なのですが、カーネルスレッドのnice値の再調整が図られました。
従来カーネルスレッドは−5のnice値で初期化されていました。しかし、nice値−5は、nice値0のプロセスに比べて約3倍（＝1.25^5）もの大きなボーナスであることを意味します。Mikeは「そんなに長時間動作し続ける行儀の悪いカーネルスレッドは1つもない。これはvruntimeの計算負荷を上げているだけで、何の意味もないではないか」と指摘しました。確かに、導入時のcommit logを見ても、nice値ボーナスを与える理由は一言も説明されておらず、このnice値削除に反対するデベロッパは1人も現れませんでした。
Sergeはこの4パッチが当たった状態で、並列makeについて再測定し、以下のグラフのように「まだv2.6.23には及ばないが、差は3％まで縮んだ」と報告しました。
 |
| Sergeが行った並列makeの再測定結果（クリックすると拡大します） |
さまざまなデベロッパがこの問題に取り組んでいるので、性能がBFSに追いつく日も近そうです。
 |
3/3 |
|
|
||||||
|
||||||
 |
連載 Linux Kernel Watch |
| Linux Squareフォーラム Linuxカーネル関連記事 |
 |
連載：Linux Kernel Watch（連載中） Linuxカーネル開発の現場ではさまざまな提案や議論が交わされています。その中からいくつかのトピックをピックアップしてお伝えします |
|
連載：Linuxファイルシステム技術解説 ファイルシステムにはそれぞれ特性がある。本連載では、基礎技術から各ファイルシステムの特徴、パフォーマンスを検証する |
|
特集：全貌を現したLinuxカーネル2.6［第1章］ エンタープライズ向けに刷新されたカーネル・コア ついに全貌が明らかになったカーネル2.6。6月に正式リリースされる予定の次期安定版カーネルの改良点や新機能を詳しく解説する |
|
特集：/procによるLinuxチューニング［前編］ /procで理解するOSの状態 Linuxの状態確認や挙動の変更で重要なのが/procファイルシステムである。/procの概念や/procを利用したOSの状態確認方法を解説する |
|
特集：仮想OS「User
Mode Linux」活用法 Linux上で仮想的なLinuxを動かすUMLの仕組みからインストール／管理方法やIPv6などに対応させるカーネル構築までを徹底解説 |
|
Linuxのカーネルメンテナは柔軟なシステム カーネルメンテナが語るコミュニティとIA-64 Linux IA-64 LinuxのカーネルメンテナであるBjorn Helgaas氏。同氏にLinuxカーネルの開発体制などについて伺った |
|
- 【 pidof 】コマンド――コマンド名からプロセスIDを探す （2017/7/27）
本連載は、Linuxのコマンドについて、基本書式からオプション、具体的な実行例までを紹介していきます。今回は、コマンド名からプロセスIDを探す「pidof」コマンドです。 - Linuxの「ジョブコントロール」をマスターしよう （2017/7/21）
今回は、コマンドライン環境でのジョブコントロールを試してみましょう。X環境を持たないサーバ管理やリモート接続時に役立つ操作です - 【 pidstat 】コマンド――プロセスのリソース使用量を表示する （2017/7/21）
本連載は、Linuxのコマンドについて、基本書式からオプション、具体的な実行例までを紹介していきます。今回は、プロセスごとのCPUの使用率やI/Oデバイスの使用状況を表示する「pidstat」コマンドです。 - 【 iostat 】コマンド――I/Oデバイスの使用状況を表示する （2017/7/20）
本連載は、Linuxのコマンドについて、基本書式からオプション、具体的な実行例までを紹介していきます。今回は、I/Oデバイスの使用状況を表示する「iostat」コマンドです。
 |
|
|
|
|
