これまでは、(FCFS スケジューリングで) 到着時間に従ってプロセスをスケジュールしていました。ただし、SJF スケジューリング アルゴリズムは、バースト時間に従ってプロセスをスケジュールします。
SJF スケジューリングでは、レディキュー内の使用可能なプロセスのリストの中で、バースト時間が最も短いプロセスが次にスケジュールされます。
ただし、プロセスに必要なバースト時間を予測することは非常に困難であるため、このアルゴリズムをシステムに実装することは非常に困難です。
SJFのメリット
- 最大スループット
- 最小の平均待ち時間と所要時間
SJFのデメリット
- 飢餓の問題に苦しむ可能性がある
- プロセスの正確なバースト時間を事前に知ることができないため、これは実装できません。
プロセスの CPU バースト時間を決定できるさまざまな手法が利用可能です。それらについては後で詳しく説明します。
例
次の例では、P1、P2、P3、P4、および P5 という名前の 5 つのジョブがあります。それらの到着時間とバースト時間を以下の表に示します。
| PID | 到着時刻 | バーストタイム | 完了時間 | ターンアラウンドタイム | 待ち時間 |
|---|---|---|---|---|---|
| 1 | 1 | 7 | 8 | 7 | 0 |
| 2 | 3 | 3 | 13 | 10 | 7 |
| 3 | 6 | 2 | 10 | 4 | 2 |
| 4 | 7 | 10 | 31 | 24 | 14 |
| 5 | 9 | 8 | 21 | 12 | 4 |
したがって、時間 0 にはプロセスが到着しません。には空のスロットが存在します ガントチャート 時間 0 から 1 (最初のプロセスが到着した時間)。
このアルゴリズムに従って、OS は、レディキュー内の使用可能なプロセスの中でバースト時間が最も短いプロセスをスケジュールします。
これまで、準備完了キューにはプロセスが 1 つしかないため、バースト時間に関係なく、スケジューラはこれをプロセッサにスケジュールします。
これは 8 単位時間まで実行されます。それまでに、さらに 3 つのプロセスが準備完了キューに到着するため、スケジューラはバースト時間が最も短いプロセスを選択します。
表に示されているプロセスのうち、利用可能なすべてのプロセスの中でバースト時間が最も短い P3 が次に実行されます。
ということで、このまま手続きが進んでいきます 最短のジョブから順 (SJF) スケジュールアルゴリズム。
平均待ち時間 = 27/5