スケジューラ
Scheduler
限られたCPUをどのプロセス・スレッドに割り当てるかを決める仕組み。公平さと応答性を両立させる。
概要
スケジューラ（scheduler）は、CPUという限られた資源を、動きたがっている多数のプロセスやスレッドのうち「次は誰に使わせるか」を決めるOSの中核部品です。コアの数よりも実行したい処理のほうが常に多いなかで、誰かが采配を振らなければCPUの奪い合いになります。その采配役、いわば実行順を裁く審判がスケジューラです。
私たちが1台のパソコンで、動画を再生しながら文書を書き、裏でファイルをダウンロードできるのは、スケジューラがCPUを高速に切り替えて各処理に少しずつ時間を配っているからです。切り替えがあまりに速いため、人間には複数の処理が同時に進んでいるように見えます。この「見かけの同時実行」の質 — 操作がキビキビ反応するか、重い処理が全体を巻き込んで固まるか — は、スケジューラの判断の良し悪しに大きく左右されます。
なぜ生まれたか
CPUのコア数には限りがあるのに、動きたいプロセスやスレッドは常にそれを上回ります。もし采配する者がいなければ、たまたま先にCPUを握った処理が、たとえば大量の計算に何十秒もかかるような重い仕事だった場合、その間ずっとCPUを独占し続けてしまいます。すると、その裏でユーザーがマウスを動かしてもクリックしても反応が返らず、画面が固まったように見えます。重要度の高い処理が、たまたま順番待ちで後ろに並んだせいで後回しにされることも起きます。
この問題を解くには、どれか1つに使わせっぱなしにせず、短い時間片ごとに強制的に交代させ、しかも「どれを優先し、どれだけ公平に配るか」を判断する仕組みが要ります。対話的な処理にはすばやく順番を回して反応を保ちつつ、重い計算にも着実に時間を割り当て、全体として誰も飢えさせない — この難しい裁定を専門に担うためにスケジューラが生まれました。
詳細
タイムスライスとプリエンプション
スケジューラの基本戦略は、CPU時間を「タイムスライス（時間片、数ミリ秒程度）」に区切り、各スレッドに順番に短い持ち時間を与えることです。持ち時間を使い切ったスレッドは、たとえ処理の途中でも強制的にCPUから降ろされ、次のスレッドに交代させられます。この強制的な横取りを「プリエンプション（preemption）」と呼びます。
この横取りを可能にしているのが割り込みです。OSは一定間隔でタイマ割り込みを受け取るようにしておき、割り込みが来るたびにスケジューラが起動して「持ち時間を使い切ったか、交代すべきか」を判断します。もしタイマ割り込みが無ければ、CPUを握った処理が自ら手放すのを待つしかなく、行儀の悪いプログラム1つで全体が止まってしまいます。プリエンプティブなマルチタスクは、割り込みという土台があって初めて成り立ちます。
時間軸で見る — 誰がCPUに乗るか
3つのスレッドが1つのコアを分け合う様子を時間軸で追うと、タイムスライスごとの交代と、待ちに入ったスレッドが列から外れる動きが見えてきます。
タイムスライスの長さを変えると応答性と効率がどう変わるか、実際に動かして確かめられます。
「実行」を押すと、ここに実行の時間軸が描かれます。
タイムスライスを選んで「実行」を押してください。3つのタスクが1つのCPUコアを交代で使う様子が時間軸に描かれます。まずは 5 のまま一度動かし、次に 2 と 20 で比べてみてください。
コンテキストスイッチのコスト
スレッドを交代させるには、いま動いていたスレッドのCPU上の状態（レジスタやプログラムカウンタ）を保存し、次のスレッドの状態を読み込む「コンテキストスイッチ（文脈の切り替え）」が必要です。この切り替え自体はごくわずかな時間ですが、無視できない隠れたコストがあります。それはCPUキャッシュが冷えることです。スレッドが動いている間、そのスレッドが頻繁に使うデータはCPUのすぐ近くの高速なキャッシュに乗っています。別のスレッドに切り替わると、そのキャッシュの中身は新しいスレッドのデータで置き換えられていき、元のスレッドが戻ってきたときには、また遅いメモリから読み直すことになります。だからタイムスライスを極端に短くして切り替えを増やしすぎると、かえって全体の効率が落ちます。反応の良さと切り替えのオーバーヘッドは、そこにトレードオフがあります。
優先度と公平性
すべてのスレッドを完全に平等に扱えばよいわけではありません。動画の再生のように遅れると体感に響く処理と、裏で走る集計処理とでは、割り当てるべき優先度が違います。UNIX系OSには古くから「nice値」という優先度の指標があり、値を高くする（nice＝譲る、の意）ほど他に順番を譲る低優先度になります。
現代の Linux で長く使われてきた CFS（Completely Fair Scheduler、完全公平スケジューラ）は、「各スレッドがこれまでに使ったCPU時間」を記録し、いちばん使っていないスレッドに次を回すという発想で公平さを実現します。優先度が高いスレッドには時間の進み方を割り引いて計算することで、「公平に配りつつ、重要なものには多めに」を1つの物差しで両立させています。完全な平等ではなく、重み付きの公平さを目指すのがポイントです。
IOバウンドとCPUバウンド
処理には性格の違いがあります。ディスクやネットワークの応答をよく待つ処理を「IOバウンド」、ひたすら計算し続ける処理を「CPUバウンド」と呼びます。IOバウンドな処理は、短くCPUを使ってはすぐ待ちに入るため、上の図のスレッドBのように待っている間はCPUの割り当て候補から外れます。スケジューラはこうした処理には気前よくCPUを回しても、すぐ手放してくれるので他を邪魔しません。むしろ待ちから戻ってきたIOバウンドな処理を優先的に走らせると、対話の反応が良くなります。逆にCPUバウンドな処理ばかりだと、タイムスライスをきっちり使い切る者同士の順番待ちになります。この性格の違いを見分けて振る舞いを変えることが、良いスケジューリングの勘所です。
応用 — 資源と要求のマッチング
「限られた資源を、それを欲しがる多数の要求にどう割り当てるか」という構図は、CPUの外にも広がります。Kubernetesのスケジューラは、コンテナ（Pod）を「どのサーバ（ノード）に載せるか」を決めますが、CPU・メモリの空き状況や配置の制約を見て最適な割り当て先を選ぶという発想は、OSのCPUスケジューラとまったく同じです。対象が「1コア上の時間」から「クラスタ全体の計算機」に変わっただけで、資源と要求をマッチングする審判、という本質は変わりません。スケジューラという考え方は、レイヤを問わず繰り返し現れる普遍的なパターンなのです。