CPU スケジューリング基礎

我々の 32 コアサーバは何百のスレッドを走らせる —— curl ハンドラ、DB ワーカー、カーネルスレッド、JVM の GC —— 任意の瞬間に走れるのは 32 個まで。カーネルが選ぶ。 5 セクションで全体像を組み立てる:スケジューリング問題と「公平」とは何を意味するか;CFS + 対話的な vruntime ウォーカ、Linux が次に走らせる者をどう決めるか; CFS が正解でないケース向けの優先度、nice 値、リアルタイムクラス;cgroup と NUMA —— 現代のコンテナとマルチソケットの制約; 最後にクイックリファレンス。

スケジューリング問題

数百のスレッドが実行可能。CPU は数十個。スケジューラが「誰がどれだけ走るか」を秒間数千回選ぶ。正解はない —— トレードオフだけ。

忙しいサーバでは任意の瞬間に 32 コアと 800 個の実行可能スレッドがあり得る。スケジューラは ~1 ms ごと(CFS スケジュールティック)に、次にどの 32 スレッドを走らせるか決めなければならない。各選択に帰結がある:

公平性。同等のスレッドは長期で同等の CPU を得るべき —— しかし「同等」とは?等しいサイクル?等しい壁時計時間?優先度で重み付けされた等しさ?
スループット。システムは有用な仕事を最大化すべき。頻繁すぎるスイッチはオーバーヘッドに時間を浪費;稀すぎるスイッチは I/O 律速タスクを餓死させる。
レイテンシ。入力を受けたばかりのインタラクティブタスクはすぐ走るべき、シェアを超えて取っていても —— ユーザが待っている。
優先度。リアルタイムオーディオスレッドがデッドラインを逃すとスピーカからクリック音が出る;バックアップジョブが 5% 遅くなっても誰も気にしない。両者は同等に扱えない。
アフィニティ。スレッドのキャッシュ状態は最後に走ったコアに住む。別のコアに弾くと ~100 μs の冷キャッシュの後悔がかかる。しかしピン留めはロードバランシングを失う。
電力。スマートフォンやラップトップでは、寝ているコアを起こすとミリ秒級のレイテンシとエネルギーがかかる。仕事を起きているコアに集約する方が、利用可能なすべてのコアに広げるより良い。

これらのゴールは衝突する。スループット最適化はレイテンシを傷つける。厳格な優先度は低優先度タスクを餓死させる。完全なアフィニティはロードバランスを失う。あらゆるプロダクションスケジューラはデフォルトとして 1 セットのトレードオフを選ぶ妥協。

簡単な歴史

ラウンドロビン(1970–80 年代)。各タスクが固定タイムスライス (10–100 ms)を得て譲る。シンプルで公平、しかし反応が鈍い —— キープレスを受けたばかりのインタラクティブタスクは計算ジョブの列の後ろで待つ。

多段フィードバックキュー(Unix、BSD、初期の Linux)。複数の優先度キュー;タスクは観察された挙動に基づいてキュー間を動く (CPU 律速タスクは下降、I/O 律速タスクは上昇)。レイテンシは改善するが、ポリシーのチューニングは Unix の方言ごとに異なるアート。

O(1) スケジューラ(Linux 2.6、2003 年)。CPU ごとのランキュー、2 つの優先度配列(active と expired)、最高優先度の実行可能タスクを見つけるための配列ウォーク。当時のシングル CPU ベンチマークで高速だったが、ヒューリスティックチューニングは絶え間ない戦い。

CFS(Linux 2.6.23、2007 年以降)。ヒューリスティック優先度ブースティングを 1 つの数学規則で置き換えた: 「仮想実行時間が最小のタスクを選ぶ」。次節で歩く。

EEVDF(Linux 6.6、2023 年)。CFS をより柔軟な「最早適格仮想デッドライン優先」アルゴリズムベースのスケジューラで置き換える。同じ原理(vruntime)だがレイテンシ保証が良く、定式化がきれい。まだロールアウト中;執筆時点で大半のプロダクションカーネルは依然 CFS を使用。

要点。「スケジューリングは公平性、スループット、レイテンシ、優先度、アフィニティ、電力を相互にトレードオフする。CFS はチューニングノブを 1 つの規則 —— 最小 vruntime 優先、nice で重み付け —— で置き換え、汎用の戦いに勝った。 EEVDF(Linux 6.6+)はその後継;同じ vruntime 原理、より良いレイテンシ数学。」

CFS —— 汎用ケースに対する 1 つの規則

