First-Come, First-Served (FCFS)

Простейшим алгоритмом планирования является алгоритм, который принято обозначать аббревиатурой FCFS по первым буквам его английского названия - First Come, First Served (первым пришел, первым обслужен). Процессы, находящиеся в состоянии готовность, организованы в очередь. Когда процесс переходит в состояние готовность, он, а точнее ссылка на его PCB, помещается в конец этой очереди. Выбор нового процесса для исполнения осуществляется из начала очереди с удалением оттуда ссылки на его PCB.

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

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

Пример 1: Пусть в очереди процессов, готовых к исполнению, находятся три процесса в порядке p0, p1 и p2 (таблица 2), для которых известны времена их очередных CPU burst (в некоторых условных единицах):

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

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

Подсчитаем среднее время ожидания и среднее полное время выполнения. Время ожидания для процесса p0 составляет 0 единиц времени, для процесса p1 - 13 единиц, для процесса p2 - 13 + 4 = 17 единиц. Таким образом, в этом случае среднее время ожидания = (0 + 13 + 17)/3 = 10 единиц времени. Полное время выполнения для процесса p0 составляет 13 единиц времени, для процесса p1 - 13 + 4 = 17 единиц, для процесса p2 - 13 + 4 + 1 = 18 единиц. Среднее полное время выполнения оказывается равным (13 + 17 + 18)/3 = 16 единицам времени.

Пример 2. Пусть те же самые процессы расположены в порядке p2, p1, p0, то картина их выполнения будет соответствовать рисунку 12.

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

Время ожидания для процесса p0 равняется 5 единицам времени, для процесса p1 - 1 единице, для процесса p2 - 0 единиц. Среднее время ожидания составит (5 + 1 + 0)/3 = 2 единицы времени. Полное время выполнения для процесса p0 получается равным 18 единицам времени, для процесса p1 - 5 единицам, для процесса p2 - 1 единице. Среднее полное время выполнения составляет (18 + 5 + 1)/3 = 8 единиц времени.

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

Модификацией алгоритма FCFS является алгоритм, получивший название Round Robin (вид детской карусели в США). По сути дела это тот же самый алгоритм, только реализованный в режиме вытесняющего планирования. Можно представить себе все множество готовых процессов организованным циклически - процессы сидят на карусели. Карусель вращается так, что каждый процесс находится около процессора небольшой фиксированный квант времени, обычно 10 - 100 миллисекунд (рис. 13). Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться.

Рис. 13. Выполнение процессов при использовании алгоритма (RR)

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

· Время непрерывного использования процессора, требующееся процессу, (остаток текущего CPU burst) меньше или равно продолжительности кванта времени. Тогда процесс по своей воле освобождает процессор до истечения кванта времени, на исполнение выбирается новый процесс из начала очереди и таймер начинает отсчет кванта заново.

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

Пример 3. Рассмотрим предыдущий пример с порядком процессов p0, p1, p2 (таблица 2) и величиной кванта времени равной 4. Выполнение этих процессов иллюстрируется таблицей 2. Обозначение "Т" – промежуток времени, "И" – процесс в состоянии исполнение, обозначение "Г" – процесс в состоянии готовность, пустые ячейки соответствуют завершившимся процессам. Состояния процессов показаны на протяжении соответствующей единицы времени, т. е. колонка с номером 1 соответствует промежутку времени от 0 до 1

Таблица 3. Выполнение процессов в порядке p0,p1,p2, квант времени = 4

Первым для исполнения выбирается процесс p0. Продолжительность его CPU burst больше, чем величина кванта времени, и поэтому процесс исполняется до истечения кванта, т. е. в течение 4 единиц времени. После этого он помещается в конец очереди готовых к исполнению процессов, которая принимает вид p1, p2, p0. Следующим начинает выполняться процесс p1. Время его исполнения совпадает с величиной выделенного кванта, поэтому процесс работает до своего завершения. Очередь процессов в состоянии готовность состоит из двух процессов p2, p0. Процессор выделяется процессу p2. Он завершается до истечения отпущенного ему процессорного времени, и очередные кванты отмеряются процессу p0.

Время ожидания для процесса p0 составляет 5 единиц времени, для процесса p1 - 4 единицы времени, для процесса p2 - 8 единиц времени. Таким образом, среднее время ожидания для этого алгоритма получается равным (5 + 4 + 8)/3 = 5,6(6) единицы времени. Полное время выполнения для процесса p0 составляет 18 единиц времени, для процесса p1 - 8 единиц, для процесса p2 - 9 единиц. Среднее полное время выполнения оказывается равным (18 + 8 + 9)/3 = 11,6(6) единицам времени.

Легко видеть, что среднее время ожидания и среднее полное время выполнения для обратного порядка процессов не отличаются от соответствующих времен для алгоритма FCFS и составляют 2 и 6 единиц времени соответственно.

На производительность алгоритма RR сильно влияет величина кванта времени.

Пример 4. Рассмотрим тот же самый пример при порядке выполнения процессов p0, p1, p2 для величины кванта времени равной 1 (см. таблицу 2). Время ожидания для процесса p0 составит 5 единиц времени, для процесса p1 - тоже 5 единиц, для процесса p2 - 2 единицы.

Таблица 4. Выполнение процессов в порядке p0,p1,p2, квант времени = 4

В этом случае среднее время ожидания получается равным (5 + 5 + 2)/3 = 4 единицам времени. Среднее полное время исполнения составит (18 + 9 + 3)/3 = 10 единиц времени.

