FIFOのソースを表示

'''FIFO'''(ファイフォ、フィフォ、フィーフォー)は'''''F'''irst '''I'''n, '''F'''irst '''O'''ut''を表す[[頭字語]]である。先入れ先出しと訳されることがある。

この言葉は[[キュー (コンピュータ)|キュー]]の動作原理を表すものであり、キューに入っているどんな要素の組に対しても、先に入ったものを先に処理して出し、後に入ってきたものは先に入ったものより後から処理して出す、というように、出入りにおいて順序が保存されることを意味している（厳密には出入りのみを定義しており、処理順ではない）。日本語の俗な慣用表現では「[[ところてん]]式」も同じものを指す。

たとえば[[優先順位付きキュー]]はキューの一種であるが、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としては、デュアルポートSRAMがある。一方のポートがライトに使われ、もう一方がリードに使われる。

同期型FIFOはリードとライトに同じクロックを使用するものである。非同期型FIFOは異なったクロックを使用する。非同期型FIFOは[[準安定状態|準安定性]]問題をはらんでいる。非同期型FIFOでは書込み・読出しのポインタの番地変化にインクリメントではなく[[グレイコード]]を使い、安定した信号生成ができるようにする。

FIFOにはいくつかのフラグが付属する。フラグはFIFOの状態を表し、いっぱいになっているとか、もうすぐいっぱいになるとか、ほとんど空だとかいうことを示す。空きが設定した容量以下・以上になったら[[割り込み_(コンピュータ)|割込み]]を起こすよう設定できるものも多い。

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

== 関連項目 ==
* [[LIFO]]
* [[スタック]] (LIFO)
* [[パイプ (コンピュータ)|パイプ]]
* [[リングバッファ]]

[[Category:データ型]]
[[Category:デジタル回路]]