FIFO — принцип организации очередей данных¶
FIFO (от англ. First In, First Out — «первый вошёл, первый вышел») — принцип организации очередей данных, при котором элемент, помещённый в очередь первым, извлекается из неё также первым. Противоположный принцип — LIFO (Last In, First Out, «последний вошёл, последний вышел»), реализуемый стеком. Термин FIFO широко применяется в информатике, электронике, телекоммуникациях и теории очередей.
¶Основные сведения
FIFO описывает упорядоченную структуру данных, доступ к которой осуществляется с двух концов: запись производится в один конец («хвост»), чтение — из другого («голова»). Такая структура гарантирует сохранение порядка поступления элементов. Операции над очередью FIFO:
- enqueue (постановка в очередь) — добавление элемента в хвост;
- dequeue (извлечение из очереди) — удаление элемента из головы;
- peek / front — просмотр элемента в голове без его удаления;
- isEmpty / isFull — проверка на пустоту или заполненность.
Простейшая реализация очереди FIFO на массиве требует сдвига всех элементов при каждом dequeue, что даёт сложность O(n). На связном списке операции enqueue и dequeue выполняются за O(1), однако требуют дополнительной памяти под хранение ссылок. Кольцевой буфер (циклический буфер) позволяет реализовать очередь FIFO на массиве с операциями O(1), используя два индекса — на голову и хвост.
¶Реализации в программировании
В стандартных библиотеках языков программирования FIFO-очереди реализованы в виде отдельных структур данных:
| Язык | Структура | Примечание |
|---|---|---|
| C++ | std::queue, std::deque | Контейнер адаптер по умолчанию на std::deque |
| Java | Queue, ArrayDeque, LinkedList | Интерфейс Queue с реализациями |
| Python | collections.deque | Двусторонняя очередь, O(1) на обоих концах |
| C# | Queue<T> | Очередь на массиве с циклической адресацией |
| Go | пакет container/list | Связный список, используется как очередь |
В однопоточных программах FIFO-очереди применяются для обработки задач в порядке поступления: планировщики задач, очереди печати, буферы ввода-вывода. В многопоточных системах используются потокобезопасные очереди (например, BlockingQueue в Java, queue.Queue в Python), обеспечивающие синхронизацию доступа.
¶Применение в операционных системах
В операционных системах принцип FIFO лежит в основе планирования процессов. Планировщик с дисциплиной FIFO размещает готовые к выполнению процессы в очередь, и процессор выделяется процессу, находящемуся в очереди дольше остальных. Такой подход называется FCFS (First Come, First Served — «первый пришёл, первый обслужен»). Простота алгоритма сочетается с недостатком, известным как «эффект необслуживаемого процессора» (convoy effect): короткие задачи ожидают завершения длинных, что увеличивает среднее время ожидания.
FIFO также применяется в файловых системах при выделении инодов и блоков данных, в драйверах устройств для упорядочивания запросов на запись и чтение, в сетевых подсистемах для обработки пакетов.
¶FIFO в электронике и телекоммуникациях
В цифровой электронике FIFO-буферы (FIFO-память) используются для синхронизации потоков данных между устройствами с разной тактовой частотой или разной шириной шины данных. Классический пример — буфер между контроллером USB и периферийным устройством. FIFO-буферы реализуются на специализированных микросхемах (например, сериях 74HC, IDT) или на FPGA с помощью блоков памяти.
В телекоммуникациях FIFO применяется в коммутаторах и маршрутизаторах при формировании очередей на передачу пакетов. Дисциплина FIFO в очередях передачи данных является одной из базовых в теории массового обслуживания, наряду с LIFO, приоритетными и взвешенными дисциплинами.
¶Ограничения
Прямолинейная реализация FIFO имеет ряд недостатков:
- отсутствие приоритетов — срочная задача не может быть обработана раньше давней;
- уязвимость к «затоплению» (flooding) — быстрое поступление элементов приводит к переполнению буфера;
- в сетевых системах FIFO-очереди подвержены эффекту хвостовой задержки (bufferbloat), когда буферы, заполненные до предела, увеличивают время прохождения пакетов.
Для устранения этих недостатков применяются приоритетные очереди, кольцевые буферы с ограничением размера и алгоритмы управления переполнением (RED, WRED).
¶См. также
- Стек (структура данных)
- Кольцевой буфер
- Планировщик процессов
- Теория массового обслуживания
¶Источники
- Кнут Д. «Структуры данных и их алгоритмы»
- Таненбаум Э. «Современные операционные системы»
- Корененко И. В. «Операционные системы»
- Стандарты IEEE по архитектуре FIFO-буферов