CPUスケジューリング

スケジューリングとは「どのプロセスに次にCPUを割り当てるか」を決定するアルゴリズムである。

この章で学ぶこと

• 主要なスケジューリングアルゴリズムを比較できる
• プリエンプティブとノンプリエンプティブの違いを説明できる
• Linuxのスケジューラの仕組みを知る
• マルチコア環境でのスケジューリング戦略を理解する
• リアルタイムスケジューリングの要件と実装を説明できる
• スケジューリングのパフォーマンス評価指標を計算できる

前提知識

このガイドを読む前に、以下の知識があると理解が深まります:

• 基本的なプログラミングの知識
• 関連する基礎概念の理解
• スレッドと並行性 の内容を理解していること

1. スケジューリングの基本

1.1 なぜスケジューリングが必要か

マルチプログラミングの本質:

  CPUは1コアあたり同時に1つのプロセスしか実行できない
  → 複数プロセスが同時にReady状態になった場合、
    誰を先に実行するかを「公平」かつ「効率的」に決定する必要がある

  現代のシステムでは数百〜数千のプロセス/スレッドが同時存在
  → スケジューリングの質がシステム全体の応答性・スループットを決定する

CPUバースト と I/Oバースト:

  プロセスの実行パターン:
  [CPU実行] → [I/O待ち] → [CPU実行] → [I/O待ち] → ...

  CPU-boundプロセス: CPUバーストが長い（科学計算、動画エンコード）
  I/O-boundプロセス: CPUバーストが短い（Webサーバー、エディタ）

スケジューラはI/O-boundプロセスを優先すべき:
  → I/O-boundはCPUをすぐ手放してI/O待ちに入る
  → 待っている間に他のプロセスがCPUを使える
  → 全体のスループットが向上する

1.2 スケジューラの目標

スケジューラの5つの評価指標:

  1. CPU利用率（CPU Utilization）:
     CPUをできるだけ忙しく保つ
     目標: 40%〜90%（システム種別による）
     100%はオーバーロード、0%はアイドル

  2. スループット（Throughput）:
     単位時間あたりの完了プロセス数を最大化
     バッチ処理システムで特に重要

  3. ターンアラウンド時間（Turnaround Time）:
     投入から完了までの総時間
     ターンアラウンド = 待ち時間 + 実行時間 + I/O時間
     バッチ処理で重要

  4. 待ち時間（Waiting Time）:
     Ready状態で待つ合計時間
     スケジューリングアルゴリズムが直接影響する唯一の指標

  5. 応答時間（Response Time）:
     リクエスト送信から最初の応答までの時間
     対話的システム（GUI、Webサーバー）で最重要

  トレードオフの関係:

システム種別ごとの優先指標:

1.3 プリエンプティブとノンプリエンプティブ

プリエンプティブ vs ノンプリエンプティブ:

  ノンプリエンプティブ（非横取り）:
    プロセスが自発的にCPUを手放すまで待つ
    手放すタイミング:
    - プロセス終了
    - I/O要求（ブロック状態に遷移）
    - yield()（自発的譲渡）

    利点: コンテキストスイッチが少ない、実装が単純
    欠点: 1プロセスがCPUを独占可能、応答性が悪い
    例: Windows 3.1、初期のMac OS

  プリエンプティブ（横取り）:
    OSがタイマー割り込みで強制的にCPUを切り替える
    切り替えタイミング:
    - タイムクォンタム（タイムスライス）の消費
    - より優先度の高いプロセスがReady状態に
    - 割り込み発生

    利点: 1プロセスの独占を防止、応答性が良い
    欠点: コンテキストスイッチのオーバーヘッド、同期の複雑化
    例: 現代の全てのOS（Linux, Windows, macOS）

  コンテキストスイッチのコスト:

1.4 スケジューリングの発生タイミング

ディスパッチャが動作する4つのタイミング:

  1. Running → Waiting:
     プロセスがI/O要求やwait()を呼んだ時
     → ノンプリエンプティブ（自発的譲渡）

  2. Running → Ready:
     タイマー割り込みが発生した時
     → プリエンプティブ（強制切替）

  3. Waiting → Ready:
     I/O完了割り込みが発生した時
     → プリエンプティブ（優先度次第で切替）

  4. プロセス終了:
     exit()が呼ばれた時
     → ノンプリエンプティブ（必然）

  ディスパッチャの処理:
  1. 現在のプロセスのコンテキストを保存
  2. スケジューラが次のプロセスを選択
  3. 選択されたプロセスのコンテキストを復元
  4. ユーザーモードに切り替え
  5. 選択されたプロセスの適切な位置にジャンプ

  ディスパッチレイテンシ:
  ディスパッチャが1つのプロセスを停止して
  別のプロセスを開始するまでの時間
  → できるだけ短くすべき（数マイクロ秒以下が理想）

2. 主要なスケジューリングアルゴリズム

2.1 FCFS（First-Come, First-Served）

FCFS: 到着順に実行。FIFOキュー。最もシンプル。

  到着: P1(24ms) P2(3ms) P3(3ms)

0                        24  27  30

  待ち時間: P1=0, P2=24, P3=27
  平均待ち時間: (0 + 24 + 27) / 3 = 17ms

  ターンアラウンド時間: P1=24, P2=27, P3=30
  平均ターンアラウンド: (24 + 27 + 30) / 3 = 27ms

  もし到着順がP2, P3, P1だったら:

0   3   6                        30

  待ち時間: P2=0, P3=3, P1=6
  平均待ち時間: (0 + 3 + 6) / 3 = 3ms
  → 到着順によって性能が大きく変動する！

