コンタクトセンター共同体

スケジューリングは、マルチタスクOS、マルチプロセッシングOS、RTOSなどの設計における重要な概念である。スケジューリングは、優先度つきキューで優先度を割り当てられたプロセス(またはタスク)を制御する手法を指す。この優先度割り当てを行うソフトウェアをスケジューラと呼ぶ。実行プロセスの切り替えを行う操作はディスパッチと呼ばれ、スケジューラはディスパッチ先のプロセスを決定するソフトウェアと言うことができる。

汎用OSでは、スケジューラの設計目標はプロセッサの負荷を公平に分散し、かつ全プロセスについてプロセッサを独占したり、逆に全く資源を割り当てられなかったりすることなく平等に実行されるよう制御することである。ミッションクリティカルな用途を指向している汎用OS(例えばSolaris、AIX、z/OSなど)では、スケジューラは「防御的」機能を備えている。プロセスが積極的にプロセッサリソースを可能な限り使用しようとする場合、システムはそのプロセスを減速させてプロセッサをなるべく割り当てないようにする。

RTOSは機器の自動制御などにも使われるが、そのような場合は処理の遅延が致命的となるので、スケジューラは保証した時間以内にタスクが実行されるようにしなければならない。

スケジューリングの望ましい属性として、システム全体のスループットが高くなること、 リアルタイム性を守ることなどがあげられる。 近年では消費電力を考慮した ローパワースケジューリングの研究が盛んに行われている。

スケジューラは3種類に分類される。「長期スケジューラ」、「中期スケジューラ」、「短期スケジューラ」(ディスパッチャとも呼ぶ)である。

長期スケジューラ

長期スケジューラはジョブやプロセスを実行可能キューに載せるかどうかを決定する。つまり、あるプログラムを実行しようとしたとき、それを実行可能なプロセス群にすぐに追加するか、それとも遅延させるかを長期スケジューラが決定するのである。この種のスケジューラはシステム上で実行すべきプロセス群を決定し、ある時点の並列性の度合いをも決定すると言える。つまり、同時並行的に実行すべきプロセス群を決め、I/Oバウンドなプロセス群とCPUバウンドなプロセス群の比率を決める(I/Oバウンドなプロセスとは入出力待ちとなることが多いプロセスを意味し、CPUバウンドなプロセスとは計算処理主体のプロセスを意味する)。一般的なパーソナルコンピュータなどでは長期スケジューラは存在せず、プロセスは生成されると自動的に実行可能状態となる。しかし、RTOSなどのリアルタイムシステムでは長期スケジューラが重要であり、応答時間の保証のために同時並行的に実行するプロセス数を制限するなどの機能によって、より確実な制御がなされる。[Stallings, 399]

なお、「長期スケジューラ」という用語で別の機能を表す場合もある。プロセスの優先度を自動的に変化させて平等性を確保する場合、CPUバウンドなプロセスは徐々に優先度が下げられ、最終的には最低優先度となる。そのようなプロセスは他に高優先度のプロセスが存在する限り、ディスパッチされないことになってしまう。そのため、実行可能状態でありながら長期間実行されていないプロセスの優先度を上げる処理が定期的に実行される。これを長期スケジューラと呼ぶ場合がある。

中期スケジューラ

中期スケジューラは仮想記憶方式のシステムに必ず存在し、プロセスを主記憶から二次記憶(ディスクなど)に一時的に退避したり、その逆に二次記憶から主記憶にプロセスを戻したりする。このような処理を「スワップアウト」および「スワップイン」と呼ぶ。中期スケジューラは、長期間ブロックされているプロセスや優先度の低いプロセス、頻繁にページフォールトの発生するプロセスや大量のメモリを確保しているプロセスなどをスワップアウトして主記憶を他のプロセスのために空ける。また、主記憶に余裕が生じたときやブロックされていたプロセスが起床した場合などに、スワップアウトされていたプロセスをスワップインする。[Stallings, 396] [Stallings, 370]

多くのシステムではスワップアウトが発生する前にページ置換アルゴリズムが働いて主記憶の空き容量を増やそうとする。そのため、中期スケジューラはある意味で長期スケジューラとも呼べるような位置づけとなっている。ページ置換は一般に特定のプロセスの使用している全メモリを一度に解放するような動作はせず、システム全体で使用頻度の低いページをターゲットとする。そのように置換されて対応する物理メモリのなくなった仮想ページへのアクセスはページフォールトを発生し、例外処理の延長でページインが行われる。実際、スワップアウトが発生するほどメモリ容量が逼迫する状況では、システムは設計段階で予定されていた性能を発揮できない可能性が高く、なるべくページ置換で済むようにメモリ負荷の事前予測を立てるのが通例である。

短期スケジューラ

短期スケジューラ(またはディスパッチャ)は、実行可能状態でメモリ上にあるプロセス群の中で次に実行すべき(CPUを割り当てるべき)プロセスを決定する。そのタイミングとしては、クロック割り込み、I/O割り込み、システムコール、その他の何らかの契機がある。従って、短期スケジューラは長期/中期スケジューラよりも頻繁にスケジューリングを行っている。少なくともタイムスライス毎にスケジューリング処理が行われる可能性があり、その間隔は非常に短い。プリエンプティブなスケジューラでは、プロセスを切り替える必要があると判断したときには強制的にディスパッチを行う。一方、非プリエンプティブなスケジューラでは強制的にディスパッチすることはなく、実行中のプロセスが何らかの資源を待つためにブロックするかプログラム上明示的にプロセッサを明け渡したときだけディスパッチを行う。[Stallings, 396]