Linux スケジューラ：実行可能タスクから CPU 時間の割り当てへ

リクエストのデータが準備され、処理スレッドもウェイクアップされたにもかかわらず、応答がなかなか返ってこない。このような場合、スケジューラのいくつかの判断基準をたどって追跡する必要があります。⁠どこで実行するか、どのくらいの CPU 時間を割り当てられるか、この瞬間に誰が順番か。

本稿では、通常の公平スケジューリングを主に扱います。Linux は 6.6 から EEVDF を導入しました。数値モデルはアルゴリズムの理解のために用いられ、実装の詳細はローカル Linux 7.2 を対照とします。

1. 実行キューは「誰が今、実行する機会があるか」に答える

Linux は主に CPU ごとに実行キューを管理しています。現在実行中のタスクも、実行待ちのタスクも TASK_RUNNING 状態になり得ますが、I/O や条件待ちでスリープしているタスクは、優先度が高くても CPU を消費し続けることはありません。ウェイクアップパスではタスク状態が更新され、適切な CPU が選択されてキューに挿入されます。新しいタスクが現在のタスクをプリエンプトするに値する場合、再スケジューリング要求が発生します。

再スケジューリング要求は、任意の命令ポイントでの強制ジャンプではありません。カーネルは対応するスケジューリング可能なポイントで要求をチェックする必要があります。割り込み、プリエンプションの無効化、ロック制約、およびカーネルプリエンプションモデルは、切り替えのタイミングに影響を与えます。スケジューラが一度実行しても、依然として現在のタスクが選択される可能性があるため、「schedule() を実行する」と「prev != next のコンテキストスイッチが発生する」は同義ではありません。

CPU ごとのキューはグローバルな競合を減らしますが、スケジューリングが完全にローカル操作であるわけではありません。遠隔タスクのウェイクアップ、負荷のプル、タスクのマイグレーションには、複数の CPU とキューロックの調整が必要です。CPU アフィニティ、cpuset、有効なスケジューリングポリシーは候補範囲をまず限定し、負荷分散は許可された範囲内で割り当てを改善するだけで、均等に見せるために隔離設定を迂回することはできません。

2. 公平な計測：実時間を仮想サービスに変換

まず、A と B のみの理想モデルを見てみましょう。両者は継続的に実行可能で、重みが 2:1 です。1 つの CPU の 9 ms の時間を共有します。重みに基づいて分配すると、A は 6 ms、B は 3 ms を得ます。

両者の実際の時間は異なりますが、各自の重みで割ると、どちらも 3 つの仮想単位分進みます。⁠重みが大きいタスクの仮想クロックはゆっくり進み、同じ進行度に追いつくにはより長い実行時間が必要です。

一般的な表現は以下の通りです。

$$\Delta v_i=\Delta t_i\frac{w_0}{w_i}$$

ここで $w_0$ は基準重みです。

例えば、nice 0 の基礎重みは 1024、nice 5 は 335 です。これら 2 つのみが同じ公平スケジューリング階層、同じ CPU 上で継続的に競合する場合、前者の理想的なシェアは 1024 / (1024 + 335) = 75.35% 程度になります。

この比率は競合集合の変化に応じて変わります。相手がブロックされると、前者はより多くのアイドル時間を使用できます。新しいタスクや cgroup 階層が追加されると、シェアを再計算する必要があります。nice は相対的な重みを表しており、固定された CPU パーセンテージではありません。

以下では、重みを幅として、実際の時間を面積として描画します。割り当てと重みを調整すると、高さによって誰がより多くの正規化サービスを得たかが示されます。

古典的な CFS は、vruntime を用いて「正規化サービスを得た量が最も少ないタスク」に近づき、遅れているタスクを優先して補填します。これにより長期シェアを説明できますが、短いリクエストがどれだけ速く応答を得るべきかを十分に表現しているわけではありません。EEVDF はこれに基づき、⁠実行資格と合格したリクエストの順序を分離します。

3. EEVDF：資格の閾値と仮想デッドラインの役割分担

ステップ 1：lag を用いて資格を判断する

固定された実行可能集合の簡易モデルにおいて、タスクの仮想実行時間を vᵢ、重みを wᵢ、システム仮想時間をその加重平均 V とします。タスクのサービス差額は以下のように書けます。

$$V=\frac{{\sum }_i{w}_i{v}_i}{{\sum }_i{w}_i},{\mathrm{lag}}_i=w_i(V-v_i)$$

lag が 0 でも資格があります。正の lag は、公平な基準に対してサービスが不足していることを示し、選択に参加する資格があります。負の lag は、すでに先行していることを示し、一時的に短いリクエストだけで他のタスクをプリエンプトすべきではありません。

ステップ 2：合格したリクエスト間で期限を比較する

現在のリクエストが実際の実行量 rᵢ を希望する場合、その仮想デッドラインは以下の式で理解できます。

$$d_i=v_{i,\mathrm{start}}+r_i\frac{w_0}{w_i}$$

