Первый пришёл — первый обслужен¶

FIFO (от англ. First In, First Out — «первым пришёл — первым обслужен») — метод организации и обработки очереди, при котором запросы, задачи или данные, поступившие раньше других, обрабатываются в первую очередь. Принцип FIFO является одним из фундаментальных в информатике, логистике, управлении запасами и теории массового обслуживания. Противоположным методом является LIFO (Last In, First Out — «последним пришёл — первым обслужен»).

¶История

Понятие очереди и принципа обслуживания в порядке поступления существовало задолго до появления вычислительной техники. В бытовой практике (например, в магазинах, банках, на почте) этот порядок сложился естественным образом как наиболее справедливый и интуитивно понятный. В математике и теории вероятностей формальное описание систем массового обслуживания (СМО) с дисциплиной FIFO начало развиваться в начале XX века, в первую очередь в работах датского инженера Агнера Эрланга (1910-е годы), который исследовал телефонные станции. Эрланг показал, что для минимизации времени ожидания при случайном потоке вызовов оптимальным является обслуживание в порядке поступления.

В вычислительной технике принцип FIFO стал применяться с появлением первых компьютеров. В 1950-х годах для организации буферов данных и очередей задач использовались последовательные структуры, реализующие этот порядок. Термин «FIFO» как аббревиатура вошёл в широкое употребление в 1960–1970-х годах вместе с развитием операционных систем и языков программирования.

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

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

• enqueue (push) — добавление элемента в конец очереди;
• dequeue (pop) — извлечение элемента из начала очереди.

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

¶Применение

¶Информатика и вычислительная техника

• Очереди задач в операционных системах — планировщики процессов часто используют FIFO для обслуживания фоновых задач или задач с одинаковым приоритетом.
• Буферизация данных — в сетевых протоколах (например, Ethernet, USB) FIFO-буферы используются для временного хранения пакетов при неравномерной скорости передачи.
• Аппаратные FIFO — в микроконтроллерах и цифровых сигнальных процессорах (DSP) для синхронизации потоков данных между разными тактовыми частотами.
• Обработка запросов — в веб-серверах и базах данных для организации очередей HTTP-запросов или транзакций.

¶Логистика и управление запасами

Метод FIFO является стандартом в управлении складскими запасами, особенно для товаров с ограниченным сроком годности (продукты питания, медикаменты, химические реактивы). Согласно этому методу, первая поступившая партия товара должна быть отгружена первой. Это позволяет минимизировать потери от порчи и устаревания. В бухгалтерском учёте метод FIFO используется для оценки себестоимости запасов: при выбытии товаров их стоимость списывается по цене наиболее ранних по времени закупок.

¶Теория массового обслуживания

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

¶Производство и управление цепочками поставок

В производственных системах (например, на конвейерах) FIFO используется для организации движения деталей между операциями. Это упрощает контроль за незавершённым производством и предотвращает «заторы» на ранних этапах.

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

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

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

¶Недостатки

• Отсутствие приоритетов — все заявки обрабатываются одинаково, что может быть неэффективно, если среди них есть срочные (например, сигнал аварии в системе управления).
• Чувствительность к «длинным» задачам — если одна заявка требует длительного времени обработки, все последующие задерживаются (эффект «головы очереди»).
• Неоптимальность для переменной нагрузки — при резких всплесках поступления заявок очередь может расти неограниченно, если скорость обработки ниже скорости поступления.

¶Сравнение с другими дисциплинами

¶Интересные факты

• В операционных системах семейства UNIX команда fifo (или mkfifo) создаёт именованный канал (named pipe), который работает по принципу FIFO.
• В микросхемах FIFO часто используются флаги «почти пусто» и «почти полно» для управления потоком данных.
• В бухгалтерском учёте метод FIFO в России регулируется Положением по бухгалтерскому учёту «Учёт материально-производственных запасов» (ПБУ 5/01).
• В теории очередей доказано, что для пуассоновского потока заявок и экспоненциального времени обслуживания система M/M/1 с дисциплиной FIFO является марковским процессом с аналитически решаемыми уравнениями.

¶Критика

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

¶Источники

• Клейнрок Л. Теория массового обслуживания. — М.: Машиностроение, 1979.
• Таненбаум Э., Бос Х. Современные операционные системы. — 4-е изд. — СПб.: Питер, 2015.
• Положение по бухгалтерскому учёту «Учёт материально-производственных запасов» (ПБУ 5/01), утверждённое Приказом Минфина РФ от 09.06.2001 № 44н.
• Stallings W. Operating Systems: Internals and Design Principles. — 9th ed. — Pearson, 2018.
• Эрланг А. К. Теория вероятностей и телефонные сообщения. — 1909.