プロセススケジューリング — OSの基本概念

プロセススケジューリングとは、実行可能状態のプロセスのうち、次にどれへCPUを割り当てるかをオペレーティングシステムが決めることです。平たく言えば、今どれを実行し、どれを待たせるかを決める規則です。この規則によって、待ち時間、応答時間、公平性、全体のスループットが変わります。

プロセススケジューリングが重要なのは、同じプロセス集合でも、FCFS、SJF、ラウンドロビンのどれを使うかで完了順序が大きく変わるからです。この1つの考え方を理解すると、教科書の多くの例がずっと読みやすくなります。

OSにおけるプロセススケジューリングの意味

一般的なOSのモデルでは、プロセスは実行可能、実行中、待機中といった状態の間を移動します。スケジューラは、その中の実行可能なプロセスから選択します。

そのため、プロセススケジューリングはCPUスケジューリングともよく呼ばれます。新しい仕事を生み出すのではなく、待っている仕事にCPUサービスを与える順番を決めるのです。

現代のシステムでは、カーネルがスレッドを直接スケジューリングすることも多いですが、「プロセススケジューリング」という古典的な呼び方は、今でも教育では標準的な用語です。

スケジューラが最適化しようとするもの

スケジューラは通常、次のような複数の目標のバランスを取ろうとします。

• 待ち時間を短くする
• 対話型タスクへの応答を速くする
• スループットを高くする
• 公平性を保つ
• 挙動を予測しやすくする

これらの目標は互いに衝突することがあります。ある単純化した例で平均待ち時間を下げる方針でも、実際には不公平に感じられることがありますし、公平なタイムシェア方式では短いジョブの完了が遅れることもあります。

プリエンプティブとノンプリエンプティブのスケジューリング

ノンプリエンプティブなスケジューラでは、実行中のプロセスはCPUバーストを終えるかブロックするまでCPUを使い続けます。代表例は先着順のFCFSです。

プリエンプティブなスケジューラでは、実行中のプロセスを中断して、別のプロセスにCPUを渡せます。ラウンドロビンや多くの優先度スケジューラがこれに当たります。

この違いが重要なのは、長時間実行される処理を途中で止められると、応答時間が改善されることが多いからです。

よく使われるプロセススケジューリングアルゴリズム

First-Come, First-Served

First-Come, First-Served、つまりFCFSは、到着順にプロセスを実行します。理解しやすく実装も簡単ですが、先頭に長いジョブがあると、その後ろの短いジョブがすべて待たされることがあります。

Shortest Job First

Shortest Job First、つまりSJFは、CPUバーストが最も短いプロセスを優先します。バースト長が正確に分かる単純化した状況では、平均待ち時間を減らせます。実際のシステムでは、そのバースト長は通常推定しなければなりません。

Round Robin

ラウンドロビンは、各実行可能プロセスにクォンタムと呼ばれる短い時間片を与えます。その時間内に終わらなければ、プロセスは実行可能キューの末尾に戻ります。これは通常、対話型ワークロードで公平性と応答性を改善します。

Priority Scheduling

優先度スケジューリングでは、最も優先度の高い実行可能プロセスを先に実行します。あるタスクが他より重要な場合に有効ですが、低優先度のタスクが長く待たされると、飢餓状態が起こる危険があります。

待ち時間を使った1つの具体例

3つのプロセスがすべて時刻 $0$ に到着し、必要なのはCPU時間だけだとします。

• $P_1$: $6\ \mathrm{ms}$
• $P_2$: $2\ \mathrm{ms}$
• $P_3$: $1\ \mathrm{ms}$

前提は次のとおりです。

• CPUは1つだけ
• I/Oによるブロックはない
• コンテキストスイッチのコストは無視する

この条件では、待ち時間とは、プロセスが実行される前に実行可能キューで過ごす時間を意味します。ターンアラウンドタイムは次の式です。

$$\text{turnaround time} = \text{completion time} - \text{arrival time}$$

FCFS

FCFSを使うと、順序は $P_1 \rightarrow P_2 \rightarrow P_3$ です。

タイムライン:

$$0 \to 6: P_1,\qquad 6 \to 8: P_2,\qquad 8 \to 9: P_3$$

待ち時間:

• $P_1 = 0$
• $P_2 = 6$
• $P_3 = 8$

平均待ち時間:

$$\frac{0 + 6 + 8}{3} = \frac{14}{3}\ \mathrm{ms}$$

SJF

ノンプリエンプティブなSJFを使うと、順序は $P_3 \rightarrow P_2 \rightarrow P_1$ です。

タイムライン:

$$0 \to 1: P_3,\qquad 1 \to 3: P_2,\qquad 3 \to 9: P_1$$

待ち時間:

• $P_3 = 0$
• $P_2 = 1$
• $P_1 = 3$

平均待ち時間:

$$\frac{0 + 1 + 3}{3} = \frac{4}{3}\ \mathrm{ms}$$

この例は、基本的な直感をよく示しています。ワークロードは変わっていないのに、規則が変わるだけで結果が変わりました。この場合、短いジョブが長いジョブの後ろで足止めされないため、SJFのほうが平均待ち時間は小さくなります。

ただし、これはSJFが現実世界で常に最良だという意味ではありません。この例の前提のもとでは、スケジューリング順序が非常に重要だという意味です。

覚えておきたい直感

プロセススケジューリングは、CPUに対する待ち行列のルールだと考えると分かりやすいです。実行可能キューに入っているジョブが同じでも、そのキューをどう処理するかの規則によって、利用者が感じる結果は変わります。

最初の応答を速くしたいなら、頻繁に共有する方式を好むかもしれません。短いジョブを素早くたくさん終わらせたいなら、短いバーストを優先する方針を好むかもしれません。厳密なタイミングが重要なら、さらに別のスケジューラが必要になることもあります。

スケジューリング問題でよくある間違い

1つの方針が常に最良だと思い込む

どんなワークロードにも通用する唯一の勝者はありません。平均待ち時間では優秀に見える方針でも、公平性や締切への対応では不十分なことがあります。

待ち時間・応答時間・ターンアラウンドタイムを混同する

これらの指標は関係していますが、同じではありません。特に応答時間は、最初にCPUサービスを受けるまで、または最初に目に見える応答が返るまでの時間を指すことが多く、ターンアラウンドタイムは到着から完了までのジョブ全体を測ります。

式の前提条件を無視する

指標は、示された前提のもとでのみ意味を持ちます。問題にI/Oブロック、異なる到着時刻、コンテキストスイッチのオーバーヘッドが含まれていれば、タイムラインも結果も変わります。

方針がプリエンプティブかどうかを忘れる

SJFと最短残余時間優先は同じ規則ではありません。優先度スケジューリングも、より高い優先度のジョブが現在のジョブを中断できるかどうかで挙動が変わります。

プロセススケジューリングが使われる場面

プロセススケジューリングは、OSがCPU時間を共有しなければならないあらゆる場面で重要です。

• アプリの応答性が必要なデスクトップやモバイルのシステム
• 多数のリクエストを処理するサーバー
• スループットを重視するバッチシステム
• タイミング保証を重視するリアルタイムシステム

実際のスケジューラは教科書の版より複雑なことが多いですが、同じトレードオフはやはり現れます。

自分でも試してみる

例を変えて $P_2$ が後から到着するようにしたり、FCFSの代わりにクォンタム $2\ \mathrm{ms}$ のラウンドロビンを使ったりして、待ち方のパターンがどう変わるか見てみましょう。手計算でやったあとにもう一歩進めたいなら、GPAI Solverで自分の例を試し、予想したタイムラインと計算結果を比べてみてください。