問題点 — Convoy Effect（護送船団効果）:
  長いプロセスの後ろに短いプロセスが並ぶと、
  短いプロセスが不必要に長く待たされる

  CPU-boundプロセス（長い）がCPUを占有
  → I/O-boundプロセス（短い）が全てReady queue で待機
  → I/Oデバイスがアイドル状態
  → CPU-boundプロセスがI/Oを開始
  → I/O-boundプロセスがCPUバーストを高速に処理してI/O待ちに
  → CPUがアイドル
  → CPU-boundプロセスがI/O完了して戻ってくる
  → 繰り返し…

  結果: CPU利用率、I/Oデバイス利用率ともに低下

特性:
  - ノンプリエンプティブ
  - 飢餓なし（全プロセスがいつか実行される）
  - 実装が最も単純
  - 平均待ち時間が一般に長い
  - バッチシステム以外には不向き

2.2 SJF（Shortest Job First）

SJF: 実行時間が最も短いプロセスを先に実行

  到着: P1(6ms) P2(8ms) P3(7ms) P4(3ms)（全て到着時刻0）

0   3      9      16       24

  待ち時間: P4=0, P1=3, P3=9, P2=16
  平均待ち時間: (0 + 3 + 9 + 16) / 4 = 7ms

  ※FCFSなら: (0 + 6 + 14 + 21) / 4 = 10.25ms

SJFの最適性の証明（直感的理解）:
  n個のジョブ t1 ≤ t2 ≤ ... ≤ tn がある場合
  SJF順で実行した時の平均待ち時間:
  = (0 + t1 + (t1+t2) + ... + (t1+t2+...+t(n-1))) / n
  = Σ(n-i)ti / n  (i=1..n)

  短いジョブの係数(n-i)が大きくなる → 合計が最小化される
  → SJFは平均待ち時間を最小化する最適アルゴリズム

問題点:
  1. 次の実行時間（CPUバースト長）の予測が困難
     → 過去のバースト長から指数平均で推定
     τ(n+1) = α * t(n) + (1-α) * τ(n)
     α = 0なら過去の推定値のみ使用
     α = 1なら直前の実測値のみ使用
     典型的にはα = 0.5

  2. 飢餓（Starvation）:
     短いプロセスが次々到着すると
     長いプロセスが永遠に実行されない

SRTF（Shortest Remaining Time First）:
  SJFのプリエンプティブ版
  → 新しいプロセスが到着した時、
    残り時間が現在実行中より短ければ切替

  到着: P1(0, 8ms) P2(1, 4ms) P3(2, 9ms) P4(3, 5ms)

0 1    5    10       17      26

  t=0: P1開始（残り8）
  t=1: P2到着（残り4 < P1の残り7）→ P2に切替
  t=2: P3到着（残り9 > P2の残り3）→ P2継続
  t=3: P4到着（残り5 > P2の残り2）→ P2継続
  t=5: P2完了、P4(残り5) vs P1(残り7) vs P3(残り9) → P4
  t=10: P4完了 → P1(残り7)
  t=17: P1完了 → P3(残り9)
  t=26: P3完了

  平均待ち時間: (9 + 0 + 15 + 2) / 4 = 6.5ms

2.3 ラウンドロビン（Round Robin）

ラウンドロビン: タイムクォンタム（タイムスライス）で交互に実行

  プロセス: P1(24ms) P2(3ms) P3(3ms)、クォンタム=4ms

0    4   7  10   14   18   22   26   30

  P1: 0-4(残20), 10-14(残16), 14-18(残12), 18-22(残8), 22-26(残4), 26-30(完了)
  P2: 4-7(完了、3ms < 4ms クォンタム)
  P3: 7-10(完了)

  待ち時間: P1 = (10-4) = 6ms（最初の待機のみでも6ms分）
           ※ 正確には P1の総待ち時間 = 30-24 = 6ms
           P2 = 4ms, P3 = 7ms
  平均待ち時間: (6 + 4 + 7) / 3 = 5.67ms

  応答時間: P1=0, P2=4, P3=7
  平均応答時間: (0 + 4 + 7) / 3 = 3.67ms
  → FCFS(応答: 0, 24, 27 = 17ms) より大幅に改善

タイムクォンタムの影響:

  クォンタムが短すぎる場合（例: 1ms）:
  → コンテキストスイッチが頻発
  → オーバーヘッドでスループットが大幅に低下
  → 実質的な実行時間が減少

  クォンタムが長すぎる場合（例: 100ms）:
  → FCFSに退化
  → 応答時間が悪化

  最適なクォンタム:

クォンタムと性能の関係:

特性:
  - プリエンプティブ
  - 公平（全プロセスが均等にCPU時間を得る）
  - 飢餓なし
  - SJFより平均待ち時間は悪いが応答時間は良い
  - 対話的システムに最適

2.4 優先度スケジューリング

優先度スケジューリング: 優先度の高いプロセスを先に実行

  プロセス  バースト  優先度（小=高）
  P1        10ms     3
  P2         1ms     1
  P3         2ms     4
  P4         1ms     5
  P5         5ms     2

  実行順:

0  1     6         16 18 19

  待ち時間: P1=6, P2=0, P3=16, P4=18, P5=1
  平均待ち時間: (6 + 0 + 16 + 18 + 1) / 5 = 8.2ms

優先度の決定方法:

  静的優先度:
  - プロセス作成時に決定、変更しない
  - 例: nice値、ユーザーの権限レベル

  動的優先度:
  - 実行状況に応じて変動
  - 例: I/O待ちからの復帰で優先度上昇
  - 例: CPU時間消費で優先度降下

  内部要因による優先度:
  - メモリ要求量
  - ファイルオープン数
  - CPU/I/Oバースト比

  外部要因による優先度:
  - プロセスの重要度
  - 支払い額（クラウド）
  - 政策的要因

