FIFOとは？仕組み・実装（リングバッファ／連結リスト／ロックフリー）と応用・性能の注意点
エバープレイ編集部FIFO とは — 概要
FIFO（First-In, First-Out）は「先入れ先出し」の原則を意味し、最初に入ったデータが最初に出ていくという振る舞いを持つデータ構造・キューイング方式を指します。IT分野では抽象データ型としてのキュー、OSの名前付きパイプ（FIFO特殊ファイル）、ネットワークやストレージのバッファリング、ハードウェアのFIFO回路など、さまざまな文脈で用いられます。
基本概念と直感
順序性：要素は入った順序を保ち、取り出しは入った順序の逆にはなりません（LIFO＝スタックとは対照的）。
代表的操作：enqueue（挿入）、dequeue（取り出し）、peek（先頭参照）、isEmpty/isFull（空/満杯判定）など。
応用分野：ジョブスケジューリング、タスクキュー、メッセージキュー、ネットワークパケットバッファ、プロセス間通信（パイプ）など。
データ構造としての実装
プログラミング上は主に以下のような実装方法があります。
配列ベース（循環バッファ／リングバッファ）：固定長の配列に head/tail インデックスを持ち、モジュロ演算で回す手法。メモリ効率が高くキャッシュにも優れる。空と満杯の判定で「1スロット分空けておく」か要素数を別途保持する必要がある。
連結リストベース：可変長で動的割当が可能。enqueue/dequeue が O(1) で実装しやすいが、割当/解放コストや断片化を考慮する必要がある。
可変長配列（循環＋自動拡張）：容量を超えたら再割当してコピーする方式で、動的な負荷に対応できるが再割当時のコストが発生する。
アルゴリズム的性質と計算量
基本操作の時間計算量はほとんどの場合 O(1)（定数時間）です。配列循環バッファ、連結リストのいずれも、enqueue/dequeue は頭と尾の更新で済みます。メモリやキャッシュの観点では配列ベースの方が有利な場合が多いです。
OS・ファイルシステムにおける FIFO（名前付きパイプ）
UNIX系では FIFO は「名前付きパイプ（named pipe）」とも呼ばれ、ファイルシステム上の特殊ファイルとして実装されます（mkfifo コマンド）。プロセス間通信（IPC）で一方が書き込み、他方が読み出す際に順序を保証する手段として使われます。ブロッキング・ノンブロッキングの振る舞いやパーミッション（ファイルモード）による制御が可能です。
ネットワークとキューイング理論
ネットワークスイッチやルータ、ソケット層では FIFO キューは最も単純なキューイング方式の一つです。FIFO は実装が簡単で公平に見えますが、問題点もあります。
ヘッドオブライン（Head-of-Line）ブロッキング：先頭パケット/メッセージが遅延すると後続が全て滞る。
バッファブロートル：過大なバッファを持つと遅延が増え、ネットワーク性能を悪化させる（バッファブロートル問題）。
スケジューリングとの連携：FIFO は単純な公平性を提供するが、優先度やQoSを要する場合は優先キューや複合スケジューラが必要。
ハードウェアでの FIFO 実装
FPGA・ASIC やシリアル接続回路では、ハードウェアFIFO（シフトレジスタやメモリベースのリングバッファ）がよく使われます。クロックドメインをまたぐ通信（クロックドメインクロッシング）ではサイドバンドの同期回路やメタスタビリティ対策を組み合わせた FIFO が不可欠です。ハードウェアFIFO の深さ（depth）はスループットと遅延、回復時間（backpressure）設計に直接影響します。
同時実行性（Concurrency）とスレッドセーフな FIFO
マルチスレッド／マルチプロセス環境では同時に複数プロデューサ／コンシューマがアクセスすることが多く、単純な実装は競合状態（race）を引き起こします。対処法は主に次のとおりです。
ロックを用いる（ミューテックス／スピンロック）：実装が簡単だが、ロック競合による待ち時間が発生する。
待機フリー／ノンブロッキング（lock-free）アルゴリズム：CAS（Compare-And-Swap）やメモリバリアを用いる手法。代表的な例に Michael & Scott のロックフリーキューがある。
スリムな設計：単一プロデューサ・単一コンシューマ（SPSC）向けのリングバッファは特別簡潔かつ高速で、メモリバリアを最小化できる。
性能上の注意点・落とし穴
容量設計：過小だとドロップやスロットリング、過大だと遅延増加（バッファブロートル）。
優先度の欠如：すべてを同列に扱うため、重要なタスクが遅れる可能性。
ヘッドオブライン問題：設計段階で回避策（複数キュー、優先キュー、フェアキューイングなど）を検討する。
フロー制御との連携：プロデューサとコンシューマの速度差に応じたバックプレッシャ（書き込み停止や遅延）を実装する必要がある。
実用的な用途と事例
OS・シェルのパイプ：プロセス間でストリームを順序通り受け渡す。
メッセージキュー：分散システムやマイクロサービスでの非同期処理（RabbitMQ や Kafka の内部でも順序保証の考慮が重要）。
ネットワークバッファ：受信／送信におけるパケットキュー。
リアルタイムデータ処理：オーディオ／ビデオのストリーミングで順序とレイテンシを管理する。
ハードウェア回路：シリアルI/O、DMAバッファ、FPGA間のデータ受け渡し。
設計時のチェックリスト
要件：順序性の保証、スループット、許容遅延を明確にする。
容量：ピーク負荷を想定して深さを決定（動的拡張が必要か）。
同時実行性：プロデューサ／コンシューマの数に応じた安全策（ロック/ロックフリー/SPSC）を選択。
障害時の挙動：溢れたときにドロップするかブロックさせるか、ログやメトリクスをどう取るか。
監視とチューニング：遅延、ドロップ率、キュー長のモニタリング。
まとめ
FIFO は単純ながら多用途で、正しく理解・設計すればシステム全体の信頼性・性能に大きく貢献します。一方で、容量設計や同時実行性、ヘッドオブライン問題、バッファブロートルなどの落とし穴を見落とすと性能劣化や予期せぬ遅延を招きます。用途に応じて配列ベースのリングバッファや連結リスト、ロック／ロックフリー実装、あるいは複数キューや優先度付きキューなどの代替を検討してください。
参考文献
投稿者プロフィール
