CSロードマップ第9回 — スケジューリング: OSは誰にCPUを渡すのか

投稿 2026/04/27

中級

By Sehyup

66 分読む時間

CSロードマップ第9回 — スケジューリング: OSは誰にCPUを渡すのか

前提知識 — 先にこちらをご確認ください

CSロードマップ第8回 — プロセスとスレッド：OSは実行単位...

TL;DR — 要点まとめ

スケジューラの2つの決定は「誰にCPUを渡すか」と「どれだけ長く渡すか」であり、評価基準はThroughput·Latency·Fairness·Response timeです
LinuxはO(n) → O(1) → CFS (2007) → EEVDF (2024)へ進化しました。CFSはvruntimeが最小のスレッドをRB-treeから常に選択し、EEVDFはeligibilityとdeadlineの軸を追加してレイテンシ感応型タスクをより上手く扱います
Windowsは32段階のpriority + 動的boost(前景ウィンドウ、I/O完了、GUI入力)で応答性を高め、macOSは5段階のQoSで優先度·P/Eコア配置·電力管理を一度に決定します
60fpsの16.67ms、120fpsの8.33msの中で入力→ロジック→物理→描画→presentが終わらなければならず、priority inversion 1回がフレームドロップの原因になります
Unity Job priority、Unreal TaskGraph named thread、SetThreadPriority / pthread / dispatch_qosは同じOSスケジューラの上で異なる抽象を提供しているにすぎません

序論: 「誰に、どれだけ」の問題

前回はプロセスとスレッドが何で、OSがそれをどう抽象化するかを見ました。ここから自然に続く問いがあります。

Ready状態のスレッドが100個あってコアが8個なら、OSは誰にCPUを渡すのでしょうか? そしてどれだけの時間渡すのでしょうか?

この2つの問いに答えるのがスケジューラ (Scheduler) です。そしてその答えが次の2つを決めます。

体感応答性: クリックして0.1秒以内に反応するか、1秒かかるか
フレーム安定性: ゲームが60fpsを維持するか、17msを時々超えるか

今回扱う内容は次のとおりです。

スケジューリング基礎: Preemptive vs Cooperative、Throughput·Latency·Fairness·Responseのトレードオフ
古典アルゴリズム: FCFS, SJF, RR, Priority, MLFQ
Linux: O(n) → O(1) → CFS → EEVDFの進化
Windows: 32段階priority、dynamic boost、foreground quantum stretch
macOS: QoSベースのスケジューリングとApple Silicon P/Eコア配置
ゲームのフレーム予算: 16.67msを埋めるものとpriority inversion
ゲームエンジンの優先度·アフィニティ活用: Unity, Unreal, そしてOS APIレベル

Stage 2の核心的な問い — 「2つのスレッドが同じ変数に書き込むとなぜプログラムが時々だけ落ちるのか?」 — の「時々」という言葉は結局スケジューラの動作から来ています。どの順序で、どの間隔で実行が混ざるかが、見えないところで決められているという意味だからです。

Part 1: スケジューリングが必要な理由

マルチタスクの幻想

デスクトップにブラウザ、IDE、Slack、Spotify、Discordが同時に立ち上がっています。コアは8個で、プロセスとスレッドは合計で通常数百個レベルです。それでも全てが「同時に」動いているように見えます。

実際にはOSが非常に高速にスレッドを入れ替えているだけです。一つのスレッドが数ミリ秒の間コアを掴み、次のスレッドに移り、また次のスレッドに移ります。人間の認知限界(約50ms)よりはるかに短い単位で入れ替えれば、同時実行のように感じられます。

この入れ替えを決めるのがスケジューラであり、2つの問いに答えます。

誰に渡すか — Ready状態のスレッドのうちどれを選んでコアに乗せるか
どれだけ長く — 一度乗せたらいつ取り上げるか、あるいは取り上げられるか

Preemptive vs Cooperative

プリエンプティブ (Preemptive): スケジューラがスレッドを強制的に取り上げられます。タイマー割り込みが周期的に発生するとカーネルが目覚めて「次は誰か」を決定します。現代のほぼ全てのOS — Linux, Windows, macOS — がこの方式です。

協調的 (Cooperative): スレッドが自ら譲る(yield)まで動き続けます。80年代のMac、95以前のWindows、そして現在の一部のコルーチン/Fiberシステムがこの方式です。1つのスレッドが無限ループを回るとシステム全体が止まります — 昔の「Mac爆弾アイコン」の原因の1つでした。

ちょっと待って、これは押さえておきましょう。 ではGoroutineやasync/awaitはcooperativeですか?
Goのgoroutineは部分的にcooperativeです。関数呼び出し、チャネル演算、GCセーフポイントでのみ譲歩点が発生します。なので無限ループの中に関数呼び出しがないと他のgoroutineが飢餓状態になり得て、Go 1.14でようやく非同期プリエンプションが導入されました。async/awaitも同様にawait地点でのみ譲ります — ただしその上で実際のスレッドはOSのプリエンプティブスケジューラで動くため、2つの層が重なっている形です。

スケジューラの評価基準

スケジューラを設計する際に考慮すべき指標は複数あり、互いに衝突します。

指標	意味	誰が好むか
Throughput	単位時間あたりの完了タスク数	バッチ処理、ビルドサーバー
Turnaround time	タスク全体の所要時間	コンパイラ、データ処理
Waiting time	Readyキューで待った時間	全タスク
Response time	入力から最初の反応まで	デスクトップ、ゲーム
Fairness	リソースの公平な分配	マルチユーザーシステム
Predictability	予測可能なレイテンシ	リアルタイムシステム、ゲーム
Energy	電力効率	モバイル、ノートPC

デスクトップとモバイルは通常Response time + Energyを優先します。サーバーはThroughput + Fairness、リアルタイム/ゲームはPredictabilityを優先します。同じアルゴリズムが全ての環境で最適になり得ない理由です。