飢餓（Starvation）問題:
  低優先度のプロセスが永遠に実行されない

  解決策 — エージング（Aging）:
  待ち時間に応じて優先度を徐々に上昇させる

  例: 15秒ごとに優先度を1段上昇

→ いつかは必ず実行される（飢餓の防止）

優先度の逆転（Priority Inversion）:
  高優先度プロセスが低優先度プロセスの
  ロック解放を待つ現象

  H(高) → ロック待ち
  M(中) → 実行中（Lをプリエンプト）
  L(低) → ロック保持中だがプリエンプトされている

  → Hは事実上Mより低い優先度になる！

  解決策:
  1. 優先度継承（Priority Inheritance）:
     ロック保持者が待機者の優先度を継承
     L → 一時的にHの優先度 → ロック解放 → 元の優先度

  2. 優先度上限（Priority Ceiling）:
     ロックに最高優先度を設定
     ロック取得時に即座にその優先度に昇格

  実例: Mars Pathfinder（1997年）
  → 優先度の逆転でシステムリセットが頻発
  → VxWorksの優先度継承を有効化して解決

2.5 マルチレベルキュー

マルチレベルキュー:
  複数の優先度キューを持ち、キュー間にも優先度

各キュー内は独自のスケジューリングアルゴリズム:
  Q0: FCFS（リアルタイム）
  Q1: 優先度スケジューリング
  Q2: ラウンドロビン（クォンタム短い）
  Q3: FCFS

  キュー間のスケジューリング:
  - 固定優先度: 上位キューが空になるまで下位を実行しない
    → 下位キューの飢餓の危険
  - タイムスライス配分: 各キューにCPU時間を割合で配分
    Q0: 10%, Q1: 20%, Q2: 50%, Q3: 20%

  問題: プロセスが固定のキューに留まる
  → 性質が変わっても適切なキューに移動しない

2.6 マルチレベルフィードバックキュー（MLFQ）

マルチレベルフィードバックキュー:
  複数の優先度キューを持ち、動的にプロセスを移動

  ルール:
  1. 高優先度キューのプロセスを先に実行
  2. 同一キュー内はラウンドロビン
  3. タイムクォンタムを使い切ったら降格
  4. I/O待ちから復帰したら昇格（または維持）
  5. 一定時間ごとに全プロセスを最高優先度に引き上げ（ブースト）

  高優先度 [Q0] ─── クォンタム 8ms
               ↓ タイムアウト（CPU-bound）
  中優先度 [Q1] ─── クォンタム 16ms
               ↓ タイムアウト
  低優先度 [Q2] ─── FCFS
               ↑ I/O完了で昇格

  動作例:
  1. 新プロセスはQ0に投入
  2. 8ms以内に完了 or I/O待ち → Q0に留まる
  3. 8msを使い切り → Q1に降格
  4. Q1で16msを使い切り → Q2に降格
  5. 周期的ブーストで全員Q0に（飢餓防止）

  パラメータの設定:

ゲーミング（Gaming）への対策:
  悪意あるプロセスがI/Oを意図的に発行して
  高優先度を維持しようとする行為

  対策: アカウンティング（accounting）
  → キュー内での累積CPU使用時間を追跡
  → 累積時間がしきい値を超えたら降格
  → I/O直前の自発的放棄も計上

2.7 各アルゴリズムの比較

※ ブーストにより飢餓を防止

3. Linuxのスケジューラ

3.1 Linuxスケジューラの歴史

Linux スケジューラの進化:

  Linux 2.4以前: O(n) スケジューラ
  → Runキュー内の全プロセスを走査して次を選択
  → プロセス数に比例して遅くなる
  → SMP対応が不十分

  Linux 2.6.0〜2.6.22: O(1) スケジューラ
  → 優先度ごとにキューを持つ
  → Active配列とExpired配列を交互に使用
  → O(1)で次のプロセスを選択
  → 対話的プロセスの判定にヒューリスティック使用
  → 判定が不正確で公平性に問題

  Linux 2.6.23〜6.5: CFS（Completely Fair Scheduler）
  → Con Kolivas氏のSD/RSDLスケジューラに触発
  → Ingo Molnár氏が開発
  → 赤黒木による公平なスケジューリング
  → 10年以上使用された安定したスケジューラ

  Linux 6.6〜: EEVDF（Earliest Eligible Virtual Deadline First）
  → Peter Zijlstra氏が開発
  → CFSの改良版、仮想デッドラインベース
  → レイテンシの改善とワークロード分離

3.2 CFS（Completely Fair Scheduler）

CFS（Completely Fair Scheduler, 2007〜2023）:

  原理: 全プロセスに「公平に」CPU時間を分配
  → 理想: n個のプロセスがそれぞれ1/nのCPU時間を得る
  → 現実: 1プロセスずつ実行するため完全な公平は不可能
  → 「最も不公平な状態のプロセス」を次に実行する

  仮想ランタイム（vruntime）:
  → プロセスが実行されると vruntime が増加
  → vruntime が最小のプロセスが「最も不公平な状態」
  → そのプロセスを次に選択

  vruntimeの計算:
  vruntime += 実行時間 × (NICE_0_LOAD / weight)

  nice値 → weight → vruntimeの増加速度

nice値が1違うと約1.25倍のCPU時間差
  → nice 0 vs nice 1: 55% vs 45%（約10%差）
  → nice 0 vs nice 5: 75% vs 25%（約3倍差）

  データ構造: 赤黒木（Red-Black Tree）
  → 最小vruntimeのプロセスをO(log n)で取得
  → 実際にはキャッシュされておりO(1)

