現代のコンピュータシステムにおいて、オペレーティングシステム（OS）が果たす役割は計り知れません。その中でも、最も根幹的かつ重要な機能の一つが「CPUスケジューリング」です。私たちの目には見えませんが、OSは常にどのプログラムにCPUという貴重な計算資源を割り当てるかという、複雑な意思決定をミリ秒単位で行っています。この意思決定のルールこそが、CPUスケジューリングアルゴリズムです。
このアルゴリズムの選択は、システムのパフォーマンス、応答性、そしてユーザー体験に直接的な影響を及ぼします。例えば、動画を再生しながら文書を作成し、バックグラウンドでファイルをダウンロードするといったマルチタスク環境がスムーズに動作するのは、優れたスケジューリングアルゴリズムのおかげです。もしこの選択が不適切であれば、システムは頻繁にフリーズしたり、アプリケーションの反応が著しく遅くなったりするでしょう。
本記事では、CPUスケジューリングの世界への第一歩として、最も古典的でありながら基本となる3つのアルゴリズム「FCFS（First-Come, First-Served）」「SJF（Shortest Job First）」「ラウンドロビン（Round Robin）」に焦点を当てます。これらのアルゴリズムがどのように動作し、それぞれがどのような長所と短所を持つのかを、具体的な例を交えながら深く掘り下げていきます。単なる定義の羅列ではなく、なぜそのアルゴリズムが特定状況下で有効または非効率なのか、その「真実」に迫ることを目指します。
CPUスケジューリングを理解するための基礎知識
具体的なアルゴリズムの解説に入る前に、スケジューリングの性能を評価するための共通の指標や用語を理解しておくことが不可欠です。これらの概念は、各アルゴリズムの特性を比較分析する際の基盤となります。
- プロセス（Process）: 実行中のプログラムのインスタンス。OSはこれらのプロセスを管理し、CPU時間を割り当てます。
- CPUバースト時間（CPU Burst Time）: 1つのプロセスが、I/O待ちなどが発生するまでにCPUを連続して使用する時間。実行時間とも呼ばれます。
- 到着時刻（Arrival Time）: プロセスが実行可能状態になり、スケジューラのキュー（待ち行列）に追加された時刻。
- ターンアラウンドタイム（Turnaround Time）: プロセスがキューに到着してから、その実行が完全に終了するまでの総時間。これは「待ち時間」と「実行時間」の合計に等しくなります。（ターンアラウンドタイム = 終了時刻 - 到着時刻）
- 待ち時間（Waiting Time）: プロセスが実行可能キューで、CPUが割り当てられるのを待っている時間の合計。（待ち時間 = ターンアラウンドタイム - CPUバースト時間）
- 応答時間（Response Time）: プロセスがキューに到着してから、初めてCPUが割り当てられ、何らかの応答を開始するまでの時間。インタラクティブなシステムにおいて特に重要な指標です。
- スループット（Throughput）: 単位時間あたりに完了したプロセスの数。システムの処理能力を示す指標です。
- コンテキストスイッチ（Context Switch）: CPUが現在実行しているプロセスを中断し、別のプロセスの実行を開始するために、プロセスの状態（レジスタ情報など）を保存・復元する処理。これにはオーバーヘッド（時間的コスト）が伴います。
これらの指標は、しばしばトレードオフの関係にあります。例えば、あるアルゴリズムが平均待ち時間を劇的に短縮できたとしても、コンテキストスイッチの回数が増加し、システム全体のスループットが低下する可能性があります。スケジューリングアルゴリズムの設計とは、まさにこれらの指標間の最適なバランスを見つける挑戦なのです。
1. FCFS（First-Come, First-Served）アルゴリズム：公平という名の罠
FCFSは、その名の通り「先に来たものから順に処理する」という、最もシンプルで直感的なスケジューリングアルゴリズムです。これは、スーパーのレジ待ち行列や銀行の窓口と全く同じ原理で動作します。OSは、実行可能キューに到着したプロセスを、到着した順番通りにFIFO（First-In, First-Out）キューで管理します。
FCFSの動作原理
実装は非常に簡単です。OSは単純なキューデータ構造を一つ用意し、新しいプロセスが到着するたびにキューの末尾に追加します。CPUが空くと、キューの先頭からプロセスを取り出して実行を開始します。そのプロセスが完了するか、I/O待ちでブロックされるまで、CPUを占有し続けます。
プロセス到着順: P1 -> P2 -> P3 実行可能キュー: [ P1 | P2 | P3 ] ↑ 次に実行 1. CPUがP1の実行を開始。 2. P1が完了。 3. CPUがP2の実行を開始。 4. P2が完了。 5. CPUがP3の実行を開始。 ...
具体例で見るFCFS
以下の3つのプロセスが、ほぼ同時に到着（到着時刻を0とする）した場合を考えてみましょう。
| プロセス | CPUバースト時間 (ms) |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
FCFSでは、到着順（P1, P2, P3）で処理されるため、実行の様子は以下のガントチャートで表せます。
ガントチャート:
|<----------- P1 (24ms) ----------->|<-- P2 (3ms) -->|<-- P3 (3ms) -->|0 24 27 30 (ms)
この場合の各プロセスの待ち時間を計算してみましょう。
- P1の待ち時間: 0 ms (到着後すぐに実行開始)
- P2の待ち時間: 24 ms (P1が終了するまで待機)
- P3の待ち時間: 27 ms (P1とP2が終了するまで待機)
平均待ち時間 = (0 + 24 + 27) / 3 = 17 ms
FCFSの長所と深刻な短所
長所
- 実装が容易: FIFOキューを管理するだけでよいため、アルゴリズム自体は非常にシンプルです。
- 公平性: 到着順という、誰にとっても分かりやすい基準で処理されるため、直感的な公平感があります。
短所：コンボイ効果（Convoy Effect）
FCFSの最大の欠点は、コンボイ効果として知られています。これは、CPUバースト時間が非常に長いプロセスが一つキューの先頭にあると、その後ろに続く多数の短いプロセスが、その長いプロセスが終わるまで延々と待たされてしまう現象です。先ほどの例がまさにこれを示しています。
もし、プロセスの到着順がP2, P3, P1だったらどうなっていたでしょうか？
ガントチャート (P2, P3, P1の順):
|<-- P2 (3ms) -->|<-- P3 (3ms) -->|<----------- P1 (24ms) ----------->|0 3 6 30 (ms)
この場合の待ち時間は、
- P2の待ち時間: 0 ms
- P3の待ち時間: 3 ms
- P1の待ち時間: 6 ms
平均待ち時間 = (0 + 3 + 6) / 3 = 3 ms
驚くべきことに、プロセスの到着順が少し変わっただけで、平均待ち時間は17msから3msへと劇的に改善しました。このことから、FCFSはプロセスの到着順に性能が大きく依存し、特にインタラクティブなシステム（短い応答時間が求められるシステム）には全く向いていないことが分かります。ユーザーがマウスをクリックするという短い処理が、裏で動いている重いバッチ処理の完了を待たなければならない状況を想像してみてください。それは非常にストレスの溜まる体験となるでしょう。
2. SJF（Shortest Job First）アルゴリズム：理想と現実の狭間
SJFアルゴリズムは、FCFSのコンボイ効果の問題を解決するために考案されました。そのアイデアは非常にシンプルで、「次に実行するプロセスとして、CPUバースト時間が最も短いものを選択する」というものです。これにより、短いプロセスが長いプロセスによってブロックされるのを防ぎ、システム全体の平均待ち時間を最小化しようとします。
SJFの種類：非プリエンプティブとプリエンプティブ
SJFには、大きく分けて2つのバリエーションが存在します。
- 非プリエンプティブSJF (Non-Preemptive SJF): CPUが空いた時点で、実行可能キュー内にいるプロセスの中から最もCPUバースト時間が短いものを選択し、実行を開始します。一度実行が始まったプロセスは、自ら終了するかI/O待ちに入るまで中断されることはありません。
- プリエンプティブSJF (Preemptive SJF): こちらはSRTF（Shortest Remaining Time First）アルゴリズムとも呼ばれます。現在あるプロセスが実行中であっても、それより「残りの」実行時間が短い新しいプロセスがキューに到着した場合、OSは現在のプロセスを強制的に中断（プリエンプション）し、新しく到着した、より短いプロセスにCPUを割り当てます。
具体例で見るSJF
ここでは、到着時刻が異なるプロセス群を例に、非プリエンプティブSJFとプリエンプティブSJF（SRTF）の動作を比較してみましょう。
| プロセス | 到着時刻 (ms) | CPUバースト時間 (ms) |
|---|---|---|
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |
非プリエンプティブSJFの場合
- 時刻0: P1が到着。キューにはP1のみなので、P1の実行が開始されます。
- 時刻2: P2が到着。しかし、P1は非プリエンプティブなので実行を続けます。
- 時刻4: P3が到着。P1はまだ実行中です。
- 時刻5: P4が到着。P1はまだ実行中です。
- 時刻7: P1が実行を終了。この時点でキューにはP2(4ms), P3(1ms), P4(4ms)がいます。最もバースト時間が短いのはP3なので、P3の実行が開始されます。
- 時刻8: P3が終了。キューにはP2(4ms)とP4(4ms)がいます。バースト時間が同じなので、ここではFCFSルールを適用し、先に到着したP2を実行します。
- 時刻12: P2が終了。最後にP4を実行します。
- 時刻16: P4が終了。
ガントチャート (非プリエンプティブSJF):
|<---- P1 (7ms) ---->|<P3(1)>|<--- P2 (4ms) --->|<--- P4 (4ms) --->|0 7 8 12 16 (ms)
平均待ち時間 = ((7-0-7) + (12-2-4) + (8-4-1) + (16-5-4)) / 4 = (0 + 6 + 3 + 7) / 4 = 4 ms
プリエンプティブSJF（SRTF）の場合
- 時刻0: P1が到着し、実行を開始。（残り時間: 7ms）
- 時刻2: P2が到着。P2のバースト時間(4ms)は、P1の残り時間(5ms)より短い。よってP1は中断され、P2の実行が開始されます。
- 時刻4: P3が到着。P3のバースト時間(1ms)は、P2の残り時間(2ms)より短い。よってP2は中断され、P3の実行が開始されます。
- 時刻5: P3が実行を終了。この時点でキューにはP1(残り5ms)とP2(残り2ms)、そして新たに到着したP4(4ms)がいます。残りの時間が最も短いのはP2なので、P2の実行を再開します。
- 時刻7: P2が実行を終了。キューにはP1(残り5ms)とP4(4ms)がいます。残りの時間が短いP4の実行を開始します。
- 時刻11: P4が実行を終了。最後に残ったP1の実行を再開します。
- 時刻16: P1が実行を終了。
ガントチャート (プリエンプティブSJF / SRTF):
|<P1(2)>|<P2(2)>|<P3(1)>|<P2(2)>|<--- P4 (4ms) --->|<---- P1 (5ms) ---->|0 2 4 5 7 11 16 (ms)
平均待ち時間 = ((16-0-7) + (7-2-4) + (5-4-1) + (11-5-4)) / 4 = (9 + 1 + 0 + 2) / 4 = 3 ms
このように、プリエンプティブ版であるSRTFは、非プリエンプティブ版よりもさらに平均待ち時間を短縮できることが分かります。実際、SRTFは平均待ち時間を最小化するという観点において、理論上最適なアルゴリズムであることが証明されています。
SJFの長所と致命的な問題点
長所
- 最適な平均待ち時間: 上述の通り、特にSRTFは平均待ち時間を最小化する上で最も効率的なアルゴリズムです。これによりシステム全体のスループットが向上します。
短所
- CPUバースト時間の予測問題: SJFの最大の欠点であり、現実世界での直接的な適用を困難にしているのがこの問題です。「未来の」CPUバースト時間を正確に知ることは不可能です。OSは過去の実行履歴から次のバースト時間を予測するしかありません。一般的な予測方法として、過去の実績値に重みをつけた指数平均法などがあります。
τn+1 = α * tn + (1 - α) * τn
（τn+1: 次の予測値, tn: n回目の実績値, τn: n回目の予測値, α: 重み係数）
しかし、この予測は完璧ではなく、予測が外れた場合のスケジューリングは最適とは言えなくなります。 - 飢餓状態（Starvation）: SJF、特にSRTFでは、CPUバースト時間が長いプロセスが、後から到着する短いプロセスに割り込まれ続け、いつまでたっても実行されない「飢餓状態」に陥る可能性があります。システムの公平性を著しく損なう危険性があります。
SJFは理論的には魅力的ですが、この「未来予測の不可能性」と「飢餓状態」という2つの大きな壁により、そのままの形では現代の汎用OSで採用されることは稀です。しかし、その思想は後述するより高度なアルゴリズムに取り入れられています。
3. ラウンドロビン（Round Robin, RR）アルゴリズム：対話的システムの寵児
FCFSがバッチ処理には向いていても対話型システムには不向きであり、SJFが理論上最適でも現実には適用が難しいという問題がありました。そこで登場するのが、現代のタイムシェアリングシステム（TSS）の基礎となっているラウンドロビン（RR）アルゴリズムです。
RRの基本的な考え方は「全てのプロセスに公平に少しずつCPU時間を与える」ことです。これにより、どのプロセスも長時間待たされることなく、短い応答時間を得ることができます。
ラウンドロビンの動作原理
RRは、FCFSと同様にFIFOキューでプロセスを管理しますが、1つのプロセスがCPUを独占するのを防ぐために「タイムクォンタム（Time Quantum）」または「タイムスライス（Time Slice）」と呼ばれる短い時間単位を導入します。
- CPUが空くと、実行可能キューの先頭からプロセスを取り出し、タイマーをタイムクォンタムに設定して実行を開始します。
- 以下のいずれかのイベントが発生すると、プロセスは中断されます。
- a) プロセスがタイムクォンタムを使い切る前に終了またはI/O待ちになった場合: プロセスはCPUを解放し、OSはキューの次のプロセスを実行します。
- b) タイムクォンタムを使い切ったが、プロセスがまだ完了していない場合: OSはタイマー割り込みによってプロセスを強制的に中断（プリエンプション）し、そのプロセスを実行可能キューの「末尾」に戻します。そして、キューの先頭にいる次のプロセスにCPUを割り当てます。
この仕組みにより、全てのプロセスが定期的にCPU時間を割り当てられ、あたかも複数のプロセスが同時に実行されているかのように見せかけることができます。
タイムクォンタム = 4ms 実行可能キュー: [ P1 | P2 | P3 ] 1. P1が実行開始 (4ms)。 - 4ms後、P1はまだ終わらない -> キューの末尾へ移動。 - キュー: [ P2 | P3 | P1 ] 2. P2が実行開始 (4ms)。 - 途中でP2が完了 -> CPU解放。 3. P3が実行開始 (4ms)。 ...
具体例で見るラウンドロビン
FCFSの例で使ったプロセス群を、タイムクォンタムを4msとしてRRで実行してみましょう。
| プロセス | CPUバースト時間 (ms) |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
ガントチャート (RR, タイムクォンタム=4ms):
|<P1(4)>|<P2(3)>|<P3(3)>|<P1(4)>|<P1(4)>|<P1(4)>|<P1(4)>|<P1(4)>|0 4 7 10 14 18 22 26 30 (ms)
この場合の各プロセスのターンアラウンドタイムと待ち時間を計算します。
- P1: 終了時刻は30ms。待ち時間は (30 - 24) = 6ms。しかし、これは単純な計算です。実際には、P1は (4-4) + (10-7) + (14-10) + ... と細切れに待っています。P1は合計で (7-4) + (10-7) = 6ms待たされました。ターンアラウンドタイムは30msです。
- P2: 終了時刻は7ms。待ち時間は (7 - 3) = 4ms。
- P3: 終了時刻は10ms。待ち時間は (10 - 3) = 7ms。
平均待ち時間 = (6 + 4 + 7) / 3 = 5.67 ms
FCFSの17msと比較すると大幅に改善されています。しかし、FCFSの順序を最適化したケースの3msよりは長くなっています。これがRRの特性です。RRは平均待ち時間を必ずしも最小化しませんが、応答時間を劇的に改善します。この例では、P2は4ms後、P3は7ms後には応答を開始できています。FCFSの最悪ケースではP3の応答は27ms後でした。
ラウンドロビンの長所とタイムクォンタムのジレンマ
長所
- 優れた応答時間: 全てのプロセスが短時間内にCPUを割り当てられるため、ユーザーの操作に対する反応が速く、対話型システムに非常に適しています。
- 飢餓状態が発生しない: どんなに実行時間が長いプロセスでも、少なくともタイムクォンタムごとに一度は実行される機会が保証されているため、飢餓状態に陥りません。公平性が高いと言えます。
短所：タイムクォンタムの大きさ
RRのパフォーマンスは、タイムクォンタムの長さに極めて大きく依存します。この設定は非常にデリケートな問題です。
- タイムクォンタムが大きすぎる場合: 例えば、タイムクォンタムがシステム内のどのプロセスのバースト時間よりも長い場合、RRは実質的にFCFSと同じ動作になります。プリエンプションがほとんど発生せず、RRの利点である応答性の良さが失われます。
- タイムクォンタムが小さすぎる場合: 頻繁にプロセスの切り替え（コンテキストスイッチ）が発生します。コンテキストスイッチにはCPU時間を消費するオーバーヘッドが伴います。もしタイムクォンタムが小さすぎると、OSがプロセスの切り替え作業にばかり時間を費やし、本来のプロセスの処理がほとんど進まないという本末転倒な事態に陥ります。これにより、システム全体のスループットが著しく低下します。
タイムクォンタムとコンテキストスイッチオーバーヘッドの関係
^ コンテキストスイッチ
| のオーバーヘッド
高 | /
| /
| /
| /
| /
| /
| /
低 |/_______________________> タイムクォンタムの長さ
小 大
したがって、タイムクォンタムは、コンテキストスイッチのオーバーヘッドが無視できる程度には長く、かつ、ユーザーが待たされていると感じない程度には短く設定する必要があります。一般的に、10msから100msの範囲で設定されることが多いです。
アルゴリズム比較まとめと実践的な考察
ここまで見てきた3つの基本的なアルゴリズムの特性を、評価指標に基づいて一覧表にまとめてみましょう。
| 評価指標 | FCFS (先着順) | SJF (最短ジョブ優先) | Round Robin (ラウンドロビン) |
|---|---|---|---|
| 平均待ち時間 | 悪い。コンボイ効果により大きく変動。 | 理論上最適（最短）。 | FCFSより良いがSJFよりは悪い。比較的長い。 |
| 応答時間 | 非常に悪い。短いジョブも待たされる。 | 非プリエンプティブ版は悪い。プリエンプティブ版は良い。 | 非常に良い。対話的システムに最適。 |
| スループット | コンボイ効果により低い傾向。 | 短いジョブを優先するため高い傾向。 | コンテキストスイッチのオーバーヘッドによりSJFよりは低い。 |
| 飢餓状態のリスク | なし。いつかは実行される。 | あり。長いジョブが実行されない可能性がある。 | なし。全プロセスに公平に時間が与えられる。 |
| 実装の複雑さ | 非常に容易。 | 困難。バースト時間の予測が必要。 | 比較的容易。タイマー割り込みの管理が必要。 |
どのアルゴリズムが「最善」か？
この問いに対する単純な答えはありません。「最善」のアルゴリズムは、システムの目的によって異なります。
- バッチ処理システムで、ユーザーとの対話がなく、スループットを最大化したいのであれば、予測精度が高い場合の非プリエンプティブSJFが有効な選択肢となり得ます。
- 汎用のデスクトップOSやサーバOSのように、多数のユーザーやプロセスが対話的にシステムを利用し、応答性が最重要視される環境では、ラウンドロビンが基本となります。
- FCFSは、その単純さから他のアルゴリズムの構成要素として使われることはあっても、単体でメインのスケジューラとして採用されることは現代のOSではほとんどありません。
現代のOSスケジューラへの道
実際のところ、Windows, macOS, Linuxといった現代のオペレーティングシステムは、これら単一のアルゴリズムをそのまま使用しているわけではありません。これらの古典的なアルゴリズムのアイデアを組み合わせ、さらに洗練させた、より複雑なスケジューリング方式を採用しています。
その代表例が多段フィードバックキュー（Multilevel Feedback Queue）です。これは、プロセスをその特性（対話的か、バッチ処理的かなど）に応じて複数のキューに分類し、キューごとに異なるスケジューリングアルゴリズム（例えば、優先度の高いキューではRR、低いキューではFCFS）を適用します。さらに、プロセスの振る舞いに応じてキュー間を移動させることで、SJFの飢餓状態の問題を緩和しつつ、RRの応答性の良さを両立しようとします。
例えば、最初はRRのキューに入れられたプロセスが、何度もタイムクォンタムを使い切る（＝CPUバースト時間が長い）ようであれば、優先度の低いFCFSのキューに降格させます。逆に、I/O待ちを頻繁に起こす（＝対話的な）プロセスは、高い優先度のキューに昇格させます。このようにして、システムの状況に動的に適応する、より賢いスケジューリングが実現されています。
結論
CPUスケジューリングは、オペレーティングシステムの中核をなす、深く、そして興味深い分野です。今回取り上げたFCFS、SJF、ラウンドロビンは、その広大な世界への入り口に過ぎません。FCFSは「公平」の単純な定義がいかに危険かを示し、SJFは「最適」の達成がいかに困難であるかを教えてくれます。そしてラウンドロビンは、パフォーマンスと応答性の間の絶妙なトレードオフの重要性を浮き彫りにしました。
これらの基本的なアルゴリズムの原理と限界を理解することは、コンピュータシステムが内部でどのように動作しているかを深く知るための重要な一歩です。そしてそれは、より効率的で応答性の高いソフトウェアを開発するための洞察にも繋がるでしょう。CPUスケジューリングの世界は、限られた資源をいかに賢く分配するかという、コンピュータサイエンスにおける永遠の課題への挑戦なのです。
0 개의 댓글:
Post a Comment