Дисциплина обслуживания FIFO

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

История и происхождение

Концепция FIFO возникла из практических потребностей управления очередями в повседневной жизни (например, в магазинах, на почте, в банках). Первое формальное описание принципа в контексте теории очередей (теории массового обслуживания) было дано в начале XX века датским математиком Агнером Крарупом Эрлангом, который в 1909 году опубликовал работу «Теория вероятностей и телефонные разговоры». Эрланг изучал телефонные станции и ввёл понятие дисциплины обслуживания, где вызовы обрабатывались в порядке поступления. Позднее, в 1950–1960-х годах, FIFO стало стандартной дисциплиной в операционных системах (как алгоритм планирования процессов) и в управлении запасами (как метод оценки себестоимости).

В СССР и России принцип FIFO активно применялся в плановой экономике для учёта товарно-материальных ценностей, а в 1990-х годах был закреплён в бухгалтерских стандартах.

Классификация и области применения

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

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

• Планирование процессов в операционных системах: алгоритм FIFO (FCFS — First-Come, First-Served) назначает процессору задачи в порядке их поступления. Это простейший невытесняющий алгоритм, при котором процесс, первым запросивший ресурс, получает его первым.
• Аппаратные буферы: FIFO-очереди реализуются в виде кольцевых буферов в микросхемах (например, в контроллерах прерываний, сетевых адаптерах, звуковых картах). Данные записываются и считываются строго по порядку.
• Кэширование: в кэш-памяти процессоров иногда используется политика FIFO для вытеснения старых строк.
• Сетевые протоколы: маршрутизаторы и коммутаторы могут использовать FIFO для обработки пакетов, хотя в современных сетях чаще применяются приоритетные очереди.

Логистика и складское хозяйство

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

Бухгалтерский учёт и финансы

• Оценка себестоимости запасов: в бухгалтерии метод FIFO (способ ФИФО) используется для расчёта стоимости списываемых материалов или товаров. При этом предполагается, что первыми списываются ценности, поступившие раньше всех. Этот метод разрешён Международными стандартами финансовой отчётности (МСФО) и Российскими стандартами бухгалтерского учёта (РСБУ). В России метод FIFO закреплён в Положении по бухгалтерскому учёту «Учёт материально-производственных запасов» (ПБУ 5/01).
• Учёт ценных бумаг: при продаже акций или облигаций FIFO позволяет определить, какие именно бумаги (по дате приобретения) были проданы, что влияет на расчёт налога на прибыль.

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

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

Устройство и реализация

Физически FIFO-очередь может быть реализована несколькими способами:

1. Линейный массив с двумя указателями (head — голова, tail — хвост). Элементы добавляются в конец (tail), а извлекаются из начала (head). При заполнении массива указатели циклически переходят на начало (кольцевой буфер).
2. Связанный список (односвязный или двусвязный). Каждый элемент содержит ссылку на следующий. Добавление и удаление выполняются за O(1).
3. Аппаратная реализация (в микросхемах) — регистры сдвига или специализированные FIFO-модули, работающие на тактовой частоте.

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

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

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

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

Недостатки:

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

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

FIFO часто противопоставляется другим дисциплинам обслуживания:

Примеры в реальной жизни

• Банк или почта: клиенты берут талон с номером и обслуживаются в порядке возрастания номеров (FIFO). Однако часто выделяются отдельные очереди для разных типов операций.
• Склад продуктов: товары с истекающим сроком годности размещаются на передних полках, чтобы их продали первыми (физическое FIFO).
• Бухгалтерия: при списании партии кирпича, поступившей в январе по цене 10 руб./шт., и партии, поступившей в феврале по цене 12 руб./шт., FIFO предпишет списать сначала январскую партию.
• Операционная система: в ранних версиях ОС (например, MS-DOS) планировщик задач работал по FIFO.

Критика и альтернативы

FIFO критикуется за неспособность учитывать приоритеты и динамику нагрузки. В современных вычислительных системах FIFO редко используется как единственный алгоритм планирования — его заменяют или дополняют приоритетными очередями, многоуровневыми очередями с обратной связью (MLFQ) или алгоритмом Round Robin. В логистике FIFO может быть неоптимальным, если товары имеют разную ценность или срок хранения — тогда применяется FEFO (First Expired, First Out — первым истекает срок годности, первым уходит). В бухгалтерии альтернативой FIFO является метод LIFO (запрещён в МСФО, но разрешён в некоторых странах, включая США до 2017 года) и метод средней себестоимости.

Источники

• Эрланг А. К. «Теория вероятностей и телефонные разговоры» (1909).
• Таненбаум Э., Бос Х. «Современные операционные системы» (4-е изд., 2015).
• Положение по бухгалтерскому учёту «Учёт материально-производственных запасов» ПБУ 5/01 (утв. Приказом Минфина РФ от 09.06.2001 № 44н).
• Клейнрок Л. «Теория массового обслуживания» (1975).
• Гмурман В. Е. «Теория вероятностей и математическая статистика» (2003).