CPUスケジューラの仕組み - 古典アルゴリズムからCFS、EEVDF、sched_extまで

CPUのコア数は有限ですが、実行したいスレッドは常にそれより多く存在します。ブラウザ、エディタ、ビルド、バックグラウンドの同期処理、そしてカーネル自身のスレッドまで、手元のマシンでも数百のタスクが同時に「動ける状態」を主張しています。この中から「次の数ミリ秒、どのCPUで誰を動かすか」を毎秒何千回と決め続けているのがCPUスケジューラ(プロセススケジューラ)です。

アプリケーションの応答が時々だけ遅れる、コンテナのCPU使用率はまだ余裕があるのにレイテンシが跳ねる、niceを付けたのに思ったほど効かない。こうした現象の多くは、スケジューラの設計を知ると説明がつきます。この記事では、スケジューラが解いている問題から始めて、古典的なアルゴリズム、LinuxのCFSからEEVDFへの移行、BPFでスケジューラを差し替えるsched_ext、スケジューリングクラス、マルチコアとcgroupでの振る舞い、そして観測方法までを、カーネル文書とソースコードをたどりながら整理します。

以下の説明はLinuxを前提とし、カーネルのソースコードやパラメータの値は執筆時点(2026年9月)のメインライン(masterブランチ)で確認したものです。スケジューラは活発に開発されている領域なので、手元のカーネルでは値や挙動が異なる場合があります。

スケジューラが解いている問題

スケジューラの評価軸は1つではありません。代表的なものは次の3つで、これらは互いに引っ張り合います。

評価軸	意味	重視されやすい場面
スループット	単位時間あたりに片付く仕事の量	バッチ処理、ビルド、科学技術計算
レイテンシ(応答性)	実行可能になってから実際にCPUを得るまでの待ち時間	GUI、音声処理、Webリクエストの処理
公平性	各タスクに期待どおりの割合でCPU時間が配られているか	マルチユーザー環境、コンテナの共存

たとえばスループットだけを最大化したいなら、一度走り始めたタスクをできるだけ長く走らせるのが得です。切り替えの回数が減り、CPUキャッシュも温まったまま使えるからです。しかしそうすると、後から来た短い仕事(キー入力への反応など)がいつまでも待たされ、応答性が悪化します。逆に応答性を上げようと頻繁に切り替えると、切り替えそのもののコストがスループットを削ります。

スケジューラの歴史は、このトレードオフに対して「どの落としどころを、どれだけ少ない調整パラメータで実現するか」の試行錯誤の歴史だと言えます。

コンテキストスイッチ、タイムスライス、プリエンプション

アルゴリズムの話に入る前に、スケジューラが操作する3つの基本概念を押さえます。

コンテキストスイッチで何が起きるか

CPU上で動いているタスクを別のタスクに入れ替える操作をコンテキストスイッチと呼びます。レジスタの値やスタックポインタなど、実行を再開するのに必要な状態を保存し、次のタスクの状態を復元します。切り替え先が別プロセスであれば、アドレス空間(ページテーブル)も切り替わります。

コンテキストスイッチには、保存と復元にかかる直接的なコストに加えて、見えにくい間接的なコストがあります。切り替え後のタスクが触るデータはCPUキャッシュやTLBに載っていないことが多く、しばらくはキャッシュミスが増えるからです。この点はCPUキャッシュとメモリ階層の記事や仮想メモリとページングの記事で扱ったTLBの話と直結します。

コンテキストスイッチには2種類あります。

自発的なスイッチ(voluntary): タスクがI/O待ちやロック待ち、sleepなどで自分からCPUを手放す
非自発的なスイッチ(involuntary): タスクはまだ走りたいのに、スケジューラが取り上げて別のタスクに渡す

後述する/proc配下のファイルでは、この2つを別々に数えられます。非自発的なスイッチが多いタスクは、CPUを奪い合っている状態だと読み取れます。

タイムスライスは長くても短くても困る

複数のタスクで1つのCPUを分け合うとき、1回に連続して走らせる時間の目安をタイムスライス(time slice、quantum)と呼びます。

長すぎると、待っているタスクの応答が悪くなる
短すぎると、コンテキストスイッチの割合が増え、実際の仕事に使える時間が減る

後で見るように、Linuxの通常タスク向けスケジューラ(EEVDF)では、基準となるスライス長sysctl_sched_base_sliceのデフォルトが0.70 msec * (1 + ilog(ncpus))とソースコードのコメントに書かれています。CPU数は最大8として計算されるため、8コア以上のマシンでは0.7ミリ秒の4倍、つまり2.8ミリ秒になります。一方でリアルタイムポリシーのSCHED_RRのデフォルトのクォンタムは、RR_TIMESLICEとして100 * HZ / 1000、つまり100ミリ秒相当で定義されています。

プリエンプション: 取り上げる仕組み

走っているタスクからCPUを取り上げることをプリエンプション(preemption)と呼びます。取り上げるきっかけは主に2つです。

タイマ割り込み(スケジューラティック): 定期的に発生する割り込みの中で、今のタスクが持ち分を使い切ったかを確認する
ウェイクアップ: I/O完了などで別のタスクが実行可能になったとき、そのタスクが今のタスクより優先されるべきかを判定する

