CPUスケジューリング — 公平さと応答性のあいだの取引
一言でいうと
スケジューラーは、スループット、待ち時間、応答時間、公平性という、互いに衝突する目標の間で何を諦めるかを決めるポリシーです。
なぜ必要なのか
実行可能なプロセスがコアより多ければ、誰かは待たなければなりません。どの順番で乗せるかによって、同じ作業の集まりの平均待ち時間が何倍も変わります。有名な例を見てみましょう。
3つのプロセスのCPUバーストが24、3、3で、すべて同時に到着したとします。
- P1、P2、P3の順に実行すると、待ち時間は0、24、27で、平均は17です。
- P2、P3、P1の順に実行すると、待ち時間は6、0、3で、平均は3です。
同じ仕事を同じ時間に終えるのに、平均待ち時間が5倍以上も違います。長い作業の後ろに短い作業が並ぶこの現象をコンボイ効果(convoy effect)といい、先に来た順に処理するFCFSの代表的な弱点です。
どう動くのか
主要なアルゴリズムの特徴は、次のように整理できます。
| アルゴリズム | プリエンプション | 飢餓 | 長所 | 弱点 |
|---|---|---|---|---|
| FCFS | なし | なし | 単純 | コンボイ効果 |
| SJF | なし | あり | 平均待ち時間が最適 | 次のバーストを知ることができない |
| SRTF | あり | あり | SJFより良い応答 | 予測が必要、スイッチが増える |
| 優先度 | 両方 | あり | ポリシーを反映できる | 飢餓、エージングが必要 |
| ラウンドロビン | あり | なし | 応答時間が均等 | 割り当て量の選択が難しい |
| 多段フィードバックキュー | あり | あり得る | 最も柔軟 | パラメーターが多い |
SJFは平均待ち時間において最適であることを証明できますが、致命的な問題があります。次のCPUバーストの長さを事前に知ることができません。そのため実際の実装は、過去のバーストの指数平均で予測します。次の予測値は、アルファ掛ける直近の実測値、足す、(1引くアルファ)掛ける前回の予測値という形で、通常アルファには0.5を使います。
ラウンドロビンでは、時間の割り当て量の選択がすべてです。割り当て量が大きすぎるとFCFSと同じになり、小さすぎるとコンテキストスイッチのコストが実際の作業時間を食いつぶします。経験的には、CPUバーストの80パーセントが割り当て量の中で終わるように設定します。
Linux CFSは、少し違う角度からアプローチします。各タスクの仮想実行時間(vruntime)を追跡し、その値が最も小さいタスクを次に実行します。vruntimeは実際の実行時間を重みで割った値で、重みはnice値から決まります。niceが低ければ(優先度が高ければ)重みが大きく、vruntimeがゆっくり増えるので、より頻繁に選ばれます。この構造を赤黒木で管理するので、挿入と削除は対数時間で済み、次の実行対象は常に一番左のノードです。
現場での姿
コンテナ環境でCPU制限をかけるとき、この概念がそのまま登場します。cgroupのCPUシェア(shares/weight)はCFSの重みに当たり、競合があるときの比率を決めます。CPUクォータは、周期ごとに使える時間の上限を決めます。この2つを混同して「シェアを下げたのに、なぜまだCPUを使い切るのか」と尋ねるケースが多いのですが、シェアは競合するときにだけ意味があり、遊んでいるCPUをふさぐことはありません。
クォータ側には別の落とし穴があります。スレッドが多いアプリケーションは、周期の序盤にクォータを使い切り、残りの期間まるごと止まるスロットリングを経験します。平均CPU使用率は低いのに、応答レイテンシのテールだけが跳ねる症状が出たら、スロットルカウンターを最初に見るべきです。
CPUを使わない待機のほうがはるかに多い
ここまでは、実行する準備ができたプロセスがCPUを奪い合う話でした。しかし実際のサーバーでプロセスが待つ時間の大部分は、CPUの順番ではなく入出力が終わるのを待つ時間です。この区別ができないと、性能問題をまるごと誤診することになります。
ロードアベレージは、代表的な誤解の場所です。Linuxのロードアベレージは、実行可能なプロセスだけでなく、ディスク入出力を待つプロセスまで一緒に数えます。そのため、CPU使用率が20%なのにロードアベレージが30という状況が、正常に起こり得ます。このときCPUを増やしても何の効果もなく、見るべきはディスクやネットワーク側です。
プロセスの状態を見ると、この区別がそのまま現れます。Rは実行中、または順番を待っている状態で、Dは割り込みできない待機です。D状態が長く続くと、そのプロセスはシグナルでも死なないので、ストレージが止まったときに終了すらできないプロセスが溜まる状況が、ここから生まれます。
そして待機そのものがスケジューリングに影響を与えます。長く待ってから起きたプロセスは、その間CPUを使っていないので、先ほど見たvruntimeが小さく、起きた直後に優先的に実行されます。対話型プログラムの反応が速いのは、この性質のおかげです。キー入力を待つ間はvruntimeが増えないので、入力が入ると、計算だけをしていたプロセスを押しのけて先に動きます。
診断の順序に置き換えると、次のようになります。応答が遅いとき、CPU使用率だけを見て済ませません。実行待ちの列が長いのか、入出力待ちが長いのか、それとも先ほど見たスロットリングにかかっているのかを、まず切り分けます。この3つは原因も対応もまったく違い、ダッシュボードのCPUグラフ1つでは区別できません。
続くクイズで確認すること
同じ作業の集まりでも、順番を変えるだけで平均待ち時間がなぜ変わるのかを計算できるか、CFSのvruntimeが優先度をどう表現するのかを確認します。