Part 2: 古典スケジューリングアルゴリズム

本格的なOSスケジューラを見る前に、教科書的アルゴリズム5つを押さえておきます。現代のスケジューラは全てこれらのアイデアの組み合わせ·進化版です。

FCFS (First-Come, First-Served)

最も単純です。到着した順に実行し、一度始まったら終わるまで取り上げません(non-preemptive)。

問題はconvoy effectです。100秒のタスクが先に入ると、その後ろの0.1秒のタスクが全て100秒ずつ待たなければなりません。平均待ち時間が爆発します。

SJF / SRTF (Shortest Job First / Shortest Remaining Time First)

最も短いタスクを先に実行します。平均待ち時間が理論的に最適であることが数学的に証明されています。

問題1: タスクの長さを事前に知る必要があります。実際には知り得ないので過去の実行履歴から推定します。問題2: starvation — 短いタスクが続けて入ると、長いタスクは永遠に始められない可能性があります。

Round Robin (RR)

Readyキューを循環しながら、各スレッドにタイムクォンタム (time quantum) だけCPUを与えます。クォンタムが終わるとキューの後ろに送り、次のスレッドに移ります。

タイムクォンタムの大きさが重要なパラメータです。

大きすぎると: FCFSに近づき応答性が悪化します
小さすぎると: コンテキストスイッチのオーバーヘッドが作業時間を食い潰します

典型的な値は10~100msです。Linuxは動的に決定し(CFS)、Windowsは約6ms(サーバーは12ms以上)です。

次の図は同じタスクセット(A=8ms, B=4ms, C=2ms)が同時に到着した場合のFCFSとRRの動作を比較します。

FCFS vs Round Robin (quantum 2ms)

FCFS

A (8ms)

B (4ms)

C (2ms)

081214

平均turnaround = (8 + 12 + 14) / 3 = 11.33ms · C 応答時間 12ms

RR (q=2)

C ✓

B ✓

A ✓

02468101214

C 応答時間 4ms (FCFSの1/3) · 平均turnaround = (14 + 8 + 6) / 3 = 9.33ms

A (8ms) B (4ms) C (2ms) ✓ タスク完了時点

RRはturnaroundで常に優位とは限りませんが、短いタスクの応答性と公平性では圧倒的です。

Priority Scheduling

各スレッドに優先度を付け、最も高いものから実行します。同じ優先度同士はRRで処理します。

問題は再びstarvationです。低い優先度のスレッドが永遠に動けない可能性があります。解決策の1つがagingで、長く待ったスレッドの優先度を徐々に上げます。

もう1つの深い問題がpriority inversionです。低い優先度のスレッドがロックを掴んでいる間、高い優先度のスレッドがそのロックを待つと、中間優先度のスレッドが低い側を絶えずプリエンプトすることで、結果的に高い側が中間側のせいで詰まる逆説が生じます。この問題は次回(同期化)で本格的に扱います。

MLFQ (Multi-Level Feedback Queue)

複数のキューを優先度別に置き、スレッドの振る舞いを観察してキューを移します。

基本ルールは次のとおりです。

新しいスレッドは最も高いキューに入ります
タイムクォンタムを使い切ると一段下のキューに下がります
クォンタムを使い切らずI/Oで譲ると同じキューに残るか一段上がります

このルールの結果が興味深いです。

I/O中心のタスク(対話型GUI、ゲーム入力): 短いburstの後に譲歩 → 高いキューを維持 → 速い応答
CPU中心のタスク(コンパイラ、エンコーディング): 長いburst → 低いキューに下がる → 応答タスクを邪魔しない

アルゴリズムがタスクの本質を知らなくても振る舞いだけを見て分類するという発想が核心です。Windowsのdynamic boost、macOSのQoS補正、Linuxのsleeper bonusも全て本質的に同じアイデアの変形です。

MLFQはSolarisと旧Mac OS、Windows NTが直接使い、現代のOSは表面的には別のアルゴリズム(CFS等)を使いますが内部のヒューリスティックはMLFQに似ています。

Part 3: Linuxスケジューラ — O(n) → O(1) → CFS → EEVDF

Linuxスケジューラの進化は学習用としてこの上ない素材です。同じ問題を4回解き直しながら何が間違っていて、どう直したのかが全て公開されているからです。

O(n)スケジューラ — 2.4以前

初期のLinuxスケジューラは1回決定するごとに全Readyキューを巡回しました。コアが少なくプロセスも少なかった時代には問題ありませんでしたが、サーバーが数千プロセスを起動する時代になると、スケジューラ自体がボトルネックになりました。CPUコアを追加してもロック競合が激しく性能が伸びませんでした。

O(1)スケジューラ — 2.6 (Ingo Molnár, 2003)

Ingo Molnárが2002年末に導入したアルゴリズムです。

核心アイデアは次のとおりです。

140個の優先度キュー (リアルタイム0~99、一般100~139)
各優先度ごとにactive queueとexpired queueの一対
次に実行するスレッドを定数時間で決定 — ビットマップで最も高いビットを見つけるだけだから

また対話型タスクボーナスをヒューリスティックとして導入しました。sleep時間が長いほど優先度を少し上げ、デスクトップの応答性を改善しました。しかしこのヒューリスティックがますます複雑になり、ボーナス計算をもてあそぶワークロードが見つかったことでコードが継ぎ接ぎだらけになりました。

CFS — Completely Fair Scheduler (2.6.23, 2007)

Ingo Molnárが再び作ったスケジューラです。インスピレーションはCon KolivasのRSDL (Rotating Staircase Deadline) パッチから受けたと本人が明らかにしています。

核心の発想は「公平性」を単純な回転ではなく累積実行時間のバランスとして定義することです。全てのスレッドは自分が受け取るべき仮想のCPU時間 — vruntime — を持ち、スケジューラは常にvruntimeが最小のスレッドを選択します。

仮想実行時間(vruntime)は実際の実行時間(runtime)をweightで補正した値です。

