スケジューリングとは
プロセスAからプロセスBにプロセスが切り替わるとき、OSでは割り込み処理、プロセススケジューリング、プロセスディスパッチャと3つの処理が実行されます。
このとき、切り替えるときどの実行可能状態のプロセスを実行するのかを決定するのがプロセススケジューリングになります。そして、実際に選択されたプロセスをCPUに割り当てるのがディスパッチャになります。
スケジューリングアルゴリズムをどう決定すればいいか
複数の実行可能状態のプロセスの中から、どれを実行中状態へ遷移させるのかを決定するのがスケジューリングアルゴリズムになります。どれを選択すると無駄なくプロセスが実行できるかを見るためには何らかの定量的な尺度が必要となります。
スケジューリングアルゴリズムに利用できる尺度
定量的な尺度として以下が用いられます。
- CPU利用時間
- システムの稼働時間に対する、CPUの利用時間の割合。
- 何の仕事もしていない、優先度が最下位のプロセスが実行された以外の時間として計測可能。
- 目標: 最大化
- スループット
- 単位時間あたりに完了できるプロセス数。
- 目標: 最大化
- ターンアラウンドタイム
- プロセスの実行を要求してから完了するまでの経過時間。
- 実行中、実行可能、待ち状態の各状態にある時間の総和。
- 目標: 最小化
- 待ち時間
- プロセスが生成から終了の間、実行可能または待ち状態にある時間の総和。
- 目標: 最小化
- 応答時間
- プロセスが実行を要求してから、最初の応答が開始されるまでの時間。
- 目標: 最小化
- 特に対話型システムでは重要。システムの応答が一定時間ないとユーザーの不安を招くため、迅速な応答が求められます。
スケジューリングの基準
これらの基準のどれを優先するのか、さらに平均値、最大値、最小値のいずれを尺度として選択するのかが重要です。用途やシステムの特性に応じて、適切な基準を検討します。
- 用途ごとの基準例
- 対話型システム: 応答時間の最大値を最小化
- バッチ処理システム: スループットの向上を重視
- リアルタイムシステム: デッドラインの遵守を最優先。ターンアラウンドタイムの短縮
- 共有環境: CPU利用率と公平性を考慮。
スケジューリングアルゴリズム
スケジューリングアルゴリズムは大きく横取りがある、なしで２つに分けることができます。
横取りがあるスケジューリングアルゴリズム
到着順（FCFS: First Come First Service）
到着順スケジューリングは、実行可能状態に遷移した順番でプロセスがCPUに割り付けられる手法です。
長所：プロセスの実行可能キューをFIFOとして構成することで簡単に実現することができます。
横取りがないスケジューリングのため、実行中状態の長いプロセスが先に実行されると全体効率が悪くなるという短所があります。また、CPUバウンド, I/Oバウンドなどプロセスの特性を利用したスケジューリングができないのも短所となります。
処理時間の長いプロセスが先に到着すると平均のターンアラウンドタイムは長くなり、処理時間の短いプロセスが先に到着すると平均ターンアラウンドタイムは小さくなります。
例：以下のようなプロセスを考えます。
| プロセス名 | 処理時間 |
| A | 5 |
| B | 10 |
| C | 15 |
A→B→Cという順で到達した場合、以下のようになります。
C→B→A という順で到着したとします。
このことから、到着順でターンアラウンドタイム、待ち時間がかなり異なることがわかります。最初に処理時間が短いプロセスが到着した方が全体的には処理速度が速く見えることがわかります。
最短要求時間順（SJF: Shortest Job First）
FCFSの課題として、プロセスの到着順序により平均のターンアラウンドタイムが長くなることがありました。この課題を解決するために、SJFでは最短の実行中状態を要求するプロセスを最優先にしてCPUに割り当てるアルゴリズムです。
長所：実装自体は簡単であり、平均のターンアラウンドタイムと平均の待ち時間の和が最小になることが保証されています。
短所：実際にはプロセスの実行中状態の時間は既知ではないため、使用することはできません。
実際には使用できないアルゴリズムになるので、アルゴリズムの有効性を評価するために比較対象として利用されます。
先ほどの例のA→B→Cは実質SJFを適用した場合と同じになります。
横取りがあるスケジューリングアルゴリム
優先度順
優先度順スケジューリングは、各時点で最高優先度のプロセスをCPUに割り当てるアルゴリズムになります。同じ優先度を持つプロセスはFCFSなどでスケジューリングされます。
優先度を測る指標としては以下がよく用いられます。
- 制限時間
- あらかじめリソースの利用率を割り当てる。割り当てた時間は制限時間として保証する
- メインメモリの使用量
- プロセスが要求するCPU時間
- バッチ処理では、最短ジョブを優先する
- 要求した時間のうち、未使用時間が最小のプロセスを優先する
- 入出力処理に要する時間
- 入出力の要求を先に出し、待ち時間となっている間、他のプロセスが実行可能なのでI/Oバウンド型のプロセスを優先する
- OS以外の要因による緊急性
長所：プロセスの特性を利用したスケジューリングが可能
短所：無限のブロックなどと呼ばれる、優先度が低いプロセスが永遠に処理されず残される状態が発生します。この対策として、長時間実行されないプロセスの優先度を徐々に高くするエージングと呼ばれる方法があります。
ラウンドロビン
ラウンドロビンスケジューリングは、タイムシェアリングシステム（TTS）にために設計されたスケジューリングアルゴリズムです。一定時間ごとに実行するプロセスを固定順で切り替える方式です。
割り当てられる時間量をタイムスライス（タイムクオンタム）と呼びます。タイムスライスが長いとFCFSとほぼ同等の性能になります、一方で短いとプロセススイッチングがオーバヘッドとなります。
長所：実装が簡単で、応答時間が短縮できることです
短所：プロセスの特性を利用していないことです。
例：同様に適用例を見ていきます。以下のようなプロセスを考えます。
| プロセス名 | 処理時間 |
| A | 5 |
| B | 10 |
| C | 15 |
このとき、タイムスライスが3の時のラウンドロビンを適用すると以下のようになります。
多重レベルスケジューリング
プロセスの特性に合わせて、上記のアルゴリズムを複合的に利用する方法も考えることができます。このように、プロセスの特性を分類分けしてスケジューリングする方式を多重レベルスケジューリングと言います。以下のように、プロセスを1つのスケジューリングアルゴリズムに対応するキューに格納し、それぞれのアルゴリズムを適用します。
これに対し、異なるキュー間での移動を可能としたものを多重レベルフィードバックスケジューリングと呼びます。プロセスが実行するにつれ、特性が変わることも考慮して、キューの間を移動することを許します。
まとめ
本記事では、スケジューリングアルゴリズムについて解説しました。横取りがある、横取りがないアルゴリズムをそれぞれ解説しどのような特性があるのかを見ました。
コメント