先入先出法
FIFO
読み方:ファイフォ,フィフォ
別名:先入れ先出し
FIFOとは、データの格納と取り出しに関する方式のひとつで、最初に格納したデータから取り出す方式のことである。
FIFOは、キュー(queue)と呼ばれるデータ構造で用いられている。キューは「待ち行列」とも呼ばれることもある。人の行列ではもっぱらこの方式が採用されている。
FIFOとは逆に、いちばん最後に入ったデータが最初に出てくるデータの入出力方式は「LIFO」(Last In, First Out)と呼ばれる。LIFOは、処理中のデータや戻りアドレスなどを一時的に退避させるスタックにおいてよく用いられる。
FIFO
FIFO (First-In First-Out)
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2016/03/08 15:27 UTC 版)
「ページ置換アルゴリズム」の記事における「FIFO (First-In First-Out)」の解説
FIFOページ置換アルゴリズムはオーバヘッドの少ないアルゴリズムのひとつで、OS内でちょっとした記録をとる。名前からもわかるとおり、プロセスに割り当てたページを割り当てた順番にキューに載せる。ページ置換が必要になったとき、キューの先頭のページ(最も古いページ)を選択する。FIFO構造はコストがかからないし簡単なのだが、実際のアプリケーションにこのアルゴリズムを適用すると性能は悪くなる。そのため、そのままの形で使われることはない。このアルゴリズムではBéládyの例外(英語版)と呼ばれる状況が発生しうる。 FIFOページ置換アルゴリズムはVAX/VMSで、若干修正された形で使われている。有効な変換テーブル参照において限定された数のエントリをスキップすることで、後述のセカンドチャンス方式を部分的に取り入れている。そしてさらに、置換されたページをプロセスのワーキングセットからシステム全体のプールに移すが、そういったページが再利用される前に再び当該ページの内容が必要になった場合は、そのまま使える。
※この「FIFO (First-In First-Out)」の解説は、「ページ置換アルゴリズム」の解説の一部です。
「FIFO (First-In First-Out)」を含む「ページ置換アルゴリズム」の記事については、「ページ置換アルゴリズム」の概要を参照ください。
FIFO
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/06/18 04:28 UTC 版)
詳細は「FIFO」を参照 FIFOは最も単純なスケジューリングアルゴリズムで、実行可能キューにプロセスが到着した順番にプロセスをキューイングし、先頭から順に実行する。FCFS (First-Come, First-Served) とも。 コンテキストスイッチはプロセス終了時にしか発生せず、キューの再編成も必要とされないので、スケジューリングのオーバーヘッドは最小である。 長くかかるプロセスがCPUを占有することがあるので、スループットは低くなりうる。 同じ理由で、ターンアラウント時間、待ち時間、応答時間は長くなる可能性がある。 優先順位付けは行わないので、プロセスのデッドラインを満たすのは難しい。 優先順位付けを行わないということは、全てのプロセスが結局は完了するという意味で、スタベーションは発生しないと言える。一部プロセスが完了しない環境では、スタベーションがありうる。 キューイングをベースとしている。
※この「FIFO」の解説は、「スケジューリング」の解説の一部です。
「FIFO」を含む「スケジューリング」の記事については、「スケジューリング」の概要を参照ください。
FIFO
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/06/18 04:28 UTC 版)
このポリシーでスケジュールされたスレッドは、ブロックされるまで、あるいはCPUの制御を明示的に明け渡すまで、あるいはより高優先度のスレッドが動作可能になるまで、動作し続ける。FIFOスケジューリングポリシーは固定優先度のスレッドのみ設定可能である。
※この「FIFO」の解説は、「スケジューリング」の解説の一部です。
「FIFO」を含む「スケジューリング」の記事については、「スケジューリング」の概要を参照ください。
固有名詞の分類
- fifoのページへのリンク