\[\Delta \text{vruntime} = \Delta \text{runtime} \times \frac{w_0}{w}\]

ここで$w$はスレッドのweight(nice値で決定)で、$w_0$はnice 0の基準weight(1024)です。niceが負(優先度が高い)ほどweightが大きくなり、vruntimeがゆっくり増加するので頻繁に選択されます。

データ構造はRed-Black Treeで、キーはvruntimeです。最も左のノード(最小vruntime)が次の実行対象であり、挿入·削除·選択は全て$O(\log n)$です。O(1)より漸近的には遅いですが実測ではnが小さく差はほぼなく、ヒューリスティックが消えてコードがはるかにすっきりしました。

次の図はCFSの核心サイクルです。RB-treeからvruntimeが最小のスレッドを取り出して実行し、一定時間後に更新されたvruntimeで再びツリーに入れます。

CFS — vruntimeソートと実行サイクル

runqueue (key = vruntime, leftmostが次の実行対象)

v=18

leftmost ← next

v=30

v=35

v=42

v=50

v=58

v=72

pick_next_task
(leftmost = T0)

→

CPU実行
vruntime += Δ × w₀ / w_T0

→

enqueue_task
更新されたvでRB-tree再挿入

Δvruntime = Δruntime × (w₀ / w) · w₀ = 1024 (nice 0) · nice ↓ → w ↑ → Δv ↓ → 頻繁に選択

結局、全スレッドのvruntimeがほぼ同じに保たれるよう自己均衡 — これが「Completely Fair」の意味です。

CFSの核心パラメータは次のとおりです。

sched_latency_ns — 1サイクルの間に全Readyスレッドを1度ずつ回そうとする目標時間 (デフォルト6ms × コア数)
sched_min_granularity_ns — 1スレッドが1度に回る最小時間 (デフォルト0.75ms)
sched_wakeup_granularity_ns — 起きたスレッドが現在のスレッドをプリエンプトするためのvruntime差の閾値

値はsysctl -a | grep schedで確認でき、コア数に応じて自動調整されます。

  
/* 単純化したCFS選択ロジック */
struct task_struct *pick_next_task_fair(struct rq *rq) {
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct sched_entity *se = __pick_first_entity(cfs_rq);  /* RB-tree leftmost */
    return container_of(se, struct task_struct, se);
}

/* tickごとに呼ばれる — vruntime更新後に再配置 */
void update_curr(struct cfs_rq *cfs_rq) {
    struct sched_entity *curr = cfs_rq->curr;
    u64 delta_exec = now - curr->exec_start;
    curr->vruntime += calc_delta_fair(delta_exec, curr);
    /* プリエンプト条件が合えばresched_curr() */
}

EEVDF — Earliest Eligible Virtual Deadline First (6.6, 2023~2024)

CFSを16年間うまく使ってきましたが、1つ構造的な問題が残っていました。latency-sensitiveなタスクの表現が難しいことです。

CFSはniceでどれだけ頻繁に回るかは調節できますが、どれだけ速く応答すべきかは別途指定できませんでした。2つの概念を同じ軸に縛ってしまった形です。

Peter Zijlstraが2023年からEEVDFをmainlineに入れ、6.6 LTSカーネルからデフォルトスケジューラに切り替わりました。学術的背景はStoica·Abdel-Wahab·Jeffay·Baruahの1996年論文です。

EEVDFの2つの軸は次のとおりです。

Eligibility (適格性) — このスレッドが自分の取り分だけ十分回ったか。受け取れていなければeligibleです
Virtual Deadline (仮想期限) — eligibleなスレッドの中で期限が最も早いものを選択します

deadlineは次のように計算されます。

\[\text{deadline} = \text{eligible time} + \frac{\text{request size}}{\text{weight}}\]

要求サイズ(latency-niceという新しいパラメータ)が小さいほどdeadlineが早くなり、より頻繁にプリエンプトされます。つまりゲームのメインスレッドのように「頻繁には回らない代わりに、起きたら即座に応答すべき」タスクを正確に表現できるようになりました。

  
/* Linux 6.6+ : niceとは別にlatency-niceを設定 */
struct sched_attr attr = {
    .sched_policy   = SCHED_NORMAL,
    .sched_nice     = 0,
    .sched_runtime  = 1   * 1000 * 1000,   /* 1ms */
    .sched_deadline = 16  * 1000 * 1000,   /* 16.67ms */
    .sched_period   = 16  * 1000 * 1000,
};
sched_setattr(pid, &attr, 0);

EEVDFが導入されてもvruntimeベースの公平性はそのまま維持されます。EEVDFはCFSの代替というより選択ポリシーの精緻化に近く、外部インターフェース(nice, cgroup cpu.weight)もほぼそのまま使えます。

Linuxの他のスケジューリングクラス

Linuxは1つのアルゴリズムだけを使うのではなく、クラスを階層に置きます。クラスごとに優先度が決まっており、上位クラスにタスクがあれば下位クラスは回りません。

クラス	ポリシー	用途
stop	(カーネル専用)	CPUホットプラグ、RCUなど
dl	SCHED_DEADLINE	リアルタイム (period + runtime + deadline保証)
rt	SCHED_FIFO, SCHED_RR	リアルタイム優先度1~99
fair	SCHED_NORMAL/BATCH/IDLE	一般、CFS/EEVDF
idle	(全てidleの時)	swapper

ゲームでSCHED_FIFO/RRをむやみに使ってはいけない理由があります。誤って使うとシステム全体を止められます — 優先度99の無限ループ1回でそのコアは以降応答不能になります。本当にRTが必要なオーディオスレッドもSCHED_FIFOよりdispatch_qos / AVAudioSession.realtimeのようにOSが提供する上位抽象を介してアクセスする方が安全です。

Part 4: Windowsスケジューラ — Priority + Boost

