情報管理技術士 学習ノート
← 一覧へ
コンピューティング・組込み
#CPU스케줄링#선점/비선점#라운드로빈#MLFQ#CFS
最終更新 · 2026-10-03

CPUスケジューリング(CPU Scheduling)

1. 概要

A. 定義

CPUスケジューリングとは、準備状態(ready)にある複数のプロセス・スレッドの中から次にCPUを占有する一つを選択し、ディスパッチャが実際にコンテキストを切り替えて実行の流れを引き継ぐ、オペレーティングシステムの中核的な資源管理技法である。

現代のオペレーティングシステムがCPUスケジューリングを置く根本的な理由は多重プログラミング(multiprogramming)にある。単一のCPUは一瞬に一つの命令しか実行できないが、プロセスは実行途中でI/Oを要求し、たびたび停止する。もしあるプロセスがディスク応答を待っている間にCPUも一緒に遊んでしまえば、高価な演算資源が無駄になる。スケジューラはこの待機区間を捉えて別の準備済みプロセスにCPUを引き継ぐことで、ユーザーには複数の作業が同時に動いているように見せ、全体の処理量を引き上げる。

B. 登場の背景と必要性

初期の一括処理(batch)の時代には、作業を提出順に一つずつ最後まで走らせたため、スケジューリングと呼ぶべきものは事実上なかった。しかし時分割(time-sharing)システムが登場すると複数のユーザーが一つのCPUを共有するようになり、「短い作業が長い作業の後ろに閉じ込められて延々と待つ」問題、「対話型作業が即座に反応しない」問題が前面に現れた。CPUスケジューリングは、このように限られた処理資源を多数の競合作業にいかに公正かつ効率的に分配するかという問いに対する解答として発展してきた。今日ではスマートフォンから大規模サーバ・リアルタイム制御機まで、応答性・公正性・電力効率を同時に要求する環境において、スケジューラの品質はシステムの体感性能を左右する決定的な要素である。

CPUスケジューリングが効果を発揮する前提はCPUバーストとI/Oバーストの交代である。プログラムの実行は「CPUを使う区間(計算)」と「I/Oを待つ区間」が交互に現れるが、計算中心(CPU-bound)の作業と入出力中心(I/O-bound)の作業が混在しているとき、スケジューラがこれらをうまく組み合わせればCPUとI/O装置が同時に忙しく動き、資源活用が最大化される。したがって良いスケジューリングとは単に「誰を先に」ではなく、作業の性質を読み取って装置間の並列性を最大化することでもある。

C. CPUスケジューリングの特徴

CPUスケジューリングはいくつかの本質的な特徴を持つ。第一に、頻繁性である。短期スケジューラは数ミリ秒ごとに呼び出されるため選択アルゴリズム自体が軽量でなければならず、選択コストが大きければそれ自体がオーバーヘッドとなる(そのためLinuxのCFSもO(log n)のデータ構造を用いる)。第二に、無容赦の資源分配であり、CPUは一瞬に一つしか占有できないため選択はすなわち残りの待機を意味する。第三に、予測の不確実性である。次のCPUバースト長やI/Oの時点を正確には知り得ないため、過去の挙動に基づく推定・適応が不可避である。第四に、ポリシーとメカニズムの分離であり、「誰を選ぶか(ポリシー)」と「どのようにコンテキストを変えるか(ディスパッチャのメカニズム)」を分離して設計し、多様なポリシーを同じ下部構造の上で差し替えられるようにする。

2. プロセス状態遷移とスケジューリング階層

プロセスは生成から終了まで複数の状態を行き来し、スケジューリングはまさにこの状態遷移の特定の分岐点で介入する。以下は典型的な5状態モデルである。

stateDiagram-v2
    [*] --> New
    New --> Ready: "承認(admit)"
    Ready --> Running: "ディスパッチ(scheduler)"
    Running --> Ready: "プリエンプト(time-out/preempt)"
    Running --> Waiting: "I/O・イベント待機"
    Waiting --> Ready: "I/O完了"
    Running --> Terminated: "終了(exit)"
    Terminated --> [*]

