CFS（完全公平スケジューラ）の内部動作

CFSが解こうとした問題

CFS（Completely Fair Scheduler）は Linux 2.6.23（2007年）から長らく標準だった CPU スケジューラです。それ以前の O(1) スケジューラは、優先度ごとの実行キューとヒューリスティックで「対話的か否か」を推定していましたが、推定が外れると応答が乱れる弱点がありました。

CFS の発想は単純です。理想的には N 個の実行可能タスクが、それぞれ CPU を 1/N ずつ同時に使えるべき——この「理想のマルチタスク CPU」を、1コアの現実の上で可能な限り再現します。古典的な方式（/os/scheduling/）が「次の1つ」を優先度やタイムスライスで選ぶのに対し、CFS は「これまで各タスクが受け取った CPU 時間の公平さ」を直接の判断基準に据えました。

vruntime ── 公平さを測る物差し

中心概念が vruntime（virtual runtime、仮想実行時間） です。各タスクは「自分が実際に CPU を使った時間」を、後述の重みで正規化した値として vruntime に積み上げます。

あるタスクが delta_exec ナノ秒だけ走ったとき:

  vruntime += delta_exec * (NICE_0_WEIGHT / weight)

weight はそのタスクの重み、NICE_0_WEIGHT（=1024）は nice 値 0 の基準重み。重みが基準と同じなら vruntime は実時間と同じ速度で進み、重いタスクほど分母が大きく vruntime はゆっくり進みます。

CFS のルールはこれだけです。常に vruntime が最小のタスクを次に走らせる。走れば vruntime が増えて他より大きくなり、やがて別のタスクに順番が回る。結果として、全タスクの vruntime は互いに追いつき追い越しを繰り返しながら、おおむね揃っていきます。これが「完全公平」の正体です。

赤黒木で「最小」を高速に取り出す

「最小の vruntime を選ぶ」を毎回ループで探すと、タスク数に比例して遅くなります。CFS は実行可能タスクを 赤黒木（red-black tree、自己平衡二分探索木） に vruntime をキーとして並べました。

            [ vruntime=120 ]
            /              \
   [ vr=90 ]              [ vr=160 ]
     /   \                    \
[vr=70] [vr=105]            [vr=180]   ← 一番左 = 最小 = 次に走る
   ^
   最小（leftmost）をキャッシュしておけば O(1) で取得

赤黒木は挿入・削除・探索がいずれも O(log N) で完結し、左端（最小ノード）はポインタでキャッシュされるため 次タスクの選択は実質 O(1)。走り終えたタスクは増えた vruntime で木に挿し直され、自然と右側へ移動します。

nice値はどう効くのか

nice 値（-20〜+19、デフォルト 0）は優先度の指定です。CFS は nice を重み（weight）テーブルに変換して使います。設計上、nice が 1 増えるごとに CPU シェアは約 10% ずつ変化するよう、隣り合う重みの比がおよそ 1.25 に取られています。

nice  -20   ...   0    ...   +19
weight 88761  ... 1024  ...   15

例: nice 0（weight 1024）と nice 5（weight 335）が競合すると
   CPUシェア比 = 1024 : 335 ≒ 75% : 25%

重みは vruntime の進み方（前掲の式）と、後述する1タスクあたりの持ち時間の両方に効きます。nice を下げて重みを上げたタスクは、vruntime がゆっくり進むので木の左側に長く留まり、結果として多くの CPU 時間を得る——優先度が「公平の重み」として一貫して効く点が CFS の美しさです。

スケジューリング遅延と最小粒度

公平なら細かく切り替えるほど良いように思えますが、切り替え（/os/context-switch/）はキャッシュや TLB を汚す純粋なコストです。CFS は2つのパラメータでこのトレードオフを調整します。

• 目標遅延（targeted latency, sched_latency_ns）：実行可能な全タスクを最低1回は走らせたい「1周期」の長さ（既定で 6ms 前後）。各タスクの持ち時間は、この周期を重みの比で分け合って決まります。
• 最小粒度（min_granularity_ns）：1回に与える最小の連続実行時間（既定 0.75ms 前後）。これより細かくは切らない下限です。

タスク数が少ないとき:
  各タスクの持ち時間 = 目標遅延 * (自分のweight / 全weightの合計)

タスク数が多くなり、上式が最小粒度を下回るとき:
  周期を伸ばす → 周期 = 最小粒度 * タスク数
  （細かく切りすぎて切替コストで溶けるのを防ぐ）

つまりタスクが少ないうちは応答性を優先して短く回し、タスクが増えたら 周期そのものを伸ばして 切り替え過多を避けます。「持ち時間」は固定値ではなく、その瞬間の実行可能タスク数と重みから動的に算出される点が、ラウンドロビンとの決定的な違いです。

sleep からの復帰と min_vruntime

I/O 待ちなどで眠っていたタスクが起きると、その vruntime は他より大きく遅れています（=値が小さい）。そのまま木へ戻すと、最小 vruntime として CPU を長時間独占 してしまいます。

これを防ぐため、CFS は実行キューごとに min_vruntime（その時点の最小値を単調増加で追う基準） を持ち、復帰タスクの vruntime を min_vruntime 付近まで引き上げてから挿入します。完全には揃えず一定の「ボーナス」を残すことで、対話的（=よく眠る）タスクに適度な応答性を与えつつ、独占は防ぐ——ヒューリスティックに頼らず公平の物差しの上で対話性を扱える設計です。

まとめ

• CFS は vruntime（重み付き実行時間）が最小のタスクを選ぶ という一本のルールで公平を実現する。
• 実行可能タスクは 赤黒木 に並び、最小ノードのキャッシュで次タスク選択は実質 O(1)。
• nice 値は重みに変換され、vruntime の進む速さと持ち時間を通じて CPU 配分を比例的に変える。
• 目標遅延と最小粒度で、タスク数に応じて応答性と切替コストのバランスを動的に取る。
• 並行処理での競合や優先度の扱いは /os/concurrency-control/、スケジュールされる単位については /os/process-thread/ も参照。