CPU スケジューリング 基礎

Linux はコアごとに 1 本のランキューを持つ。グローバルなキューは決定のたびにグローバルなロックを要求するからだ。だから問いは「800 スレッドの誰が走るか」ではなく「このコアのキューの誰が取るか」だ。各コアには走っているタスクが 1 つ座り、残りは待っている。実行可能スレッドを足してほしい：

コアが忙しくなってはいないことに注目 —— 8 スレッドですでに飽和している。伸びるのは各キューの深さで、深さとはレイテンシだ。実行可能 256 なら、自分の順番と次の順番の間に他の 31 個が走る。負荷は CPU を遅くしない。あなたのタスクを遠ざけるだけだ。

その下のただ 1 つのつまみがタイムスライス。短ければ待ちが短くなり切替オーバーヘッドを払う。長ければ仕事が流れ、全員が待つ。最初の境界をドラッグしてほしい：

2 本のバーが反対方向に動くこと、そしてどちらも間違いではないことを見てほしい。4 ms—— 誰かが出荷している定数ではなく、§03 のモデルが 32 コアで実行可能 8 本のときに与える値だ —— ではコアの 1.1%が切替に消え、最悪の待ちは 28 ms。0.25 msにすると待ちは 1.75 ms に潰れ、オーバーヘッドは 15% に上がる。

そのオーバーヘッドは切替命令ではない。切替そのものは左端の細片で、残りは前のタスクが冷やしたキャッシュの再充填だ。ワーキングセットをドラッグしてほしい：

切替は約 1.2 µs —— lmbench の lat_ctx が 3 GHz の x86 コアでフットプリント 0 の 2 プロセスに対して報告する値で、約 3,600 サイクル。レジスタの退避、mm の入れ替え、スケジューラの実行だ。256 KB の再充填は 43.7 µs、その 36 倍。2 ソケットの Ice Lake で 1 コアが DRAM から持続的に得るシーケンシャル読み出しが約 6 GB/s(Intel Memory Latency Checker、--bandwidth_matrix)で、64 バイトのラインは 10.6 ns に 1 本だからだ。これは Linux が配る最短スライスの 6%。2 MBなら 350 µs、周期の半分になる。

固定スライスは Unix が 20 年やってきた方法で、体感できるところで壊れる。キー入力ハンドラを 1 つ 10 ms の計算タスクの列の後ろに置き、100 ms の予算を越えるまで足してほしい：

計算タスク 10 個でキー入力はちょうど 100 ms 待ち、それを越えるとマシンは聞いてくれている感じを失う。ラウンドロビンには直せない。今この瞬間そのハンドラが 9 番目のバッチジョブより価値があると知る術がない。

実行可能なタスクは vruntime というカウンタを持ち、走る間、自分の重みで割った速さで進む。規則は実行可能なうち vruntime が最小のものを走らせる。下では同等の 3 タスクが同じ地点から始まり、最小のものが選ばれて残りの 2 つを追い越す：

規則のどこにも「順番に」とは書かれていないのに、得られるのは順番だ。 9 回の判断のあと各タスクはきっかり 6 ms —— 6 ms の周期のうち 2 ms のスライス。これが不変条件で、実行可能な vruntime はどれも互いに 1 スライス以内に収まる。

その重みが nice だ。Linux は 40 項を持ち、 1 段ごとに約 1.25 倍、vruntime は実時間の 1024 / 重み 倍で進む。 2 番目のタスクを公平な半分から動かしてほしい：

nice 1 段でマシンの約 10% が動く。nice 1 のタスクが 44%、相手のnice 0 が 56%、 −20 から +19 までの全幅は 5,917 倍だ。重みが割るのはキューの門ではなく速さなので、止まるものは何もない：

renice したタスクを +19 で見てほしい —— それでも CPU の 0.73% を取り、他の 2 つは各 50% を保つ。 −20 では 98% を取り、他の 2 つに 1.1% が残る。nice は比率であって拒否権ではない。何も餓死させられず、だからユーザに渡せる。

「最小の vruntime」はティックごとに答えるので、走査であってはならない。 CFS は実行可能集合を vruntime をキーにした赤黒木に置き、答えは常に最左のノードだ。キューを伸ばしてほしい：

実行可能 255 タスクならその走査は 8 段、平坦なリストが読む 255 に対して —— しかも Linux は歩かない。最左ポインタがキャッシュされているからだ。選ぶのは O(1)、O(log n) なのはスライス後の再挿入だけで、コストは書き込み側にある。

そこで規則だけでは答えられない問いが出る。1 秒眠ったタスクは 1 秒ぶん古い vruntime を持って起き、ぶっちぎりで最左になる。眠っていた長さをドラッグし、配置クランプを切ってほしい：

クランプを切ると、200 ms 眠ったタスクには 200 ms の中断なしの CPU が貸し付けられている —— ブロッキング read 1 回でコアを独占でき、どんなプログラムも眠るだけで稼げる。place_entity() は起床時の vruntime をmin_vruntime − sched_latency/2まで引き上げ、どれだけ離れていても取り戻せるのは 3 ms までにする。