最左ノード（min vruntime）がO(1)でキャッシュされている
  → 実質的にO(1)の選択時間

  スケジューリング粒度:
  → sched_latency: 全プロセスが一巡する目標時間（デフォルト6ms × プロセス数、上限24ms）
  → sched_min_granularity: 最小実行時間（デフォルト0.75ms）
  → nr_running > sched_latency / sched_min_granularity の場合
    各プロセスにsched_min_granularity を保証

  グループスケジューリング:
  → cgroup v2によるCPU帯域制御
  → ユーザーAとユーザーBがそれぞれ公平にCPU使用
  → ユーザーA(100プロセス) vs ユーザーB(1プロセス)でも50:50

  例（cgroupsでのCPU制御）:

3.3 EEVDF（Earliest Eligible Virtual Deadline First）

EEVDF（Earliest Eligible Virtual Deadline First, Linux 6.6〜）:

  CFSの後継。CFSの問題点を解決:

  CFSの問題点:
  1. レイテンシに敏感なプロセスへの対応が不十分
  2. スリープしたプロセスへのボーナス処理が複雑
  3. nice値とレイテンシの関係が直感的でない
  4. 多くのヒューリスティック（経験則）に依存

  EEVDFの仕組み:
  → 各プロセスに仮想デッドライン（virtual deadline）を設定
  → eligible（実行可能）かつ最も早いデッドラインのプロセスを選択

  仮想デッドライン = 仮想開始時刻 + タイムスライス / weight

  2つの条件:
  1. Eligible（資格あり）: vruntimeが十分に小さい
     → CPU時間を「借り過ぎていない」こと
  2. Earliest Deadline: 仮想デッドラインが最も早い
     → 早く完了すべきプロセスを優先

利点:
  - レイテンシに敏感なワークロード（音声、動画）の改善
  - sleeper bonus等のヒューリスティック排除
  - よりシンプルで予測可能な動作
  - タイムスライスの概念がnice値と直結

  sched_ext（Linux 6.11〜）:
  → BPFプログラムによるカスタムスケジューラ
  → ユーザー空間からスケジューリングポリシーを定義
  → 再起動不要でスケジューラを切り替え可能
  → Meta（Facebook）が開発・活用
  → ゲーミング、サーバー等用途別に最適化

3.4 リアルタイムスケジューリング

Linuxのリアルタイムスケジューリングクラス:

  優先度順:
  1. SCHED_DEADLINE: デッドラインベース（最高優先度）
  2. SCHED_FIFO: リアルタイムFIFO
  3. SCHED_RR: リアルタイムラウンドロビン
  4. SCHED_OTHER（CFS/EEVDF）: 通常プロセス（最低優先度）
  5. SCHED_BATCH: バッチ処理向け（CPU-bound）
  6. SCHED_IDLE: 最低優先度（アイドル時のみ実行）

  リアルタイムプロセスは常に通常プロセスより優先:

SCHED_FIFO:
  → 同優先度内ではFIFO（先着順）
  → より高い優先度が来るまでCPUを手放さない
  → yield()または終了まで実行し続ける
  → 危険: 暴走するとシステムがハングする

  SCHED_RR:
  → SCHED_FIFOにタイムクォンタムを追加
  → 同優先度内でラウンドロビン
  → 高優先度には即座にプリエンプトされる

  SCHED_DEADLINE:
  → EDF（Earliest Deadline First）ベース
  → 3つのパラメータ: Runtime, Deadline, Period
  → Runtime: Period内に保証されるCPU時間
  → Deadline: Runtime分の実行を完了すべき期限
  → Period: タスクの繰り返し周期
  → CBS（Constant Bandwidth Server）で帯域を予約

  例: 音声処理（5ms/20ms周期）

# リアルタイムスケジューリングの設定例
 
# 現在のスケジューリングポリシーの確認
chrt -p $$
 
# SCHED_FIFO（優先度50）で実行
sudo chrt -f 50 ./realtime_app
 
# SCHED_RR（優先度30）で実行
sudo chrt -r 30 ./realtime_app
 
# SCHED_DEADLINE で実行
# Runtime=5ms, Deadline=10ms, Period=20ms
sudo chrt -d --sched-runtime 5000000 \
             --sched-deadline 10000000 \
             --sched-period 20000000 \
             0 ./realtime_app
 
# リアルタイム帯域の制限（暴走防止）
# デフォルト: 1秒中950msまでリアルタイムに使用可能
cat /proc/sys/kernel/sched_rt_runtime_us   # 950000
cat /proc/sys/kernel/sched_rt_period_us    # 1000000
 
# リアルタイム帯域制限を無効化（危険）
echo -1 > /proc/sys/kernel/sched_rt_runtime_us

3.5 マルチコアスケジューリング

マルチコアスケジューリングの課題:

  1. ロードバランシング:
     各コアに均等にプロセスを分配

     Push migration: 過負荷のコアからプロセスを移動
     Pull migration: アイドルのコアがプロセスを引き取る

│ push                      │ pull
          └───────────→ P3 ←──────────┘

  2. キャッシュアフィニティ:
     プロセスをできるだけ同じコアで実行し続ける
     → L1/L2キャッシュにデータが残っている
     → 別コアに移動するとキャッシュミスが発生

     キャッシュのウォームアップコスト:
     L1キャッシュ: 〜1ns（数サイクル）
     L2キャッシュ: 〜5ns
     L3キャッシュ: 〜20ns
     メインメモリ: 〜100ns

     → 移動のコスト vs バランスの利益を天秤にかける

  3. NUMA（Non-Uniform Memory Access）対応:
     メモリへのアクセス速度がCPU位置に依存

