FIFO

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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と呼ばれることがある。

デジタル回路[編集]

FIFOはデジタル回路でバッファリングとフロー制御を行うものである。 FIFOはリードポインタとライトポインタ、格納場所と制御ロジックからなる。 格納場所としてはSRAM、フリップフロップ、ラッチなどが考えられる。 重要な役割を果たしているFIFOとしては、デュアルポートSRAMが上げられ、一方のポートがライトに使われ、もう一方がリードに使われる。

同期型FIFOはリードとライトに同じクロックを使用するものである。非同期型FIFOは異なったクロックを使用する。 非同期型FIFOは準安定性問題をはらんでいる。 非同期型FIFOの一般的な実装ではグレイコードを使ってリードとライトのポインタを構成し、安定したフラグ生成ができるようにしている。

FIFOは様々なフラグを発生する可能性がある。フラグはFIFOの状態を表し、いっぱいになっているとか、もうすぐいっぱいになるとか、ほとんど空だとかいうことを示す。

会計学[編集]

原価計算の方法にも同様に、先入先出法 (FIFO) と後入先出法 (LIFO) がある。

関連項目[編集]