ユーザー空間で走っているタスクは基本的にいつでも取り上げられますが、タスクがシステムコールなどでカーネル内を実行している最中にどこまで取り上げてよいかは、カーネルのビルド設定で変わります。カーネルのKconfig.preemptには次のプリエンプションモデルが並んでいます。

設定	Kconfig上の説明	性格
`PREEMPT_NONE`	No Forced Preemption (Server)	伝統的なモデル。スループット寄りで、遅延の保証はない
`PREEMPT_VOLUNTARY`	Voluntary Kernel Preemption (Desktop)	カーネルコードに明示的なプリエンプションポイントを増やす
`PREEMPT`	Preemptible Kernel (Low-Latency Desktop)	クリティカルセクション外のカーネルコードをすべてプリエンプト可能にする
`PREEMPT_LAZY`	Scheduler controlled preemption model	フルプリエンプションに近いが、`SCHED_NORMAL`タスクの取り上げは控えめにする
`PREEMPT_RT`	Fully Preemptible Kernel (Real-Time)	可能な限り全体をプリエンプト可能にする

各設定にはアーキテクチャなどの依存条件があり、どれを選べるかは環境によって異なります。

PREEMPT_RTは長年メインラインの外でパッチとして開発されてきましたが、kernelnewbiesのリリースノートによればLinux 6.12(2024年11月17日リリース)でメインラインに統合されました。システムコールでカーネル内に入る仕組みそのものはシステムコールの記事を参照してください。

古典的なスケジューリングアルゴリズム

Linuxの実装を理解するには、教科書的なアルゴリズムが「何に失敗したか」を知っておくと近道です。ここではArpaci-Dusseau夫妻の教科書『Operating Systems: Three Easy Pieces』(OSTEP)のスケジューリング章に沿って整理します。

OSTEPでは主な指標として次の2つを定義しています。

ターンアラウンドタイム: ジョブが完了した時刻から、到着した時刻を引いたもの
レスポンスタイム: ジョブが到着してから、初めてCPUを割り当てられるまでの時間

FIFOとコンボイ効果

到着した順に最後まで走らせるのがFIFO(FCFS)です。実装は単純ですが、長いジョブの後ろに短いジョブが並ぶと、全体の待ち時間が大きく悪化します。

OSTEPの例では、実行時間100秒のジョブAの直後に、それぞれ10秒のジョブBとCが同時刻に到着した場合、平均ターンアラウンドタイムは110秒になります。スーパーのレジで、山盛りのカートの後ろに商品1つの客が並んでしまう状況で、これをコンボイ効果(convoy effect)と呼びます。

SJFとSTCF

短いジョブから先に走らせるのがSJF(Shortest Job First)です。同じ例でBとCを先に走らせると、平均ターンアラウンドタイムは50秒まで下がります。

ただしSJFは、長いジョブが走り出した直後に短いジョブが到着すると、やはり待たせてしまいます。そこで新しいジョブが来るたびに残り時間が最短のものへ切り替えるのがSTCF(Shortest Time-to-Completion First)で、プリエンプティブなSJFとも呼ばれます。OSTEPでは、ターンアラウンドタイムの観点ではSTCFが最適であると説明しています。

しかし、現実のOSには2つの問題があります。1つは、ジョブの実行時間を事前に知る方法がないことです。もう1つは、ターンアラウンドタイムが最適でも、長いジョブに挟まれた対話的なタスクのレスポンスタイムは良くならないことです。

ラウンドロビン

レスポンスタイムを重視するなら、全員にタイムスライス分ずつ順番にCPUを回すラウンドロビン(RR)が有効です。どのジョブもすぐに一度はCPUを得られます。

その代わり、ジョブを細切れにして引き延ばすため、ターンアラウンドタイムは悪化します。「応答性を取るとターンアラウンドを失う」という、冒頭のトレードオフがそのまま現れます。

優先度スケジューリングと飢餓

タスクに優先度を付け、高い優先度から先に走らせる方式も古くからあります。重要なタスクを確実に先に走らせられる一方で、高優先度のタスクが常に実行可能だと、低優先度のタスクがいつまでもCPUを得られない飢餓(starvation)が起きます。

MLFQ: 振る舞いから優先度を学習する

実行時間を事前に知らなくても、対話的なタスクを優遇しつつ長いジョブも進めたい。この問題に対する古典的な答えがMLFQ(Multi-Level Feedback Queue)です。OSTEPによれば、1962年にCorbatóらがCTSS(Compatible Time-Sharing System)で最初に記述したものです。

OSTEPの章末では、MLFQのルールが次の5つにまとめられています(原文を要約して訳しています)。

優先度が高いジョブAと低いジョブBがあれば、Aを走らせる
優先度が同じなら、そのキューのタイムスライスでラウンドロビンする
新しく到着したジョブは最上位のキューに入れる
ジョブがその段で割り当て時間を使い切ったら(途中で何回CPUを手放したかに関係なく)、1段下げる
一定時間Sごとに、全ジョブを最上位のキューに戻す

ルール3と4によって、すぐに終わる短いジョブや、I/Oですぐに手放す対話的なジョブは上位に留まり、CPUを使い続けるジョブは下位に沈みます。ルール5は、下位に沈んだジョブの飢餓を防ぐための定期的な優先度ブーストです。ルール4に「何回手放したかに関係なく」とあるのは、割り当て時間を使い切る直前にわざとI/Oを発行して上位に居座る、というスケジューラの「ゲーミング」を防ぐためです。

