FCFS

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

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

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

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

История

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

С развитием интерактивных систем и многозадачности FCFS уступил место более сложным алгоритмам (например, Round Robin, SJF — Shortest Job First), однако остаётся важным эталонным методом для сравнения производительности планировщиков.

Характеристики и свойства

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

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

Недостатки

• Эффект конвоя (convoy effect): если первым в очереди оказывается процесс с большим временем выполнения (CPU-bound), все последующие короткие процессы (I/O-bound) вынуждены ждать, что приводит к неэффективному использованию процессора и периферийных устройств. Например, в системах с интенсивным вводом-выводом длительный процесс блокирует освобождение ресурсов, снижая общую пропускную способность.
• Высокое среднее время ожидания: при случайном порядке поступления задач с сильно различающейся длительностью среднее время ожидания может быть значительно выше, чем при использовании алгоритмов, учитывающих длину задачи (например, SJF).
• Непригодность для интерактивных систем: в системах реального времени или с разделением времени (time-sharing) FCFS не обеспечивает приемлемого времени отклика, так как пользователь может ждать завершения длительной задачи, не имея возможности прервать её.

Применение

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

• Планирование процессов: FCFS используется в простых встраиваемых системах, однопользовательских средах и в качестве алгоритма по умолчанию в некоторых утилитах (например, в команде at в UNIX).
• Диспетчеризация заданий: в пакетных системах (batch processing) задачи обрабатываются в порядке поступления, что упрощает управление очередями.
• Управление вводом-выводом: в контроллерах жёстких дисков (например, в старых моделях ATA) запросы к диску могли обслуживаться по принципу FCFS, хотя современные контроллеры используют более эффективные алгоритмы (NCQ — Native Command Queuing).

В теории массового обслуживания

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

В повседневной жизни

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

Пример работы

Пусть в систему в моменты времени t=0, t=2, t=4 поступают три процесса P1, P2, P3 с длительностями выполнения 5, 3 и 1 единицу времени соответственно. При использовании FCFS порядок выполнения будет следующим:

• P1 начинает в момент t=0 и завершается в t=5.
• P2 начинает в t=5 и завершается в t=8.
• P3 начинает в t=8 и завершается в t=9.

Время ожидания для P1 = 0, для P2 = 3 (с 2 до 5), для P3 = 4 (с 4 до 8). Среднее время ожидания = (0+3+4)/3 ≈ 2,33. Если бы процессы были обработаны в порядке P3, P2, P1 (SJF), среднее время ожидания составило бы (0+1+3)/3 ≈ 1,33, что демонстрирует неоптимальность FCFS для смешанных нагрузок.

Сравнение с другими алгоритмами

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

Основная критика FCFS связана с его неэффективностью в современных многозадачных средах. Алгоритм не учитывает ни длительность задачи, ни её приоритет, ни требования к времени отклика. В результате в системах с разделением времени (например, в современных операционных системах Windows, Linux, macOS) FCFS не используется для планирования процессов общего назначения. Вместо него применяются гибридные алгоритмы (например, CFS — Completely Fair Scheduler в Linux, основанный на концепции виртуального времени).

Тем не менее, FCFS остаётся важным теоретическим инструментом для анализа производительности очередей и часто используется в качестве базового алгоритма в учебных целях, а также в простых системах, где требования к производительности невысоки.

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

• В некоторых ранних операционных системах, например, в RT-11 для PDP-11, FCFS был единственным алгоритмом планирования.
• В сетевых технологиях FCFS используется в коммутаторах Ethernet (store-and-forward) для обработки кадров, хотя современные коммутаторы применяют более сложные схемы (например, Weighted Fair Queuing).
• В психологии и социологии принцип FCFS часто рассматривается как «естественная» форма справедливости, хотя на практике он может приводить к неоправданным задержкам для «быстрых» задач.

Источники

• Таненбаум Э., Бос Х. «Современные операционные системы». 4-е изд. — СПб.: Питер, 2015.
• Сильбершац А., Гэлвин П., Гэгн Г. «Операционные системы: внутренняя структура и принципы проектирования». 9-е изд. — М.: Вильямс, 2016.
• Клейнрок Л. «Теория массового обслуживания». — М.: Машиностроение, 1979.
• Stallings W. «Operating Systems: Internals and Design Principles». 9th ed. — Pearson, 2017.