ここ数ヶ月、Linux カーネルが「次にどのタスクに CPU を渡すか」を決める仕組みについての連載を、数週間おきに読み進めてきた。全4回。最初の3回は満足のいく物語だった――スケジューラは、測れないもの（公平さ）を計算可能にするために虚構の時計を発明し、破れないもの（保証）を実装可能にするために、拒否権に裏打ちされた本物の契約を発明する。だが最終回は、その満足の一部を崩す。きれいな保証が、同時に2種類の資源をカバーするよう求められた瞬間に何が起きるかを見せてくれるのだ。その答えは、僕が思っていたより遠くまで一般化できる。

似ているようで違う2つの問題

現代の CPU は実質的に複数の CPU の集合体だ――コア、ソケット、メモリノードが、それぞれ違う長さ・違うコストの配線で繋がっている。Linux が「いつ」タスクを走らせるかを決めるとき、そこには本物の理論が使える。EEVDF（Earliest Eligible Virtual Deadline First）は、2023年10月の v6.6 で従来の Completely Fair Scheduler に代わって既定ポリシーとなったが1、公平さを1個のスカラー――lag――に還元し、そのスカラーが有界であることを証明する。その上に乗る SCHED_DEADLINE は、公平さを本物の契約に変える。タスクは「周期ごとにこれだけの実行時間が必要」と申告し、入口の admission control がその申告を他の全タスクの申告に足し合わせて、合計が CPU の 100% を超えるなら拒否する。受理されたタスクだけが、「どれだけ遅れうるか（tardiness）」について数学的に有界な保証を得る2。

だが「いつ」はスケジューラの仕事の半分でしかない。「どこで」――マシンのどのコアでタスクを実際に走らせるか――も決めなければならない。そしてこの決定は、同じ服を着た別種の問題であることが分かる。

理論を持たない軸

時間の軸にはおよそ300行の原理的な数学が与えられた。空間の軸に与えられたのは、それとは違うもの――ヒューリスティックの積み重ねだ。Linux は物理マシンを「スケジューリングドメイン」の木として表現する――ハイパースレッドの兄弟、同じダイ上のコア、ソケット、NUMA ノード――そして周期的にその木を辿り、最も混んでいるグループとその中で最も混んでいるキューを探し、空いている側へ仕事を動かす。空いているコアを間に合う速さで見つけるにはそれ自体独自のショートカットが要り（フルスキャンする価値があるかを事前判定する使用率チェックなど）、そのショートカットは今も継ぎ足され続けている。物理的な距離のための vruntime は存在しない。「このタスクをこのコアからあのコアへ動かすコストはどれだけか」を、lag が「このタスクは自分の取り分に対してどれだけ CPU を受け取ったか」を捉えるのと同じように、1個の虚構の数値で捉える方法を、誰もまだ発明できていない。

これは怠慢ではない。2016年の実測研究「The Linux Scheduler: A Decade of Wasted Cores」は、このヒューリスティック層が現実の、再現可能なバグを生むことを示した――実行可能なスレッドが他所で待っているのに、コアが数秒間もアイドルのまま座っている。ある例では、スケジューリンググループの構成方法のバグにより、同じコア集合が重複する2つのグループに登録されてしまい、起動時にそこへ配置されたタスクは二度とバランシングで外へ出ていけなくなっていた。この論文は、同期の多い科学計算ワークロードで数倍の速度低下、カーネルビルドで2桁パーセントのレイテンシ増加、商用データベースで同程度のスループット低下を報告している――すべて配置の問題であり、公平さの数学そのものの欠陥ではない3。実運用では、人々が頼る修正策はより賢いスケジューラではなく taskset だ。タスクを手動でコアに固定し、自動的な判断そのものから降りてしまう。

契約が破れる場所

ここが、数週間前に僕自身が書いたことへの考えを変えた部分だ。SCHED_DEADLINE の admission control による保証――以前の記事で、「自分を縛るタスクは、単に優先度が高いと主張するだけのタスクより信頼される」という性質ゆえに、スケジューラ全体の中で最も強い約束だと僕が呼んだもの――は、時間の軸に沿ってのみ成立することが分かった。タスクを特定のコアの部分集合に固定する（CPU affinity）と、その瞬間に保証が破れうる。2021年の論文は、一般的な affinity マスクの下では SCHED_DEADLINE が tardiness の保証を確実には維持できず、これを一般に修正するには非現実的なほどの内部の作り直しが必要になると報告している。修正可能なのは限定的なケース（semi-partitioned affinity）だけだ4。根本の理由はコードのミスではない――1つの共有資源（CPU の総時間）に対してタスクを受理するのは単純な算術チェックだが、CPU 時間と、許可されたコアの特定部分集合を同時に受理するのは、ビンパッキング問題になり、ビンパッキングは一般に NP困難だからだ。示唆的なのは、この保証のギャップが、tardiness 保証が最初に実装されてから何年も経った後も、スケジューラの担当者自身によって未解決問題として挙げられていたことだ5。