При очень больших величинах кванта времени, когда каждый процесс успевает завершить свой CPU burst до возникновения прерывания по времени, алгоритм RR вырождается в алгоритм FCFS. При очень малых величинах создается иллюзия того, что каждый из n процессов работает на своем собственном виртуальном процессоре с производительностью ~ 1/n от производительности реального процессора. Однако это справедливо лишь при теоретическом анализе при условии пренебрежения временами переключения контекста процессов. В реальных условиях при слишком малой величине кванта времени и, соответственно, слишком частом переключении контекста, накладные расходы на переключение резко снижают производительность системы.

Для алгоритмов FCFS и RR существенным является порядок расположения процессов в очереди процессов готовых к исполнению. Если короткие задачи расположены в очереди ближе к ее началу, то общая производительность этих алгоритмов значительно возрастает.

Алгоритм Shortest Job First (SJF – «кратчайшая работа первой») выбирает для исполнения не процесс из начала очереди, а процесс с минимальной длительностью CPU burst. Если таких процессов два или больше, то для выбора одного из них можно использовать уже известный нам алгоритм FCFS. Квантование времени при этом не применяется.

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

Пример 5. Рассмотрим пример работы невытесняющего алгоритма SJF. Пусть в состоянии готовность находятся четыре процесса p0, p1, p2 и p3, для которых известны времена их очередных CPU burst (таблица 5). Предположим, что процессы не совершают операций ввода-вывода, и что время переключения контекста пренебрежимо мало.

При использовании невытесняющего алгоритма SJF первым для исполнения будет выбран процесс p3, имеющий наименьшее значение очередного CPU burst. После его завершения для исполнения выбирается процесс p1, затем p0 и, наконец, p2 (таблица 6).

Таблица 6. Пример работы алгоритма SJF в режиме невытесняющего планирования

Среднее время ожидания для алгоритма SJF составляет (4 + 1 + 9 + 0)/4 = 3,5 единицы времени. Для алгоритма FCFS при порядке процессов p0, p1, p2, p3 эта величина будет равняться (0 + 5 + 8 + 15)/4 = 7 единицам времени, т. е. будет в 2 раза больше, чем для алгоритма SJF. Для заданного набора процессов (если в очереди не появляются новые процессы) алгоритм SJF является оптимальным с точки зрения минимизации среднего времени ожидания среди класса всех невытесняющих алгоритмов.

Пример 6. Рассмотрим пример вытесняющего SJF планирования с различными временами CPU burst и различными моментами их появления в очереди процессов готовых к исполнению (таблица 7).

В начальный момент времени в состоянии готовность находятся только два процесса p0 и p3. Меньшее время очередного CPU burst оказывается у процесса p3, поэтому он и выбирается для исполнения (см. таблицу 8, колонка с номером 1 соответствует промежутку времени от 0 до 1). По прошествии 2-х единиц времени в систему поступает процесс p1. Время его CPU burst меньше, чем остаток CPU burst у процесса p3, который вытесняется из состояния исполнение и переводится в состояние готовность. По прошествии еще 2-х единиц времени процесс p1 завершается, и для исполнения вновь выбирается процесс p3. В момент времени t = 6 в очереди процессов готовых к исполнению появляется процесс p2, но поскольку ему для работы нужно 7 единиц времени, а процессу p3 осталось всего 2 единицы времени, то процесс p3 остается в состоянии исполнение. После его завершения в момент времени t = 7 в очереди находятся процессы p0 и p2, из которых выбирается процесс p0. Наконец, последним получит возможность выполняться процесс p2.

Таблица 8. Пример работы алгоритма SJF в режиме вытесняющего планирования

Основную сложность при реализации алгоритма SJF представляет невозможность точного знания времени очередного CPU burst для исполняющихся процессов. В пакетных системах количество процессорного времени, требующееся заданию для выполнения, указывает пользователь при формировании задания. Эту величину можно использовать для осуществления долгосрочного SJF планирования. Если пользователь укажет больше времени, чем ему нужно, он будет ждать получения результата дольше, чем мог бы, так как задание будет загружено в систему позже. Если же он укажет меньшее количество времени, задача может не досчитаться до конца. Таким образом, в пакетных системах решение задачи оценки времени использования процессора перекладывается на плечи пользователя. При краткосрочном планировании можно делать только прогноз длительности следующего CPU burst, исходя из предыстории работы процесса. Пусть t(n) - величина n-го CPU burst, T(n + 1)- предсказываемое значение для n + 1-го CPU burst, a - некоторая величина в диапазоне от 0 до 1.

Определим рекуррентное соотношение: T(n + 1) = at(n) + (1 - a)T(n),

где T(0) – произвольная константа. Первое слагаемое учитывает последнее поведение процесса, тогда как второе слагаемое учитывает его предысторию.

При a = 0 перестаем следить за последним поведением процесса, полагая T(n) = T(n - 1) = ¼= T(0), т. е все CPU burst оцениваются одинаково, исходя из некоторого начального предположения.

При a = 1 не учитывается предыстория процесса. В этом случае полагаем, что время очередного CPU burst будет совпадать со временем последнего CPU burst: T(n + 1) = t(n). Обычно выбирают a = 1/2 для равноценного учета последнего поведения и предыстории.

Надо отметить, что такой выбор a удобен и для быстрой организации вычисления оценки T(n + 1). Для подсчета новой оценки нужно взять старую оценку, сложить с измеренным временем CPU burst и полученную сумму разделить на 2, например, с помощью ее сдвига на 1 бит вправо. Полученные оценки T(n + 1) применяются как продолжительности очередных промежутков времени непрерывного использования процессора для краткосрочного SJF планирования.

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: