Алгоритм FCFS

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

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

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

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

После освобождения ЦП диспетчер выбирает следующий процесс из начала очереди. Если очередь пуста, ЦП переходит в состояние простоя (idle).

История

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

С развитием многозадачных операционных систем и появлением интерактивных пользовательских интерфейсов (1960–1970-е годы) недостатки FCFS, такие как длительное время отклика для коротких задач, стали очевидны. Это привело к разработке более сложных алгоритмов, включая циклическое планирование (Round Robin) и планирование на основе приоритетов. Тем не менее, FCFS остаётся базовым понятием в теории операционных систем и используется в некоторых специализированных областях, где порядок поступления критичен.

Характеристики

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

• Простота реализации: алгоритм требует лишь поддержки очереди FIFO и не нуждается в сложных структурах данных или вычислениях приоритетов.
• Справедливость в порядке поступления: каждый процесс гарантированно получает ЦП, причём время ожидания пропорционально времени прибытия.
• Предсказуемость: при отсутствии блокировок порядок выполнения строго определён.
• Минимальные накладные расходы: переключение контекста происходит только при завершении или блокировке процесса, что снижает издержки.

Недостатки

• Эффект конвоя (convoy effect): если в начале очереди находится длительный процесс, все последующие короткие процессы вынуждены ждать его завершения, что резко увеличивает среднее время ожидания и снижает общую пропускную способность системы.
• Неоптимальность для интерактивных систем: время отклика для коротких задач может быть очень большим, что неприемлемо для пользователей, ожидающих быстрой реакции.
• Отсутствие приоритезации: все процессы обслуживаются в порядке поступления, независимо от их важности или срочности.
• Чувствительность к блокировкам: если процесс часто блокируется (например, при вводе-выводе), ЦП простаивает, пока процесс не возобновится, что снижает эффективность использования ресурсов.

Применение

Алгоритм FCFS применяется в следующих областях:

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

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

Рассмотрим три процесса, поступивших в моменты времени 0, 2 и 4 с длительностью выполнения (время ЦП) 10, 2 и 3 единицы соответственно:

• Процесс A (время поступления 0, длительность 10) — начинает выполнение в момент 0, завершается в момент 10.
• Процесс B (время поступления 2, длительность 2) — ожидает в очереди с момента 2, начинает выполнение в момент 10, завершается в момент 12.
• Процесс C (время поступления 4, длительность 3) — ожидает в очереди с момента 4, начинает выполнение в момент 12, завершается в момент 15.

Среднее время ожидания: ((0) + (10-2) + (12-4)) / 3 = (0 + 8 + 8) / 3 ≈ 5,33 единицы. Среднее время оборота: ((10-0) + (12-2) + (15-4)) / 3 = (10 + 10 + 11) / 3 ≈ 10,33 единицы.

В данном примере эффект конвоя проявляется в том, что короткие процессы B и C вынуждены ждать завершения длительного процесса A, что увеличивает их время ожидания.

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

Критика

Основная критика алгоритма FCFS связана с его неэффективностью в современных многозадачных операционных системах. Эффект конвоя может приводить к значительному снижению производительности, особенно в системах с интенсивным вводом-выводом, где короткие процессы часто блокируются. Кроме того, FCFS не учитывает приоритеты процессов, что делает его непригодным для систем реального времени, где важна гарантированная задержка. В интерактивных средах (например, в операционных системах Windows, Linux, macOS) FCFS практически не используется в чистом виде, уступая место циклическому планированию или многоуровневым очередям с обратной связью.

Источники

• Таненбаум Э., Бос Х. Современные операционные системы. 4-е изд. — СПб.: Питер, 2015.
• Сильбершац А., Гэлвин П., Гэгн Г. Операционные системы: внутренняя структура и принципы проектирования. 9-е изд. — М.: Вильямс, 2016.
• Столлингс У. Операционные системы: внутреннее устройство и принципы проектирования. 6-е изд. — М.: Вильямс, 2014.
• Дейтел Х. М. Введение в операционные системы. — М.: Мир, 1987.