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

優先スケジュールの種類

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

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

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

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

このタイプのスケジューリング方法では、CPU が特定のプロセスに割り当てられます。 CPU をビジー状態に保つプロセスは、コンテキストを切り替えるか終了することによって CPU を解放します。 これは、さまざまなハードウェア プラットフォームで使用できる唯一の方法です。 それは、プリエンプティブ スケジューリングのような特別なハードウェア (タイマーなど) が必要ないためです。

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

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

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

次の 1 つのプロセス P5 から PXNUMX について考えます。各プロセスには、固有の優先度、バースト時間、到着時間があります。

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

ステップ0） time=0 で、プロセス P1 と P2 が到着します。 P1 は P2 よりも優先されます。 実行は、バースト時間 1 のプロセス P4 から始まります。

ステップ1） time=1 では、新しいプロセスは到着しません。 実行は P1 から続行されます。

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

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

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

ステップ5） 時間 = 5 では、新しいプロセスは到着しないため、P2 を続行します。

ステップ6） 時刻 = 6 に P3 が到着します。 P3 の優先順位 (1) と比較して、P2 の優先順位 (2) は高くなります。 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 で、P4 が優先度 4 で到着します。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） time=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 だけです。 実行が開始されます。

ステップ17） 時間 =20 で、P5 は実行を完了し、プロセスは残りません。

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

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

P1 = o - o = o
P2 =4 - o + 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 を待つ必要があります。
• 新しい優先度の高いプロセスが準備完了キューに入り続ける場合、待機状態にあるプロセスは長時間待機する必要がある可能性があります。

まとめ

• 優先スケジューリングは、優先度に基づいてプロセスをスケジュールする方法です。 このアルゴリズムでは、スケジューラは優先度に従って作業するタスクを選択します。
• Priority Preemptive Scheduling では、ほとんどのタスクには優先度が割り当てられます。
• Priority Non-preemptive スケジューリング方式では、CPU が特定のプロセスに割り当てられます。
• プロセスは優先度に基づいて実行されるため、優先度が高くても長時間待つ必要がなく、時間を節約できます。
• 優先度の高いプロセスが多くの CPU 時間を消費すると、優先度の低いプロセスが枯渇し、無期限に延期される可能性があります。