ここでRunning→Ready(プリエンプト)の遷移が可能かどうかがスケジューリングポリシーの性格を分ける。プリエンプトが許されれば実行中のプロセスであってもより急ぎの作業やタイムスライス満了によってCPUを奪われ得るし、許されなければ自らI/Oを要求するか終了するまでCPUを握り続ける。またWaiting→Readyの遷移直後が、I/O中心の作業に再び機会を与える重要な決定地点となる。

スケジューリングは時間尺度に応じて三つの階層に分かれる。以下の構造図は各スケジューラの役割と位置を示す。

flowchart LR
    J["作業キュー(new)"] -->|"長期スケジューラ<br/>多重プログラミング度を決定"| R["準備キュー(ready)"]
    R -->|"短期スケジューラ<br/>ミリ秒単位の選択"| D["ディスパッチャ"]
    D --> C["CPU実行(running)"]
    C -->|"I/O要求"| W["待機キュー(waiting)"]
    W -->|"完了"| R
    C -.->|"スワップアウト"| M["中期スケジューラ<br/>メモリ過負荷を調整"]
    M -.->|"スワップイン"| R

ディスパッチャは選択直後に次の作業を順次実行し、この全過程にかかる時間がディスパッチ遅延である。

  • コンテキストの保存・復元: 去るプロセスのレジスタ・PCをPCBに保存し、入ってくるプロセスの状態をロードする。
  • モード切替: カーネルモードからユーザーモードへ切り替える。
  • アドレス空間切替: ページテーブル・TLBを新プロセス基準で入れ替える(仮想アドレス保護)。
  • ジャンプ: 復元したプログラムカウンタの位置へ分岐してユーザーコードを再開する。

長期スケジューラ(long-term)はどの作業をメモリに載せて活性化するかを決定して多重プログラミングの度合いを調整し、中期スケジューラ(medium-term)はメモリ圧迫時に一部のプロセスをディスクへスワップアウトしては戻し、負荷を平準化する。我々が通常「CPUスケジューリング」と呼ぶものはミリ秒単位で最も頻繁に動作する短期スケジューラ(short-term)であり、選択されたプロセスへコンテキストを実際に切り替える役割はディスパッチャ(dispatcher)が担う。ディスパッチャが消費する時間をディスパッチ遅延(dispatch latency)といい、このオーバーヘッドが大きければスケジューリングを頻繁に行うほど損になるため、タイムスライス設計と直結する。

3. スケジューリング性能基準とプリエンプトの有無

スケジューラを評価する尺度は互いにトレードオフ(trade-off)の関係にあるという点が核心である。代表的な指標は次のとおりである。

  • CPU利用率(utilization): CPUが休まず働く割合。高いほど良い。
  • 処理量(throughput): 単位時間あたりの完了作業数。一括処理サーバが重視する。
  • ターンアラウンド時間(turnaround time): 作業の提出から完了までの総時間。
  • 待機時間(waiting time): 準備キューで待った時間の合計。スケジューラが直接減らせる量である。
  • 応答時間(response time): 要求後、最初の反応が出るまでの時間。対話型・リアルタイムシステムの核心である。

処理量を高めようと長いタイムスライスを用いるとコンテキスト切替のオーバーヘッドは減るが応答性が悪化し、逆に短く刻めば対話型の反応は速くなるが切替コストが増えて利用率が落ちる。したがってどの指標を最優先とするかがそのままポリシー選択であり、汎用OSは複数指標の均衡を、リアルタイムシステムは締め切り遵守を絶対優先とする。指標別の優先順位をシステム類型とマッピングすると次のようになる。

システム類型 最優先指標 代表ポリシー
一括処理サーバ 処理量・利用率 SJF近似
時分割・対話型 応答時間 RR・MLFQ
リアルタイム制御 締め切り遵守 EDF・RMS
モバイル端末 応答性・電力効率 EAS結合スケジューラ
区分 非プリエンプト(Non-preemptive) プリエンプト(Preemptive)
CPU返却 自発的(I/O・終了時) 強制回収が可能
応答性 低い(長い作業が独占) 高い
コンテキスト切替オーバーヘッド 少ない 多い
共有資源の一貫性 単純 競合状態・同期が必要
適用 単純な一括処理 時分割・リアルタイム

