Открыть сервисСервис

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-буферов
Заметили ошибку или не согласны с информацией в статье? Напишите нам support@bfometr.ru