ローカルアクセス      リモートアクセス
       〜100ns              〜300ns（3倍遅い）

     → プロセスはメモリが近いNUMAノードで実行すべき
     → Linuxはnumactl, libnumaで制御可能

  4. SMT（Simultaneous Multi-Threading / Hyper-Threading）:
     1つの物理コアに2つ以上の論理コア
     → 実行ユニットを共有するため、100%の性能向上にはならない
     → 典型的には20〜30%の性能向上
     → スケジューラはSMT兄弟の使い方を考慮

  Linuxのスケジューリングドメイン:

# マルチコアスケジューリングの実践
 
# CPUアフィニティの設定
taskset -p 0x3 $$              # CPU 0,1に限定（ビットマスク）
taskset -c 0-3 ./my_program   # CPU 0〜3で実行
 
# NUMAの確認
numactl --hardware              # NUMAトポロジの表示
numactl --membind=0 ./program  # Node 0のメモリに限定
numactl --cpunodebind=0 --membind=0 ./program  # CPU+メモリをNode 0に
 
# スケジューリング統計の確認
cat /proc/schedstat             # グローバル統計
cat /proc/$$/sched              # プロセス別統計
cat /proc/$$/status | grep -i cpu  # 実行コア
 
# per-CPUのRunキュー長
cat /proc/schedstat | awk '{if(NR%3==1) print "CPU"(NR-1)/3": rq_len="$2}'
 
# CPU使用率のリアルタイム監視
mpstat -P ALL 1                 # コアごと
pidstat -u 1                    # プロセスごと
htop                            # 対話的（CPU棒グラフ表示）

4. 他のOSのスケジューラ

4.1 Windows のスケジューラ

Windows スケジューラ:

  優先度ベースのプリエンプティブスケジューリング
  32段階の優先度:
  - 0: ゼロページスレッド（メモリゼロ化専用）
  - 1-15: 通常プロセス（動的優先度）
  - 16-31: リアルタイムプロセス（固定優先度）

  優先度クラス × 相対優先度 = 実効優先度:

動的優先度ブースト:
  - フォアグラウンドウィンドウのスレッド: +2
  - I/O完了: +1〜+8（デバイス種別による）
  - GUI入力待ちからの復帰: +2
  → ブースト後は1ずつ元の基本優先度に戻る

  Multimedia Class Scheduler Service (MMCSS):
  → 音声・動画再生のスレッドに自動的に高優先度を付与
  → 定期的にCPU時間を保証

4.2 macOS/iOS のスケジューラ

macOS/iOS（XNU Kernel）スケジューラ:

  マルチレベルフィードバックキュー + デケイスケジューリング

  スケジューリングバンド:
  1. RT (リアルタイム): 固定優先度
  2. System High: カーネルスレッド
  3. System: カーネルスレッド
  4. User Initiated: ユーザー操作
  5. Default: 一般
  6. Utility: 長時間タスク
  7. Background: バックグラウンド
  8. Maintenance: メンテナンス

  Quality of Service (QoS):
  → アプリはQoSクラスを指定して意図を伝える
  → システムがCPU、I/O、タイマーの優先度を自動調整

  GCD（Grand Central Dispatch）連携:
  → dispatch_async(dispatch_get_global_queue(QOS_CLASS_USER_INITIATED, 0), ^{ ... });
  → スケジューラとGCDが連携してリソースを最適配分

  Apple Silicon（M1〜）の高効率/高性能コア:
  → P-core（Performance）: 高優先度タスク
  → E-core（Efficiency）: 低優先度・バックグラウンドタスク
  → スケジューラがQoSに基づいて自動振り分け

5. スケジューリングの応用

5.1 コンテナ環境でのスケジューリング

コンテナとCPUスケジューリング:

  Dockerコンテナ:
  → cgroups v2でCPU帯域を制御
  → スケジューラはcgroup単位でも公平性を保証

  CPU制限の設定:
  # CPUの50%に制限
  docker run --cpus="0.5" nginx

  # CPU 0と1のみ使用
  docker run --cpuset-cpus="0,1" nginx

  # 相対的なCPU weightの設定
  docker run --cpu-shares=512 app_low    # 通常の半分
  docker run --cpu-shares=2048 app_high  # 通常の2倍

  Kubernetes のCPUリソース:

CPU throttling問題:
  → limits設定時、バースト的なCPU使用でスロットリングが発生
  → 短時間で大量のCPUを消費するとperiod終了まで待機させられる
  → レイテンシが急増する原因になる
  → 対策: limitsを設定しない or 十分に余裕を持たせる

5.2 データベースのCPUスケジューリング

データベースでのスケジューリング考慮事項:

  PostgreSQL:
  → 各接続が独立したプロセス（fork）
  → OSスケジューラに依存
  → hugepages推奨（TLBミス削減）
  → NUMAローカルメモリ配置が重要

  MySQL (InnoDB):
  → スレッドプール + ワーカースレッド
  → innodb_thread_concurrency でスレッド数制御
  → OSスケジューラに依存するが、内部にも軽量スケジューラ

  推奨設定例（Linux）:

5.3 仮想化環境でのスケジューリング

仮想マシンのスケジューリング:

  2レベルのスケジューリング:
  1. ハイパーバイザが仮想CPUをスケジュール
  2. ゲストOSが仮想CPU上でプロセスをスケジュール

問題: Lock Holder Preemption
  → ゲストOS内でロックを保持しているvCPUが
    ハイパーバイザにプリエンプトされる
  → 他のvCPUがロック待ちでスピン
  → CPU時間の無駄遣い

  対策:
  - pause loop exiting（Intel VT-x）
  - halting（スピンを検出してハイパーバイザに通知）
  - CPU overcommit を避ける（vCPU ≤ pCPU）

  VMware vSphere:
  → Proportional Share Based Scheduling
  → CPU shares, reservations, limits でリソース配分
  → DRS（Distributed Resource Scheduler）でクラスタ間バランス

