First-Come First-Served

First-Come First-Served (FCFS, с англ. — «первым пришёл — первым обслужен») — это дисциплина обслуживания запросов (задач, процессов, клиентов), при которой порядок обработки определяется исключительно моментом поступления запроса. Запрос, поступивший раньше, начинает обслуживаться раньше, независимо от его приоритета, сложности или требуемого времени выполнения. FCFS является одной из базовых и наиболее интуитивно понятных дисциплин в теории массового обслуживания, операционных системах, компьютерных сетях и логистике.

История

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

С развитием вычислительной техники в середине XX века FCFS стал одной из первых дисциплин планирования процессов в операционных системах. В ранних системах, таких как IBM OS/360, использовались простейшие алгоритмы, близкие к FCFS, поскольку ресурсы были ограничены, а задачи — однородны. В 1960-х годах Дональд Кнут и другие исследователи формализовали FCFS как часть теории очередей, введя понятие «очередь FIFO» (First In, First Out) — синоним FCFS в контексте структур данных.

В настоящее время FCFS применяется в системах, где важна простота реализации и предсказуемость, но где не требуется дифференциация приоритетов. В России и странах постсоветского пространства FCFS часто реализуется в виде «живой очереди» в государственных учреждениях, банках и поликлиниках, а также в программных решениях для управления очередями.

Характеристики и принцип работы

FCFS является разновидностью невытесняющей дисциплины обслуживания. Это означает, что после начала обслуживания запроса он не может быть прерван и будет выполняться до полного завершения, даже если поступит более срочный или короткий запрос. В операционных системах это соответствует алгоритму планирования процессов FIFO (First In, First Out), где каждый процесс выполняется до завершения или до блокировки.

Основные свойства:

• Порядок обслуживания — строго по времени поступления. Запросы помещаются в очередь FIFO: первый добавленный элемент становится первым извлечённым.
• Невытесняемость — начатый запрос не прерывается.
• Отсутствие приоритетов — все запросы равны с точки зрения алгоритма.
• Справедливость — каждый запрос рано или поздно будет обслужен, если очередь не бесконечна.

Математическая модель

В теории массового обслуживания FCFS описывается моделью M/M/1 (пуассоновский входящий поток, экспоненциальное время обслуживания, один сервер) с дисциплиной FIFO. Среднее время ожидания в очереди \(W_q\) для такой модели вычисляется по формуле: \[ W_q = \frac{\lambda}{\mu(\mu - \lambda)} \] где \(\lambda\) — интенсивность поступления запросов, \(\mu\) — интенсивность обслуживания. При \(\lambda \ge \mu\) очередь растёт неограниченно.

Применение в различных областях

Операционные системы

В операционных системах FCFS (или FIFO) используется как один из простейших алгоритмов планирования процессов. Он применяется в пакетных системах, где задачи однородны и не требуют интерактивного взаимодействия. Например, в ранних версиях UNIX и в некоторых встраиваемых системах. Однако в современных ОС общего назначения (Windows, Linux, macOS) FCFS редко используется в чистом виде из-за проблем с «эффектом конвоя» (convoy effect), когда короткий процесс вынужден ждать завершения длительного.

Компьютерные сети

В сетевых протоколах FCFS реализуется в виде очередей FIFO на маршрутизаторах и коммутаторах. Пакеты, поступающие на интерфейс, обрабатываются в порядке поступления. Это простейший механизм, но он не обеспечивает качества обслуживания (QoS) — при перегрузке сети пакеты с высоким приоритетом могут задерживаться из-за потока низкоприоритетных данных.

Логистика и производство

В складских и производственных системах FCFS применяется при управлении запасами и обработке заказов. Например, на складах товары отгружаются в порядке поступления (FIFO — First In, First Out). Это позволяет избежать порчи скоропортящихся продуктов и упрощает учёт.

Государственные и коммерческие услуги

В учреждениях, работающих с большим потоком клиентов (банки, МФЦ, почта, поликлиники), FCFS реализуется через систему электронных очередей или «живую очередь». Клиент получает номер или талон, и обслуживание производится строго по порядку номеров. В России такая система регулируется, в частности, Федеральным законом «Об организации предоставления государственных и муниципальных услуг» (№ 210-ФЗ), который предписывает равный доступ к услугам.

Достоинства и недостатки

Достоинства

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

Недостатки

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

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

Критика и ограничения

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

В России и других странах FCFS в государственных услугах иногда критикуется за формализм: клиент, пришедший раньше, но с простым вопросом, вынужден ждать, пока обслужится клиент со сложной проблемой. Это приводит к раздражению и снижению удовлетворённости. Альтернативой может быть система с приоритетами (например, отдельные окна для срочных операций) или смешанные дисциплины.

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

• В некоторых культурах (например, в Великобритании) FCFS в виде «живой очереди» считается неотъемлемой частью национального этикета.
• В операционных системах FCFS часто используется как «эталонный» алгоритм для сравнения производительности других дисциплин.
• В теории очередей FCFS является единственной дисциплиной, которая гарантирует отсутствие голодания при любой нагрузке, если очередь не бесконечна.

Источники

• Таненбаум Э., Бос Х. «Современные операционные системы». — 4-е изд. — СПб.: Питер, 2015.
• Клейнрок Л. «Теория массового обслуживания». — М.: Машиностроение, 1979.
• Федеральный закон от 27.07.2010 № 210-ФЗ «Об организации предоставления государственных и муниципальных услуг».
• Stallings W. «Operating Systems: Internals and Design Principles». — 9th ed. — Pearson, 2017.
• Harchol-Balter M. «Performance Modeling and Design of Computer Systems». — Cambridge University Press, 2013.