FIFO — буфер обмена данными¶
FIFO (англ. First In, First Out — «первый вошёл, первый вышел») — принцип организации очереди данных, при котором элемент, поступивший в очередь первым, извлекается из неё также первым. Термин применяется в информатике, электронике, телекоммуникации и автоматизации, обозначая как сам принцип, так и реализующие его структуры данных и аппаратные устройства — буферы, очереди, регистры.
¶Основной принцип
FIFO-очередь работает по принципу линейного буфера: данные записываются в один конец («хвост» очереди) и считываются с другого («голова»). Порядок элементов при этом сохраняется. Операция записи называется enqueue, операция чтения — dequeue. В отличие от стека (LIFO — Last In, First Out), где последний добавленный элемент извлекается первым, FIFO гарантирует строгую последовательность обработки.
Типичная реализация в программировании — кольцевой буфер (ring buffer) на массиве с двумя индексами: на запись и на чтение. Такая структура позволяет работать с фиксированным объёмом памяти без сдвига элементов.
¶Применение в программировании
FIFO-очереди используются повсеместно:
- Планирование задач — операционные системы распределяют процессорное время по алгоритму FCFS (First Come, First Served), являющемуся FIFO-очередью.
- Сетевые буферы — пакеты, пришедшие на сетевой интерфейс, обрабатываются в порядке поступления.
- Очереди сообщений — системы вроде Apache Kafka, RabbitMQ и Redis Streams построены на FIFO-принципе.
- Обход графов и деревьев — алгоритм поиска в ширину (BFS) использует FIFO-очередь.
- Потоки данных — буферы ввода-вывода, конвейеры (pipes) в Unix-системах.
В языках программирования FIFO-очереди реализуются стандартными библиотеками: collections.deque в Python, std::queue в C++, Queue в Java и Go.
¶Аппаратная реализация
¶FIFO-буферы в цифровой электронике
В цифровой электронике FIFO-буферы (FIFO buffers) — это специализированные микросхемы или блоки в программируемых логических матрицах (ПЛИС/FPGA), обеспечивающие синхронизацию потоков данных с разной частотой. Классическая задача — соединение двух устройств, работающих на разных тактовых частотах (CDC, clock domain crossing).
Типичные параметры аппаратного FIFO-буфера:
| Параметр | Описание |
|---|---|
| Глубина | Количество хранимых слов (от единиц до тысяч) |
| Ширина слова | 1–64 бит и более |
| Тип | Синхронный или асинхронный (двухтактовый) |
| Управление | Сигналы full, empty, read enable, write enable |
Асинхронные FIFO используются для передачи данных между доменами тактовой частоты и построены на указателях с кодом Грея, что исключает сбои при одновременном изменении нескольких бит.
¶FIFO в микроконтроллерах и периферии
Многие микроконтроллеры (STM32, AVR, MSP430) содержат аппаратные UART-, SPI- и USB-FIFO-буферы, снижающие нагрузку на процессор при обмене данными. В промышленной автоматизации FIFO-буферы применяются в контроллерах ПЛК для обмена данными между шинами с разной скоростью.
¶FIFO в телекоммуникациях
В сетях передачи данных FIFO-принцип лежит в основе управления очередями в маршрутизаторах и коммутаторах. При переполнении буфера применяются политики управления перегрузкой: Tail Drop (отбрасывание последних пакетов), RED (Random Early Detection), WRED (с дифференциацием по классам обслуживания). В сетях с гарантированным качеством обслуживания FIFO-очередь часто заменяется на приоритетную или WFQ.
¶Ограничения
FIFO-очередь не учитывает приоритеты: элемент, находящийся в начале очереди, будет обслужен независимо от его срочности. Это может приводить к эффекту «головной блокировки» (head-of-line blocking), когда один медленный элемент задерживает обработку остальных. Для решения этих задач используются приоритетные очереди, многоуровневые очереди (MLQ) и алгоритмы взвешенного кругового обслуживания (WRR, WFQ).
¶См. также
- LIFO (стек)
- Кольцевой буфер
- Очередь сообщений
- Алгоритм поиска в ширину
¶Источники
- Кнут Д. «Искусство программирования», том 1: основные алгоритмы
- Таненбаум Э. «Современные операционные системы»
- Хоровиц С., Сахни С. «Основы алгоритмов на C++»
- Документация Apache Kafka, Redis Streams
- Спецификации IEEE для асинхронных FIFO-буферов