6. 実践演習

演習1: [基礎] — スケジューリングの手計算

以下のプロセスをFCFS、SJF、RR(q=2)でスケジュールし、
平均待ち時間と平均ターンアラウンド時間を比較せよ。

| プロセス | 到着時刻 | 実行時間 |
|---------|---------|---------|
| P1      | 0       | 6       |
| P2      | 1       | 3       |
| P3      | 2       | 1       |
| P4      | 3       | 4       |

解答例（FCFS）:

0          6   9 10   14

待ち時間: P1=0, P2=6-1=5, P3=9-2=7, P4=10-3=7
平均待ち時間: (0+5+7+7)/4 = 4.75ms

ターンアラウンド: P1=6, P2=9-1=8, P3=10-2=8, P4=14-3=11
平均ターンアラウンド: (6+8+8+11)/4 = 8.25ms

解答例（SJF ノンプリエンプティブ）:
t=0: P1のみ → P1開始
t=6: P1完了。Ready: P2(3), P3(1), P4(4) → P3(最短)
t=7: P3完了。Ready: P2(3), P4(4) → P2
t=10: P2完了。→ P4
t=14: P4完了

0          6 7   10   14

待ち時間: P1=0, P3=7-2-1=4, P2=7-1=6, P4=10-3=7
→ 修正: P1=0, P3=6-2=4, P2=7-1=6, P4=10-3=7
平均待ち時間: (0+6+4+7)/4 = 4.25ms

解答例（RR, q=2）:
t=0-2:   P1(残4)  → Ready: P2, P1
t=2-4:   P2(残1)  → Ready: P3, P4, P1, P2
t=4-5:   P3(完了) → Ready: P4, P1, P2
t=5-7:   P4(残2)  → Ready: P1, P2, P4
t=7-9:   P1(残2)  → Ready: P2, P4, P1
t=9-10:  P2(完了) → Ready: P4, P1
t=10-12: P4(完了) → Ready: P1
t=12-14: P1(完了)

待ち時間: P1=14-6=8, P2=10-1-3=6, P3=5-2-1=2, P4=12-3-4=5
平均待ち時間: (8+6+2+5)/4 = 5.25ms

演習2: [応用] — Linuxスケジューラの観察

# プロセスのスケジューリング情報を確認
chrt -p $$                    # 現在のスケジューリングポリシー
cat /proc/$$/sched            # スケジューリング統計（Linux）
 
# nice値の変更
nice -n 10 sleep 100 &        # nice値10で起動
renice -n 5 -p <PID>          # 実行中のプロセスのnice値変更
 
# CPU使用率の監視
top                           # リアルタイム監視
mpstat -P ALL 1               # コアごとの使用率
pidstat -u 1                  # プロセスごとのCPU使用率
 
# スケジューリング遅延の測定
perf sched record sleep 10     # 10秒間のスケジューリングイベント記録
perf sched latency             # スケジューリング遅延の統計
 
# スケジューラのデバッグ情報
cat /proc/sched_debug          # スケジューラの内部状態
cat /sys/kernel/debug/sched/debug  # デバッグ情報（debugfs）
 
# CFS パラメータの確認・変更
cat /proc/sys/kernel/sched_latency_ns          # 目標レイテンシ
cat /proc/sys/kernel/sched_min_granularity_ns  # 最小粒度
cat /proc/sys/kernel/sched_wakeup_granularity_ns  # ウェイクアップ粒度

演習3: [応用] — CPUバウンドとI/Oバウンドの違いの体験

#!/bin/bash
# CPUバウンドプロセスの生成
cpu_bound() {
    echo "CPU-bound (PID: $$) starting with nice $1"
    nice -n $1 dd if=/dev/urandom of=/dev/null bs=1M count=1000 2>&1
}
 
# I/Oバウンドプロセスの生成
io_bound() {
    echo "I/O-bound (PID: $$) starting"
    for i in $(seq 1 1000); do
        dd if=/dev/zero of=/tmp/test_$$ bs=4K count=1 2>/dev/null
        rm -f /tmp/test_$$
    done
}
 
# 異なるnice値で同時実行して比較
time nice -n  0 python3 -c "sum(range(10**8))" &
time nice -n 19 python3 -c "sum(range(10**8))" &
wait
 
# 結果: nice 0のプロセスが先に終了する

演習4: [発展] — コンテナのCPU制限

# Docker でCPU制限のテスト
# CPUを0.5コアに制限
docker run --rm --cpus="0.5" ubuntu:22.04 \
    bash -c "time dd if=/dev/urandom of=/dev/null bs=1M count=500"
 
# CPU制限なし
docker run --rm ubuntu:22.04 \
    bash -c "time dd if=/dev/urandom of=/dev/null bs=1M count=500"
 
# CPU throttling の確認
docker run -d --name test --cpus="0.2" ubuntu:22.04 sleep 3600
# コンテナのcgroup統計
cat /sys/fs/cgroup/system.slice/docker-$(docker inspect test --format '{{.Id}}').scope/cpu.stat
# nr_throttled: スロットリングされた回数
# throttled_time: スロットリングされた合計時間
 
# クリーンアップ
docker rm -f test

トラブルシューティング

よくあるエラーと解決策

デバッグの手順

1. エラーメッセージの確認: スタックトレースを読み、発生箇所を特定する
2. 再現手順の確立: 最小限のコードでエラーを再現する
3. 仮説の立案: 考えられる原因をリストアップする
4. 段階的な検証: ログ出力やデバッガを使って仮説を検証する
5. 修正と回帰テスト: 修正後、関連する箇所のテストも実行する

