Принцип first come first served

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

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

Принцип FCFS имеет глубокие исторические корни и восходит к практикам организации очередей в обществе. В древних цивилизациях, например в Древнем Риме и Греции, при распределении воды из общественных фонтанов или при записи на приём к государственным чиновникам использовался порядок, основанный на времени прибытия. В Средние века этот принцип применялся в гильдиях и ремесленных цехах для определения очерёдности выполнения заказов.

В современном виде термин «first come, first served» закрепился в англоязычной правовой и административной практике. В США, например, он используется в законодательстве о регистрации земельных участков (принцип «первого во времени — первого по праву»). В вычислительную технику концепция FCFS перешла в середине XX века с развитием первых операционных систем, где требовалось управлять потоками задач на однопроцессорных машинах.

Применение в вычислительной технике

Планирование процессов в операционных системах

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

Достоинства:

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

Недостатки:

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

Диспетчеризация задач в пакетных системах

В ранних пакетных системах (например, IBM OS/360) FCFS использовался для управления очередями заданий на выполнение. Задания сортировались по времени поступления и выполнялись последовательно. С развитием многозадачности этот алгоритм был вытеснен более эффективными методами (например, Shortest Job First, Round Robin), но до сих пор применяется в простых встраиваемых системах и в качестве базового алгоритма в учебных целях.

Применение в обслуживании клиентов и логистике

Очереди в сфере услуг

Принцип FCFS широко используется в розничной торговле, банковском деле, здравоохранении и других сферах обслуживания. Клиенты обслуживаются в порядке поступления в очередь, что воспринимается как справедливый и прозрачный механизм. В современных системах управления очередями (например, в отделениях Сбербанка или МФЦ) часто применяются электронные талоны, реализующие FCFS с учётом приоритетов (например, для льготных категорий граждан).

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

На складах и в распределительных центрах FCFS используется для управления отгрузкой товаров. Принцип «первый пришёл — первый ушёл» (FIFO) применяется для товаров с ограниченным сроком годности (продукты питания, медикаменты), чтобы минимизировать потери от порчи. В отличие от LIFO (последний пришёл — первый ушёл), FIFO обеспечивает естественное старение запасов.

Применение в информационных системах и сетях

Обработка запросов на веб-серверах

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

Сетевые протоколы

В некоторых сетевых протоколах, таких как Ethernet (CSMA/CD), принцип FCFS реализуется через механизм случайной задержки при обнаружении коллизий. Узел, первым начавший передачу, получает доступ к среде, а остальные ждут. В более современных протоколах (например, в коммутации пакетов) FCFS используется как один из вариантов обслуживания очередей на маршрутизаторах.

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

В теории массового обслуживания (теории очередей) FCFS является одной из базовых дисциплин обслуживания. Для системы M/M/1 (пуассоновский поток заявок, экспоненциальное время обслуживания, один сервер) с дисциплиной FCFS среднее время ожидания в очереди вычисляется по формуле:

\[ W_q = \frac{\lambda}{\mu(\mu - \lambda)} \]

где \(\lambda\) — интенсивность поступления заявок, \(\mu\) — интенсивность обслуживания. Эта модель демонстрирует, что при приближении загрузки системы к единице время ожидания неограниченно возрастает, что является недостатком FCFS в условиях высокой нагрузки.

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

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

Альтернативными дисциплинами являются:

• Shortest Job First (SJF) — обслуживание задач с наименьшим временем выполнения.
• Priority Scheduling — обслуживание с учётом приоритетов.
• Round Robin — циклическое обслуживание с квантом времени.
• Earliest Deadline First (EDF) — обслуживание по ближайшему сроку выполнения (используется в системах реального времени).

Примеры в повседневной жизни

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

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

• В некоторых культурах (например, в Японии) принцип FCFS воспринимается как фундаментальная норма социальной справедливости, и его нарушение (например, «внеочередное» обслуживание) вызывает сильное неодобрение.
• В операционных системах семейства UNIX алгоритм FCFS используется как часть планировщика задач в режиме реального времени (SCHED_FIFO), где процессы выполняются до их блокировки или добровольного отказа от ЦП.
• В теории игр FCFS рассматривается как механизм, минимизирующий конфликты при распределении ограниченных ресурсов, но не гарантирующий оптимального результата с точки зрения общей полезности.

Источники

• Таненбаум Э., Бос Х. Современные операционные системы. — 4-е изд. — СПб.: Питер, 2015. — 1120 с.
• Клейнрок Л. Теория массового обслуживания. — М.: Машиностроение, 1979. — 432 с.
• Столлингс У. Операционные системы: внутренняя структура и принципы проектирования. — 9-е изд. — М.: Вильямс, 2018. — 848 с.
• ГОСТ Р ИСО 9000-2015. Системы менеджмента качества. Основные положения и словарь. — М.: Стандартинформ, 2015.
• Harchol-Balter M. Performance Modeling and Design of Computer Systems: Queueing Theory in Action. — Cambridge University Press, 2013. — 576 p.