MLFQはよく機能しますが、キューの段数、各段のタイムスライス、ブースト間隔Sなど、調整すべき定数が多いという弱点があります。OSTEPはこうした定数を、正しく設定するには黒魔術が必要に見えることから「voo-doo constants」と呼ぶ話を紹介しています。Linuxのスケジューラも、まさにこの「ヒューリスティクスと調整値の山」から抜け出す方向に進化してきました。

Linuxスケジューラの歴史

O(1)スケジューラ

kernelnewbiesのLinux 2.6.23のリリースノートによると、Linux 2.5の開発期間中にIngo MolnarによるO(1)スケジューラが統合され、2.4から引き継いだスケジューラを置き換えました。O(1)スケジューラは、優先度ごとのランキューを「実行中(active)」と「使い切った(expired)」の2つの配列で持ち、配列を入れ替えることで、タスク数に依存しない定数時間でタスクを選べるようにしたものです。

性能面では大きな改善でしたが、対話的なタスクを見分けるために「インタラクティブ性推定」というヒューリスティクスを持っていました。同じリリースノートでは、この推定コードが一部のケースを直すと別のケースが壊れる状態に陥り、「統計で未来を予測しようとして失敗する典型例」になっていたと振り返っています。

CFS: 理想的なマルチタスクCPUを模倣する

CFS(Completely Fair Scheduler)はIngo Molnarが実装し、Linux 2.6.23でメインラインに統合されました。カーネル文書は、CFSの設計の80%は「実機の上で理想的で正確なマルチタスクCPUをモデル化する」という1文で要約できると述べています。

理想的なマルチタスクCPUとは、2つのタスクがあればそれぞれを50%の速さで本当に同時に走らせられる、架空のCPUです。実際のCPUは一度に1つしか走らせられないので、CFSは各タスクがどれだけCPUを使ったかを仮想実行時間(vruntime)として記録し、次のルールで選びます。

常に、vruntimeが最も小さいタスク(これまで最も走っていないタスク)を選ぶ
走ったタスクは、使った時間に応じてvruntimeが増える
別のタスクのほうがvruntimeが小さくなったら、切り替える

この「最小のvruntimeを持つタスク」を効率よく取り出すために、CFSは実行可能なタスクをvruntimeをキーにした赤黒木(red-black tree)に並べます。一番左のノードが次に走るタスクです。走ったタスクのvruntimeが増えると木の右側へ移動していくため、どのタスクもいずれ左端に来てCPUを得られます。

CFSのもう1つの特徴は、ナノ秒単位で時間を計測し、旧来のようにタイマのtick(HZ)単位の固定タイムスライスや、インタラクティブ性の推定ヒューリスティクスを持たないことです。

nice値と重み

vruntimeの増え方をタスクごとに変えることで、優先度を表現します。その入力がnice値です。sched(7)によれば、現在のLinuxでのnice値の範囲はマイナス20(高優先度)からプラス19(低優先度)です。

nice値はカーネル内で重み(weight)に変換されます。kernel/sched/core.cには40段階分の対応表sched_prio_to_weightが定義されています。

const int sched_prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
};

nice 0の重みが1024で、1段ごとにおよそ1.25倍ずつ変わります。この表の直前のコメントには、CPUバウンドなタスクがnice 0から1になると、nice 0のままのタスクに比べて約10%少ないCPU時間を得る、と書かれています。カーネル文書のsched-nice-designでも、nice差1の2タスクはどの絶対値から始めても55%と45%に分かれる、と説明されています。実際、1024と820で分けると、1024を1844で割っておよそ55.5%になります。

重みはvruntimeの進み方に効きます。kernel/sched/fair.cのcalc_delta_fairは、実際に走った時間にnice 0の基準負荷を掛けてタスクの重みで割る(コメントではdelta /= w)処理です。概念的には次のようになります。

vruntimeの増分 = 実際に走った時間 x (nice 0の重み / そのタスクの重み)
 
nice  0 (重み 1024) が 10ms 走ると vruntime は 約10ms 進む
nice  5 (重み  335) が 10ms 走ると vruntime は 約30.6ms 進む
nice -5 (重み 3121) が 10ms 走ると vruntime は 約3.3ms 進む

重みが大きいタスクほどvruntimeがゆっくり進むので、木の左側に長く留まり、結果として多くのCPU時間を得ます。nice 0と19を並べると重みは1024対15なので、nice 19のタスクが得るのは1.5%程度です。これはsched-nice-designに書かれている「nice +19は1.5%」という記述とも一致します。

相対的な比率で効くということは、競合相手がいなければniceは何もしないということでもあります。CPUが空いているマシンでnice 19のタスクを走らせても、他に走りたいタスクがなければ100%近く使えます。

EEVDF: lagと仮想デッドライン

CFSは長く使われてきましたが、公平性を保つことと、短い応答時間が欲しいタスクを優先することを両立させるために、多くのヒューリスティクスと調整値が積み重なっていきました。kernelnewbiesのLinux 6.6(2023年10月29日リリース)のリリースノートは、このリリースでCFSがEEVDF(Earliest Eligible Virtual Deadline First)という新しいアルゴリズムを使うコードに置き換えられたと記しています。

