到着順方式

読み：とうちゃくじゅんほうしき　／　英語表記：First Come First Served

性能・監視・運用

ジョブやプロセスを、到着した順番に実行するスケジューリングの方式。実行中のプロセスからCPUを強制的に取り上げない。FCFS（First Come First Served）ともいう。

イマシルちゃんの解説

到着順方式は、OSがプログラムへCPUを割り当てる順番を決めるスケジューリング方式の一つだよ。
実行できる状態になったプログラムを待ち行列の末尾に入れ、CPUが空いたら先頭のものを動かすんだ。
動き始めたプログラムは、処理を終えるか入出力待ちになるまでCPUを使えるよ。
途中で別のプログラムが実行可能になっても、それだけでは交代しないの。
順番の管理が簡単な一方、長い処理の後ろでは、すぐ終わる処理も待たされてしまうんだ。

より深い解説

定義

到着順方式（FCFS：First Come First Served、FIFO方式）は、実行可能になった順（到着順）にジョブやプロセスをCPUに割り当てるスケジューリングの方式である。実行中のジョブは、終了するまで（または入出力などで自ら待ちになるまで）CPUを使い続ける、ノンプリエンプティブ（横取りしない）方式である。

特徴

長所	短所
仕組みが単純で、オーバーヘッドが小さい	処理時間の長いジョブが先にあると、後ろの短いジョブも長く待たされる（コンボイ効果）
到着順なので公平で、いつまでも実行されないジョブ（飢餓状態）が生じない	対話型の処理では、応答時間が長くなることがある

主なスケジューリングの方式

方式	実行する順番	横取り
到着順（FCFS）	到着した順	しない
処理時間順（SPT）	処理時間が短い順	しない
優先度順	優先度が高い順	する方式もある
ラウンドロビン	一定の時間（タイムクウォンタム）ずつ、順番に実行する。時間を使い切ったら列の最後に回す	する
多重レベルフィードバックキュー	優先度の異なる複数の列を使い、長く実行したジョブほど優先度を下げる	する

処理時間順（SPT：Shortest Processing Time first）は、平均のターンアラウンドタイムを最小にできるが、長いジョブが後回しにされ続ける飢餓状態が起こりうる。ラウンドロビンは、すべてのジョブに少しずつ実行の機会を与えるため、対話型のシステムに向く。

到着順方式での計算例

ジョブ	到着時刻	処理時間
X	0	6
Y	1	2
Z	3	1

ジョブ	開始	終了	ターンアラウンドタイム
X	0	6	6
Y	6	8	7
Z	8	9	6

Zは処理時間が1しかないのに、Xの終了を待つために、ターンアラウンドタイムが6になっている。これがコンボイ効果である。

処理時間順（SPT）で実行すると、時刻6の時点で待っているYとZのうち、処理時間の短いZを先に実行する。Zのターンアラウンドタイムは 7 − 3 = 4 に縮み、その代わりYは 9 − 1 = 8 に延びる。3つのジョブの平均は、到着順の約6.3から6.0に短くなる。

ネットワークとの関係

到着順の考え方は、ネットワーク機器の送信待ちのキュー（FIFOキュー）にも使われる。FIFOキューでは、音声のように遅延に弱いパケットも、大きなデータのパケットの後ろで待たされるため、優先度の高いパケットを先に送る優先キューイングなどのQoSの仕組みが使われる。

短い時間で交代する場合の経過時間

ラウンドロビン方式では、一つのジョブが終わると、残ったジョブが使えるCPU時間の割合が増える。切替え時間を無視し、非常に短いタイムクウォンタムで交代する場合は、未完了ジョブが処理能力を均等に分けると近似できる。

独自の例として、単独では2分、6分、10分かかる三つのジョブが同時に始まるとする。最初の6分は三つで分け、各ジョブが2分相当進む。一つ目が終わった時点で、残りの必要量は4分と8分である。

そこから二つで分けるため、二つ目の終了にはさらに8分かかり、開始からの経過時間は14分となる。最初から最後まで三等分すると誤る。実際には切替えに必要な時間があり、時間片を細かくしすぎるとオーバーヘッドが増える。

実際の試験ではここに出る！全2問

ネットワークスペシャリスト

午前Ⅱ

R6春問23

テクニカルエンジニア（ネットワーク）

午前

H20秋問8