Курс лекций Операционным системам и среды (стр. 11 из 21)

Полное время выполнения для процесса p1 составляет 13 единиц времени, для процесса p2 – 13 + 4 = 17 единиц, для процесса p3 – 13 + 4 + 1 = 18 единиц. Среднее полное время выполнения оказывается равным (13 + 17 + 18)/3 = 16 единицам времени.

Если те же самые процессы расположены в порядке p3, p2, p1, то картина их выполнения будет соответствовать рис. 10.

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

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

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

2) «Кратчайшее задание – первое»

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

Рассмотрим изображение, приведенное на рис. 11,а. Здесь представлены четыре задания: А, В, С, D сo сроками выполнения 8,4,4 и 4 минуты соответственно. Если их запустить в этом порядке, оборотное время для задания А составит 8 мин, для В — 12 мин, для С — 16 мин и для D — 20 мин, при среднем времени 14 мин.

Теперь рассмотрим запуск этих четырех заданий, когда первым запускается самое короткое из них, как показано на рис. 11,б. Теперь показатели оборотного времени составляют 4, 8,12 и 20 мин при среднем времени 11 мин.

Рис. 11. Пример планирования, когда первым выполняется самое короткое задание

Следует заметить, что алгоритм, основанный на выполнении первым самого короткого задания, прост только в том случае, если все задания доступны одновременно.

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

Таблица 2

Процесс	Время появления	Время выполнения
P1	0	6
P2	2	2
P3	6	7
P4	0	5

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

Время ожидания для процесса p1 составляет 7 единиц времени, для процесса p2 – 0 единицы, для процесса p3 – 7единиц, p4 - 2. Таким образом, среднее время ожидания в этом случае – 4 единиц времени.

Полное время выполнения для процесса p1 составляет 13 единиц времени, для процесса p2 – 2 единицы, для процесса p3 – 14 единиц, р4 – 7 единиц. Среднее полное время выполнения оказывается равным 9 единицам времени.

Рис. 12. Диаграмма процессов с учетом времени появления

3) Приоритет наименьшему оставшемуся времени выполнения

Это версия алгоритма выполнения первым самого короткого задания.

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

Планирование в интерактивных системах

1) Циклическое планирование

Одним из самых старых, простых, справедливых и наиболее используемых алгоритмов.

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

Процессы сидят на карусели. Карусель вращается так, что каждый процесс находится около процессора в течение кванта времени. Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться (рис. 13).

Рис. 13. Процессы на карусели

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

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

Пример. Пусть в состоянии готовность находятся три процесса p1, p2 и p3, для которых известны времена их выполнения в некоторых условных единицах:

Таблица 3

Процесс	Время выполнения
P1	13
P2	4
P3	1

Пусть процессы подвергаются циклическому планированию с величиной кванта 4 мс.

Первым для исполнения выбирается процесс p1. Продолжительность его больше, чем величина кванта времени, и поэтому процесс исполняется до истечения кванта, т. е. в течение 4 единиц времени. После этого он помещается в конец очереди готовых к исполнению процессов, которая принимает вид p2, p3, p1.

Следующим начинает выполняться процесс p2. Время его исполнения совпадает с величиной выделенного кванта, поэтому процесс работает до своего завершения. Теперь очередь процессов в состоянии готовность состоит из двух процессов, p3 и p1.

Процессор выделяется процессу p3. Он завершается до истечения отпущенного ему процессорного времени, и очередные кванты отмеряются процессу p₀ – единственному не закончившему к этому моменту свою работу.

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

Полное время выполнения для процесса p1 составляет 18 единиц времени, для процесса p2 – 8 единиц, для процесса p3 – 9 единиц. Среднее полное время выполнения оказывается равным (18 + 8 + 9)/3 = 11,6(6) единицы времени.

Рис. 14. Диаграмма процессов при циклическом планировании

На производительность циклического алгоритма сильно влияет величина кванта времени. Рассмотрим тот же самый пример с порядком процессов p1, p2, p3 для величины кванта времени, равной 1. Время ожидания для процесса p1 составит 5 единиц времени, для процесса p2 – тоже 5 единиц, для процесса p3 – 2 единицы. В этом случае среднее время ожидания получается равным (5 + 5 + 2)/3 = 4 единицам времени. Среднее полное время исполнения составит (18 + 9 + 3)/3 = 10 единиц времени.

2) Приоритетное планирование

Каждому процессу присваивается определенное числовое значение – приоритет, в соответствии с которым ему выделяется процессор. Процессы с одинаковыми приоритетами планируются в порядке FIFO. Для алгоритма «Кратчайшее задание - первое» в качестве такого приоритета выступает продолжительности процесса. Чем меньше значение продолжительности, тем более высокий приоритет имеет процесс.