最短ジョブ優先 (SJF): プリエンプティブ、非プリエンプティブの例

SJF メソッドには基本的に XNUMX つのタイプがあります。

• 非プリエンプティブ SJF
• 先制SJF

SJFスケジューリングの特徴

• これは、完了までの時間単位として各ジョブに関連付けられます。
• このアルゴリズム方法は、ジョブの完了を待つことが重要ではないバッチタイプの処理に役立ちます。
• 短いジョブが最初に実行されるようにすることで、プロセスのスループットを向上させることができるため、所要時間が短縮される可能性があります。
• 最初に実行する必要がある短いジョブを提供することにより、ジョブの出力が向上します。これらのジョブは、ほとんどの場合、所要時間が短くなります。

非プリエンプティブ SJF

非プリエンプティブ スケジューリングでは、CPU サイクルがプロセスに割り当てられると、プロセスは待機状態に達するか終了するまでそのサイクルを保持します。

それぞれ独自のバースト時間と到着時間を持つ次の 5 つのプロセスについて考えます。

プロセスキュー	バースト時間	到着時刻
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

ステップ0） time=0 で、P4 が到着し、実行を開始します。

ステップ1） 時刻 = 1 に、プロセス P3 が到着します。 ただし、P4 を完了するにはまだ 2 つの実行ユニットが必要です。 実行を継続します。

ステップ2） 時間 =2 にプロセス P1 が到着し、待機キューに追加されます。 P4 は実行を継続します。

ステップ3） 時間 = 3 で、プロセス P4 は実行を終了します。 P3とP1のバースト時間を比較します。 プロセス P1 は、P3 に比べてバースト時間が短いため実行されます。

ステップ4） 時刻 = 4 で、プロセス P5 が到着し、待機キューに追加されます。 P1 は実行を継続します。

ステップ5） 時刻 = 5 で、プロセス P2 が到着し、待機キューに追加されます。 P1 は実行を継続します。

ステップ6） 時刻 = 9 で、プロセス P1 は実行を終了します。 P3、P5、P2のバースト時間を比較します。 プロセス P2 はバースト時間が最も短いため実行されます。

ステップ7） 時刻 = 10 では、P2 が実行中で、P3 と P5 は待機キューに入っています。

ステップ8） 時刻 = 11 で、プロセス P2 は実行を終了します。 P3とP5のバースト時間を比較します。 プロセス P5 はバースト時間が短いため実行されます。

ステップ9） 時刻 = 15 で、プロセス P5 は実行を終了します。

ステップ10） 時刻 = 23 で、プロセス P3 は実行を終了します。

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

Wait time 
P4= 0-0=0
P1=  3-2=1
P2= 9-5=4
P5= 11-4=7
P3= 15-1=14

Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2

先制SJF

プリエンプティブ SJF スケジューリングでは、ジョブは到着するとレディ キューに入れられます。 バースト時間が最も短いプロセスが実行を開始します。 さらにバースト時間の短いプロセスが到着すると、現在のプロセスは削除されるか実行からプリエンプトされ、短いジョブに CPU サイクルが割り当てられます。

次の 5 つのプロセスを検討してください。

プロセスキュー	バースト時間	到着時刻
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

ステップ0） time=0 で、P4 が到着し、実行を開始します。

プロセスキュー	バースト時間	到着時刻
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

ステップ1） 時刻 = 1 に、プロセス P3 が到着します。 ただし、P4 のバースト時間は短くなります。 実行を継続します。

ステップ2） 時間 = 2 で、プロセス P1 がバースト時間 = 6 で到着します。バースト時間は P4 のバースト時間よりも長くなります。 したがって、P4 は実行を継続します。

ステップ3） 時刻 = 3 で、プロセス P4 は実行を終了します。 P3とP1のバースト時間を比較します。 プロセス P1 はバースト時間が短いため実行されます。

ステップ4） 時間 = 4 で、プロセス P5 が到着します。 P3、P5、P1のバースト時間を比較します。 プロセス P5 はバースト時間が最も短いため実行されます。 プロセス P1 がプリエンプトされます。

プロセスキュー	バースト時間	到着時刻
P1	5個中6個残ってます	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