EEVDFのアルゴリズム自体は1995年の論文で提案されたもので、カーネル文書によれば、LinuxのものはPeter Zijlstraが2023年に提案した版です。Linux 6.12のリリースノートでは、置き換えは段階的に進められ、6.12でEEVDFへの移行が完了した、と説明されています。ただし、ソースファイル名は引き続きkernel/sched/fair.cで、カーネル内では今も「fair class」と呼ばれています。

EEVDFの中心となる概念は3つです。

概念	意味
lag	そのタスクが本来受け取るべきだったCPU時間と、実際に受け取った時間の差。正ならCPU時間を「貸している」、負なら「使いすぎ」
eligible(適格)	lagが0以上、つまり取り分をまだ受け取り切っていないタスク
仮想デッドライン	要求するスライス長を重みで割った分だけ、vruntimeより先に置かれる締め切り

選択のルールは名前のとおりです。eligibleなタスクの中から、仮想デッドラインが最も早いものを選ぶ。fair.cのpick_eevdfの前のコメントにも、1)タスクはeligible(サービスを受ける権利がある)でなければならず、2)その中から仮想デッドラインが最も早いものを選ぶ、と書かれています。

仮想デッドラインはupdate_deadlineで次のように計算されます。

/*
 * EEVDF: vd_i = ve_i + r_i / w_i
 */
se->deadline = se->vruntime + calc_delta_fair(se->slice, se);

ここでr_iは要求するスライス長、w_iは重みです。スライスが短いタスクほどデッドラインが近くなるため、同じ重み(同じnice)でも、短く頻繁に走りたいタスクが先に選ばれやすくなります。一方で、eligibleであることが前提なので、取り分を使いすぎたタスクは短いスライスを主張しても割り込めません。これにより「公平性はnice(重み)で、応答性はスライス長で」という形で、2つの軸を別々に扱えるようになりました。

データ構造も変わっています。pick_eevdfのコメントによれば、赤黒木はデッドライン順に並べつつ、各ノードに部分木内の最小vruntimeを持たせた拡張赤黒木にすることで、eligibleでない部分木を枝刈りしながらO(log n)で選択できるようにしています。

眠っているタスクの扱いについて、カーネル文書は次のように説明しています。短く眠ることで負のlagをリセットする悪用を防ぐため、眠ったタスクは「遅延デキュー(deferred dequeue)」の印を付けてしばらくランキューに残し、仮想時間の経過とともにlagを減衰させます。ただし文書自身が、眠っているタスクのlagの扱いには議論が続いていると明記しています。

スライス長はタスクごとに要求することもできます。chrt(1)のmanページによれば、SCHED_OTHERとSCHED_BATCHでのカスタムスライス長の指定はLinux 6.12からサポートされています。fair.cでは、sched_setattr(2)のsched_runtimeで渡された値を0.1ミリ秒から100ミリ秒の範囲にクランプして使っています。

sched_ext: BPFでスケジューラを書く

EEVDFは汎用のスケジューラですが、ゲーム、特定のデータベース、巨大なサービス群など、ワークロードに特化したほうが良い結果が出る場面もあります。そこで導入されたのがsched_ext(Extensible Scheduler Class)です。kernelnewbiesのLinux 6.12のリリースノートには、BPFでタスクスケジューリングのアルゴリズムを書けるsched_extの最初の部分が含まれた、と記されています。

カーネル文書による主な性質は次のとおりです。

スケジューラの振る舞いを、BPFプログラムの集まり(BPFスケジューラ)として定義する
BPFスケジューラは、いつでも動的に有効化・無効化できる
BPFスケジューラが何をしてもシステムの整合性は保たれる。エラーの検出、実行可能なタスクのストール(停止)、またはSysRq-Sのキー操作で、デフォルトのスケジューラに戻る

BPFスケジューラはstruct sched_ext_opsの各コールバックを実装します。カーネル文書に載っている最小のグローバルFIFOスケジューラ(tools/sched_ext/scx_simple.bpf.cの抜粋)を、さらに要点だけに絞ると次のようになります。

/* 起床時などに、どのCPUで走らせるかを決める */
s32 BPF_STRUCT_OPS(simple_select_cpu, struct task_struct *p,
                   s32 prev_cpu, u64 wake_flags)
{
        s32 cpu;
        bool direct = false;
 
        cpu = scx_bpf_select_cpu_dfl(p, prev_cpu, wake_flags, &direct);
        if (direct)
                scx_bpf_dsq_insert(p, SCX_DSQ_LOCAL, SCX_SLICE_DFL, 0);
        return cpu;
}
 
/* 空きCPUが見つからなかったタスクを、グローバルなキューに入れる */
void BPF_STRUCT_OPS(simple_enqueue, struct task_struct *p, u64 enq_flags)
{
        scx_bpf_dsq_insert(p, SCX_DSQ_GLOBAL, SCX_SLICE_DFL, enq_flags);
}

sched_extではDSQ(dispatch queue)というキューにタスクを入れていきます。デフォルトでグローバルなFIFOが1つと、CPUごとのローカルDSQがあり、CPUは常に自分のローカルDSQからタスクを取り出して実行します。ローカルDSQが空ならグローバルDSQから取り、それでもなければops.dispatch()が呼ばれます。上の関数名(scx_bpf_dsq_insertなど)はmasterブランチの文書に基づくもので、手元のカーネルのバージョンに対応する文書やサンプルも併せて確認してください。

実用的なBPFスケジューラの実装は、GitHubのsched-ext/scxリポジトリで開発されています。現在どのBPFスケジューラが動いているかは、次のファイルで確認できます(sched_ext有効なカーネルが必要です)。

cat /sys/kernel/sched_ext/state
cat /sys/kernel/sched_ext/root/ops

スケジューリングクラスとポリシー

ここまでの話は、主に通常のタスクの話でした。Linuxのスケジューラは、性格の異なる複数のスケジューリングクラスを優先順に並べた構造になっています。リンカスクリプトinclude/asm-generic/vmlinux.lds.hのSCHED_DATAには、クラスの優先順位を決める並び順として、次の順番が書かれています。

stop  >  dl (deadline)  >  rt  >  fair  >  ext  >  idle

上位のクラスに実行可能なタスクがある限り、下位のクラスのタスクは選ばれません。ユーザーがポリシーとして選べるのは次のものです。

ポリシー	クラス	優先度の指定	用途
`SCHED_OTHER`(`SCHED_NORMAL`)	fair	nice値(マイナス20からプラス19)	通常のタスク。デフォルト
`SCHED_BATCH`	fair	nice値	非対話的な処理。常にCPUバウンドとみなされ、起床時にやや不利に扱われる
`SCHED_IDLE`	fair	なし(niceは無視)	nice 19よりさらに低い優先度のジョブ
`SCHED_FIFO`	rt	静的優先度1から99	リアルタイム。同じ優先度内では、手放すかより高い優先度に奪われるまで走り続ける
`SCHED_RR`	rt	静的優先度1から99	リアルタイム。`SCHED_FIFO`にタイムクォンタムを加えたもの
`SCHED_DEADLINE`	dl	runtime、deadline、period	周期的な処理に実行時間を予約する
`SCHED_EXT`	ext	BPFスケジューラ次第	sched_extのBPFスケジューラで管理

SCHED_IDLEの重みは、kernel/sched/sched.hでWEIGHT_IDLEPRIOとして3と定義されており、nice 19の15よりさらに小さい値です。

SCHED_EXTについて、カーネル文書では、BPFスケジューラが読み込まれていないときはSCHED_NORMALとして扱われること、またSCX_OPS_SWITCH_PARTIALフラグを付けずに読み込むとSCHED_NORMAL、SCHED_BATCH、SCHED_IDLEのタスクもまとめてsched_extで管理されることが説明されています。

リアルタイムポリシーの注意点

SCHED_FIFOやSCHED_RRは、通常のタスクより必ず優先されます。そのため、リアルタイムポリシーのタスクがブロックせずに無限ループすると、他のタスクがCPUを得られなくなる危険があります。

sched(7)によれば、その対策としてLinux 2.6.25から/proc/sys/kernel/sched_rt_period_usと/proc/sys/kernel/sched_rt_runtime_usが用意されています。デフォルトはそれぞれ1,000,000(1秒)と950,000(0.95秒)で、1秒のうち5%はリアルタイムでもデッドラインでもないタスクのために残されます。また、Linux 6.12のリリースノートでは、高優先度タスクがCPUを独占したときのSCHED_OTHERなどの飢餓を解決する手段として、SCHED_DEADLINEサーバーが導入されたことにも触れられています。両者の現在の関係(どちらがどの条件で効くか)は、この記事では確認し切れていないため未確認とします。

リアルタイムポリシーを使ってよいのは、処理が必ずブロックすることが分かっていて、なおかつ遅延の上限が本当に必要な場合に限るべきです。「速くしたいから」という理由でSCHED_FIFOを付けるのは、システム全体を不安定にする典型的な誤用です。

SCHED_DEADLINE

SCHED_DEADLINEはLinux 3.14から使えるポリシーで、sched(7)によればGEDF(Global Earliest Deadline First)とCBS(Constant Bandwidth Server)を組み合わせて実装されています。「周期Periodごとに、Deadlineまでの間にRuntimeだけCPU時間を使わせる」という予約をします。

3つの値の間には、Runtime以下のDeadline、Deadline以下のPeriodという関係が必要
設定時にカーネルが受け入れ判定を行い、全体として実現できない場合はsched_setattr(2)がEBUSYで失敗する
設定したRuntimeを超えて走ろうとすると、CBSによって抑えられる
設定にはCAP_SYS_NICEが必要

SCHED_DEADLINEの設定には、glibcがラッパを提供していないsched_setattr(2)を使います。コマンドラインからはchrtで指定できます。

# 10ミリ秒周期で、そのうち2ミリ秒を予約して実行する例(要root)
sudo chrt -d -T 2000000 -D 10000000 -P 10000000 0 ./periodic-task

マルチコアでのロードバランシングとCPUアフィニティ

ここまでは1つのCPUのランキューの中の話でした。実際のLinuxでは、CPUごとにランキューを持ち、各CPUが自分のランキューからタスクを選びます。すると「あるCPUには10個のタスクが並び、隣のCPUは暇」という偏りが起きうるため、タスクをCPU間で移すロードバランシングが必要になります。

スケジューリングドメイン

カーネル文書sched-domainsによれば、各CPUは基本のスケジューリングドメインを持ち、それを親へたどる階層を作ります。文書の例では、基本ドメインがSMTの兄弟スレッドをまとめ、その親がノード内の物理CPUを、さらにその親がNUMAノードをグループとしてマシン全体をまとめる、というように、近いCPUほど下の階層にまとまります。バランシングはドメイン内のグループ間で行われ、グループの負荷に偏りが出たときだけタスクが移動します。

