先入先出法
FIFO
読み方:ファイフォ,フィフォ
別名:先入れ先出し
FIFOとは、データの格納と取り出しに関する方式のひとつで、最初に格納したデータから取り出す方式のことである。
FIFOは、キュー(queue)と呼ばれるデータ構造で用いられている。キューは「待ち行列」とも呼ばれることもある。人の行列ではもっぱらこの方式が採用されている。
FIFOとは逆に、いちばん最後に入ったデータが最初に出てくるデータの入出力方式は「LIFO」(Last In, First Out)と呼ばれる。LIFOは、処理中のデータや戻りアドレスなどを一時的に退避させるスタックにおいてよく用いられる。
FIFO
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/11/21 14:41 UTC 版)
![]() | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。2022年11月) ( |
FIFO(ファイフォ、フィフォ、フィーフォー)は、First In, First Outを表す頭字語である。先入れ先出しと訳されることがある。
この言葉はキューの動作原理を表すものであり、キューに入っているどんな要素の組に対しても、先に入ったものを先に処理して出し、後に入ってきたものは先に入ったものより後から処理して出す、というように、出入りにおいて順序が保存されることを意味している(厳密には出入りのみを定義しており、処理順ではない)。日本語の俗な慣用表現では「ところてん式」も同じものを指す。
たとえば優先度付きキューはキューの一種であるが、FIFOではない。優先順位によって順序が入れ替わるからである。待ち行列理論における、FIFOキューについての厳密な定義もある。
FIFOは、いくつかの異なる文脈で用いられる。すなわち一般概念のこともあれば、特定の実装のこともある。以下ではそれぞれを解説するが、これが全てではない。たとえばもっとくだけた感じで、同時通訳のような情報の処理方法をFIFOと呼ぶこともある。
コンピュータ
データ構造
キューに格納されたデータの処理方法のひとつである。キュー上の各要素はキューのデータ構造内に格納される。FIFOのキューでは、最初に格納されたデータが、(後で)最初に取出されると同時に削除される。入出力(格納と取出し)は常にその順番で行われる。同義語としてLILO(Last In Last Out)がある。これはキューの一般的な動作である。これの対称として、先入れ後出し(後入れ先出し)の順序があり、スタックまたはLIFOを参照されたい。
典型的なデータ構造は次のようになる。
struct fifo_node { fifo_node *next; value_type value; };
class fifo { fifo_node *front; fifo_node *back; fifo_node dequeue(void) { fifo_node *tmp = front; front = front->next; return tmp; } queue(value) { fifo_node *tempNode = new fifo_node; tempNode->value = value; back->next = tempNode; back = tempNode; } }
この例では、queue(value) で valueがキューに格納され、dequeue() でキューの先頭のデータを取り出すようになっている。
パイプ
一般に、いわゆる「パイプ」の動作はFIFOだが、特にファイルシステム名前空間に名前が作られる「名前付きパイプ」は、ファイルシステム中での種別(通常ファイル、ディレクトリ、デバイスファイル、etc)として「FIFO」と呼ばれている。
論理回路
論理回路では、データの流れる方向が一方向であるという特性のある記憶装置として、バッファリングに使われる。実現方法としては、シフトレジスタのようにデータ全体が一方向に動くという方法と、アドレス付けされたメモリと書込み・読出しの各ポインタ、制御ロジックを組み合わせる方法がある。
重要な役割を果たしているFIFOとしては、デュアルポートSRAMがある。一方のポートがライトに使われ、もう一方がリードに使われる。
同期型FIFOはリードとライトに同じクロックを使用するものである。非同期型FIFOは異なったクロックを使用する。非同期型FIFOは準安定性問題をはらんでいる。非同期型FIFOでは書込み・読出しのポインタの番地変化にインクリメントではなくグレイコードを使い、安定した信号生成ができるようにする。
FIFOにはいくつかのフラグが付属する。フラグは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のページへのリンク