CFS は 1 つの約束から始まる。実行可能なタスクはすべてsched_latency(既定 6 ms)以内に CPU を得る。実行可能タスク数で割れば各自のスライスだ。下では周期とスライスが 1 本の軸を共有する：

8 で何が起きるかに注目。8 以下では約束が成り立ち、スライスが縮んでそれを守る。8 を超えるとスライスは0.75 ms の最小粒度を割るので、 CFS は周期のほうを伸ばす。実行可能 32 では「6 ms の目標」は 24 ms、64 では 48 ms だ。

さらに悪いことに、どちらの定数もその定数ではない。両方とも起動時に1 + ilog2(ncpus) を掛けられるので、カーネルが実際に走らせる目標レイテンシは、起動時に数えたコアの数で決まる。コア数をドラッグしてほしい：

32 コア機は目標レイテンシ 36 msと粒度 4.5 ms で起動する —— 前段落の数字の 6 倍で、実行可能 32 のときの周期は 24 ms ではなく 144 ms だ。誰かに 6 ms と言う前に /sys/kernel/debug/sched/latency_ns を読むこと。

他の誰かのほうがコアに値するとき、スライスは早く終わる。起床時、CFS は 2 つの vruntime を比べ、差が起床粒度を上回るときだけ奪う。起床側を近づけたり遠ざけたりしてほしい：

1 ms 以内なら起床側は切替に値しない —— 1 ミリ秒に満たない利得に 44.9 µs を払うことになる —— のでカーネルは実行中のタスクを走らせきり、次のティックで帳尻を合わせる。「時間通りに起きたのに走り出したのは 4 ms 後」の正体で、nice では動かない。

この確認がティック上で起きるので、ティックが上のすべての実解像度だ。ここでは0.75 ms のスライスがティックの間で終わり、終わりを越えて持ち続けるぶんが超過になる。CONFIG_HZ を変え、次にプリエンプションモデルを切り替えてほしい：

よくある CONFIG_HZ=250 ではティックは 4 ms なので、0.75 ms のスライスは気づかれずに 4 ms —— 予算の 5 倍以上 —— 走れる。その超過が p99 だ。PREEMPT_FULL はゼロにしてスループットで払う。

CFS の弱点は公平性ではなく、レイテンシの近くのつまみがすべてヒューリスティックだったことだ。 §02 の睡眠ボーナスが 1 つ、 §03 の起床粒度がもう 1 つ、どちらも昔調整された定数だ。

その量が lag だ。今の時点でそのタスクが受け取るべきだったサービス量から、実際に受け取った量を引いたもの。lag ≥ 0のタスクは適格で、先に進みすぎたタスクは適格でない —— そもそも選ばれない。ここでは T2 が 4 ms 先行して現れる。サービス量を進め、取り返していく様子を見てほしい：

適格性は罰ではなく門だという点に注目。T2 は罰せられず、 4 ms を失いもしない。他の 2 つが追いつく総サービス量 8 ms まで選ばれないだけで、そこで 3 つの lag はすべて 0 になる。不変条件はlag の総和が常に 0 だということ。

2 つめの語が仮想デッドラインだ。各タスクはリクエストサイズ r を申告し、ve + r/重み というデッドラインを得る。適格な中で最も早いものが勝つ。リクエストをドラッグしてほしい：

小さいリクエストは早いデッドラインを意味するので、少なく求めることが出番の多さを買い、切替で払う。既定の 0.75 ms は 4 タスクに 2.25 ms の上界を毎秒 1,333 回の切替で与える。0.1 ms なら上界 0.3 ms、毎秒 10,000 回 —— 1 回 44.9 µs でコアの 45% を食う。

肝心なのはタスク自身が選ぶことと、取り分とレイテンシが切り離されたことだ。ここでは同じ 3 タスクを両方のスケジューラで走らせる。T2 は 0.75 ms を要求し、他の 2 つは 3 ms を取る。 2 本とも走り終えている —— どちらかが埋まる様子を巻き戻して見てほしい：

どちらも T2 にきっかり 33% の CPU を与える —— EEVDF が気前よくなったのではない。変わったのは形だ。出番は 3 回ではなく 5 回、最長の空白は 4.0 ms ではなく 3.0 ms。CFS では要求する手段がなく、レイテンシに敏感なスレッドは優先度が高いふりをするしかなかった。

Linux は公平クラスの周りにさらに 5 つのクラスを厳格な順序で置く。スタックの上にあるクラスに実行可能タスクがあればそれが勝ち、nice は口を挟めない。タスクを上下に歩かせ、それが上回るクラスを通り過ぎてほしい：

これは重み付けではなく順位だという点に注目。実行可能な SCHED_FIFO タスクはその下の 4 クラスを奪い、自分がブロックするまでコアを離さない。nice が動かすのが比率なら、クラスが動かすのは絶対的な拒否権だ。

