プロセス・スケジューリング

プロセススケジューリングとは

プロセススケジューリングとは、 複数の実行可能なプロセスがある場合、 どの順序で CPU を割り当てるかという問題です。 そして、この問題を担当するプログラムを プロセス・スケジューラと呼び、 プロセス選択に用いるアルゴリズムをスケジューリング・アルゴリズムといいます。。

スケジューリングの目標

どのようなスケジューリングが望ましいか

スケジューリングの設計に関して重要な項目を以下に示します。

スケジューリングアルゴリズムは少なくとも、
スループットを最大にし、応答時間を最小にする。
しかし、両者は一般に相反することが多いため、どちらを重視するかで、
最適なスケジューリングアルゴリズムが異なる。

スケジューリングアルゴリズム

スケジューリングアルゴリズムにはどういうものがあるのだろうか

CPUを割り当てられたプロセスが、 実行を終了するか入出力を行うまでCUPを手放さないとしたら、 他のプロセスの応答時間がそのプロセスの特性に大きく依存してしまいます。 したがって、多くのオペレーティングシステムでは、 オペレーティングシステムがプロセスの実行を途中で中断し、 別のプロセスの実行を開始させます。

これを横取り(preemption)といいます。 スケジューリングは横取りを許すか許さないかで性質が大きく異なります。

以下に、代表的なスケジューリングのアルゴリズムを示します。

(1)到着順スケジューリング (FCFS,first come first service)

プロセスがシステムに到着した(新たに実行可能となった)プロセスから順に処理する、
横取りのないアルゴリズムである。
プロセスは実行可能になると、実行可能待ち行列の最後に置かれる。
スケジューラはCPUを、実行可能待ち行列の先頭のプロセスから順に割り当てる。

(2)処理時間順スケジューリング (SPT,shortest processing time first)

処理時間の短いプロセスから順にCPUを割り当てる、
横取りのないアルゴリズムである。
処理時間順は全プロセスの平均応答時間を最小にする。
横取りを適用した処理時間順アルゴリズムの1つに、
残余処理時間順(SRPT,shortest remaining processing time first)があります。

(3)優先度順スケジューリング (priority)

各プロセスに実行の優先度を与え、優先度の順に実行するというものである。
優先度はさまざまな基準によって定義される。
優先度順では、優先度の高いプロセスを優先的に扱うという性質から、
優先度の低いプロセスは実行可能であってもなかなか実行されないという飢餓状態(starvation)に陥ることがある。

(4)ラウンドロビンスケジューリング (round-robin)

横取りのあるスケジューリングの方針として最も広く用いられているのは、
一定の時間(定時間)ごとにプログラムの実行を切り替えるというものである。
プログラムの実行が開始され定時間が経過すると、次のプログラムが開始される。
いったん実行を終えたプログラムは待ち行列の最後にまわされる。
すなわち、プログラムは待ち行列を巡回しながら順番に実行されるわけである。
このスケジューリングアルゴリズムをラウンドロビンという。

スケジューリングの評価

スケジューリングはなにを基準に評価されるか

評価基準を以下に示す。