# デバッグ用ユーティリティ
import logging
import traceback
from functools import wraps
 
# ロガーの設定
logging.basicConfig(
    level=logging.DEBUG,
    format='%(asctime)s [%(levelname)s] %(name)s: %(message)s'
)
logger = logging.getLogger(__name__)
 
def debug_decorator(func):
    """関数の入出力をログ出力するデコレータ"""
    @wraps(func)
    def wrapper(*args, **kwargs):
        logger.debug(f"呼び出し: {func.__name__}(args={args}, kwargs={kwargs})")
        try:
            result = func(*args, **kwargs)
            logger.debug(f"戻り値: {func.__name__} -> {result}")
            return result
        except Exception as e:
            logger.error(f"例外発生: {func.__name__}: {e}")
            logger.error(traceback.format_exc())
            raise
    return wrapper
 
@debug_decorator
def process_data(items):
    """データ処理（デバッグ対象）"""
    if not items:
        raise ValueError("空のデータ")
    return [item * 2 for item in items]

パフォーマンス問題の診断

パフォーマンス問題が発生した場合の診断手順:

1. ボトルネックの特定: プロファイリングツールで計測
2. メモリ使用量の確認: メモリリークの有無をチェック
3. I/O待ちの確認: ディスクやネットワークI/Oの状況を確認
4. 同時接続数の確認: コネクションプールの状態を確認

設計判断ガイド

選択基準マトリクス

技術選択を行う際の判断基準を以下にまとめます。

アーキテクチャパターンの選択

トレードオフの分析

技術的な判断には必ずトレードオフが伴います。以下の観点で分析を行いましょう:

1. 短期 vs 長期のコスト

• 短期的に速い方法が長期的には技術的負債になることがある
• 逆に、過剰な設計は短期的なコストが高く、プロジェクトの遅延を招く

2. 一貫性 vs 柔軟性

• 統一された技術スタックは学習コストが低い
• 多様な技術の採用は適材適所が可能だが、運用コストが増加

3. 抽象化のレベル

• 高い抽象化は再利用性が高いが、デバッグが困難になる場合がある
• 低い抽象化は直感的だが、コードの重複が発生しやすい

# 設計判断の記録テンプレート
class ArchitectureDecisionRecord:
    """ADR (Architecture Decision Record) の作成"""
 
    def __init__(self, title: str):
        self.title = title
        self.context = ""
        self.decision = ""
        self.consequences = []
        self.alternatives = []
 
    def set_context(self, context: str):
        """背景と課題の記述"""
        self.context = context
        return self
 
    def set_decision(self, decision: str):
        """決定内容の記述"""
        self.decision = decision
        return self
 
    def add_consequence(self, consequence: str, positive: bool = True):
        """結果の追加"""
        self.consequences.append({
            'description': consequence,
            'type': 'positive' if positive else 'negative'
        })
        return self
 
    def add_alternative(self, name: str, reason_rejected: str):
        """却下した代替案の追加"""
        self.alternatives.append({
            'name': name,
            'reason_rejected': reason_rejected
        })
        return self
 
    def to_markdown(self) -> str:
        """Markdown形式で出力"""
        md = f"# ADR: {self.title}\n\n"
        md += f"## 背景\n{self.context}\n\n"
        md += f"## 決定\n{self.decision}\n\n"
        md += "## 結果\n"
        for c in self.consequences:
            icon = "✅" if c['type'] == 'positive' else "⚠️"
            md += f"- {icon} {c['description']}\n"
        md += "\n## 却下した代替案\n"
        for a in self.alternatives:
            md += f"- **{a['name']}**: {a['reason_rejected']}\n"
        return md

実務での適用シナリオ

シナリオ1: スタートアップでのMVP開発

状況: 限られたリソースで素早くプロダクトをリリースする必要がある

アプローチ:

• シンプルなアーキテクチャを選択
• 必要最小限の機能に集中
• 自動テストはクリティカルパスのみ
• モニタリングは早期から導入

学んだ教訓:

• 完璧を求めすぎない（YAGNI原則）
• ユーザーフィードバックを早期に取得
• 技術的負債は意識的に管理する

シナリオ2: レガシーシステムのモダナイゼーション

状況: 10年以上運用されているシステムを段階的に刷新する

アプローチ:

• Strangler Fig パターンで段階的に移行
• 既存のテストがない場合はCharacterization Testを先に作成
• APIゲートウェイで新旧システムを共存
• データ移行は段階的に実施

シナリオ3: 大規模チームでの開発

状況: 50人以上のエンジニアが同一プロダクトを開発する

アプローチ:

• ドメイン駆動設計で境界を明確化
• チームごとにオーナーシップを設定
• 共通ライブラリはInner Source方式で管理
• APIファーストで設計し、チーム間の依存を最小化

# チーム間のAPI契約定義
from dataclasses import dataclass
from typing import List, Optional
from enum import Enum
 
class Priority(Enum):
    LOW = "low"
    MEDIUM = "medium"
    HIGH = "high"
    CRITICAL = "critical"
 
@dataclass
class APIContract:
    """チーム間のAPI契約"""
    endpoint: str
    method: str
    owner_team: str
    consumers: List[str]
    sla_ms: int  # レスポンスタイムSLA
    priority: Priority
 
    def validate_sla(self, actual_ms: int) -> bool:
        """SLA準拠の確認"""
        return actual_ms <= self.sla_ms
 
    def to_openapi(self) -> dict:
        """OpenAPI形式で出力"""
        return {
            'path': self.endpoint,
            'method': self.method,
            'x-owner': self.owner_team,
            'x-consumers': self.consumers,
            'x-sla-ms': self.sla_ms
        }
 
