First-Come, First-Served

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

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

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

С развитием промышленной революции и появлением массового производства принцип FCFS стал стандартом для организации поточных линий и обслуживания клиентов. В 1950-х годах, с возникновением теории массового обслуживания (теории очередей), FCFS был формализован как математическая модель. В вычислительной технике алгоритм FCFS впервые был реализован в ранних операционных системах (например, в IBM OS/360) для управления очередями задач и доступа к процессору.

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

Основные правила

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

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

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

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

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

В ранних операционных системах (например, в MS-DOS, ранних версиях UNIX) планировщик задач использовал алгоритм FCFS (также известный как FIFO — First In, First Out). Процессы помещались в очередь готовности и выполнялись строго по порядку поступления. Недостатком такого подхода является так называемый «эффект конвоя»: длительный процесс задерживает выполнение всех последующих коротких процессов, что приводит к значительному увеличению среднего времени ожидания. В современных операционных системах (Windows, Linux, macOS) FCFS используется редко как основной алгоритм, но применяется в комбинации с другими дисциплинами (например, в алгоритме Round Robin или в планировщиках ввода-вывода).

В сетевых протоколах

В компьютерных сетях FCFS применяется в коммутаторах и маршрутизаторах для организации очередей пакетов. Например, в технологии Ethernet коммутаторы используют FIFO-буферы для хранения кадров, ожидающих передачи. В протоколах транспортного уровня (TCP) FCFS используется для управления очередями сегментов на стороне получателя. В сетях с коммутацией пакетов FCFS может приводить к задержкам для пакетов с высокой приоритетностью, поэтому часто применяются более сложные алгоритмы (например, Weighted Fair Queuing).

В логистике и обслуживании

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

В производственных системах

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

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

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

Простота реализации: Алгоритм не требует сложных вычислений или хранения информации о приоритетах.
Справедливость по времени: Каждый запрос гарантированно будет обслужен, и порядок обслуживания предсказуем.
Отсутствие голодания: Ни один запрос не может быть бесконечно отложен, так как очередь продвигается строго последовательно.
Низкие накладные расходы: Не требуется дополнительных ресурсов для сортировки или перестановки запросов.

Недостатки

Эффект конвоя: Длительный запрос блокирует выполнение всех последующих, что резко увеличивает среднее время ожидания для коротких запросов.
Неоптимальное использование ресурсов: В системах с переменной нагрузкой FCFS может приводить к простою ресурсов, если в очереди нет запросов, а затем к перегрузке при поступлении большого числа запросов.
Отсутствие приоритизации: Все запросы считаются равнозначными, что неэффективно в системах, где некоторые задачи требуют срочного выполнения.
Чувствительность к времени обслуживания: Среднее время ожидания сильно зависит от дисперсии времени обслуживания; при большом разбросе эффективность падает.

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

Дисциплина	Принцип	Преимущества	Недостатки
FCFS (FIFO)	Первым пришёл — первым обслужен	Простота, справедливость	Эффект конвоя
SJF (Shortest Job First)	Сначала короткие задачи	Минимальное среднее время ожидания	Возможно голодание длинных задач
Round Robin	Квант времени по кругу	Равномерное распределение процессорного времени	Накладные расходы на переключение контекста
Priority Scheduling	По приоритету	Гибкость, реакция на срочные задачи	Возможно голодание низкоприоритетных задач
LCFS (LIFO)	Последним пришёл — первым обслужен	Минимальное время ожидания для последних	Непредсказуемость, возможен «эффект новизны»

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

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

Источники

Клейнрок Л. Теория массового обслуживания. — М.: Машиностроение, 1979.
Таненбаум Э., Бос Х. Современные операционные системы. — 4-е изд. — СПб.: Питер, 2015.
Столлингс У. Операционные системы. — 6-е изд. — М.: Вильямс, 2007.
Кузнецов А. В., Холод Н. И. Теория массового обслуживания. — М.: Высшая школа, 2008.
Harchol-Balter M. Performance Modeling and Design of Computer Systems: Queueing Theory in Action. — Cambridge University Press, 2013.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →