この項目では、データ処理方式について説明しています。
会計学の原価計算におけるFIFOについては「先入先出法 」をご覧ください。
enqueue (エンキュー) および dequeue (デキュー) による、FIFO (queue) のイメージ
FIFO (ファイフォ、フィフォ、フィーフォー)は、F irst I n, F irst O ut を表す頭字語 である。先入れ先出し と訳されることがある。
この言葉はキュー の動作原理を表すものであり、キューに入っているどんな要素の組に対しても、先に入ったものを先に処理して出し、後に入ってきたものは先に入ったものより後から処理して出す、というように、出入りにおいて順序が保存されることを意味している(厳密には出入りのみを定義しており、処理順ではない)。日本語の俗な慣用表現では「ところてん 式」も同じものを指す。
たとえば優先度付きキュー はキューの一種であるが、FIFOではない。優先順位によって順序が入れ替わるからである。待ち行列理論 における、FIFOキューについての厳密な定義もある。
FIFO は、いくつかの異なる文脈で用いられる。すなわち一般概念のこともあれば、特定の実装のこともある。以下ではそれぞれを解説するが、これが全てではない。たとえばもっとくだけた感じで、同時通訳のような情報の処理方法をFIFOと呼ぶこともある。
コンピュータ
データ構造
FIFO (queue) のキューのイメージ
キューに格納されたデータの処理方法のひとつである。キュー上の各要素はキューのデータ構造内に格納される。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の状態を表し、いっぱいになっているとか、もうすぐいっぱいになるとか、ほとんど空だとかいうことを示す。空きが設定した容量以下・以上になったら割込み を起こすよう設定できるものも多い。
関連項目