ステップ5） 時間 = 5 で、プロセス P2 が到着します。 P1、P2、P3、P5 のバースト時間を比較します。 プロセス P2 はバースト時間が最小であるため実行されます。 プロセス P5 がプリエンプトされます。

プロセスキュー	バースト時間	到着時刻
P1	5個中6個残ってます	2
P2	2	5
P3	8	1
P4	3	0
P5	3個中4個残ってます	4

ステップ6） 時間 =6 では、P2 が実行されています。

ステップ7） 時刻 =7 で、P2 は実行を終了します。 P1、P3、P5のバースト時間を比較します。 プロセス P5 はバースト時間が短いため実行されます。

プロセスキュー	バースト時間	到着時刻
P1	5個中6個残ってます	2
P2	2	5
P3	8	1
P4	3	0
P5	3個中4個残ってます	4

ステップ8） 時間 =10 で、P5 は実行を終了します。 P1とP3のバースト時間を比較します。 プロセス P1 はバースト時間が短いため実行されます。

ステップ9） 時間 =15 で、P1 は実行を終了します。 残っているプロセスは P3 だけです。 実行が開始されます。

ステップ10） 時刻 =23 で、P3 は実行を終了します。

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

Wait time 
P4= 0-0=0
P1=  (3-2) + 6 =7
P2= 5-5 = 0
P5= 4-4+2 =2
P3= 15-1 = 14

Average Waiting Time = 0+7+0+2+14/5 = 23/5 =4.6

SJFのメリット

SJF メソッドを使用する利点/長所は次のとおりです。

• SJF は長期的なスケジューリングによく使用されます。
• FIFO (先入れ先出し) アルゴリズムにより平均待ち時間が短縮されます。
• SJF メソッドは、特定のプロセス セットの平均待ち時間を最小にします。
• これは、実行時間が事前にわかっている、バッチで実行されるジョブに適しています。
• 長期スケジューリングのバッチ システムの場合、バースト時間の推定値はジョブ記述から取得できます。
• 短期スケジューリングの場合、次のバースト時間の値を予測する必要があります。
• 平均所要時間に関してはおそらく最適です。

SJFのデメリット・デメリット

SJF アルゴリズムの欠点/短所は次のとおりです。

• ジョブの完了時間はより早く知る必要がありますが、予測するのは困難です。
• 長期的なスケジューリングのためにバッチ システムでよく使用されます。
• SJF は次の場合には実装できません CPU スケジューリング 短期的には。 これは、今後の CPU バーストの長さを予測する具体的な方法がないためです。
• このアルゴリズムにより、ターンアラウンドタイムが非常に長くなったり、飢餓が発生したりする可能性があります。
• プロセスまたはジョブの実行時間に関する知識が必要です。
• 平均所要時間は短縮されない飢餓状態につながります。
• 今後の CPU リクエストの長さを知るのは困難です。
• 経過時間を記録する必要がありますが、これによりプロセッサのオーバーヘッドが増加します。

製品概要

• SJF は、実行時間が最も短いプロセスが次回の実行に選択されるアルゴリズムです。
• SJF スケジュールは、完了までの時間単位として各ジョブに関連付けられます。
• このアルゴリズム方法は、ジョブの完了を待つことが重要ではないバッチタイプの処理に役立ちます。
• SJF 方式には基本的に 1 つのタイプがあります。2) ノンプリエンプティブ SJF と XNUMX) プリエンプティブ SJF です。
• 非プリエンプティブ スケジューリングでは、CPU サイクルがプロセスに割り当てられると、プロセスは待機状態に達するか終了するまでそのサイクルを保持します。
• プリエンプティブ SJF スケジューリングでは、ジョブは到着するとレディ キューに入れられます。
• バースト時間の短いプロセスが開始されますが、現在のプロセスは削除または実行からプリエンプトされ、短い方のジョブが最初に実行されます。
• SJF は長期的なスケジューリングによく使用されます。
• FIFO (先入れ先出し) アルゴリズムにより平均待ち時間が短縮されます。
• SJF スケジューリングでは、ジョブの完了時間をより早く知る必要がありますが、予測するのは困難です。
• SJF は、短期的には CPU スケジューリングに実装できません。 これは、今後の CPU バーストの長さを予測する具体的な方法がないためです。