FCFS スケジューリング アルゴリズム: サンプル プログラムとは

先着順方式とは何ですか?

先入れ先出し（FCFS） FCFSは、キューに登録されたリクエストとプロセスを到着順に自動的に実行するオペレーティングシステムのスケジューリングアルゴリズムです。最も簡単でシンプルなCPUスケジューリングアルゴリズムです。このアルゴリズムでは、CPUを最初に要求したプロセスが最初にCPUを割り当てられます。これはFIFOキューによって管理されます。FCFSの正式名称はFirst Come First Serveです。

プロセスが準備完了キューに入ると、そのプロセス制御ブロック（PCB）はキューの末尾にリンクされます。そのため、CPUが空くと、キューの先頭にあるプロセスに割り当てられます。

FCFS方式の特徴

先着順方式の主な特徴は以下のとおりです。

• それは、 非優先 スケジューリングアルゴリズムにより、プロセスはバースト時間を完了するまでCPUを保持します。
• ジョブは常に先着順で実行されます。
• 実装と使用は簡単です。
• この方法はパフォーマンスが低く、一般に待ち時間が非常に長くなります。

FCFSスケジューリングの例

FCFS方式の実際の例としては、映画館のチケット売り場でチケットを購入することが挙げられます。このスケジューリングアルゴリズムでは、列に並んだ順番にチケットが販売されます。列の先頭に到着した人が最初にチケットを購入し、次に次の人が購入します。これは列の最後の人がチケットを購入するまで続きます。CPUプロセスも、このアルゴリズムと同様の方法で動作します。

FCFSはどのように機能するのでしょうか? 平均待ち時間の計算

アルゴリズムがどのようにプロセスをスケジュールするかを理解するために、異なる時間に到着する5つのプロセスの例を以下に示します。各プロセスは異なるバースト時間を持っています。

FCFS スケジューリング アルゴリズムを使用すると、これらのプロセスは次のように処理されます。

ステップ1） このプロセスは、到着時刻が0であるP4から始まります。

ステップ2） time=1 で、P3 が到着します。 P4 はまだ実行中です。 したがって、P3 はキュー内に保持されます。

ステップ3） 時刻2にP1が到着し、キューに保持される。

ステップ4） 時刻3において、P4プロセスは実行を完了する。

ステップ5） time=4 で、キューの最初にある P3 が実行を開始します。

ステップ6） 時刻5にP2が到着し、キューに待機する。

ステップ7） 時刻11において、P3は実行を完了する。

ステップ8） 時刻11で、P1の実行が開始されます。P1のバースト時間は6なので、時刻17で実行が完了します。

ステップ9） 時刻17で、P5の実行が開始されます。P5のバースト時間は4なので、時刻21で実行が完了します。

ステップ10） 時刻21で、P2の実行が開始されます。P1のバースト時間は2なので、時刻23で実行が完了します。

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

Waiting time = Start time - Arrival time

P4 = 0 – 0 = 0

P3 = 3 – 1 = 2

P1 = 11 – 2 = 9

P5 = 17 – 4 = 13

P2 = 21 – 5 = 16

平均待ち時間 = (0 + 2 + 9 + 13 + 16) / 5 = 40 / 5 = 8

FCFSの利点

FCFSスケジューリングアルゴリズムを使用するメリットと利点は以下のとおりです。

• これは最も単純な形です CPUスケジューリングアルゴリズム.
• プログラミングは簡単です。
• 単純な先着順です。

FCFSの欠点

FCFSスケジューリングアルゴリズムを使用する際のデメリットと欠点は以下のとおりです。

• これは非プリエンプティブなCPUスケジューリングアルゴリズムであるため、プロセスがCPUに割り当てられると、そのプロセスが実行を完了するまでCPUを解放することはありません。
• 平均待ち時間が長い。
• 列の後ろにある短い処理は、先頭にある長い処理が終わるまで待たなければならない。
• これはタイムシェアリングシステムにとって理想的な手法ではありません。
• FCFS はその単純さのため、あまり効率的ではありません。

よくあるご質問