Completely Fair Scheduler は 10 年分のヒューリスティックを 1 行で置き換えた: 「実行可能タスクのうち vruntime が最小のものを選ぶ」。この規則だけで公平な分配、優先度の重み付け、合理的なレイテンシが生まれる。

各実行可能タスクは vruntime と呼ばれるカウンタを持つ、単位はナノ秒。タスクが走ると vruntime が増える —— nice-0 タスクは壁時計レート、低優先度はより速く、高優先度はより遅く。スケジューラはタスクを vruntime をキーとする赤黒木に保持するので、最左(vruntime 最小)のタスクは O(log n) で見つかる。そのタスクが次に走る。

nice が vruntime レートにどうマップされるか

Linux はウェイトテーブルを定義する:nice 0 = ウェイト 1024、 nice ±1 ごとにウェイトは ~1.25 倍変わる。nice +10 ≈ ウェイト 110(~9× 少)、 nice -5 ≈ ウェイト 3121(~3× 多)、nice -20 ≈ 88761(~87× 多)。

走っているタスクの vruntime 増分は actual_runtime × (NICE_0_LOAD / task.weight)。だから nice-0 タスクは壁時計レートで vruntime を蓄積する。nice-10 タスクは ~9× 速く蓄積 —— 他者が追いつくまで再選択を待つ必要があるので、~1/9 の壁時計シェアを得る。 nice-(-20) タスクは ~87× 遅く蓄積し、スケジュールを支配する。

鍵となる言葉は「乗算」。厳格な優先度は「高優先度タスクが常に先に走る」を意味する —— 低い方を餓死させる。CFS は vruntime 蓄積に重み付けするので、両タスクとも常に進捗する; 高優先度の方が比例的により進捗するだけ。

1 / 8

CFS の決定全部は「実行可能タスクの中で vruntime が最小のものを走らせる」。 nice が同じタスクは同じレートで vruntime を蓄積するので、順番に走る。 nice +10 のタスクは nice 0 の ~9 倍速く蓄積するので、~1/10 の壁時計シェア; nice -5 のタスクは ~3 倍遅く蓄積するので、~3 倍のシェア。 CFS は古い固定タイムスライス・スケジューラを 1 つの数学的にきれいな規則で置き換えた。

レイテンシターゲットと最小粒度

CFS はターゲットレイテンシ(大半の設定でデフォルト 6 ms)を定義する —— 各実行可能タスクはこのウィンドウ内に走る機会を得るべき。レイテンシをタスク数で割ると各タスクのスライスになる。 nice 同じ 3 タスクなら 2 ms ずつ;30 タスクなら 0.2 ms —— しかしそれはコンテキストスイッチオーバーヘッドでスループットを潰す。 CFS は最小粒度(デフォルト 0.75 ms)を強制する: どのタスクのスライスもこれより短くならない、たとえターゲットレイテンシを延ばすことになっても。

したがって 30 個の実行可能タスク:レイテンシは 6 のままではなく 30 × 0.75 = 22.5 ms に伸びる。これが CFS が高負荷下で反応が鈍く感じる理由の 1 つ —— 実際のレイテンシ約束は実行可能スレッド数によってのみ制限される。

ウェイクアッププリエンプション

タスクがウェイクアップするとき(例:I/O が終わった、または別のタスクがpthread_cond_signal した)、CFS はその vruntime が現在実行中タスクをプリエンプトするのに「ふさわしい」ほど小さいかチェックする。そうなら —— そして実行中タスクが少なくとも最小粒度走っているなら —— カーネルがスイッチをスケジュールする。これがインタラクティブタスクを応答的にする仕組み: ネットワーク読みでブロックしているスレッドはスリープ中に vruntime を蓄積しないので、読みが返ったときに非常に低い vruntime を持ち、即座に走る権利を得る。

CFS が扱わないもの

CFS はすべての SCHED_NORMAL(別名 SCHED_OTHER)タスクを扱う。リアルタイムタスクは扱わない —— それらは次節で扱う別のスケジューリングクラス(SCHED_FIFO、SCHED_RR、SCHED_DEADLINE)が扱う。リアルタイムタスクは vruntime にかかわらず常に SCHED_NORMAL をプリエンプトする; CFS はリアルタイムキューが空になってから初めて選ぶ。

要点。「CFS の規則は 1 行:実行可能タスクのうち vruntime 最小のものを選ぶ。 nice 値は vruntime がどれだけ速く蓄積するかに重み付けする —— nice +10 は ~9× 速い(~1/9 シェア)、nice -5 は ~3× 遅い(~3× シェア)。ターゲットレイテンシ(デフォルト 6 ms)と最小粒度(デフォルト 0.75 ms)がスライスサイズを縛る。 CFS はリアルタイムタスクを扱わない;それらには別のスケジューリングクラスがある。」

優先度、nice、リアルタイムクラス

ほとんどのコードは CFS の公平規則の下で走る。ひと握りのケース —— オーディオ、産業制御、ハードリアルタイム —— はより厳格な保証が要る。 Linux はそれらに 4 つの追加スケジューリングクラスを与える、厳格な優先順位で。

各 Linux タスクは 1 つのスケジューリングクラスに属する。高優先度から低へ:

SCHED_DEADLINE —— 最早デッドライン優先 + 帯域強制。各タスクは (runtime、deadline、period) を宣言する; スケジューラは総帯域が収まる場合のみ受理し、各 period 内でデッドラインまでに runtime を走らせることを保証する。ハードリアルタイム用:産業制御、自動運転スタック、低レイテンシオーディオパイプライン。
SCHED_FIFO —— 固定優先度、完了またはブロックまで走る。高優先度 FIFO タスクは常に低優先度をプリエンプト。同優先度 FIFO タスク間にタイムスライスなし。 POSIX からの古典的「リアルタイム」ポリシー。オーディオサーバ(JACK)、一部のゲームエンジン、ロボティクス。
SCHED_RR —— FIFO に似るが同優先度タスク間でラウンドロビンタイムスライスがある。同優先度 RR タスクは交互する;異なる優先度は依然厳格。
SCHED_NORMAL(別名 SCHED_OTHER)—— CFS。99% のものがこれで走る。
SCHED_BATCH —— NORMAL に似るがタスクが CPU 律速だとスケジューラに伝え、ウェイクアッププリエンプションを抑制する。バックグラウンドコンパイル、ビッグデータジョブ用。
SCHED_IDLE —— CFS 内で最低可能優先度。他のどの SCHED_NORMAL タスクも走りたがらないときのみ走る。cron ジョブ、最後の手段の GC。

nice —— SCHED_NORMAL のつまみ

SCHED_NORMAL 内で nice が優先度の重み付けを調整する。範囲 -20(最高ウェイト)から +19(最低)。デフォルトは 0。各単位がウェイトを ~1.25× 変える;累計範囲は約 1000×。ほとんどのコードは nice に触れない —— スケジューラが処理する。例外:

nice 19 をバックグラウンドコンパイルやバッチジョブに、インタラクティブ作業に譲るように。古典的な nice -n 19 make イディオム。
nice -10 以下(CAP_SYS_NICE 必要)を、プリエンプション優先度が欲しいがハードリアルタイム保証は要らない低レイテンシサーバプロセスへ。データベースマスタープロセス、ネットワークパケットプロセッサ。

リアルタイムのリスク

ブロックしない SCHED_FIFO タスクはシステム全体を餓死させ得る。スケジューラは何のためにもプリエンプトしない(より高優先度の FIFO タスク、割り込みのようなカーネル作業、または別の SCHED_DEADLINE デッドラインを除く)。SCHED_FIFO タスク内のwhile (true); のようなバグはマシンをロックする —— シェルなし、ログなし、SSH ログインなしで、再起動以外に救えない。

Linux はこれを sched_rt_runtime_us で緩和する:デフォルトでリアルタイムスケジューラは任意の 100 ms ウィンドウで最大 95% を許可され、SCHED_NORMAL に 5 ms を残す。これが暴走したリアルタイムタスクから回復させる。SCHED_FIFO をデプロイする人は誰もこの設定を知るべき。

cgroup CPU 制御 —— スケジューリングクラスと直交

cgroup(次節で扱う)はスケジューリングクラスの上に第 2 層を課す: CPU shares(比例重み)、CPU quota(ハード上限)、CPU set(許可されたコア)。 cgroup 内で quota が 1 コアの 50% の SCHED_NORMAL タスクは、本来どれだけの CPU 時間に値するかに関係なくスロットルされる。これがコンテナが CPU を制限する方法。

要点。「Linux には厳格優先順位の 6 つのスケジューリングクラスがある: DEADLINE、FIFO、RR、NORMAL(=CFS)、BATCH、IDLE。ほとんどのコードは NORMAL の下で走る;nice 値(-20 から +19)はその内部で優先度を調整する。ブロックしない SCHED_FIFO はシステム全体を餓死させ得る —— Linux は sched_rt_runtime_us で制限(デフォルト:非 RT に 5% を残す)。 cgroup CPU 制御は以上すべての上に直交に構成される。」

