優先度スケジューリングアルゴリズム：プリエンプティブ、非プリエンプティブ

優先スケジュールとは何ですか?

優先スケジューリング 優先度に基づいてプロセスをスケジュールする方法です。 このアルゴリズムでは、スケジューラは優先度に従って作業するタスクを選択します。

優先度の高いプロセスが最初に実行される必要がありますが、同じ優先度のジョブはラウンドロビンまたは FCFS ベースで実行されます。 優先順位はメモリ要件、時間要件などによって異なります。

優先スケジュールの種類

優先順位スケジューリングは、主に2つのタイプに分けられます。

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

プリエンプティブ スケジューリングでは、ほとんどのタスクには優先順位が割り当てられます。 場合によっては、たとえ優先度の低いタスクがまだ実行中であっても、優先度の高いタスクを別の優先度の低いタスクの前に実行することが重要である場合があります。 優先度の低いタスクはしばらく保持され、優先度の高いタスクの実行が終了すると再開されます。

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

このスケジューリング方式では、CPUは特定のプロセスに割り当てられます。CPUを占有しているプロセスは、コンテキストを切り替えるか、終了することでCPUを解放します。この方式は、プリエンプティブスケジューリングのように特別なハードウェア（例えばタイマー）を必要としないため、様々なハードウェアプラットフォームで使用できる唯一の方式です。

優先スケジューリングの特徴

• 優先度に基づいてプロセスをスケジュールする CPU アルゴリズム。
• それはで使用されています Operaバッチ処理を実行するためのシステム。
• 同じ優先度を持つ XNUMX つのジョブが READY の場合、そのジョブは XNUMX つのジョブで動作します。 早い者勝ち 基本。
• 優先度スケジューリングでは、各プロセスに優先度を示す番号が割り当てられます。
• 数値が小さいほど、優先順位が高くなります。
• このタイプのスケジューリングアルゴリズムでは、現在実行中のプロセスよりも優先度の高い新しいプロセスが到着した場合、現在実行中のプロセスはプリエンプトされます。

優先スケジューリングの例

次の5つのプロセスP1～P5を考えてみましょう。各プロセスは、それぞれ固有の優先度、バースト時間、到着時間を持っています。

プロセス	優先	バースト時間	到着時刻
P1	1	4	0
P2	2	3	0
P3	1	7	6
P4	3	4	11
P5	2	2	12

ステップ0） 時刻 0 に、プロセス P1 と P2 が到着します。P1 は P2 よりも優先度が高いです。実行はプロセス P1 から開始され、P1 のバースト時間は 4 です。

ステップ1） 時刻 1 において、新たなプロセスは到着しない。実行は P1 で継続される。

ステップ2） 時間 2 では、新しいプロセスは到着しないため、P1 を続行できます。 P2 は待機キューにあります。

ステップ3） 時刻3では、新しいプロセスは到着しないため、P1の処理を続行できます。P2プロセスはまだ待機キューにあります。

ステップ4） 時刻 4 で、P1 は実行を終了します。 P2 が実行を開始します。

ステップ5） 時刻＝5の時点で、新しいプロセスは到着しないため、P2の処理を続行します。

ステップ6） 時刻 6 に P3 が到着します。P3 は優先度 (1) が高く、優先度 (2) の P2 よりも高いです。P2 はプリエンプトされ、P3 の実行が開始されます。

プロセス	優先	バースト時間	到着時刻
P1	1	4	0
P2	2	1 件中 3 件が保留中	0
P3	1	7	6
P4	3	4	11
P5	2	2	12

ステップ7） 時刻7において、新たなプロセスが到着しなかったため、P3の処理を続行します。P2は待機キューに入っています。

ステップ8） 時刻 = 8 の時点で新しいプロセスは到着しないため、P3 の処理を​​続行できます。

ステップ9） 時刻＝9の時点で新しいプロセスは発生しないため、P3の処理を続行できます。

ステップ10） 時間間隔10では新しいプロセスは発生しないため、P3の処理を継続します。

ステップ11） 時刻11において、優先度4のP4が到着する。P3の方が優先度が高いため、実行を継続する。

プロセス	優先	バースト時間	到着時刻
P1	1	4	0
P2	2	1 件中 3 件が保留中	0
P3	1	2 件中 7 件が保留中	6
P4	3	4	11
P5	2	2	12

ステップ12） 時刻12でP5が到着する。P3の方が優先度が高いため、実行が継続される。

ステップ13） 時刻 13 で、P3 の実行が完了します。準備完了キューには P2、P4、P5 があります。P2 と P5 の優先順位は同等です。P2 の到着時刻は P5 より前なので、P2 が実行を開始します。

プロセス	優先	バースト時間	到着時刻
P1	1	4	0
P2	2	1 件中 3 件が保留中	0
P3	1	7	6
P4	3	4	11
P5	2	2	12

ステップ14） 時刻14において、プロセスP2の実行が完了しました。P4とP5は待機状態です。P5が最も高い優先度を持ち、実行を開始します。

ステップ15） 時刻15において、P5は実行を継続する。

ステップ16） 時刻16において、プロセスP5の実行が完了しました。残っているプロセスはP4のみです。P4は実行を開始します。

ステップ17） 時刻 20 において、P4 の実行が完了し、プロセスは残っていません。

ステップ18） 上記の例における平均待ち時間を計算してみましょう。

待機時間 = 開始時間 – 到着時間 + 次のバーストの待機時間

P1 = 0 - 0 = 0
P2 = 4 - 0 + 7 = 11
P3 = 6 - 6 = 0
P4 = 16 - 11 = 5
Average Waiting time = (0 + 11 + 0 + 5 + 2)/5 = 18/5 = 3.6

優先スケジューリングの利点

優先順位付け方式を採用するメリット／利点は以下のとおりです。

• 使いやすいスケジュール管理方法。
• 処理は優先度に基づいて実行されるため、優先度の高い処理は長時間待つ必要がなく、時間の節約につながります。
• この方法は、各プロセスの相対的な重要性を正確に定義できる優れた仕組みを提供する。
• 時間とリソースの要件が変動するアプリケーションに適しています。

優先スケジュールのデメリット

優先順位スケジューリングのデメリットは以下のとおりです。

• 最終的にシステムがクラッシュすると、優先度の低いプロセスがすべて失われます。
• 優先度の高いプロセスが多くの CPU 時間を消費すると、優先度の低いプロセスが枯渇し、無期限に延期される可能性があります。
• このスケジューリング アルゴリズムにより、一部の優先度の低いプロセスが無期限に待機したままになる場合があります。
• プロセスは、実行の準備ができてもブロックされますが、現在他のプロセスが実行されているため、CPU を待つ必要があります。
• 新しい優先度の高いプロセスが準備完了キューに入り続ける場合、待機状態にあるプロセスは長時間待機する必要がある可能性があります。

よくあるご質問