岩波講座 ソフトウエア科学6「オペレーティングシステム」#4

スケジューリング方式

基本的なスケジューリング方式
(1) 到着順(FCFS))
(2) 処理時間順(SPT)、残っている処理時間の短い順(SRPT)
(3) 優先度順
(4) アラウンドロビン
(5) フィードバック待ち行列(フォアグラウンド・バックグラウンド待ち行列)(FB)

プロセスとジョブを基本的に同一視する。

性能評価基準
(1) 応答時間
    タイムシェアリングシステムや対話型システムではレスポンスタイムと言い、バッチシステムではターンアラウンドタイムと呼ぶ。
(2) スループット
    単位時間に処理するジョブの数で、CPUなどのデバイスの利用効率に比例する。


ラウンドロビン方式では、かかる時間の短いジョブが優先されることとなる。

SRPT方式はSPT方式の変形である。

SPT・SRPT方式は、平均応答時間を最小にする。

スケジューリング方式によって、応答時間は大きな影響を受ける。

一般に、応答時間を短くするという要求と、利用効率を改善するという要求は相反する。

自分でスケジューリングをやってみた。
同一のスケジューリング方式の下では、応答時間と利用効率は、ほぼ反比例の関係にある(単一サーバーシステムでも、マルチサーバーシステムでも)

単一サーバーシステムとは、CPUやI/Oなどの能動的な入出力機器が1個のシステムを言う。

マルチサーバーシステムとは、複数個のサーバーを持つシステムを言う。

マルチサーバーシステムでは、サーバー間で干渉が起こる(1つのサーバーにジョブが集中してしまい、他のサーバーが遊んでしまう)ことにより、無駄な待ち時間が生じてしまう。この待ち時間をスケジューリング方式によって減少させられれば、応答時間の減少と利用効率の向上を同時に実現できる。

マルチプログラミングの主要な目的は、リソース利用の向上またはジョブのスループットの増加である。

一般に、マルチプログラミングは利用効率(ジョブのスループットと比例する)を最大にすることを目的とする。

一般にタイムシェアリングシステムは応答時間を最小にすることを目的としている。

利用効率と応答時間以外の性能評価基準
(1) 予測性
    平均としては短いがばらつきの大きな応答時間より、安定した応答時間が好まれることもある。
(2) 公平性
    あるジョブが無期限に塩基されるのは不公平である。しかし一般に、システム全体の性能を向上させることと、個々のジョブを公平に扱うことは相容れない。
(3) グレイスフルな終了(段階的な終了)
    過負荷になったとき、突然動かなくなるのではなく、段階的に性能を落とすべきである。

FCFS方式

公平で単純であるが、応答時間が非常に大きくなるため、タイムシェアリングシステムには適さない。

プリエンプションのない方式である。


SPT方式

平均応答時間を最小にする方式である。利用効率を向上させることも多い。

しかし一般に、そもそも前もってジョブの処理時間を知ることはできない。

プリエンプションと組み合わせると良い。これはSRPT方式である。SRPT方式は、新しいジョブが到着するたびに、実行中のジョブも含め、全てのジョブにSPT方式を適用する。

プリエンプションは、CPUの場合にはコンテクストスイッチングのオーバーヘッドを伴う。I/Oの場合には、実際には中断はできない。つまりプリエンプションは適用できない。

入出力処理は処理時間の予測ができることが多く、これについてはSPT方式を適用できる。

プリエンプションとは、実行を一時中断し、他のジョブを実行する方式である。


優先度順方式

各プロセスに優先度を与え、その優先度の順に実行する方式である。

良く使われる優先度の付け方は、リアルタイム・プロセス、オペレーティングシステム・プロセス、対話型ジョブのプロセス、バッチジョブの順に優先度を割り当てる。

いったん設定されら優先度が変化しない静的優先度順方式と、実行中に優先度を変える動的優先度順方式がある。

動的優先度順方式は、システムの性能向上のために用いられる。

動的優先度順方式には、SPT方式が含まれる。これは短いジョブに高い優先度を与える。

優先度の低いジョブは、無期延期(スタベーション)の状態に陥ることがある。これに対してエージング(ジョブの待ち時間の長さに比例して優先度を上げる方式)が対策としてある。


ラウンドロビン方式

クオンタムを無限に大きくすれば、FCFS方式となり、クオンタムを小さくすれば、処理時間も短いプロセスが優先される。

クオンタムを非常に小さくすると、実行可能な各プロセスは、みな平等に扱われるようになり、処理時間は、要求されたCPUサービス時間に比例するようになる。このような状態は、プロセッサー分割方式と呼ばれる。

ラウンドロビン方式は、対話型ジョブの応答時間を短くするために開発された。

クオンタムを適切に選べば、適度な応答時間を保証できる。


FB方式

多段のラウンドロビン方式である。」

FB方式は短いジョブをラウンドロビン方式よりさらに優先して扱う。

スタベーションの問題も存在するので、エージング等で対応する。

FB方式、ラウンドロビン方式は、タイムシェアリングシステムだけでなく、マルチプログラミングシステムにも有効である。

統計的には、CPU処理時間はCPU処理の実行が長引けば長引くほど、完了するまでに多くの時間を必要とする。つまり、新しいCPU処理は高い確率ですぐに終了する。これを考慮するのがFB方式である。


入出力ジョブ優先方式

あるPCU処理が非常に長くかかると、他のジョブがCPUサービスを受けられない状態が生じる(ブロッキング現象)

これに対して、CPU処理の短い、つまり、I/O処理の割合の大きいジョブ(入出力ジョブ)を優先することで対応する。

入出力ジョブを優先する理由
(1) CPU処理によるブロッキングを避ける。
(2) 入出力ジョブの多くは、ユーザーがジョブを準備するためのものであるため、優先して実行する必要がある。

実質的に、入出力ジョブ優先方式は、CPU利用効率を高める。