プリエンプト型は応答性を得る代わりに共有データの一貫性という代償を払う。カーネルのデータ構造を更新している途中でプリエンプトされると他のプロセスが半端な状態を読み得るため、クリティカルセクションの保護(セマフォ・スピンロック)とカーネルプリエンプト地点の設計がともに要求される。

一方であらゆるプリエンプト・切替にはコンテキスト切替(context switch)のコストが隠れている。切替時にOSは去るプロセスのレジスタ・プログラムカウンタ・メモリマップ情報をPCB(Process Control Block)に保存し、入ってくるプロセスの状態を復元するが、この作業の間CPUは有用な仕事を一切できない。より大きな隠れコストはキャッシュ・TLB汚染であり、新プロセスは温まったキャッシュを使えないため初期にキャッシュミスが急増する。したがってスケジューリング頻度を高めて公正性を得る設計は、この間接コストとの均衡の上でのみ正当化され、これがタイムクォンタムを「コンテキスト切替時間の数十倍以上」に設定する実務的な根拠である。

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

A. FCFS(First-Come, First-Served)

最も単純な非プリエンプトポリシーで、到着順にキューから取り出して最後まで実行する。実装が容易で飢餓(starvation)がないという利点があるが、長い作業一つが前を塞ぐと後ろの短い作業がすべて押し出される護衛効果(convoy effect)が致命的である。たとえばバーストが24・3・3msのP1・P2・P3がこの順で到着すると平均待機時間は(0+24+27)/3 = 17msだが、P2・P3・P1の順なら(0+3+6)/3 = 3msへ急減する。同一の作業集合であるにもかかわらず順序だけで性能が5倍以上開くわけであり、この事例は「先に来た順」が効率と無関係であることを劇的に示す。

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

残りのCPUバーストが最も短い作業を先に処理するポリシーで、平均待機時間を最小化することが数学的に証明された最適アルゴリズムである。非プリエンプト版がSJF、プリエンプト版がSRTFである。しかし実際には次のバースト長を事前に知り得ないという根本的な限界があり、過去のバーストの指数平滑(exponential averaging, τ(n+1)=α·t(n)+(1-α)·τ(n))で予測して近似する。もう一つの弱点は飢餓であり、短い作業が絶え間なく入ってくると長い作業は永遠に選ばれないことがある。これを緩和する装置が後で扱うエイジング(aging)である。実務ではビルドキュー・バッチジョブスケジューラが予想実行時間ベースの優先度でSJFの思想を借用する。

C. 優先度スケジューリング(Priority Scheduling)

各作業に優先度を与えて高い方を先に実行する(SJFも「バーストが短いほど高い優先度」という特殊事例である)。プリエンプト・非プリエンプトのいずれも可能で、システムデーモン・ユーザー作業・バックグラウンド作業を差別的に扱えるため柔軟である。核心的な落とし穴はやはり無期限封鎖(飢餓)であり、これを防ぐために長く待った作業の優先度を徐々に上げるエイジングを結合する。また低優先度の作業が共有資源を握ったまま高優先度の作業を塞ぐ優先度逆転(priority inversion)が発生し得るため、優先度継承(priority inheritance)プロトコルで対応する(火星探査機Mars Pathfinderのリセット事故が代表的な事例である)。

D. ラウンドロビン(Round Robin, RR)とMLFQ

RRは時分割の標準であり、各作業に同一のタイムクォンタム(time quantum)を与え、使い切ればキューの最後尾へ送るプリエンプト型FCFSである。公正で応答時間が予測可能という利点のため対話型システムに適する。性能はクォンタムサイズに敏感で、大きすぎるとFCFSに退化し、小さすぎるとコンテキスト切替のオーバーヘッドが急増する。通常は切替コストの数十倍(数ms〜数十ms)に設定し、「バーストの80%がクォンタム内に終わるように」調整する。たとえばバースト24・3・3ms、クォンタム4msならP1が4ms後にプリエンプトされてP2・P3が素早く割り込むため、平均応答時間がFCFSより大きく改善する。