階層になっている理由は、移動のコストが距離によって違うからです。同じコアのSMT兄弟に移すならキャッシュもそのまま使えますが、別のNUMAノードに移すとキャッシュは冷え、メモリアクセスも遠くなります。fair.cにあるsysctl_sched_migration_cost(デフォルト500000ナノ秒)は、最近走ったばかりのタスクをキャッシュが温かいとみなして移動を控えるための目安です。

CPUアフィニティ: tasksetとsched_setaffinity

特定のタスクを特定のCPUに固定したい場合は、CPUアフィニティを設定します。コマンドラインではtasksetを使います。

# CPU 0と1だけで実行する
taskset -c 0,1 ./app
 
# 既存プロセスのアフィニティを確認する
taskset -pc 1234
 
# 既存プロセスの全スレッドをCPU 2から3に固定する
taskset -a -pc 2-3 1234

プログラムから設定する場合はsched_setaffinity(2)を使います。

#define _GNU_SOURCE
#include <sched.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/resource.h>
 
int main(void)
{
    cpu_set_t set;
 
    /* このスレッドをCPU 1だけで動かす */
    CPU_ZERO(&set);
    CPU_SET(1, &set);
    if (sched_setaffinity(0, sizeof(set), &set) == -1) {
        perror("sched_setaffinity");
        return EXIT_FAILURE;
    }
 
    /* nice値を10にする(優先度を下げる操作は特権なしで可能) */
    if (setpriority(PRIO_PROCESS, 0, 10) == -1) {
        perror("setpriority");
        return EXIT_FAILURE;
    }
 
    printf("running on CPU %d, nice=%d\n",
           sched_getcpu(), getpriority(PRIO_PROCESS, 0));
    return EXIT_SUCCESS;
}

sched_setaffinity(2)のmanページにあるとおり、第1引数のpidに0を渡すと呼び出したスレッド自身が対象です。現在走っているCPUがマスクに含まれていなければ、許可されたCPUのどれかへ移されます。なお、sched(7)にあるとおり、LinuxではPOSIXの規定と異なり、nice値はスレッドごとの属性です。

アフィニティは強力ですが、スケジューラの自由度を奪います。固定したCPUが混んでいても、他の空いたCPUに逃がせなくなるからです。本当にCPUを占有させたい場合は、manページでも触れられているisolcpusブートオプションやcpuset cgroupで、他のタスクをそのCPUから追い出す設計と組み合わせる必要があります。

cgroupのcpu.weightとcpu.max

コンテナ環境では、スケジューラの挙動にcgroupの設定が重なります。cgroup v2のCPUコントローラには、性格がまったく異なる2種類の設定があります。namespaceとcgroupの基本はLinuxコンテナの記事で扱っています。

cpu.weight: 重みによる配分

cpu.weightはデフォルト100、範囲は1から10000です。cgroup v2の文書では「Weights」の配分モデルとして、親のリソースを、その時点でリソースを使える子の重みの比で分けると説明されています。使っていない子は分配に参加しないので、空いているCPUは誰でも使える(work-conserving)のが特徴です。

これはniceの重みと同じ発想で、実際にkernel/sched/sched.hのsched_weight_from_cgroupは、cgroupの重みに1024を掛けて100で割っています。つまりcpu.weightの100は、nice 0の重み1024に対応します。nice値の感覚で設定したい場合はcpu.weight.niceというファイルもあります。

グループ単位の重みがあるため、タスク単位のniceとグループ単位の配分は階層的に効きます。たとえば同じcpu.weightの2つのcgroupがあり、一方に1スレッド、もう一方に10スレッドが入っていれば、まずcgroup同士で半分ずつ分け、その中でスレッドに分けることになります。

cpu.max: 帯域制御とスロットリング

cpu.maxは「$MAX $PERIOD」の形式で、周期$PERIODごとに最大$MAXまで使える、という上限です。単位はマイクロ秒で、デフォルトはmax 100000(上限なし、周期100ミリ秒)です。こちらは「Limits」の配分モデルなので、CPUが空いていても上限を超えては使えません。

# cgroup v2で、CPU 0.5個分に制限したグループを作る例(要root)
sudo mkdir /sys/fs/cgroup/demo
echo "+cpu" | sudo tee /sys/fs/cgroup/cgroup.subtree_control
echo "50000 100000" | sudo tee /sys/fs/cgroup/demo/cpu.max
echo $$ | sudo tee /sys/fs/cgroup/demo/cgroup.procs
 
# スロットリングの発生状況を見る
cat /sys/fs/cgroup/demo/cpu.stat

cpu.statには、コントローラ有効時にnr_periods、nr_throttled、throttled_usecなどが出ます。nr_throttledが増え続けていれば、上限に当たって止められています。

ここに、コンテナでよく起きる落とし穴があります。上限は「CPU何個分」という量で表されますが、実際には周期ごとの合計CPU時間として消費されます。単純化したモデルで考えてみます。

cpu.max = "200000 100000"   (100ms周期ごとに合計200ms、つまりCPU 2個分)
8コアのマシンで、8スレッドが同時にCPUバウンドな処理をする
 
  0ms - 25ms  : 8スレッド x 25ms = 200ms を消費して上限到達
 25ms - 100ms : 周期が終わるまで、グループ全体が止められる(75ms)