つまり、単体で見たときにあれほど信頼できると僕が感じた約束――「これだけを、これだけの頻度で消費する」――は、「どこで（空間）」という第2の軸が「いつ（時間）」に同乗した瞬間、静かに約束であることをやめる。申告の内容は何も変わっていない。変わったのは、それが同時に何個の独立したものを保証するよう求められているか、だ。

一般化できること

ここには、はっきり述べる価値のある主張があると思う。カーネルに限った話には見えないからだ――保証の強さは、それがカバーする独立に変動する資源の個数に反比例する。応答時間を約束するベンダーは、検証可能な主張をしている。応答時間と固定チームと固定予算と固定稼働時間を約束するベンダーは、ある点を超えると、約束の時点で誰にも検証できない内的整合性を主張していることになる――嘘をついているからではなく、検証すべき問題そのものが組み合わせ的に難しくなるからだ。これは野心的な契約への反論ではない。「全部を約束します」と「これ1つを約束します」は、両方とも誠実に言われたとしても、違う種類の言明だと気づくべきだという主張だ。

もう1つ、これより狭いが隣接する観察がある。時間の軸を扱いやすくする虚構の時計――vruntime、lag――が機能するのは、CPU 時間がそもそも人為的・恣意的な単位だからにすぎない。それを「自然に」消費する方法など最初から存在しなかったので、そのための会計方式を発明することに概念上のコストはかからない。コア間の物理的な距離はそうではない。キャッシュ共有、メモリレイテンシ、電力ドメインは、スケジューラが割り当てを始める前から、シリコンに関する事実として固定されている。すでに形を持った資源に、時計を発明することで蓋をすることはできない――できるのは、自分が選んだわけではないその形を尊重するヒューリスティックを組み上げることだけだ。この区別――恣意的だからこそ割り当て可能なもの、と、物理的であるにもかかわらず割り当てざるを得ないもの――が、カーネルの外でどこまで通用するのかはまだ分からない。だが、土地・電波帯域・注意のように、希少で半ば自然なものを人々が分け合おうとする場所ならどこにでも顔を出しそうな種類の話だと感じている。

連載の著者たちは今、sched_ext に注目している。2024年後半にカーネルにマージされた仕組みで、カスタムスケジューラをカーネル本体に組み込む代わりに、ロード可能な BPF プログラムとして走らせられるようにするものだ6。これが空間軸の問題への本物の答えなのか、それとも同じ未解決のヒューリスティックを、より反復開発しやすい場所へ移しただけなのか、僕にはまだ分からない。これが今、僕が抱え続けている問いだ――より柔軟な実験の場は、難しい問題への本当の前進なのか、それとも未解決のままにしておくための、より居心地の良い場所なのか。

  1. Michael Larabel, “EEVDF Scheduler Merged For Linux 6.6,” Phoronix. 参照日: 2026-08-15. ↩

  2. “Deadline Task Scheduling,” The Linux Kernel documentation. 参照日: 2026-08-15. ↩

  3. Jean-Pierre Lozi, Baptiste Lepers, Justin Funston, Fabien Gaud, Vivien Quéma, Alexandra Fedorova, “The Linux Scheduler: a Decade of Wasted Cores,” EuroSys 2016. 参照日: 2026-08-15. ↩

  4. “On the Defectiveness of SCHED_DEADLINE w.r.t. Tardiness and Affinities, and a Partial Fix,” RTNS 2021. 参照日: 2026-08-15. ↩

  5. “GEDF Tardiness: Open Problems Involving Uniform Multiprocessors and Affinity Masks Resolved,” ECRTS 2019（Peter Zijlstra の ECRTS 2017 基調講演の未解決問題リストへの言及を含む）. 参照日: 2026-08-15. ↩

  6. “Sched_EXT With Linux 6.19 Improves Recovering For Misbehaving eBPF Schedulers,” Phoronix（sched_ext の拡張可能スケジューラクラスとしてのマージ経緯の背景情報）. 参照日: 2026-08-15. ↩