タイムクォンタム設定の実務原則は次のように要約される。

  • 切替コストに対して十分に大きく: コンテキスト切替時間の数十倍以上に置いてオーバーヘッド比率を1%水準以下に抑える。
  • バースト分布に合わせる: 大多数(約80%)のCPUバーストが一クォンタム内に終わるように設定し、不要なプリエンプトを減らす。
  • ワークロード別の差別化: 対話型は小さく(速い反応)、計算中心は大きく(切替の節減) — MLFQがこれを自動化する。

多段フィードバックキュー(MLFQ, Multi-Level Feedback Queue)は複数のRRキューを優先度別に積み、作業の挙動を観察してキューを移動させる適応型ポリシーである。クォンタムを使い切ったCPU-boundの作業は下のキュー(長いクォンタム)へ下げ、早くCPUを返すI/O-bound・対話型の作業は上のキュー(短いクォンタム、高い優先度)にとどめて応答性と処理量を同時に狙う。事前に作業の性質を知らなくても自ら学習するように分類する点が強力であり、周期的な優先度再調整(ブースティング)で飢餓を防止する。

アルゴリズム プリエンプト 平均待機 飢餓 特徴
FCFS X 悪い なし 単純、護衛効果
SJF/SRTF 選択 最適 あり 予測が必要
Priority 選択 可変 あり エイジングが必要
RR O 普通 なし クォンタム敏感、公正
MLFQ O 優秀 なし(ブースティング) 適応型、汎用OS標準

E. 総合比較例 — 同じ作業、異なる結果

ポリシー間の差を数値で体感するため、同時(時刻0)に到着した三つのプロセスP1(24ms)・P2(3ms)・P3(3ms)をFCFS・SJF・RR(クォンタム4ms)でそれぞれ走らせた結果を比較する。以下の表は各ポリシーの完了時刻と待機時間(= 完了時刻 − バースト)を整理したものである。同じ入力であるにもかかわらず平均待機時間がポリシーによって3倍以上開く点に注目すべきである。

ポリシー P1 完了/待機 P2 完了/待機 P3 完了/待機 平均待機時間
FCFS(P1→P2→P3) 24 / 0 27 / 24 30 / 27 17ms
SJF(P2→P3→P1) 30 / 6 3 / 0 6 / 3 3ms
RR(クォンタム4) 30 / 6 10 / 7 13 / 10 7.7ms

FCFSは長いP1が前を塞いで護衛効果により平均待機が最も悪い。SJFは短い作業を先立たせて平均待機を最小化(最適)するが、もし短い作業が入り続ければP1は飢餓に陥る危険を抱える。RRは平均待機はSJFに劣るものの、P2・P3が最初の反応を受けるまでの応答時間(それぞれ4ms、8ms以内)が短く、対話型環境では体感性能が最も優秀である。すなわち「平均待機時間が小さい」と「反応が速い」は異なる目標であり、この例はスケジューラの選択がそのままどの指標を犠牲にして何を得るかの決定であることを明確に示す。

5. 深化 — 実務スケジューラとマルチコアの動向

現実の汎用OSは上の古典アルゴリズムをそのまま使わず、公正性・拡張性・電力を結合した精巧なスケジューラを運用する。Linuxは2007年からCFS(Completely Fair Scheduler)を導入したが、タイムスライスの代わりに各作業が受けたCPU時間を仮想実行時間(vruntime)として累積し、レッドブラックツリーでvruntimeが最も小さい作業をO(log n)で選択することで、「すべての作業に均等なCPUの取り分」を近似する。2024年のLinux 6.6からは遅延に敏感な作業をより良く扱うEEVDF(Earliest Eligible Virtual Deadline First)へ置き換えられ、仮想締め切りの概念で応答性と公正性の均衡を改善した。Windowsは32段階の優先度ベースのプリエンプト型スケジューラに優先度ブースティング(フォアグラウンドのウィンドウ・I/O完了時に一時的に上げる)を結合する。

