FIFO-буфер

FIFO-буфер (от англ. First In, First Out — «первым пришёл — первым ушёл») — это способ организации данных в компьютерной памяти, при котором элементы обрабатываются в порядке их поступления. В контексте аппаратного и программного обеспечения FIFO-буфером называют структуру данных (очередь), реализующую этот принцип, или специализированное устройство (например, регистр сдвига), обеспечивающее временное хранение и последовательную передачу данных. Основное свойство FIFO: первый записанный элемент извлекается первым, а последний — последним.

Принцип работы

FIFO-буфер функционирует как односторонняя очередь. Данные записываются на один конец (вход) и считываются с другого (выход). Операции записи и чтения могут выполняться асинхронно, с разными тактовыми частотами, что делает FIFO незаменимым для согласования потоков данных между устройствами с разной скоростью работы.

В простейшем случае FIFO реализуется с помощью двух указателей: указателя записи (write pointer) и указателя чтения (read pointer). При записи данные помещаются в ячейку памяти по адресу, на который указывает указатель записи, после чего указатель инкрементируется. При чтении данные извлекаются из ячейки по адресу указателя чтения, и он также инкрементируется. Когда указатели равны, буфер считается пустым. Если указатель записи «догоняет» указатель чтения (с учётом циклической адресации), буфер считается полным.

Синхронные и асинхронные FIFO

• Синхронный FIFO — все операции (запись и чтение) выполняются по одному тактовому сигналу. Используется, когда источник и приёмник данных работают на одной частоте.
• Асинхронный FIFO — запись и чтение управляются разными тактовыми сигналами. Применяется для передачи данных между двумя независимыми тактовыми доменами, например, между процессором и периферийным устройством.

Виды и реализации

Аппаратные FIFO

Аппаратные FIFO реализуются на уровне цифровых микросхем, программируемых логических интегральных схем (ПЛИС) или в составе специализированных контроллеров. Они представляют собой массивы регистров или ячеек памяти (SRAM), управляемые логикой формирования указателей и сигналов состояния (пусто, полно, почти пусто, почти полно). Аппаратные FIFO широко применяются в:

• Последовательных интерфейсах (UART, SPI, I²C) — для буферизации принимаемых или передаваемых байтов, чтобы процессор мог обрабатывать данные блоками, а не прерываться на каждый байт.
• Цифровой обработке сигналов — для согласования потоков данных между АЦП, ЦАП и процессорами.
• Сетевых коммутаторах и маршрутизаторах — для временного хранения пакетов при перегрузках.
• Графических процессорах — для организации конвейеров команд и данных.

Программные FIFO

В программном обеспечении FIFO-буфер реализуется как очередь (queue) — структура данных, поддерживающая операции enqueue (добавление в конец) и dequeue (извлечение из начала). Типичные реализации:

• Кольцевой буфер (circular buffer) — массив фиксированного размера, в котором указатели записи и чтения циклически перемещаются. Эффективен для встраиваемых систем и драйверов.
• Динамическая очередь — на основе связных списков, позволяет изменять размер буфера во время выполнения, но требует динамического выделения памяти.
• Очередь на основе массива с фиксированным размером — простая реализация для систем с предсказуемыми нагрузками.

В операционных системах FIFO-буферы используются для:

• Межпроцессного взаимодействия (IPC) — очереди сообщений, каналы (pipes).
• Буферизации ввода-вывода — драйверы клавиатуры, мыши, сетевых карт.
• Планирования задач — очереди готовых к выполнению процессов.

Характеристики и параметры

Ключевые параметры FIFO-буфера:

Применение

Согласование скоростей передачи данных

FIFO-буфер позволяет сгладить неравномерность поступления данных. Например, при передаче данных с АЦП, работающего на частоте 100 МГц, в память с шиной 50 МГц, FIFO накапливает выборки и выдаёт их пачками, синхронизированными с более медленной шиной.

Буферизация в последовательных интерфейсах

В микроконтроллерах FIFO-буферы встроены в модули UART (например, в STM32 — до 16 байт), SPI и I²C. Это снижает нагрузку на центральный процессор: вместо обработки каждого байта по прерыванию, процессор может дождаться заполнения буфера и обработать блок данных за одно прерывание.

Реализация очередей в программном обеспечении

В многопоточных приложениях FIFO-буферы обеспечивают потокобезопасную передачу данных между потоками. Например, в веб-серверах запросы от клиентов помещаются в очередь и обрабатываются рабочими потоками в порядке поступления.

Цифровая обработка сигналов

В фильтрах с конечной импульсной характеристикой (КИХ-фильтрах) FIFO используется для хранения отсчётов сигнала, которые затем умножаются на коэффициенты фильтра. Глубина буфера определяет порядок фильтра.

Преимущества и недостатки

Преимущества

• Простота реализации и предсказуемость поведения.
• Гарантированный порядок обработки данных.
• Эффективное использование памяти (особенно в кольцевых буферах).
• Возможность работы с разными тактовыми частотами (асинхронные FIFO).

Недостатки

• Фиксированный размер буфера (при переполнении данные теряются, если не реализована защита).
• Задержка на запись/чтение (обычно 1-2 такта).
• Сложность управления флагами состояния в асинхронных FIFO (требуется синхронизация указателей между тактовыми доменами).

Примеры использования

• UART 16550 — стандартный контроллер последовательного порта в IBM PC-совместимых компьютерах, оснащён FIFO-буфером на 16 байт. Позволяет снизить частоту прерываний при обмене данными.
• ПЛИС Xilinx — в составе IP-ядер (например, FIFO Generator) предоставляются настраиваемые синхронные и асинхронные FIFO с глубиной до нескольких мегабайт.
• Linux kernel — реализация кольцевого буфера для драйверов (struct kfifo) используется для буферизации данных от устройств ввода, сетевых пакетов и сообщений от датчиков.
• Язык Verilog — описание асинхронного FIFO является классической задачей для проектирования цифровых схем, часто используется в учебных курсах по ПЛИС.

См. также

• Очередь (структура данных)
• Кольцевой буфер
• LIFO (Last In, First Out) — стек
• Буфер (информатика)

Источники

• Харрис Д., Харрис С. «Цифровая схемотехника и архитектура компьютера» (глава «Последовательные логические схемы»).
• Таненбаум Э., Остин Т. «Архитектура компьютера» (раздел «Организация памяти и ввода-вывода»).
• Спецификация UART 16550 (National Semiconductor, 1995).
• Документация Xilinx: «LogiCORE IP FIFO Generator v13.2» (2017).
• Исходный код ядра Linux: drivers/base/fifo.c, include/linux/kfifo.h.