cgroup、コンテナ、NUMA

現代の Linux サーバは共有ハードウェアで多くのワークロードを走らせる。 cgroup がそれらの間で CPU、メモリ、I/O を分割する; NUMA がどの CPU がどのメモリに近いかを規定する。両方ともスケジューラの上の第 2 層の制約。

90 秒の cgroup

コントロールグループ(cgroup)はプロセスをグループ化しリソース制限をグループ全体に適用するカーネルメカニズム。cgroup v2(あらゆる現代ディストロのデフォルト)は/sys/fs/cgroup/ に階層的ファイルシステムを公開する; 各ディレクトリがグループ、その中の各ファイルがつまみ。

CPU について 3 つの制御が重要:

cpu.weight —— 比例シェア、nice に似る。ウェイト 200 の cgroup は競合時ウェイト 100 の cgroup の 2 倍の CPU シェアを得る。 1 つの cgroup のみが実行可能な作業を持つなら、それが全 CPU を得る。
cpu.max —— 絶対のハード上限、「quota / period」をマイクロ秒で表現。cpu.max = "50000 100000" は「100 ms 壁時計あたり最大 50 ms の CPU」—— 半コア。Docker / Kubernetes の --cpus=0.5 がこれに翻訳される。
cpuset.cpus —— 許可された CPU セット。cpuset.cpus = "0-7" は cgroup がコア 0 から 7 でのみ走れることを意味。 NUMA ピン留めとコア隔離に使う。

これらはスケジューリングクラスと直交に構成される。cgroup でスロットルされた SCHED_NORMAL タスクは依然として cgroup 内で nice を尊重する;cgroup 内の SCHED_FIFO タスクは依然として同じ cgroup 内の SCHED_NORMAL をプリエンプトするが、同時に cpu.max でスロットルされる。

スロットルの罠

cpu.max スロットルはコンテナ化ワークロードでの謎のレイテンシスパイクの最頻の原因。仕組み:各ピリオド(デフォルト 100 ms)で cgroup が新しいクォータを得る。ワークロードがクォータを 30 ms で使うと、残りの 70 ms フリーズされる。その 70 ms がスパイク —— スケジューラの説明なし、明らかな CPU 餓死なし、アプリケーションのログでただの死の静寂、その後次のピリオド開始時の突然のバースト。

さらに悪い:cpu.max は cgroup ごとに強制され、スレッドごとではない。 200 スレッドと 1 コアクォータの Java アプリは、1 スレッドが 4 ms でクォータ全体を燃やし、他の 199 が 96 ms 何も得られない状況になり得る。JVM の-XX:ActiveProcessorCount のようなチューニングは、ランタイムに「実際には 1 コアしかない」と伝えて、それに応じてスレッドプールサイズを決めさせるために存在する。 Node(UV_THREADPOOL_SIZE)、Go(GOMAXPROCS)、 Python(asyncio デフォルト)などで同じ発想。

NUMA —— 非均一メモリアクセス

マルチソケットサーバ(2 ソケット × 32 コア = 64 コア、よくある)は各ソケットに物理メモリが付いている。コアは自ソケットメモリへ ~100 ns でアクセスできる; 他ソケットのメモリへのアクセスは 200–400 ns(ソケット間リンク経由)。これがNUMA(Non-Uniform Memory Access)、無視するとソケット間アクセスで 2–4× のメモリレイテンシ。

Linux のスケジューラは NUMA 認識:タスクをそのメモリが住む場所に近い CPU にスケジュールしたがり、要求タスクが現在走っているのと同じ NUMA ノードでメモリを割り当てたがる (first-touch ポリシー)。周期的なバランシングも行い、タスクをデータへ向けて移動するか、タスクが集まっている場所へデータを移動する。完璧ではない;高性能データベースや JVM は予測可能性のために numactl で明示的にピン留めすることが多い。

実際の観察

cat /sys/fs/cgroup/$(cat /proc/self/cgroup | cut -d: -f3)/cpu.max —— 現在プロセスにかかっている CPU 上限。
cat /sys/fs/cgroup/.../cpu.stat が nr_throttled とthrottled_usec を表示。ゼロでなく増えていたら、スロットルされている。
numactl --hardware がマシンの NUMA トポロジを表示;numastat がプロセスごとのノード跨ぎメモリトラフィックを表示。