この発展の効果は具体的な数値で現れる。LinuxがO(1)スケジューラからCFSへ移行することで数千個の作業が同時に動いても選択コストがログ規模に抑えられ、大規模ウェブサーバのテール遅延(tail latency)が改善され、EEVDF導入後はオーディオ・ゲームのような遅延に敏感な作業のフレームドロップが減ったという報告が続いている。逆にスケジューラを誤って扱えば性能が崩れる。代表的な実務事例がKubernetesのcgroups帯域スロットリング(CPU throttling)問題で、コンテナにCPU limitを低く設定するとCFSが100ms周期ごとにクォータ消尽時に該当コンテナを強制的に止め、CPUに余裕があるのに応答時間p99が数百msに跳ね上がる。多くの組織がこの現象のため、遅延に敏感なサービスでCPU limitを除去または上方調整する運用指針を置くが、これはOSスケジューリングの原理を知らなければクラウドの性能チューニングも不可能であることを示す実例である。

モバイル・サーバのヘテロジニアスマルチコアは新たな次元を加える。ARM big.LITTLE / DynamIQは高性能コアと低電力コアを混在させて置き、スケジューラが作業負荷と電力予算に応じてコアを選択(EAS, Energy-Aware Scheduling)してバッテリー寿命を延ばす。またコアごとに準備キューを置くマルチコア環境では負荷の不均衡が生じるため、周期的なロードバランシングと、キャッシュが温まったコアに作業を縛り付けるキャッシュ親和性(processor affinity)の間のトレードオフを管理しなければならない。仮想化・クラウドではハイパーバイザがvCPUを物理CPUに再スケジューリングするため二重スケジューリング(double scheduling)とロックホルダープリエンプト(lock-holder preemption)問題まで考慮対象となる。リアルタイム領域では周期的作業の締め切り保証のためRMS(Rate Monotonic)・EDF(Earliest Deadline First)のような締め切りベースのポリシーが別途用いられる。

6. 考慮事項および示唆点(技術士の観点)

  • 適用戦略 — 目的に合ったポリシー選択: 対話型端末は応答時間(RR・MLFQ)、バッチサーバは処理量(SJF近似)、リアルタイム制御機は締め切り遵守(EDF・RMS)を最優先とすべきである。単一の「最高のスケジューラ」は存在せず、ワークロード特性の分析が先行されなければならない。
  • トレードオフの管理: タイムクォンタムは応答性(短く)とコンテキスト切替オーバーヘッド(長く)の均衡点であり、プリエンプトは応答性を与える代わりに同期コストとキャッシュ汚染を誘発する。指標間の相反を定量的に測定(utilization・p99遅延)してチューニングする力量が要求される。
  • 飢餓・逆転防止の制度化: 優先度ベースのポリシーには必ずエイジングと優先度継承をともに設計して無期限封鎖と優先度逆転を構造的に遮断しなければならない(ミッション遂行システムでは安全事故に直結する)。
  • 電力・持続可能性との連携: ヘテロジニアスコア・DVFSと結合したエネルギー認知スケジューリングはモバイルバッテリーとデータセンターの電力費(グリーンIT)に直接影響する。今後のスケジューラは性能だけでなくワットあたり性能と炭素効率をともに最適化する方向へ進化するだろう。
  • 連携技術への拡張: コンテナ(cgroups CPUクォータ・CFS帯域制御)・Kubernetesのリクエスト/リミット、仮想化のvCPUスケジューリング、そしてGPU・NPU作業のスケジューリングまで同一の原理が拡張適用されるため、OSスケジューリングの理解はクラウド資源管理の土台となる。
  • 観測・検証体系の必要性: スケジューリング品質は平均値ではなくテール遅延(p99・p99.9)とスケジュール遅延(scheduling latency)として現れるため、perf sched・eBPFベースのトレースなどで実際の遅延分布を計測し、SLOに連動して管理する観測体系がともに整ってこそポリシーチューニングが根拠を持つ。

参考資料

一言まとめ: CPUスケジューリングは準備キューの作業の中から次の実行対象を選択して多重プログラミングの効率を引き出す技法であり、FCFS・SJF・優先度・RR・MLFQが応答性・処理量・公正性をそれぞれ異なる形で秤にかけ、実務ではLinuxのCFS/EEVDFやエネルギー認知・マルチコアスケジューリングへと発展している。