First-Come, First-Served

Простейшим алгоритмом планирования является алгоритм, который принято обозначать аббревиатурой FCFS по первым буквам его английского названия – First-Come, First-Served (первым пришел, первым обслужен).

При таком алгоритме планирование и выполнение заданий происходит в той последовательности, в которой они поступили. Задачи, приостановленные для ожидания какого-либо ресурса, после перехода в состояние готовности становятся в эту очередь перед задачами, которые еще не выполнялись.

При этом образуются две очереди:

- новые задачи;

- ранее выполнявшиеся, но попавшие в состояние ожидания.

Представим себе, что процессы, находящиеся в состоянии готовность, выстроены в очередь. Когда процесс переходит в состояние готовность, он, а точнее, ссылка на его PCB (process control bloct) помещается в конец этой очереди. Выбор нового процесса для исполнения осуществляется из начала очереди с удалением оттуда ссылки на его PCB. Очередь подобного типа имеет в программировании специальное наименование – FIFO (First In, First Out (первым вошел, первым вышел).

Алгоритм FCFS реализует стратегию обслуживания «по возможности заканчивать вычисления в порядке их появления». Эта дисциплина не требует внешнего вмешательства в ход вычислений и перераспределения процессорного времени. По классу диспетчеризации (вытесняющие и невытесняющие) алгоритм планирования FCFS относится к невытесняющим. Процесс, получивший в свое распоряжение процессор, занимает его до истечения текущего CPU burst. После этого для выполнения выбирается новый процесс из начала очереди.

Достоинства алгоритма FCFS:

- простота реализации;

- малые расходы системных ресурсов на формирование очереди задач.

Основной недостаток: среднее время ожидания и среднее время выполнения задания зависят от порядка расположения заданий в очереди. Если в начале очереди находятся задания, которые требуют для выполнения большого количества ресурсов (а они в это время отсутствуют), то может возникнуть ситуация, при которой остальные задания, требующие меньший объем ресурсов, будут простаивать даже при условии, что для их выполнения имеется необходимый объем ресурсов, т.е. короткие задачи ожидают столько же времени, сколько и трудоемкие.

Рассмотрим следующий пример. Пусть в состоянии готовность находятся три процесса p₀, p₁ и p₂, для которых известны времена их очередных CPU burst. Эти времена приведены в таблице 1.1 в некоторых условных единицах.

Таблица 1.1.

Для простоты будем полагать, что вся деятельность процессов ограничивается использованием только одного промежутка CPU burst, что процессы не совершают операций ввода-вывода и что время переключения контекста так мало, что им можно пренебречь.

Если процессы расположены в очереди процессов, готовых к исполнению, в порядке p₀, p₁, p₂, то картина их выполнения выглядит так, как показано на рис. 1.1 или представлено в таблице 1.2.

Состояния процессов показаны на протяжении соответствующей единицы времени, то есть колонка с номером 1 соответствует промежутку времени от 0 до 1.

Рисунок 1.1 Выполнение процессов при порядке p0, p1, p2

Таблица 1.2.

Первым для выполнения выбирается процесс p₀, который получает процессор на все время своего CPU burst, т.е. на 13 единиц времени. После его окончания в состояние исполнение переводится процесс p₁, он занимает процессор на 4 единицы времени. И, наконец, возможность работать получает процесс p₂.

Время ожидания для процесса p₀ составляет 0 единиц времени, для процесса p₁ – 13 единиц, для процесса p₂ – 13 + 4 = 17 единиц.

Таким образом, среднее время ожидания в этом случае – (0 + 13 + 17)/3 = 10 единиц времени.

Полное время выполнения для процесса p₀ составляет 13 единиц времени, для процесса p₁ – 13 + 4 = 17 единиц, для процесса p₂ – 13 + 4 + 1 = 18 единиц.

Среднее полное время выполнения оказывается равным (13 + 17 + 18)/3 = 16 единицам времени.

Если те же самые процессы расположены в порядке p₂, p₁, p₀, то картина их выполнения будет соответствовать рис. 1.2 или таблице 1.3.

Рисунок 1.2 Выполнение процессов при порядке p2, p1, p0

Таблица 1.3.

Время ожидания для процесса p₀ равняется 5 единицам времени, для процесса p₁ – 1 единице, для процесса p₂ – 0 единиц.

Среднее время ожидания составит (5 + 1 + 0)/3 = 2 единицы времени. Это в 5 (!) раз меньше, чем в предыдущем случае.

Полное время выполнения для процесса p₀ получается равным 18 единицам времени, для процесса p₁ – 5 единицам, для процесса p₂ – 1 единице.

Среднее полное время выполнения составляет (18 + 5 + 1)/3 = 8 единиц времени, что почти в 2 раза меньше, чем при первой расстановке процессов.

Как мы видим, среднее время ожидания и среднее полное время выполнения для этого алгоритма существенно зависят от порядка расположения процессов в очереди. Если у нас есть процесс с длительным CPU burst, то короткие процессы, перешедшие в состояние готовность после длительного процесса, будут очень долго ждать начала выполнения. Поэтому алгоритм FCFS практически неприменим для систем разделения времени – слишком большим получается среднее время отклика в интерактивных процессах.