Windows NTのスケジューラはDave CutlerがVMSの経験を持ち込んで設計した32段階の優先度ベースシステムです。基本骨格はNT 3.1(1993)以来ほぼそのまま維持されており、時間が経つにつれヒューリスティックとハードウェア適応コードだけが厚く積み上げられました。

32 Priority Levels

レベル	意味
0	Zero page thread (メモリゼロ埋め専用)
1~15	Variable priority (一般プロセス、動的調整対象)
16~31	Real-time priority (管理者権限必要、動的調整なし)

各プロセスにはPriority Classがあり、その中でスレッドはThread Priorityで微調整します。

  
/* Windows優先度 = Process Class + Thread Priority offset */
SetPriorityClass(hProcess, NORMAL_PRIORITY_CLASS);    /* base 8 */
SetThreadPriority(hThread, THREAD_PRIORITY_NORMAL);   /* offset 0 */

/* HIGH_PRIORITY_CLASS = 13, THREAD_PRIORITY_HIGHEST = +2 → effective 15 */
/* REALTIME_PRIORITY_CLASS = 24, ... */

Quantum

Windowsのタイムクォンタムはclock intervalの倍数で測られます。通常クロックインターバルは約15ms(HPETベース)あるいは1ms(マルチメディアタイマー有効時)です。

Workstation: 2 clock interval (デフォルトは約30msだが起動後の補正で通常もっと短くなる)
Server: 12 clock interval (長いクォンタムでthroughput優先)

またforegroundプロセスはquantumがstretchされます。ユーザーが見ているウィンドウのスレッドにより長い時間を与え、応答性を高めます (コントロールパネル → システム → 詳細 → パフォーマンスオプション → 詳細の「プログラム」/「バックグラウンドサービス」トグルがこの機能をオン·オフします)。

Priority Boost — Windowsの核心ヒューリスティック

Variable priority領域(1~15)のスレッドはさまざまなイベントで一時的に優先度が上がります。boostはquantumごとに1ずつ減って結局baseに戻ります。

イベント	Boost量
Disk I/O完了	+1
ネットワーク / Mailslot	+2
マウス / キーボード入力	+6
サウンドカード	+8
GUIスレッドがメッセージ受信	+2 (foreground追加)
Semaphore wait終了	+1
Mutex/Event/Timer wait終了	+1

このヒューリスティックがWindowsの応答性を作るメカニズムです。ユーザーがマウスを動かすとGUIスレッドが+6、キー入力も+6を受け取ります。他のCPU-boundタスクが動いていても入力反応が即座に来ます。

ちょっと待って、これは押さえておきましょう。 GUIスレッドのboostが+6なら、複数のウィンドウにどう優先度が分配されますか?
フォーカスを持ったウィンドウのスレッドだけがforeground追加boostを受けます。Alt-Tabでアクティブウィンドウが変わる瞬間、boost分配も即座に変わります。Process Explorerで優先度欄をオンにして他のウィンドウをクリックしてみると、クリックされたウィンドウのスレッドの優先度数値が一瞬上がるのが確認できます。

Realtime Priorityの罠

レベル16~31はdynamic boostがなく、常にその優先度で動きます。理論上は「絶対に譲らない」となります。なのでオーディオ、ビデオキャプチャ、一部のゲームスレッドが16~22程度を使います。

しかしREALTIME_PRIORITY_CLASS (24~31) を一般のコードで使うのは危険です。24以上の無限ループ1回がマウスカーソルまで止められます — マウス処理も結局スレッドだからです。

NUMA, SMT, Heterogeneous

現代のWindowsスケジューラはNUMAノード、SMT(ハイパースレッディング)、Intel Thread Director(P/Eコアヒント)を全て考慮します。Windows 11で導入されたHardware Threaded SchedulingがThread Directorのヒントを受けてP/Eコア配置を調整します — Apple SiliconがOSレベルでやることをIntelはOS·CPU協調で解決しています。

  
/* Windows: スレッドpriority調整 + affinity */
HANDLE h = GetCurrentThread();
SetThreadPriority(h, THREAD_PRIORITY_TIME_CRITICAL);  /* +15 */

/* コア0,1番にだけ固定 */
DWORD_PTR mask = 0x3;
SetThreadAffinityMask(h, mask);

/* Windows 10+ : E-core推奨ヒント */
THREAD_POWER_THROTTLING_STATE state = {};
state.Version = THREAD_POWER_THROTTLING_CURRENT_VERSION;
state.ControlMask = THREAD_POWER_THROTTLING_EXECUTION_SPEED;
state.StateMask   = THREAD_POWER_THROTTLING_EXECUTION_SPEED;
SetThreadInformation(h, ThreadPowerThrottling, &state, sizeof(state));

最後のTHREAD_POWER_THROTTLING_EXECUTION_SPEEDは「このスレッドはE-coreでゆっくり動いても良い」とOSにヒントを与えるAPIです。バックグラウンドタスクに適用するとP-coreがゲームのメインスレッド用に空きます。

Part 5: macOSスケジューラ — QoS + P/Eコア

macOSは外見はMachベースですが、スケジューラはBSDベースのpriorityシステムの上にQoS (Quality of Service) という上位抽象を載せた形です。開発者はほぼ常にQoSを介して優先度を表現し、カーネルがそれをpriority + コア配置 + 電力管理に翻訳します。

QoS Class 5段階

QoS Class	意味	例	マッピングpriority
User Interactive	即座に反応必要、ユーザーが直接見るタスク	メインスレッド、アニメーション、入力	47
User Initiated	ユーザーが開始して結果を待つタスク	ファイルオープン、検索	37
Default	明示しなかった時	一般タスク	31
Utility	ユーザーが即座に結果を見なくてもよいタスク (進捗表示)	ダウンロード、インポート	20
Background	ユーザーに見えないタスク	インデックス、バックアップ	5

このQoS値が決定するのは次のとおりです。