SCHED_DEADLINE はさらに進み、スケジューラが唯一「否」と言う場所になる。(runtime, deadline, period) を申告すると、カーネルは利用率を合計して帯域の上限と比べる。新しいタスクの要求量を上げてほしい：

20% を超えると合計が 95% を越え、sched_setattr() はEBUSY を返す —— そのタスクは起動すらしない。起動してから後でデッドラインを落とすのではない。それが保証と優先度の違いだ。保証は、あなたを断れなければならない。

厳格な順位には明らかな壊れ方が 1 つあり、Linux はシートベルトを積んでいる。ここでは決してブロックしない SCHED_FIFO ループがコアを握り、帯域の予備があなたの shell の全財産だ。sched_rt_runtime_us を最大までドラッグしてほしい：

既定の 1,000,000 µs あたり 950,000 では毎秒 50 msが残る —— 200 ms の shell コマンドが「永遠に終わらない」ではなく 4 秒で終わる量だ。予備をゼロまで押すと読み値は数字を出すのをやめる。shell もなく、SSH もなく、ログもなく、復旧手段は電源ボタンだけになる。

より見えにくい壊れ方にはバグすら要らない。ここでは低優先度のタスクがロックを持ち、高優先度のタスクがそこでブロックし、どちらも必要としない中優先度のタスクが保持者を奪う。ミューテックスを切り替え、どちらの版も巻き戻して見てほしい：

高優先度のタスクは素のミューテックスで 11 ms、優先度継承つきで 5 ms —— 自分が上回るタスクの後ろで、無関係なタスクが走りたかっただけ待たされていた。1997 年、Mars Pathfinder を止めたのがこれだ。PTHREAD_PRIO_INHERIT が直すのはミューテックスだけで、スピンロックは変わらず逆転する。

cpu.max は重みではなくハードな上限だ。グループは 100 ms の周期ごとにクォータぶんの CPU マイクロ秒を得て、使い切ると次の周期まで凍結される。罠は、クォータが並列に消えることだ。スレッドを足すか、クォータの境界をドラッグしてほしい：

200 スレッドの JVM が 1 コアぶんのクォータに当たると、32 スレッドが同時に走るのでクォータは3.13 ms で消え、残る 97 ms は凍る。見えるのは 97 ms の停止だけで、CPU 圧も GC ポーズもログも何もない。

直感は、周期を短くして凍結を短くすることだ。cpu.cfs_period_us を下げ、最悪の停止を読んでほしい：

効く —— 10 ms の周期は停止を 9.7 ms に抑える —— そして毎秒 10 回ではなく 100 回の強制点を払う。本当の修正は上流にある。ランタイムに実際のコア数を教えること(GOMAXPROCS、-XX:ActiveProcessorCount)。nproc はホストを返す。

2 つめは、ロードバランサが正しく仕事をした結果だ。タスクをアイドルのコアへ移すと待ち時間は縮み、冷えたキャッシュへの切替を払う。タスクを移し、それからワーキングセットを上げてほしい：

256 KB なら 6 個中 3 個を移すのは0.14 ms の移動費で1.0 ms の待ちを節約する。2 MB では同じ移動が 1.0 ms を節約するのに 1.1 ms かかり、6 個すべてなら節約ゼロで 2.1 ms —— 不均衡が反対側に移っただけだ。sched_migration_cost_ns があるのはこのためだ。

最後の 1 つはスケジューラのものですらないが、スケジューラを通って届く。 2 ソケット機ではメモリはソケットに付いているので、バランサが移したスレッドは手元ではなくリンク越しに読む。その割合をドラッグしてほしい：

Intel の Memory Latency Checker は 2 ソケットの Ice Lake でローカル 85 ns、リモート 139 nsを測る —— 1.64 倍だ。top は何も教えてくれない。 Linux はファーストタッチで割り当てるので、「起動スレッド 1 つが大きなヒープを確保し 40 スレッドが使う」形がいつも壊れる。

pick_next(rq):              # the whole policy
  V = avg_vruntime(rq)      # the fair-share clock
  ok = [e for e in rq if e.vruntime <= V]
  return min(ok, key=lambda e: e.deadline)

覚える価値のある落差は 3 段目から最後の段まで。切替はマイクロ秒、スロットルされた cgroup 周期は 97 ms。上ではスライスと nice で調整でき、下ではクォータと議論している。

実行可能 32 では並んだほうが 88 ms、空いたコアの 2 ms に対して 44 倍 —— プロファイラには映らない。cpu.stat とperf sched latency を読むこと。

レビューでの赤信号

• コンテナ内で nproc からスレッドプールを決める。返るのはホストの数だ。
• ウォッチドッグのない SCHED_FIFO。マシンが消える。
• リアルタイムスレッドのミューテックスにPTHREAD_PRIO_INHERIT がない。逆転する。
• 6 ms をレイテンシ目標として引用する。起動時に拡大される。