Loading article…
コンピューティングやシステム理論において、先入れ先出し（ FIFO）とは、データ構造（多くの場合、特にデータバッファ）の操作を整理する方法であり、最も古い（最初の）エントリ、つまりキューの「先頭」が最初に処理される。
FIFOは、非常に幅広い用途で使用されています。用途に応じて、FIFOは電子論理回路としてハードウェアで実装される場合もあれば、ソフトウェアで実装される場合もあります。
FIFO は、さまざまなアプリケーションで広く使用されています。たとえば、ディスクコントローラは、ディスクI/O要求を処理する順序を決定するディスク スケジューリングアルゴリズムとして FIFO を使用します。 [ 1 ]コンピュータ ネットワークで使用される通信ネットワーク ブリッジ、スイッチ、ルータは、次の宛先への経路上のデータ パケットを保持するために FIFO を使用します。通常、ネットワーク接続ごとに少なくとも 1 つの FIFO が使用されます。[ 2 ] FIFO は、オペレーティングシステムのスケジューリングで使用され、要求された順序で各プロセスの中央処理装置(CPU) に時間を与えます。 [ 1 ] FIFO は、互換性のないデータ レートを持つソフトウェアまたはハードウェア (またはその両方) 間でストリーム データの交換を容易にするために、デジタル ビデオおよびオーディオ ストリームをバッファリングするために使用されます。
ソフトウェアFIFOは通常、循環バッファまたはリスト構造に基づいています。ほとんどのソフトウェア実装はスレッドセーフではないため、データ構造チェーンが一度に1つのスレッドによってのみ操作されるように、ロック機構が必要です。
プロセス間通信にパイプとフィルタのモデルをサポートするコンピューティング環境では、FIFOは名前付きパイプの別名です。
以下のコードは、連結リストFIFOのC++言語実装例を示しています。実際には、Unix系システムで広く使われているC言語のsys/queue.hマクロや、C++標準ライブラリのstd::listテンプレートなど、多くのリスト実装が存在し、データ構造を一から実装する必要がなくなります。
#include <memory> #include <stdexcept>using namespace std ;template < typename T > class FIFO { struct Node { T value ; shared_ptr < Node > next = nullptr ;ノード( T _value ) :値( _value ) {} };shared_ptr < Node > front = nullptr ; shared_ptr < Node > back = nullptr ;public : void enqueue ( T _value ) { if ( front == nullptr ) { front = make_shared <Node> ( _value ) ; back = front ; } else { back- > next = make_shared <Node> ( _value ) ; back = back- > next ; } }T dequeue () { if ( front == nullptr ) throw underflow_error ( "デキューするものがありません" );T value = front -> value ; front = move ( front -> next ); return value ; } };
電子式FIFOは、ハードウェアデバイス間、あるいは有限時間間隔で異なるデータレートで動作するソフトウェアデバイスとハードウェアデバイス間のバッファリングやフロー制御に一般的に使用されます。
FIFOは、メモリのアドレス読み出しレジスタと書き込みレジスタとして機能する2つのカウンタ、メモリ配列、およびステータス制御ロジックで構成されます。メモリは通常、FIFOの読み出しと書き込み操作を同時に行えるようにデュアルポート化されており、レジスタファイルまたはデュアルポートRAM（ランダムアクセスメモリ）で構成されます。