CPU priority — 上記表の数字
CPU scheduling latency — User Interactiveは速いwake-up、Backgroundはまとめて処理
I/O priority — ディスクキューの優先度
CPUコア配置 (Apple Silicon) — User Interactive/InitiatedはP-core優先、Utility/BackgroundはE-core優先
Timer coalescing — Backgroundはタイマー発火をバッチでまとめる
GPU優先度 — 一部のグラフィックスワークロードに影響

QoS 1行が6つを同時に決定します。

QoS API

  
/* C/Objective-C — スレッド自身のQoS設定 */
pthread_set_qos_class_self_np(QOS_CLASS_USER_INTERACTIVE, 0);

/* GCDキュー作成時 */
dispatch_queue_t q = dispatch_queue_create_with_target(
    "com.example.render",
    DISPATCH_QUEUE_SERIAL,
    dispatch_get_global_queue(QOS_CLASS_USER_INTERACTIVE, 0));

/* dispatch_asyncにQoS attach */
dispatch_async(q, ^{
    /* User Interactiveで実行 */
});

  
// Swift
DispatchQueue.global(qos: .userInteractive).async {
    // メインスレッドの負担を減らすための速い処理
}

// Operation API
let op = BlockOperation { /* ... */ }
op.qualityOfService = .userInitiated
queue.addOperation(op)

QoS Inheritance — 優先度逆転防止

QoSは自動伝播します。User Interactiveキューでdispatchしたタスクが内部で他のキューにdispatch_syncすると、呼ばれる側のキューのQoSが一時的にUser Interactiveにブーストされます。このメカニズムがmacOSのpriority inversion防止の核心です。

ロックにも同じメカニズムが適用されます。os_unfair_lockはロック保有スレッドのQoSを待機スレッドのQoSまで引き上げます — POSIXのPTHREAD_PRIO_INHERITと同じことをOSレベルで自動的に行います。

QoS → priority → P/Eコアマッピング

次の図はQoS 1行がMach priorityとApple SiliconのP/Eコア配置にどう翻訳されるかを示します。

macOS QoS — 1行で決まる6つ

QoS Class

Mach priority

Apple Silicon コア配置

USER_INTERACTIVE

メインスレッド / アニメーション

P-core 専用

最高性能 / 最大電力

USER_INITIATED

ファイルオープン / 検索

P-core 優先

必要時E-core使用可

DEFAULT

未指定

P/E 混合

負荷に応じてOSが決定

UTILITY

進捗表示タスク

E-core 優先

電力効率優先

BACKGROUND

インデックス / バックアップ

E-core 専用 + バッチ

timer coalescing, 低電力

QoS 1行が同時に決定するもの

① CPU priority ② scheduling latency ③ I/O priority ④ P/E core 配置 ⑤ timer coalescing ⑥ GPU priority

QoSは自動伝播(inheritance)してdispatchチェーンとロック保持者までブーストされるのでpriority inversionが自動的に緩和されます。

Game Mode (macOS 14+)

macOS Sonomaから追加されたGame Modeはゲームがフルスクリーン時にOSが自動有効化するモードです。効果は次のとおりです。

バックグラウンドタスクのQoSをより強く抑制 (Spotlightインデックス、Time Machineなど)
ゲームプロセスへのP-core配置優先権強化
AirPods/PS5コントローラーのオーディオ·入力ポーリングレートを2倍に増加

iOSのSustained Performance APIと発想が似ています — 「今このアプリは16.67msを逃せない状態です」とOSに知らせ、システム全体のリソース分配が調整されます。

Part 6: ゲームのフレーム予算 — 16.67ms

ここまでのOS理論をゲームのコンテキストに移してみましょう。ゲーム開発者にとってスケジューリングは結局フレーム予算の問題です。

フレーム予算の数学

\[\text{frame budget} = \frac{1000\,\text{ms}}{\text{target FPS}}\]

Target FPS	フレーム予算	誰が使うか
30	33.33ms	コンソールシネマティック、一部モバイル
60	16.67ms	一般ゲーム標準
90	11.11ms	VR最低線
120	8.33ms	高フレームPC、PS5 Performance
144	6.94ms	高リフレッシュレートモニター
240	4.17ms	競技FPS、eスポーツ

この時間の中で次が全て終わらなければなりません。

Input処理 — キーボード、マウス、ゲームパッド、タッチ
Game Logic — AI、振る舞い、状態更新
Physics / Collision — 離散シミュレーション1ステップ
Animation — ボーン行列計算、ブレンディング
Particle / VFX — パーティクル更新
Render commandビルド — ドローコールソート、カリング
GPU submit — コマンドバッファキューイング
Present — バックバッファ → 画面 (VSync待機含む)

ゲームエンジンはこれを複数のスレッドに分散します。1フレームの中で起こることを時間軸に描くと次のような形になります。

60fps フレーム予算 16.67ms — 誰がいつ何をするか

硬い締切: 16.67ms以内に終わらせなければフレームドロップ

Main

Input

Logic / AI

Physics

Animation

Cull / Sort

Render

CommandBuffer build (frame N-1)

GPU submit + sync

Workers

AI Job

Particle

Skinning

Frustum Cull

GPU

GPU レンダリング (shadow → opaque → transparent → post)

VBlank

VBlank → Present

0 4.2 8.3 12.5 16.67ms

Input Logic/AI Physics Animation CommandBuffer/Cull Worker Job GPU

CPUメインスレッドはRenderと1フレームパイプライン — Renderが見るデータはMainのN-1フレームの結果です。

1フレームパイプライン

ほとんどのエンジンはMainとRenderを1フレームずらします。MainがFrame Nのゲーム状態を作っている間、RenderはFrame N-1の状態でGPUに作業を投げます。2つのスレッドが同じデータを同時に触らないのでロックが減りますが、入力遅延が1フレーム増えます。

VRとeスポーツタイトルはこのトレードオフに非常に敏感です。NVIDIA ReflexやAMD Anti-LagのようなGPUドライバ機能がこのパイプライン深度を減らそうと試みます。

