スケジューラ
Scheduler ・ すけじゅーら
限られたCPUを、どのスレッドにいつ・どれだけ使わせるかを決めるOSの仕組み。応答性と効率を天秤にかける。
✦ 30秒で試す — 航海計算する装置は1つなのに、なぜ2つのアプリが同時に動くのかエディタの計算に、CPUが回ってくるのは？予想してみる概要
スケジューラ（scheduler）は、CPUという限られた資源を、動きたがっている多数のプロセスやスレッドのうち「次は誰に、どれだけ使わせるか」を決めるOSの中核部品です。コアの数よりも実行したい処理のほうが常に多いなかで、誰かが采配を振らなければCPUの奪い合いになります。その采配役がスケジューラです。
私たちが1台のパソコンで動画を再生しながら文書を書き、裏でファイルをダウンロードできるのは、スケジューラが数ミリ秒単位でCPUを切り替えて各処理に少しずつ時間を配っているからです。切り替えがあまりに速いため、人間には複数の処理が同時に進んでいるように見えます。キーを打ったら文字がすぐ出るか、重い処理が全体を巻き込んで固まるか——この「見かけの同時実行」の質は、スケジューラの判断に大きく左右されます。
なぜ生まれたか
1950年代の計算機は、仕事を1本ずつ順番に流すバッチ処理で使われていました。1本が入出力を待つ間もCPUは遊び、結果が返るまで利用者は何時間も待たされました。そこで、入出力を待つ仕事の隙間に別の仕事を入れる多重プログラミングが生まれ、さらに1961年に MIT で動いた CTSS のように、タイマで強制的に交代させて多数の利用者が端末から同時に対話できるタイムシェアリングが登場します。「次に誰を動かすか」を決める部品が、ここで独立した役割になりました。
課題は今も同じです。もし采配する者がいなければ、たまたま先にCPUを握ったプロセスが何十秒もかかる重い計算だった場合、その間ずっとCPUを独占してしまい、裏でユーザーがマウスを動かしても反応が返りません。どれか1つに使わせっぱなしにせず短い時間片ごとに強制的に交代させ、しかも対話的なスレッドにはすばやく順番を回し、重い計算にも着実に時間を配り、誰も飢えさせない。この難しい裁定を専門に担うのがスケジューラです。
詳細
タイムスライスとプリエンプション
スケジューラの基本戦略は、CPU時間を「タイムスライス（時間片、数ミリ秒程度）」に区切り、実行できるスレッドに順番に短い持ち時間を与えることです。持ち時間を使い切ったスレッドは、処理の途中でも強制的にCPUから降ろされ、次のスレッドに交代させられます。この強制的な横取りを「プリエンプション（preemption）」と呼びます。
横取りを可能にしているのが割り込みです。OSは一定間隔でタイマ割り込みを受け取るようにしておき、割り込みが来るたびにスケジューラが「持ち時間を使い切ったか、もっと優先すべきスレッドが起きていないか」を判断します。タイマ割り込みが無ければ、CPUを握った処理が自ら手放すのを待つしかなく、行儀の悪いプログラム1つで全体が止まってしまいます。
時間軸で見る — 誰がCPUに乗るか
3つのスレッドが1つのコアを分け合う様子を時間軸で追うと、タイムスライスごとの交代と、待ちに入ったスレッドが候補から外れる動き、そして交代のたびに挟まる小さな隙間が見えてきます。
コンテキストスイッチのコスト
スレッドを交代させるには、いま動いていたスレッドのCPU上の状態（レジスタやプログラムカウンタ）を保存し、次のスレッドの状態を読み込む「コンテキストスイッチ（文脈の切り替え）」が必要です。上の図の隙間がそれで、その間はどのスレッドの仕事も進みません。切り替え自体はマイクロ秒単位ですが、隠れたコストがあります。CPUキャッシュが冷えることです。スレッドが動いている間、よく使うデータはCPUのすぐ近くのキャッシュに乗っていますが、別のスレッドに切り替わるとキャッシュの中身は置き換えられていき、元のスレッドが戻ってきたときには遅いメモリから読み直すことになります。プロセスをまたぐ切り替えでは、アドレス変換の情報（TLB）も入れ替わります。
だからタイムスライスを短くすれば、対話的な処理にすばやく順番が回る一方で、切り替えの回数が増えて全体の効率が落ちます。長くすれば効率は上がりますが、順番を待つ時間が伸びます。応答性と効率は、この1本の物差しの上で綱引きをしています。下の部品で確かめてください。キーを打つと、エディタに順番が回ってくるまでの待ちが測られます。重い計算を増やしたり、タイムスライスの端をドラッグして縮めたりすると、待ちと隙間がどう変わるかが見えます。
エディタはいま眠っています（キー入力待ち）。「キーを打つ」を押すと、エディタに 2ms の仕事が生まれ、CPU の順番が回ってくるまでの待ちが測られます。
時間の単位は ms（擬似）。切り替えの隙間は見えるように誇張しています（実際はマイクロ秒単位だが、キャッシュが冷える損失が後に続く）。
優先度と公平性 — CFS から EEVDF へ
すべてのスレッドを完全に平等に扱えばよいわけではありません。動画の再生のように遅れると体感に響く処理と、裏で走る集計処理とでは、優先度が違います。UNIX 系OSには古くから「nice 値」という指標があり、値を高くする（nice＝譲る）ほど他に順番を譲る低優先度になります。
Linux では 2007年のバージョン 2.6.23 から、CFS（Completely Fair Scheduler、完全公平スケジューラ）が長く使われてきました。CFS は「各スレッドがこれまでに使ったCPU時間」を仮想的な時計（vruntime）で記録し、いちばん使っていないスレッドに次を回します。優先度の高いスレッドは時計の進み方を遅くして、「公平に配りつつ、重要なものには多めに」を1つの物差しで実現しました。
2023年の Linux 6.6 で、CFS の選び方は EEVDF（Earliest Eligible Virtual Deadline First）に置き換えられました。EEVDF は 1990年代の研究に由来する方式で、各スレッドが「本来受け取るべき時間に対してどれだけ貸しがあるか」（lag）を見て、貸しのあるスレッドだけを候補にし、その中で仮想的な締め切りが最も早いものを選びます。短い時間片を求めるスレッドほど締め切りが早くなるため、「少しだけ使ってすぐ待ちに戻る」対話的なスレッドを、CPUを余分に与えることなく早く走らせられます。CFS が経験則の調整で補っていた応答性を、計算の仕組みそのものに組み込んだ形です。
飢餓と優先度逆転
優先度を厳格に守ると、別の問題が起きます。高優先度の仕事が途切れなく来続けると、低優先度の仕事がいつまでも走れない飢餓（starvation）です。古典的な対策は、待たされている時間に応じて優先度を少しずつ上げるエージングで、CFS や EEVDF のように「使った時間」で公平を測る方式は、構造的に飢餓を起こしにくくなっています。
もう1つの落とし穴が優先度逆転です。低優先度のスレッドがロックを握ったまま中優先度のスレッドに横取りされると、そのロックを待つ高優先度のスレッドまで止まってしまいます。1997年に火星探査機マーズ・パスファインダーが繰り返しリセットした原因として知られ、ロックを握るスレッドの優先度を一時的に引き上げる「優先度継承」で対処します。
リアルタイムスケジューリング
通常のスケジューラは「全体として公平に、平均して速く」を目指しますが、制御機器や音声処理では「締め切りまでに必ず終える」ことが重要です。Linux には通常のクラスより必ず優先されるリアルタイムのクラスがあり、優先度の高い順に止まるまで走り続ける SCHED_FIFO、同じ優先度の中で時間片を回す SCHED_RR、周期と締め切りを宣言して予約する SCHED_DEADLINE を選べます。リアルタイムのスレッドが暴走すると通常のスレッドが一切動けなくなるため、Linux は既定でリアルタイムのスレッドが使える時間を1秒あたり0.95秒に制限しています。カーネル自体の中断できない区間を細かく刻んで遅延の上限を小さくする PREEMPT_RT は、長年の別開発を経て 2024年に本流のカーネル（6.12）に取り込まれました。
マルチコアでの負荷分散とアフィニティ
コアが複数あると、スケジューラは「誰を」に加えて「どのコアで」も決めなければなりません。Linux はコアごとに実行待ちの列を持ち、列の長さに偏りが出ると、暇なコアが忙しいコアから仕事を引き取ります（負荷分散）。ただし、スレッドを別のコアへ移すと、それまでのコアのキャッシュに乗っていたデータを失います。そのためスケジューラは、できるだけ同じコアで動かし続けようとします。
アプリケーション側から「このスレッドはこのコアで」と固定するのが CPU アフィニティです（taskset コマンドや sched_setaffinity）。ネットワーク処理のコアと計算のコアを分けたり、メモリが近いコアに寄せたり（NUMA）して、キャッシュと待ち時間を安定させたいときに使います。
I/O バウンドと CPU バウンド
処理には性格の違いがあります。ディスクやネットワークの応答をよく待つ処理を「I/O バウンド」、ひたすら計算し続ける処理を「CPU バウンド」と呼びます。I/O バウンドな処理は、短くCPUを使ってはすぐ待ちに入るため、上の図のスレッド B のように待っている間はCPUの割り当て候補から外れます。待ちから戻ってきた I/O バウンドな処理を優先的に走らせると、対話の反応が良くなり、しかもすぐ手放してくれるので他を邪魔しません。逆に CPU バウンドな処理ばかりだと、タイムスライスをきっちり使い切る者同士の順番待ちになります。
サーバとコンテナでの落とし穴
サーバの運用では、スケジューラの判断が遅延の分布に直接表れます。CPU使用率が100%に近づくと、実行待ちの列に並ぶ時間が急に伸び、平均は問題なく見えても一部のリクエストだけが極端に遅くなります。Linux の「ロードアベレージ」は、この列の長さ（と I/O 待ち）を平均したものです。
コンテナに CPU の上限を設定すると、Linux は cgroup の仕組みで「100ミリ秒ごとに何ミリ秒まで」という枠を与えます。複数のスレッドが並行して枠を短時間で使い切ると、その周期の残りの間は全員が止められます（スロットリング）。平均のCPU使用率は低いのにレイテンシだけが跳ねる、という現象の多くはこれが原因です。上限を外す、周期を見直す、スレッド数を枠に合わせる、といった対処が知られています。
応用 — 資源と要求のマッチング
「限られた資源を、それを欲しがる多数の要求にどう割り当てるか」という構図は、CPUの外にも広がります。Kubernetes にも Pod を「どのノードに載せるか」を決める同名の部品がありますが、これは起動時の配置を決めるもので、CPU の時間を刻々と配るOSのスケジューラとは別物です。それでも、空き状況と制約を見て割り当て先を選ぶという発想は共通しています。対象が「1コア上の時間」から「クラスタ全体の計算機」に変わっても、資源と要求をマッチングする審判、という本質は同じです。
試問
CPU のコアが1つだけの計算機で、重い計算（エンコード・集計・ビルド）3つとエディタが CPU を交代で使う様子が、右端を「いま」として流れます。「キーを打つ」でエディタに 2ms の仕事が生まれ、CPU が回ってくるまでの待ちが測られます。タイムスライス（1回に走れる長さ）は金の丸をドラッグして変えられ、方式は「順番どおり」と「起きたタスクを優先」から選べます。切り替えのたびに、どのタスクも進まない隙間ができます。
エディタはいま眠っています（キー入力待ち）。「キーを打つ」を押すと、エディタに 2ms の仕事が生まれ、CPU の順番が回ってくるまでの待ちが測られます。
時間の単位は ms（擬似）。切り替えの隙間は見えるように誇張しています（実際はマイクロ秒単位だが、キャッシュが冷える損失が後に続く）。