要点。「cgroup v2 は weight(比例)、max(ハード上限)、 cpuset(許可コア)経由でグループ間に CPU を分割する。大半のコンテナ CPU レイテンシスパイクは cpu.max スロットル —— クォータがピリオド早期に使い切られ、次のピリオド開始まで沈黙。 NUMA がもう 1 層:ソケット間アクセスに 2–4× メモリレイテンシペナルティ、スケジューラの NUMA 認識配置で緩和されるが明示的ピン留めでのみ完璧。」

クイックリファレンス

冷たく説明できる価値のある 6 つの核心問題と、コードレビューで一目で見抜くべき 5 つの赤旗。

CFS を 1 文で説明。

スケジューラは vruntime が最小の実行可能タスクを選び、 vruntime はタスクのウェイト(nice 経由で設定)に反比例するレートで進む。その 1 つの規則が公平な共有と優先度重み付きスケジューリングの両方を生む。

nice と SCHED_FIFO 優先度の違いは?

nice は SCHED_NORMAL 内のヒント —— vruntime 蓄積に重み付けする、そのため低 nice タスクが比例的に多くの CPU を得るが、各タスクは依然進む。 SCHED_FIFO 優先度は厳格:高優先度 FIFO タスクはすべての低優先度を完全にプリエンプトし、ブロックするかより高優先度の FIFO タスクが到着しない限り譲らない。 SCHED_FIFO はすべてを餓死させ得る;nice はできない。

なぜコンテナ化アプリに説明できないレイテンシスパイクがあるか?

ほぼ確実に cgroup の cpu.max スロットル。cpu.stat の nr_throttled > 0 を確認 —— それが煙る銃。解決はクォータを上げるか、ワークロードを平滑化してピリオド全体で均等に CPU を使うか、ランタイムに実際に何コアあるか伝える(GOMAXPROCS、-XX:ActiveProcessorCount など)、内部スレッドプールを大きくしすぎないようにする。

リアルタイムオーディオスレッドが必要なウェイクアップレイテンシは、どう達成するか?

ライブオーディオの標準は ~1 ms(バッファ 5–10 ms があり、アンダーランの前に補充が必要)。達成するには:SCHED_FIFO 優先度 ~80(カーネルの整備の上、リアルタイムティックの下)、isolcpus または cpuset で CPU 隔離、mlockall でメモリロックしページフォールトを回避、sched_rt_runtime_us をカーネル自身が必要なサイクルだけ残すように調整。

NUMA は書くコードに何を意味するか?

マルチソケットマシンでは、間違ったソケットからのメモリは 2–4× 遅い。 Linux スケジューラは first-touch 割り当てを行いスレッドをそのメモリの近くに保とうとする。問題は長寿命プロセスが 1 ソケットに大きなヒープを割り当て、多くのスレッドが他へ移行すると発生する —— ソケット間トラフィックが支配的になる。緩和:起動時の明示的numactl --cpubind=N --membind=N、jemalloc のようなアロケータのスレッドごと arena、またはコード内の NUMA 認識割り当て。

プロダクションでスケジューリング問題をどう測るか?

vmstat 1 で秒間コンテキストスイッチと実行可能スレッド数(r 列);perf sched latency でウェイクアップから実行までの遅延(尾レイテンシはここから来る);perf stat -e cs,migrations でスイッチと CPU バウンスレート;cat /sys/fs/cgroup/.../cpu.stat でスロットル統計;uptime のロードアベレージが実行可能スレッド数のベースライン。

コードレビューの赤旗

sched_rt_runtime_us の認識なしの SCHED_FIFO。暴走するリアルタイムタスクがマシンをロックし得る。優先度選択を文書化; リアルタイムスレッドにウォッチドッグをペアにする。
コンテナ内で nproc でサイズされたスレッドプール。nproc はホストのコア数を報告する、コンテナの CPU クォータではない。ランタイム固有のつまみを使うか、cpu.max を直接読む。
sched_yield や sleep なしのポーリングループ。タイトな while (!flag) は同コア上の他タスクを餓死させ得る。代わりに condvar や futex を使う。
nice 5–10 にすべき nice 0 のプロダクション daemon。バッチジョブ、ログシッパー、監視エージェントはすべて CFS のデフォルトの公平さの下でインタラクティブリクエストハンドラと競合する。それらを nice ダウンすると負荷下のリクエスト処理レイテンシを保護する。
NUMA ブラインドな大ヒープ割り当て。起動時に 1 スレッドで割り当てられた 200 GB のヒープは 1 NUMA ノードに着地し、他ソケットにスケジュールされた他のすべてのスレッドを傷つける。ピン留めするか、first-touch 並列割り当てを使う。