【OS入門#4】Operating Systemを学習：スケジューリングとは
はじめに
書いたコードが遅いとき、原因は本当にアルゴリズムやネットワークでしょうか？
実は、「CPUがプログラムに“いつ”実行権を渡すか」 がボトルネックになることがあります。
これは、OSがすべてのプロセスに対して“誰をいつ実行させるか”を選んでいるからです。
この選択こそが「CPUスケジューリング」であり、表に出て来ませんが、あらゆるソフトウェアのパフォーマンスや体験を根本から左右しています。
前回はプロセスを扱いましたが、今回はそのプロセスの実行の順序を支配する、スケジューリングについて書きます。
今回も今回もOperating System Concepts 10th Editionを参考に読み解いていきたいです。よければプロセスについて書いた前回のやつも参考にしながら読んでみてください！
CPUスケジューリング（CPU Scheduling）
まず、CPUスケジューリングの意義はなんだろうか。本にはこう書いてある：
“The objective of multiprogramming is to have some process running at all times to maximize CPU utilization.”
CPUスケジューリングの目的は、CPUの利用効率を最大化することであり、単一プロセスであれば、I/O待ちの間にCPUが遊んでしまうため、複数のプロセスを管理して切り替えながらCPUをフルに使おう、というのがマルチプログラミングの基本思想である。
Linuxカーネルにおいてプロセス管理はtask_struct構造体により行われている。これは、以前のプロセスの記事でも出てきた、「Process Control Block (PCB)」に相当する。
ここで、スケジューリングについて理解するために、そもそもプロセスがどのような形で実行されるか知る必要がある。
プロセスの実行は通常、CPUバースト（CPU burst）とI/Oバースト（I/O burst） を交互に繰り返す形で進行する。プロセスは、基本的に以下の三つの種類に分けられる：
- CPU-boundプロセスは、長時間にわたってCPUを占有する計算主体の処理を行う。
- I/O-boundプロセスは、頻繁にI/O処理を伴い、CPUの使用は短時間にとどまる。
- インタラクティブプロセスは、ユーザ入力に対する迅速な応答が求められる。
スケジューリングでは、アクティブなプロセスが複数ある場合は、それを入れ換えながら実行する。これらのプロセスに対して、スケジューリングの戦略としては大きく2つに分かれる。
Preemptive Scheduling（プリエンプティブ）
“A preemptive scheduler allows a process to be interrupted in the midst of its execution.”
プリエンプティブ（preemptive）スケジューリングでは、一定の時間間隔でタイマ割り込みを発生させることで、OSが強制的に現在のプロセスを中断し、他のプロセスへと切り替えることができる。これにより、複数のプロセス間で公平性や応答性を高めることが可能となり、特にインタラクティブなアプリケーションでは不可欠な仕組みである。ただし、文脈切り替えに伴うオーバーヘッドは無視できない。GPUやゲームなどでは、こちらが推奨されるだろう。
Non-preemptive Scheduling（非プリエンプティブ）
“Once the CPU has been allocated to a process, it keeps the CPU until it releases the CPU either by terminating or by switching to the waiting state.”
非プリエンプティブ（non-preemptive）スケジューリングでは、プロセスが自発的にI/O要求やAPI呼び出しによってCPUを明け渡すまで、OSは割り込みを行わず、処理の継続を許す。オーバーヘッドは小さいが、CPU-boundプロセスがCPUを長時間占有してしまうと、I/O-boundやインタラクティブなプロセスの応答性が損なわれるという欠点がある。こちらでは化学計算やバックグラウンド処理が適切。
このように、それぞれのプロセスを行なっている時間であるバーストとスケジューリング戦略を組み合わせることは、OS設計において重要な観点の一つであるのは確かだろう。
GanttChartとスケジューリングの評価基準
CPUの割当ての様子はGantt Chartという一種の棒グラフがわかりやすい。GanttChart（ガントチャート）は、CPUの割り当てスケジュールを視覚的に示すタイムラインである。
“A Gantt chart can be used to show a schedule produced by a particular scheduling algorithm.”
プロセスがどのタイミングでCPUを使ったかを横棒で表し、時間経過に沿ってプロセスの切り替わりを見ることができる。ここでは作るのが難儀だったので例は載せない。
また、スケジューリングの評価基準としての指標に以下のようなものがある：
- CPU Utilization：CPUの稼働率。可能な限り100%に近づけるのが理想
- Throughput：単位時間あたりに終了するプロセス数（多い方が良い）
- Turnaround Time：プロセスの開始から終了までの総時間（短いほど良い）
- Waiting Time：レディキューにいた時間の合計（短いほど良い）
- Response Time：初めてCPUをもらうまでの時間（特にインタラクティブで重要）
それぞれの評価項目は、プロセスの特性やシステムの目的に応じて最適化の優先順位が変わる。
スケジューリングアルゴリズム（Scheduling Algorithms）
ここでは、さまざまなスケジューリング手法を見ていく。それぞれのアルゴリズムは先ほどの評価指標（Waiting Time、Turnaround Time、Response Timeなど） に対して長所・短所があり、ユースケースによって選択が異なる。
-
First-Come, First-Served（FCFS）
“The simplest scheduling algorithm is first-come, first-served (FCFS) scheduling.”
このアルゴリズムでは、プロセスは到着順に処理され、実装はキュー（FIFO）で簡単である。待ち時間のばらつきが大きく（Convoy Effect）、I/O boundプロセスがCPU boundに巻き込まれる問題が起きやすいのが特徴である。
-
Shortest Job First（SJF）
“This algorithm associates with each process the length of the process’s next CPU burst.”
このアルゴリズムでは、実行時間が短いプロセスから優先されるため、最短平均待ち時間を実現している。実行時間の予測が必要であることもあげられる。調べたところ、Preemptive版（Shortest Remaining Time First）も存在している。
-
Priority Scheduling
“A priority number (integer) is associated with each process.”
各プロセスに優先度を割り当て、数値の低い（または高い）ものから実行していくアルゴリズム。
飢餓状態（Starvation） と呼ばれる、優先度の低いプロセスが、優先度の高いプロセスによって長時間実行されずに、飢餓状態に陥る状態が発生しやすい。
対策として、実行されないプロセスの優先度を徐々に上げていくAgingというものがある。 -
Round Robin（RR）
“The ready queue is treated as a circular queue.”
各プロセスに 時間量（quantum） を設定し、順番に少しずつCPUを分け合うアルゴリズム。
インタラクティブシステム向けであり、文脈切り替え（Context Switch）のオーバーヘッドが多すぎると効率が悪化する特徴がある。 -
Multilevel Queue（MLQ）Scheduling
“A multilevel queue scheduling algorithm partitions the ready queue into several separate queues.”
プロセスを特性別に分類（例：interactive, batch, system）し、各キューに別々のスケジューリングポリシーを与えるが、一度分類されるとキューの移動ができないのが欠点である。
-
Multilevel Feedback Queue（MLFQ）
“A process can move between the various queues.”
このアルゴリズムは上記のMLQの改良版であり、キュー間で移動できないという欠点を補っており、プロセスがキュー間を移動可能である。よく動く（短いバーストの）プロセスは高優先度キューに、長く動き続けるものは低優先度へ移動される。
実際のOSでは複数の戦略を組み合わせたハイブリッド型が使われている。たとえばLinuxのCFS（Completely Fair Scheduler）は Red-Black Tree を使って、SJFとRRの中間のような動作をする。データ構造の一つである赤黒木については以下で説明されており、面白かったので載せとく。
リアルタイムスケジューリング（Real-Time Scheduling）
リアルタイムシステムでは、処理の正しさは「結果の正確さ」だけでなく「時間内に処理されること」も重要である。つまり、締め切り、デッドラインに間に合うかどうかが鍵の一つである。
ここで、スケジューリングには、利用率条件（Utilization Test） というものがある。
m 個の周期的タスク（periodic task） があるとき、タスクiが必要とするCPU時間を
この合計が1未満であれば、理論上すべてのタスクを期限内に処理可能である、ということを意味する。ここで重要なのは、「理論的にスケジューリング可能な条件」であって、「絶対にすべてのデッドラインに間に合う保証条件」ではないことである。
ここで、参考までにではあるが、最も締め切りが近いタスクを優先的に実行し、動的優先度（Dynamic Priority）をつけ、Preemptiveで動作する**Earliest Deadline First（EDF）**というアルゴリズムでは、「利用率の合計が1以下なら必ずスケジューリングできる」という必要十分条件となる。
リアルタイムプログラミングにおける注意点：ロックと優先度逆転（Priority Inversion）
リアルタイムシステムでは、予測不能な待ち時間がタスクの実行遅延やデッドラインミスにつながるため、同期とロックの扱いに特別な注意が必要である。
では、優先度逆転では何が起きているのだろうか。
例えば、高優先度タスク
そしてOSのスケジューラは中優先度タスク
結果として、
“Priority inversion occurs when a lower-priority process holds a lock needed by a higher-priority process.”
では対策として、どうすればいいのだろうか。この解決策として、優先度継承（Priority Inheritance） という方法がある。
“The solution is to have the lower-priority process temporarily inherit the priority of the higher-priority process.”
結果として、
まとめ
本記事では、CPUスケジューリングの基礎から主要なアルゴリズム、リアルタイム処理における設計の難しさまでを横断的に見てきました。
プロセスという「実行の単位」がどのように切り替えられ、どんな特性を持つかを理解することは、OSの設計原理を知るうえで欠かせない第一歩です。
そして次回は、この「プロセス」という単位をさらに軽量化した実行単位――スレッド（軽量プロセス） の登場に迫ります。
また、それに伴って避けて通れない排他制御（ロック）のメカニズムについても、プロセスと資源の関係から深掘りしたいです。
参考文献
- Abraham Silberschatz, Peter B. Galvin, Greg Gagne, Operating System Concepts, 10th Edition, Wiley, 2018.: https://amzn.to/44zHODM
Discussion