Frame Spikeの原因 — スケジューリングの観点

フレーム時間が平均11msなのに時々23msが跳ねる現象(「frame spike」)の原因はGC、ディスクI/O、syscall以外にもOSスケジューリング自体がよくあります。

コンテキストスイッチの暴走: スレッド数がコア数より多い時、OSが頻繁に入れ替えキャッシュ汚染でメインスレッドが遅くなる
Priority inversion: メインスレッドがworkerスレッドのロックを待っている間、無関係な他のスレッドがworkerをプリエンプト
NUMA miss: スレッドが別のNUMAノードに移動してキャッシュ·メモリレイテンシが爆発
P/Eコア降格: macOS Game Mode未適用時、ゲームのメインスレッドが一時的にE-coreに押されてframetimeが2倍

対処法は次のとおりです。

メインスレッドとレンダースレッドは固定コア (affinity) に縛る
ワーカーはコア数 - 2程度に制限してメイン/レンダー用コアを空けておく
macOSはQOS_CLASS_USER_INTERACTIVE、WindowsはTHREAD_PRIORITY_HIGHEST(TIME_CRITICALはなるべく避ける)を使う
バックグラウンドスレッドは明示的にBACKGROUND/低いpriorityに — OSがP/E分離処理

Priority Inversion シナリオ

ゲームでよく見る形です。

時刻      Main (qos=USER_INTERACTIVE)         Worker (qos=UTILITY)         Other (qos=DEFAULT)
0ms       enqueue logic                        idle                          running
1ms       AI結果が必要 → mutex_lock(M) wait    M保有中                       -
2ms       (待機)                                preempted by Other            running ← 問題
... 6ms   (待機)                                preempted by Other            running
7ms       (待機)                                M解放                         -
7.1ms     unblock → 進行開始                                                  -

Mainが1msから7msまで止まっているがその間Workerも動けず、Otherだけが動きます。macOSはこの場合、自動的にM保有者(Worker)のQoSをUSER_INTERACTIVEにブーストするのでOtherがWorkerをプリエンプトできません。POSIXのPTHREAD_PRIO_INHERITやWindowsのALPC自動boostも同じ種類の解決策です。次回(同期化)でさらに深く扱います。

Part 7: ゲームエンジンの優先度·アフィニティ活用

Unity — Job System priority

UnityのC# Job Systemは内部的にworkerスレッドプールを管理し(worker count = ProcessorCount - 1がデフォルト)、JobHandleを介してスケジューリングされます。

  
// Unity 2022+
using Unity.Jobs;
using Unity.Collections;

[Unity.Burst.BurstCompile]
struct PhysicsStepJob : IJobParallelFor {
    public NativeArray<float3> positions;
    public NativeArray<float3> velocities;
    public float dt;

    public void Execute(int i) {
        positions[i] += velocities[i] * dt;
    }
}

void Update() {
    var job = new PhysicsStepJob {
        positions = positionsArray,
        velocities = velocitiesArray,
        dt = Time.deltaTime
    };
    JobHandle h = job.Schedule(positionsArray.Length, 64);
    h.Complete();  /* メインスレッド同期 — フレーム内に終わる必要あり */
}

ScheduleBatchedJobs()やJobsUtility.JobWorkerMaximumCountで個数制御が可能です。Player Settings → Other Settings → Use job worker countで明示的設定もできます — 8コアP-core + 4コアE-coreマシンでworkerを8に減らすとメインがP-coreをより安定して占有します。

Unity — Application.targetFrameRate, vSyncCount

  
// モバイル60fps固定
QualitySettings.vSyncCount = 0;
Application.targetFrameRate = 60;

// デスクトップモニターのリフレッシュレートに合わせる
QualitySettings.vSyncCount = 1;
Application.targetFrameRate = -1;

Unreal — TaskGraphとNamed Threads

  
// Unreal: 特定threadに作業を投げる
ENamedThreads::Type Target = ENamedThreads::GameThread;  /* or RenderThread, AnyThread */
FFunctionGraphTask::CreateAndDispatchWhenReady(
    [](){ /* GameThreadで実行 */ },
    TStatId(),
    nullptr,
    Target);

// 並列worker pool
ParallelFor(NumElements, [&](int32 i) {
    Process(i);
}, EParallelForFlags::None);

UnrealはGameThread, RenderThread, RHIThreadなどnamed threadを置いて明示的な直列化を強制します。WorkerPoolに落ちる作業は優先度キューに入り、Insightsツールで作業がどこで動いているか可視化できます。

OS API直接呼び出し

エンジンを介さずOS APIで直接優先度を設定すべき時もあります。

  
// クロスプラットフォームスレッド優先度設定 — ゲームエンジンコアでよく使うパターン
void SetThreadHighPriority(std::thread& t) {
#if defined(_WIN32)
    SetThreadPriority(t.native_handle(), THREAD_PRIORITY_HIGHEST);
#elif defined(__APPLE__)
    pthread_set_qos_class_self_np(QOS_CLASS_USER_INITIATED, 0);
    /* または thread_policy_set + thread_extended_policy_data_t */
#elif defined(__linux__)
    struct sched_param p;
    p.sched_priority = 0;  /* SCHED_NORMALの中ではniceで調整 */
    pthread_setschedparam(t.native_handle(), SCHED_NORMAL, &p);
    setpriority(PRIO_PROCESS, gettid_via_syscall(), -5);
#endif
}

Thread Affinity — コア固定

  
// Linux
cpu_set_t set;
CPU_ZERO(&set);
CPU_SET(0, &set);  /* コア0番 */
CPU_SET(1, &set);
pthread_setaffinity_np(pthread_self(), sizeof(set), &set);

// Windows
SetThreadAffinityMask(GetCurrentThread(), 0x3);

// macOS — affinity APIはdeprecated、hintのみ可能
thread_affinity_policy_data_t policy = { 1 /* tag */ };
thread_policy_set(pthread_mach_thread_np(pthread_self()),
                  THREAD_AFFINITY_POLICY,
                  (thread_policy_t)&policy, 1);