1秒間の平均使用率は「CPU 2個分」に収まっているので、監視ダッシュボード上は余裕があるように見えます。しかし個々のリクエストから見ると、処理の途中で最大75ミリ秒止まることがあり、これがテールレイテンシの悪化として現れます。

Kubernetesの文書でも、CPUのlimitはCPUスロットリングによって強制されるハードな上限であり、CPUのrequestは一般に重み付けとして使われる、と説明されています。対策としては次のようなものがあります。

スレッド数を上限に見合った数にする。たとえばGo 1.25のリリースノートによれば、Linux上のGoランタイムはcgroupのCPU帯域制限を考慮してGOMAXPROCSのデフォルト値を決めるようになっています
短時間のバーストを許すcpu.max.burstを検討する
上限ではなくcpu.weight(Kubernetesならrequest)による配分で済むなら、上限を外すことを検討する

スケジューラを観測する

procファイル: sched と schedstat

/proc/<pid>/schedには、スケジューラから見たタスクの状態が出力されます。kernel/sched/debug.cのproc_sched_show_taskを見ると、主に次の項目が並びます。

項目	意味
`se.vruntime`	仮想実行時間
`se.sum_exec_runtime`	これまでに実際にCPUで走った時間の合計
`se.nr_migrations`	CPU間を移動した回数
`nr_voluntary_switches`	自発的なコンテキストスイッチの回数
`nr_involuntary_switches`	非自発的なコンテキストスイッチの回数
`se.load.weight`	重み
`policy`、`prio`	スケジューリングポリシーと優先度

se.load.weightは、64ビット環境では内部で精度を上げるために10ビット左シフトした値が格納されます(scale_load)。そのため、nice 0のタスクでも1024ではなく、その1024倍の値が表示されます。

# 自分のシェルのスケジューラ統計から、主要な項目だけ抜き出す
grep -E 'vruntime|sum_exec_runtime|nr_(in)?voluntary_switches|policy|prio' /proc/$$/sched

/proc/<pid>/schedstatはより簡素で、カーネル文書sched-statsによれば、CPUで走った時間(ナノ秒)、ランキューで待っていた時間(ナノ秒)、このCPUで走ったタイムスライスの数、の3つの値が並びます。2番目の値は「走りたいのに待たされた時間」なので、CPUの取り合いを直接示す指標として使えます。

perf sched

perf schedは、スケジューラのイベントを記録して分析するツールです。perf-sched(1)のmanページに沿って、代表的な使い方を挙げます。

# 1秒間、システム全体のスケジューリングイベントを記録する
sudo perf sched record -- sleep 1
 
# タスクごとのスケジューリング遅延を集計する
sudo perf sched latency
 
# イベントごとの時系列(待ち時間・実行時間)を見る
sudo perf sched timehist
 
# CPUごとに、どのタスクが走っていたかをテキストで図示する
sudo perf sched map

perf sched latencyは、タスクごとの最大遅延や平均遅延を示すので、「どのタスクがCPUを待たされているか」の当たりを付けるのに向いています。記録はイベント量が多くなりやすいので、本番環境では記録時間を短くしてください。出力形式はperfのバージョンによって変わるため、ここでは出力例は載せません。

chrt と nice / renice

ポリシーや優先度の確認と変更には、chrtとnice、reniceを使います。

# 既存プロセスのポリシーと優先度を確認する
chrt -p 1234
 
# 各ポリシーで指定できる優先度の範囲を表示する
chrt -m
 
# nice値10でビルドを走らせる
nice -n 10 make -j8
 
# 既存プロセスのnice値を5にする
renice -n 5 -p 1234
 
# SCHED_BATCHで実行する
chrt -b 0 ./batch-job
 
# SCHED_IDLEで実行する
chrt -i 0 ./backup-job
 
# リアルタイムの SCHED_FIFO 優先度50で実行する(要CAP_SYS_NICE)
sudo chrt -f 50 ./audio-app
 
# SCHED_OTHERのタスクに1ミリ秒のカスタムスライスを指定する(Linux 6.12以降)
sudo chrt --pid -o -T 1000000 0 1234

chrt(1)のmanページによれば、util-linux v2.42以降ではSCHED_OTHER、SCHED_BATCH、SCHED_IDLEなどで優先度の引数を省略できますが、それより前の版との互換のため、上の例では0を明示しています。

アプリ開発者のための実務指針

最後に、ここまでの内容をアプリケーション開発と運用の指針にまとめます。

