FIFO
出典: フリー百科事典『ウィキペディア（Wikipedia）』
FIFO(ファイフォ、フィフォ、フィーフォー)はFirst In, First Outを表す頭字語である。先入れ先出しと訳されることがある。 この言葉はキューの動作原理を表すものであり、最初に入ってきたものを最初に処理し、次に入ってきたものは最初の処理が終わるまで待たせる、ということを意味している。
優先順位付きキューはキューの一種であるが、FIFOと呼ぶのは適当でない。 というのは、FIFOという言葉ではこのデータ構造の動作を正確には表していないからである。 待ち行列理論は、より一般的なキューの概念を確立した理論であり、厳密なFIFOキューについても定義している。
FIFOは、いくつかの異なる文脈で用いられる。以下ではそれぞれを解説するが、これが全てではない。
目次 |
[編集] 情報工学
[編集] データ構造
情報工学では、キューに格納されたデータの処理方法を意味する。 キュー上の各要素はキューのデータ構造内に格納される。 最初に格納されたデータが(後で)最初に削除される。 処理は常にその順番で行われる。 これはキューの一般的な動作であるが、同じような一時格納をするデータ構造としてスタックまたは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) がある。