ちょっと待って、これは押さえておきましょう。 macOSはなぜhard affinityがないのでしょう?
Appleの立場は一貫しています — 「開発者はOSよりよく知らない」。P/E異質コア、電力状態、発熱限界、コアパーキングなどをOSが総合判断するので、アプリがコアを強制的に掴むとむしろ損が大きいのです。代わりにTHREAD_AFFINITY_POLICYで同じキャッシュグループにまとめてくれというヒントは出せて、QoSでP/E選好を表現できます。

Naughty DogのFiber事例 (再訪)

Part 8(プロセスとスレッド)でNaughty DogエンジンのFiberモデルを短く紹介しました。スケジューリングの観点で再び見ると、Naughty DogはOSスケジューラをほぼ使いません。

コアごとにworkerスレッド1個ずつ、affinityでコアに固定
全てのスレッドはfiberプールから次のfiberを取り出して実行 (協調型)
fiber間の切り替えは約数十ns (OSコンテキストスイッチの約数μsの100分の1)
OSの立場からは事実上「スレッド7個をコア7個に固定しておいて起こすな」という状態

これがGDC 2015 Christian Gyrlingの発表の核心です。一般的なゲームでは過剰な設計ですが、鋭敏なフレーム一貫性が必要なAAAコンソールタイトルではOSに依存せず直接スケジュールを統制する道を選んだのです。

Part 8: 実戦観察 — どのスレッドがどこで動くか

Linux — chrt, nice, perf sched

  
# 現在のシェルのnice変更 (値が小さいほど高い優先度)
$ nice -n -5 ./mygame

# 実行中プロセスのポリシー/優先度確認
$ chrt -p $(pidof mygame)
pid 12345's current scheduling policy: SCHED_OTHER
pid 12345's current scheduling priority: 0

# SCHED_RRに変更 (root必要)
$ sudo chrt -r -p 50 $(pidof mygame)

# スケジューリングイベント追跡
$ sudo perf sched record -a sleep 10
$ sudo perf sched latency
# Task                       | Runtime ms | Switches | Avg delay ms | Max delay ms |
# mygame:12345               |   2543.123 |     8421 |        0.045 |        2.103 |

Max delayが16msを超えるとそのフレームでframe spikeが発生した可能性が高いです。

macOS — Activity Monitor, Instruments, sample

InstrumentsのSystem Traceテンプレートが最も正確です。測定対象は次のとおりです。

各コア(P0~P7, E0~E3)でどのスレッドが動いているか
QoSクラス別の色分け表示
コンテキストスイッチイベントとその理由 (preemption, voluntary blockなど)
スレッド状態遷移 (run / runnable / waiting / stopped)

  
# スレッド別CPU使用量
$ top -F -R -o cpu -stats pid,command,cpu,th,state

# プロセスの全スレッドのコールスタックを1秒間隔で5回サンプリング
$ sample <pid> 5 1 -mayDie

# powermetricsでコア別使用率 (P/E分離)
$ sudo powermetrics --samplers cpu_power -i 1000

Windows — Process Explorer, WPA, Xperf

Process ExplorerのThreadsタブが見せるもの:

各スレッドのbase/dynamic priority欄
「Stack」ボタンでコールスタック確認
「I/O Priority」、「Memory Priority」欄 (Win10+)

Xperf / Windows Performance Recorder:

  
# 1: プロファイル開始
wpr -start GeneralProfile -filemode

# 2: ゲーム実行、測定区間進行

# 3: 停止 → ETL収集
wpr -stop trace.etl

# 4: WPAで分析 (CPU usage by Thread, Generic Eventsなど)
wpa.exe trace.etl

WPAの「CPU Usage (Sampled)」と「CPU Usage (Precise)」2つのグラフの違いが重要です。Sampledは平均で、Preciseはコンテキストスイッチイベントベースなのでframe spike分析に正確です。

測定する習慣

スケジューラが何をしているかを推測する代わりに測定する習慣が重要です。Tracy Profilerはゲームエンジンに組み込んでフレーム内の全thread活動をns単位で可視化してくれます — Unity, Unrealともに統合プラグインがあります。

  
// Tracy使用例
#include "Tracy.hpp"

void GameLoop() {
    ZoneScoped;  /* 関数単位で自動測定 */
    {
        ZoneScopedN("AI Update");
        UpdateAI();
    }
    {
        ZoneScopedN("Physics Step");
        StepPhysics();
    }
}

TracyはLockableBase, FrameMarkなど同期·フレーム境界マーキングマクロも提供してpriority inversionを視覚的に捉えるのに良いです。

まとめ

今回扱った内容は次のとおりです。

スケジューリング基礎:

2つの決定: 「誰に」+「どれだけ長く」
Preemptive vs Cooperative
評価基準: Throughput, Latency, Fairness, Response, Energy

古典アルゴリズム:

FCFS — convoy effect
SJF — 平均待ち時間最適、starvation
RR — quantumトレードオフ
Priority — starvation, priority inversion予告
MLFQ — 振る舞い観察ベースの優先度自動調整

Linux:

O(n) → O(1) (Ingo Molnár, 2003)
CFS (2007) — vruntime, RB-tree, completely fair
EEVDF (2024) — eligibility + virtual deadline, latency-nice追加
クラス階層: stop > dl > rt > fair > idle

Windows:

32 priority levels (Variable 1~15, Realtime 16~31)
Foreground quantum stretch
Dynamic boost: I/O完了 +1, Mouse/Keyboard +6, Sound +8
Realtimeはdynamic boostなし — 危険な領域

macOS:

5 QoSクラス (User Interactive ↔ Background)
1行でpriority + scheduling latency + I/O priority + P/E core + timer coalescing + GPU priorityを同時決定
QoS inheritanceでpriority inversionを自動緩和
Game Mode (macOS 14+)