レイテンシの悪化を見たら、まず「待たされているか」を確認する。/proc/<pid>/schedstatの2番目の値やperf sched latencyで、ランキュー待ちの時間を見ます。CPU使用率だけを見ても、取り合いは分かりません
コンテナのCPU上限はスロットリングとして効く。cpu.statのnr_throttledとthrottled_usecを監視し、上限に対してスレッド数が多すぎないかを確認します
ランタイムのスレッド数をCPU上限に合わせる。GoのGOMAXPROCS、JVMやNode.jsのワーカ数、スレッドプールのサイズは、ホストのコア数ではなくコンテナに許されたCPU量を基準に決めます
niceは比率でしか効かない。CPUが空いていれば低優先度でも普通に走ります。バックグラウンド処理を確実に脇役にしたいなら、SCHED_IDLEやSCHED_BATCH、あるいはcgroupのcpu.weightを検討します
リアルタイムポリシーは最後の手段にする。SCHED_FIFOはバグ1つでシステムを止め得ます。まずは通常ポリシーのままで、スライス長の調整やCPUの分離で足りないかを検討します
アフィニティの固定は、分離とセットで考える。tasksetで固定しただけでは、そのCPUに他のタスクも来ます。固定はスケジューラの逃げ道を減らすことでもあります
スレッドを増やせば速くなるとは限らない。コア数を大きく超えるCPUバウンドなスレッドは、コンテキストスイッチとキャッシュミスを増やすだけです。並行性と並列性の整理は並行処理と並列処理の記事を、I/O待ちの多い処理をスレッドを増やさずに捌く方法はI/O多重化の記事を参照してください

まとめ

CPUスケジューラは、スループット、レイテンシ、公平性という互いに引っ張り合う目標の落としどころを探す仕組みです
FIFO、SJF、STCF、ラウンドロビン、優先度スケジューリングはそれぞれ一部の指標に強く、MLFQは振る舞いから優先度を学習することで両立を狙いましたが、調整値の多さという課題を抱えました
Linuxは、ヒューリスティクスに頼るO(1)スケジューラから、vruntimeと赤黒木で理想的なマルチタスクCPUを模倣するCFS(2.6.23)へ移り、Linux 6.6からはlagと仮想デッドラインで公平性と応答性を分けて扱うEEVDFへ移行しました
nice値は重み(nice 0で1024、1段でおよそ1.25倍)に変換され、比率としてCPU時間の配分に効きます
Linux 6.12では、BPFでスケジューラを実装できるsched_extと、PREEMPT_RTがメインラインに入りました
コンテナでは、cpu.weightは空きを分け合う重み、cpu.maxは空いていても超えられない上限であり、後者はスロットリングとしてテールレイテンシに現れます
観測には/proc/<pid>/sched、/proc/<pid>/schedstat、perf sched、cgroupのcpu.statを使います

CPUスケジューラの仕組み - 古典アルゴリズムからCFS、EEVDF、sched_extまで

スケジューラが解いている問題

コンテキストスイッチ、タイムスライス、プリエンプション

コンテキストスイッチで何が起きるか

タイムスライスは長くても短くても困る

プリエンプション: 取り上げる仕組み

古典的なスケジューリングアルゴリズム

FIFOとコンボイ効果

SJFとSTCF

ラウンドロビン

優先度スケジューリングと飢餓

MLFQ: 振る舞いから優先度を学習する

Linuxスケジューラの歴史

O(1)スケジューラ

CFS: 理想的なマルチタスクCPUを模倣する

nice値と重み

EEVDF: lagと仮想デッドライン

sched_ext: BPFでスケジューラを書く

スケジューリングクラスとポリシー

リアルタイムポリシーの注意点

SCHED_DEADLINE

マルチコアでのロードバランシングとCPUアフィニティ

スケジューリングドメイン

CPUアフィニティ: tasksetとsched_setaffinity

cgroupのcpu.weightとcpu.max

cpu.weight: 重みによる配分

cpu.max: 帯域制御とスロットリング

スケジューラを観測する

procファイル: sched と schedstat

perf sched

chrt と nice / renice

アプリ開発者のための実務指針

まとめ

参考リンク

システムコールの仕組み - ユーザー空間とカーネル空間の境界、モード遷移とそのコスト

ファイルシステムの仕組み徹底解説 - inode・ジャーナリング・ページキャッシュ

zram 実践入門 - 圧縮スワップの効果測定と「優先度でティアリング」の落とし穴

スケジューラが解いている問題

コンテキストスイッチ、タイムスライス、プリエンプション

コンテキストスイッチで何が起きるか

タイムスライスは長くても短くても困る

プリエンプション: 取り上げる仕組み

古典的なスケジューリングアルゴリズム

FIFOとコンボイ効果

SJFとSTCF

ラウンドロビン

優先度スケジューリングと飢餓

MLFQ: 振る舞いから優先度を学習する

Linuxスケジューラの歴史

O(1)スケジューラ

CFS: 理想的なマルチタスクCPUを模倣する

nice値と重み

EEVDF: lagと仮想デッドライン

sched_ext: BPFでスケジューラを書く

スケジューリングクラスとポリシー

リアルタイムポリシーの注意点

SCHED_DEADLINE

マルチコアでのロードバランシングとCPUアフィニティ

スケジューリングドメイン

CPUアフィニティ: tasksetとsched_setaffinity

cgroupのcpu.weightとcpu.max

cpu.weight: 重みによる配分

cpu.max: 帯域制御とスロットリング

スケジューラを観測する

procファイル: sched と schedstat

perf sched

chrt と nice / renice

アプリ開発者のための実務指針

まとめ

参考リンク

関連記事

システムコールの仕組み - ユーザー空間とカーネル空間の境界、モード遷移とそのコスト

ファイルシステムの仕組み 徹底解説 - inode・ジャーナリング・ページキャッシュ

zram 実践入門 - 圧縮スワップの効果測定と「優先度でティアリング」の落とし穴

ファイルシステムの仕組み徹底解説 - inode・ジャーナリング・ページキャッシュ