FCFS スケジューリング アルゴリズム: サンプル プログラムとは
ナサニエル・ブルックス
先着順方式とは何ですか?
先入れ先出し（FCFS） は、キューに入れられた要求とプロセスを到着順に自動的に実行するオペレーティング システムのスケジューリング アルゴリズムです。これは、最も簡単でシンプルな CPU スケジューリング アルゴリズムです。このタイプのアルゴリズムでは、最初に CPU を要求したプロセスが最初に CPU 割り当てを取得します。これは FIFO キューで管理されます。FCFS の完全な形式は、First Come First Serve です。
プロセスがレディキューに入るとき、その PCB (プロセス制御ブロック) はキューの最後尾にリンクされ、CPU が空になったら、キューの先頭のプロセスに割り当てられる必要があります。
FCFS工法の特徴
- ノンプリエンプティブおよびプリエンプティブのスケジューリング アルゴリズムをサポートします。
- ジョブは常に先着順で実行されます。
- 実装と使用は簡単です。
- この方法はパフォーマンスが低く、一般に待ち時間が非常に長くなります。
FCFSスケジューリングの例
FCFS 手法の実際の例は、チケット カウンターで映画のチケットを購入することです。 このスケジューリング アルゴリズムでは、キュー メソッドに従って人にサービスが提供されます。 列に最初に到着した人が最初にチケットを購入し、次に次のチケットを購入します。 これは、列の最後の人がチケットを購入するまで続きます。 このアルゴリズムを使用すると、CPU プロセスは同様の方法で動作します。
FCFSはどのように機能するのでしょうか? 平均待ち時間の計算
以下は、異なる時間に到着する XNUMX つのプロセスの例です。 各プロセスのバースト時間は異なります。
| プロセス | バースト時間 | 到着時刻 |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
FCFS スケジューリング アルゴリズムを使用すると、これらのプロセスは次のように処理されます。
ステップ1） プロセスは到着時間が 4 の P0 から始まります。
ステップ2） time=1 で、P3 が到着します。 P4 はまだ実行中です。 したがって、P3 はキュー内に保持されます。
| プロセス | バースト時間 | 到着時刻 |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
ステップ3） 時刻 = 2 で、P1 が到着し、キューに保持されます。
| プロセス | バースト時間 | 到着時刻 |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
ステップ4） time=3 で、P4 プロセスは実行を完了します。
ステップ5） time=4 で、キューの最初にある P3 が実行を開始します。
| プロセス | バースト時間 | 到着時刻 |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
ステップ6） 時刻 =5 に P2 が到着し、キューに入れられます。
| プロセス | バースト時間 | 到着時刻 |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
ステップ7） 時刻 11 で、P3 は実行を完了します。
ステップ8） time=11 で、P1 が実行を開始します。 バースト時間は 6 です。時間間隔 17 で実行を完了します。
ステップ9） time=17 で、P5 が実行を開始します。 バースト時間は 4 です。time=21 で実行が完了します。
ステップ10） time=21 で、P2 が実行を開始します。 バースト時間は 2 です。時間間隔 23 で実行を完了します。
ステップ11） 上の例の平均待ち時間を計算してみましょう。
Waiting time = Start time - Arrival time
P4 = 0-0 = 0
P3 = 3-1 = 2
PI = 11-2 = 9
P5= 17-4 = 13
P2= 21-5= 16
平均待機時間
= 40 / 5 = 8
FCFSの利点
FCFS スケジューリング アルゴリズムを使用する利点と利点は次のとおりです。
- の最も単純な形式 CPUスケジューリングアルゴリズム
- プログラミングが簡単
- 先着順
FCFSの欠点
FCFS スケジューリング アルゴリズムを使用する場合の短所/欠点を次に示します。
- これは非プリエンプティブ CPU スケジューリング アルゴリズムであるため、プロセスが CPU に割り当てられた後は、実行が完了するまで CPU を解放しません。
- 平均待ち時間が長い。
- キューの後ろにある短いプロセスは、前にある長いプロセスが終了するまで待つ必要があります。
- タイムシェアリング システムにとっては理想的な手法ではありません。
- FCFS はその単純さのため、あまり効率的ではありません。
まとめ
- 定義: FCFS は、キューに入れられた要求とプロセスを到着順に自動的に実行するオペレーティングシステムのスケジューリングアルゴリズムです。
- ノンプリエンプティブおよびプリエンプティブのスケジューリングをサポートします。
- アルゴリズム。
- FCFS は先着順サービスの略です
- FCFS 手法の実際の例は、チケット カウンターで映画のチケットを購入することです。
- これは、CPU スケジューリング アルゴリズムの最も単純な形式です。
- これは非プリエンプティブ CPU スケジューリング アルゴリズムであるため、プロセスが CPU に割り当てられた後は、実行が完了するまで CPU を解放しません。