ゲームのフレーム予算:

60fps = 16.67ms, 120fps = 8.33ms, VR 90fps = 11.11ms
1フレームでinput → logic → physics → animation → render build → submit → present
1フレームパイプライン: MainとRenderの時差で並列性確保、入力遅延+1フレームのトレードオフ
Frame spikeのスケジューリング原因: コンテキストスイッチ暴走, priority inversion, NUMA miss, P/E降格

ゲームエンジン活用:

Unity Job System, Unreal TaskGraph + Named Thread
OS API: SetThreadPriority / pthread_setschedparam / pthread_set_qos_class_self_np
Affinity: Linux/Windowsでhard, macOSはhint only
Naughty Dog Fiber — OSスケジューラをほぼ迂回

観察ツール:

Linux: chrt, nice, perf sched
macOS: Instruments System Trace, sample, powermetrics
Windows: Process Explorer, WPA / Xperf
クロスプラットフォーム: Tracy Profiler

次回はPart 10 同期化プリミティブです。今回priority inversionを少しだけ言及しましたが、それに答えるにはまずlockの本質から見る必要があります。Mutex, Semaphore, SpinLockの違いは何で、なぜOSはfutex / SRWLock / os_unfair_lockのようなOS-specificプリミティブを別途置くのか扱います。そしてついにStage 2の核心の問い — 「2つのスレッドが同じ変数に書き込むとなぜプログラムが時々だけ落ちるのか」 — の正面からの答えに近づきます。

References

教科書

Silberschatz, Galvin, Gagne — Operating System Concepts, 10th ed., Wiley, 2018 — Ch.5 (CPU Scheduling), Ch.6 (Synchronization)
Tanenbaum, Bos — Modern Operating Systems, 4th ed., Pearson, 2014 — Ch.2.4 (Process Scheduling)
Bovet, Cesati — Understanding the Linux Kernel, 3rd ed., O’Reilly, 2005 — Ch.7 (Process Scheduling, O(1)時代)
Mauerer — Professional Linux Kernel Architecture, Wrox, 2008 — Ch.2 (Process Management and Scheduling, CFS導入後)
Russinovich, Solomon, Ionescu — Windows Internals, 7th ed., Microsoft Press, 2017 — Ch.4 (Thread Scheduling)
Singh — Mac OS X Internals: A Systems Approach, Addison-Wesley, 2006 — Ch.7 (Processes), Mach scheduler
Gregory — Game Engine Architecture, 3rd ed., CRC Press, 2018 — Ch.8 (Multiprocessor Game Loops)

論文

Stoica, Abdel-Wahab, Jeffay, Baruah, Plaxton, Tan — “A Proportional Share Resource Allocation Algorithm for Real-Time, Time-Shared Systems”, RTSS 1996 — EEVDFの理論的原典 — DOI
Pabla — “Completely Fair Scheduler”, Linux Journal, 2009 — CFS入門 — linuxjournal.com
Molnár, Ingo — “Modular Scheduler Core and Completely Fair Scheduler [CFS]”, LKMLパッチシリーズ, 2007 — CFS導入発表
Zijlstra, Peter — “EEVDF Scheduler”, LWN articles, 2023 — lwn.net/Articles/925371
Anderson, Bershad, Lazowska, Levy — “Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism”, SOSP 1991 — M:Nモデル (スケジューリングの観点で再参照)
Mogul, Borg — “The Effect of Context Switches on Cache Performance”, ASPLOS 1991 — frame spike原理

公式ドキュメント

Linux man pages — sched(7), chrt(1), sched_setattr(2), nice(1) — man7.org
Linux Kernel Documentation — Documentation/scheduler/sched-design-CFS.rst, sched-eevdf.rst
Microsoft Docs — Scheduling Priorities — learn.microsoft.com
Microsoft Docs — Priority Boosts — learn.microsoft.com
Apple Developer — Energy Efficiency Guide for Mac Apps — Prioritize Work with Quality of Service Classes — developer.apple.com
Apple Developer — Tuning Your Code’s Performance for Apple Silicon — developer.apple.com
Apple Developer — Game Mode (macOS 14+) — WWDC23 “Bring your game to Mac” セッション

ゲーム開発 / GDC

Gyrling, C. — Parallelizing the Naughty Dog Engine Using Fibers, GDC 2015 — gdcvault.com
Acton, M. — Data-Oriented Design and C++, CppCon 2014 — Insomniac Gamesのキャッシュ·スケジュール思考法
Schreiber, B. — Multithreading the Entire Destiny Engine, GDC 2015 — Bungieのスレッドモデル
Boulton, M. — Threading the Frostbite Engine, GDC 2009 — DICEのJobシステム
Unity Technologies — C# Job System, Burst Compiler マニュアル — docs.unity3d.com
Epic Games — Task Graph System, Async Tasks in Unreal — dev.epicgames.com
Tracy Profiler — github.com/wolfpld/tracy

ブログ / 記事

Brendan Gregg — Linux Performance, perf sched — brendangregg.com
Howard Oakley — The Eclectic Light Company — macOS QoS / P-Eコア観察シリーズ
Fabian Giesen — Reading List on Multithreading and Synchronization — fgiesen.wordpress.com
Raymond Chen — The Old New Thing — Windows priority boost回想録
LWN.net — EEVDF, CFS group scheduling, sched_ext シリーズ
Dmitry Vyukov — 1024cores.net — go scheduler内部

ツール

Linux: chrt, nice, taskset, perf sched, ftrace, bpftrace
macOS: Instruments (System Trace, Time Profiler, CPU Counters), sample, powermetrics, dispatch_introspection
Windows: Process Explorer, Windows Performance Recorder + Analyzer, ETW, PerfView
クロスプラットフォーム: Tracy Profiler, Optick, Superluminal

AI, CS

cs os scheduler cfs eevdf qos frame-budget game-engine

この記事は著者の CC BY 4.0 ライセンスの下で提供されています。