# 使用例
contracts = [
    APIContract(
        endpoint="/api/v1/users",
        method="GET",
        owner_team="user-team",
        consumers=["order-team", "notification-team"],
        sla_ms=200,
        priority=Priority.HIGH
    ),
    APIContract(
        endpoint="/api/v1/orders",
        method="POST",
        owner_team="order-team",
        consumers=["payment-team", "inventory-team"],
        sla_ms=500,
        priority=Priority.CRITICAL
    )
]

シナリオ4: パフォーマンスクリティカルなシステム

状況: ミリ秒単位のレスポンスが求められるシステム

最適化ポイント:

1. キャッシュ戦略（L1: インメモリ、L2: Redis、L3: CDN）
2. 非同期処理の活用
3. コネクションプーリング
4. クエリ最適化とインデックス設計

7. FAQ

Q1: タイムクォンタムの最適値は？

一般的には10〜100ms。短すぎるとコンテキストスイッチのオーバーヘッドが増大、長すぎると応答性が悪化。Linuxのデフォルトは約6ms（CFSの目標レイテンシから算出、sched_latency_ns / プロセス数）。ただしEEVDFでは明示的なタイムスライスの概念がnice値のweightから自然に導出される。

Q2: リアルタイムOSと汎用OSの違いは？

リアルタイムOS（RTOS）は「デッドラインまでに必ず処理を完了する」保証を提供。ハードリアルタイム（航空機制御、ABS）は違反が致命的。ソフトリアルタイム（動画再生、VoIP）は違反が品質低下に留まる。LinuxはCONFIG_PREEMPT_RTパッチで「ほぼリアルタイム」を実現可能（Linux 6.12でメインラインに完全統合）。代表的なRTOSにはVxWorks、FreeRTOS、QNX、Zephyrなどがある。

Q3: nice値と優先度の違いは？

nice値はユーザーが設定する相対的な「親切さ」の度合い（-20〜+19）。高いnice値のプロセスは「他のプロセスに親切」=自分のCPU時間を譲る。OSの内部優先度はnice値から計算されるが、他の要因（I/O待ちからの復帰、リアルタイム優先度など）も加味される。Linuxでは内部優先度100〜139がnice -20〜+19に対応する。一般ユーザーはniceを上げることのみ可能（nice値を下げるにはroot権限が必要）。

Q4: なぜLinuxはMLFQではなくCFS/EEVDFを採用しているのか？

MLFQは多くのパラメータ（キュー数、各キューのクォンタム、昇降格条件など）を適切に設定する必要があり、ワークロードに依存する。CFSは「公平性」という単一の原理に基づき、パラメータが少なく、幅広いワークロードで良好な性能を発揮する。EEVDFはさらにレイテンシの保証を改善し、ヒューリスティックを排除した。ただし、sched_ext（Linux 6.11+）によりBPFベースのカスタムMLFQスケジューラを実装することも可能になった。

Q5: スケジューリングはパフォーマンスにどの程度影響するのか？

通常のワークロードではスケジューラの選択による影響は数%〜10%程度。しかし、以下の場合は大きな影響がある:

• レイテンシに敏感なワークロード（ゲーム、音声、HFT）: 数ms〜数十msの差が品質に直結
• 大量のスレッド（数百〜数千）: スケジューラのオーバーヘッドが顕著に
• NUMA環境: 不適切なスケジューリングでメモリアクセスが3倍遅くなる
• コンテナ環境: CPU throttlingにより99パーセンタイルレイテンシが10倍以上に

Q6: コンテキストスイッチを減らすには？

1. スレッド数をCPUコア数に合わせる（過剰なスレッド作成を避ける）
2. I/O多重化（epoll/kqueue/io_uring）でスレッド数を削減
3. ユーザー空間スケジューリング（goroutine, Tokio, Green Thread）を使用
4. CPUアフィニティを設定してコア間移動を防止
5. リアルタイム優先度でプリエンプトを防ぐ（慎重に）
6. ロックの粒度を適切にしてロック待ちによるスイッチを削減

FAQ

Q1: このトピックを学ぶ上で最も重要なポイントは何ですか？

実践的な経験を積むことが最も重要です。理論だけでなく、実際にコードを書いて動作を確認することで理解が深まります。

Q2: 初心者がよく陥る間違いは何ですか？

基礎を飛ばして応用に進むことです。このガイドで説明している基本概念をしっかり理解してから、次のステップに進むことをお勧めします。

Q3: 実務ではどのように活用されていますか？

このトピックの知識は、日常的な開発業務で頻繁に活用されます。特にコードレビューやアーキテクチャ設計の際に重要になります。

8. まとめ

次に読むべきガイド

参考文献

1. Silberschatz, A. et al. "Operating System Concepts." 10th Ed, Ch.5, 2018.
2. Love, R. "Linux Kernel Development." 3rd Ed, Ch.4, 2010.
3. Arpaci-Dusseau, R. H. & Arpaci-Dusseau, A. C. "Operating Systems: Three Easy Pieces." Ch.7-10, 2018.
4. Molnár, I. "CFS Scheduler." Linux Kernel Documentation, 2007.
5. Zijlstra, P. "EEVDF Scheduler." Linux Kernel Mailing List, 2023.
6. Corbet, J. "An EEVDF CPU scheduler for Linux." LWN.net, 2023.
7. Corbet, J. "Extensible scheduling with sched_ext." LWN.net, 2024.
8. Tanenbaum, A. S. & Bos, H. "Modern Operating Systems." 4th Ed, Ch.2, 2014.