この式は、新しいリクエストが期限を確立するときの関係を記述しており、このとき vᵢ はそのリクエストの開始仮想位置です。リクエストの実行中に vruntime は引き続き増加しますが、すでに確定された deadline はそれに伴って後方にシフトしてはいけません。新しいリクエストのみが期限を再設定します。以下のスナップショットは、各タスクのリクエスト起点の状態を選択し、直接比較できるようにしています。

合格したエンティティの中では、仮想デッドラインが早い方を優先して選択します。ここでいう deadline は仮想サービス座標であり、壁時計時刻でも、SCHED_DEADLINE のリアルタイム完了保証でもありません。

シミュレーション：なぜ最後に B が選ばれるか

3 つの等重みタスクを考えます。基準重みを 1 に正規化します。

このとき V = (98 + 99 + 103) / 3 = 100 です。vruntime のみが最小であれば A が選ばれます。deadline のみが最小であれば C が選ばれます。EEVDF はこのスナップショットで B を選択します。C の短いリクエストは、すでに多くのサービスを得ているという事実を相殺できません。一方、B は A よりも期限が切れている合格したリクエストであり、優先的な応答を得ます。これが、2 つの判断を分離する必要がある理由です。

C のサービス位置を変更すると資格に影響します。B のリクエスト量を変更すると期限に影響しますが、すでに得られたサービスは変わりません。パラメータの調整は毎回新しいリクエストスナップショットとなります。

この小さなモデルを実行して結果を確認できます。Linux のウェイクアップ、階層、マイグレーションロジックをシミュレートするものではありません。

from fractions import Fraction as F

tasks = {
    "A": {"w": F(1), "v": F(98), "r": F(10)},
    "B": {"w": F(1), "v": F(99), "r": F(5)},
    "C": {"w": F(1), "v": F(103), "r": F(1, 4)},
}
V = sum(t["w"] * t["v"] for t in tasks.values()) / sum(
    t["w"] for t in tasks.values()
)
eligible = {}
for name, t in tasks.items():
    lag = t["w"] * (V - t["v"])
    deadline = t["v"] + t["r"] / t["w"]
    print(name, "lag=", lag, "deadline=", deadline)
    if lag >= 0:
        eligible[name] = deadline
assert V == 100
assert min(eligible, key=eligible.get) == "B"

教育用モデルからカーネル実装へ

リクエスト量を短くすることは応答順序に影響しますが、タスクの長期重みを自動的に増やすわけではありません。実際のカ kernel は、タスクが「先行するまで実行して、短時間スリープし、ウェイクアップ後に再び信用を得る」という方法で公平性を破壊するのを防がなければなりません。スリープ中の lag の保存、減衰、および遅延出隊の会計処理は、この制約を維持する手段です。遅延出隊中の会計エンティティは、イベントを待っているタスクがユーザーコードを実行できることを意味しません。

実際の実装では検索コストの問題も解決する必要があります。ローカルの kernel/sched/fair.c に関連する木構造は deadline で整理されており、サブツリー vruntime 情報を用いて合格エンティティの検索を剪枝します。pick_eevdf() は現在のリクエスト保護も処理します。

階層化されたグループエンティティ、入隊/出隊の修正、および整数精度により、V の維持は固定集合の平均値よりも複雑になります。ソースコードを読む際は、まず「資格と期限」という 2 つの判断を確認し、その後これらの実装の詳細を追跡することをお勧めします。EEVDF ドキュメント、CFS デザイン

4. スケジューリングポリシーとスケジューリングクラス：3 種類の deadline を混同しない

通常、タスクは SCHED_OTHER を使用します。カーネルでは SCHED_NORMAL と呼ばれることも多いです。公平クラス内部では EEVDF が採用されており、アプリケーションが SCHED_EEVDF に変更して初めて有効になるような一般的なポリシーは存在しません。リアルタイムポリシーと拡張スケジューリングは別の選択肢です。

通常、deadline クラスはリアルタイムクラスより先に、リアルタイムクラスは公平クラスより先に位置します。カーネルには stop などの内部クラスもあり、sched_ext を有効化する際は実行モードとクラス順序を合わせて読む必要があり、3 行の表をすべてと捉えてはいけません。

対照：スケジューリング期限とビジネスタイムアウト

runtime=2 ms、deadline=10 ms、period=10 ms を例に挙げます。タスクは、各周期で最大 2 ms の CPU サービスが必要であり、対応する期限を要求します。パラメータは runtime ≤ deadline ≤ period などの制約を満たす必要があり、准入チェックも通過する必要があります。

これは、アプリケーションが 10 ms ごとに自動的に関数を呼び出すことを意味するものではありません。アプリケーションは依然としてワークを解放し、実行予算を制御し、ブロックを分析して、期限が実現可能かどうかを議論する必要があります。

これら 3 種類の期限は異なる階層に属しており、相互に代替できません。SCHED_DEADLINE、sched_ext

5. cgroup：重みが競合シェアを決定し、クォータが利用可能な上限を決定する

グループ重み：まずグループに分配し、次にタスクに分配する

公平スケジューリングは階層化できます。ルート配下に A、B の 2 つのグループがあり、重みが 2:1 で、A 内に 2 つの等重みで継続的に実行可能なタスク、B 内に 1 つのタスクがあるとします。1 つの CPU のみ、クォータがない場合を考慮すると、A はまず約 2/3 を獲得し、グループ内でそれぞれ 1/2 に分配されるため、3 つのタスクはそれぞれ約 1/3 になります。A にタスクが 1 つ追加されると、A は依然として約 2/3 を占め、内部ではそれぞれ約 2/9 になります。B の唯一のタスクは依然として約 1/3 です。グループ隔離により、「スレッドをいくつか作成する」ことが別のグループのシェアを直接侵害する必要はありません。

クォータ：マルチコアで予算を共有して消費する

cpu.weight は相対的なシェアを示すものであり、リソースの予約や厳格な上限ではありません。cpu.max は、周期内でのグループの総 CPU 時間を制限します。例えば 50000 100000 は、100 ms の周期で最大 50 ms の CPU 時間を使用できることを意味します。2 つのスレッドが 2 つの CPU 上で同時に実行する場合、合計 50 ms の予算を約 25 ms で使い果たし、その後補充を待ってスロットルされます。「各 CPU が 50 ms 使用可能」と理解してはいけません。

並列数を調整し、壁時計時間を周期の境界までドラッグします。各 CPU の実行帯は、同じ予算から時間を差し引きます。

冒頭の遅いリクエストに戻りましょう。マシン全体に空き CPU があったとしても、この cgroup の現在の周期の予算はすでに使い果たされている可能性があります。⁠供給に余力があっても、そのグループが使用できるクレジットがあるとは限りません。

調査時には、cpu.stat のスロットル回数/時間、cpu.max、およびリクエスト遅延を同じ時間ウィンドウで比較します。スロットルの増分はトラブルシューティングの手がかりを提供しますが、具体的な遅いリクエストについては、アプリケーションのロック、I/O、および上位層のキューと組み合わせて分析する必要があります。cgroup v2 CPU コントローラ

6. マルチコア配置：均等であることが必ずしも最速ではない

2 つの CPU がそれぞれ 1 つのタスクを実行している場合、1 つが混雑して 1 つがアイドルであるよりも合理的に見えますが、マイグレーションにはコストがかかります。タスクが CPU 0 でキャッシュを温めた直後に CPU 1 にマイグレートすると、局所性が失われます。データが主に別の NUMA ノードにある場合、メモリアクセスが遠くなる可能性もあります。SMT の兄弟スレッドは実行リソースを共有するため、機械的に 2 つの完全に独立したコアとして扱うことはできません。そのため、スケジューラはアイドル容量、キャッシュ、トポロジ、およびエネルギー消費の間でトレードオフを行います。

PELT などの歴史的な信号は、タスクの直近の実行/実行可能行動を推定するのに役立ちます。利用率、実行可能負荷、および加重負荷は同じ数値ではありません。タスクが CPU を非常に長く待機している場合、それはキュー待ちの圧力を示す可能性がありますが、実際に実行された割合のみが、消費された計算力を直接反映します。ある CPU が 100% であるという短いサンプリングは、マイグレーションが必ずしも利益をもたらすとは予測できず、それがシステム全体のボトルネックであることも保証しません。

ウェイクアップ配置、周期的な均衡化、およびアイドル CPU のプル作業は、異なる状況で発生します。アフィニティと cpuset は候補集合を縮小し、異種 CPU の能力とエネルギー消費ポリシーは選択をさらに変化させます。したがって、調査する際は、まずタスクが実際にどの CPU を使用できるかを確認し、負荷が不均等かどうかを説明してから、1 つの CPU にバインドされたタスクについては、他の CPU の数が増加してもキュー待ちが自動的に解消されるわけではないことを理解する必要があります。

7. 再現可能な読み取り専用観察

以下では、現在の Python プロセスのポリシー、nice、アフィニティ、および一部のスケジューリング統計のみをクエリし、ポリシーやシステム構成を変更することはありません。/proc/self/sched のフィールドはカーネル構成の影響を受けるため、固定された列数形式として解析すべきではありません。

import os
from pathlib import Path

print("policy:", os.sched_getscheduler(0))
print("nice:", os.getpriority(os.PRIO_PROCESS, 0))
print("allowed CPUs:", sorted(os.sched_getaffinity(0)))
try:
    for line in Path("/proc/self/sched").read_text().splitlines():
        if any(key in line for key in (
            "se.sum_exec_runtime", "nr_switches", "nr_voluntary_switches",
            "nr_involuntary_switches", "se.load.weight", "policy", "prio"
        )):
            print(line)
except OSError as exc:
    print("sched statistics unavailable:", exc)

1 回の遅延を分解するには、イベントの発生、sched_wakeup、およびタスクが実際に sched_switch の next 位置に現れる時間をそれぞれ観測する必要があります。ウェイクアップから実行までの間隔は、実行キューの待機および関連するスケジューリング遅延を反映します。実行時間には、アプリケーション自体の作業時間も含まれます。これらは、レジスタとアドレス空間の切り替えの純粋なコストとは等しくありません。次の記事コンテキストスイッチでは、具体的な切り替えを通じてこれらの境界を説明します。