2018-02-13
1719
Ожидается, что время выполнения этих задач составит для:
§ A – 4 минуты,
§ B – 2 минуты
§ C - 7 минут.
Требуется определить среднее время выполнения запущенных задач, считая, что:
§ время смены контекста или время переключения между процессами равно - 2 мс,
§ время кванта процессора равно – 20 мс.
§ используемая дисциплина планирования – RR, при которой по истечении определенного кванта времени процесс прерывается и помещается в конец очереди готовых процессов, а процессор выделяется для использования процессу, находящемуся в ее начале.
Модификацией алгоритма FCFS является алгоритм, получивший название Round Robin (Round Robin – это вид детской карусели в США) или сокращенно RR. По сути дела, это тот же самый алгоритм, только реализованный в режиме вытесняющего планирования.
Можно представить себе все множество готовых процессов организованным циклически – процессы сидят на карусели. Карусель вращается так, что каждый процесс находится около процессора небольшой фиксированный квант времени, обычно 10 – 100 миллисекунд (см. рисунок В3.17.4).
Рисунок В3.17.4 - Процессы на карусели
Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться.
Реализуется такой алгоритм с помощью организации процессов, находящихся в состоянии готовность, в очередь FIFO.
Планировщик выбирает для очередного исполнения процесс, расположенный в начале очереди, и устанавливает таймер для генерации прерывания по истечении определенного кванта времени.
При выполнении процесса возможны два варианта.
§ Время непрерывного использования процессора, необходимое процессу (остаток текущего CPU burst), меньше или равно продолжительности кванта времени. Тогда процесс по своей воле освобождает процессор до истечения кванта времени, на исполнение поступает новый процесс из начала очереди, и таймер начинает отсчет кванта заново.
§ Продолжительность остатка текущего CPU burst процесса больше, чем квант времени. Тогда по истечении этого кванта процесс прерывается таймером и помещается в конец очереди процессов, готовых к исполнению, а процессор выделяется для использования процессу, находящемуся в ее начале.
Рассмотрим пример с порядком процессов А, В, С и величиной кванта времени равной 1мин. Выполнение этих процессов иллюстрируется таблицей В3.17.1. Обозначение "И" используется в ней для процесса, находящегося в состоянии исполнение, обозначение "Г" – для процессов в состоянии готовность, пустые ячейки соответствуют завершившимся процессам.
Состояния процессов показаны на протяжении соответствующей единицы времени, т. е. колонка с номером 1 соответствует промежутку времени от 0 до 1.
Таблица В3.17.1 Выполнение процессов
| Время | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| А | И | Г | Г | И | Г | Г | И | Г | И | |||||
| В | Г | И | Г | Г | И | |||||||||
| С | Г | Г | И | Г | Г | И | Г | И | Г | И | И | И | И |
Первым для исполнения выбирается процесс А. Продолжительность его CPU burst больше, чем величина кванта времени, и поэтому процесс исполняется до истечения кванта, т. е. в течение 1 единицы времени.
Следующим начинает выполняться процесс В.. После этого он помещается в конец очереди готовых к исполнению процессов, которая принимает вид С, А, В.
Следующим начинает выполняться процесс С.. После этого он помещается в конец очереди готовых к исполнению процессов, которая принимает вид А, В, С.
Далее действия повторяются.
На втором цикле процесс В должен закончиться и дальше переключения будут уже между двумя процессами.
Время ожидания для процесса А (количество символов "Г" в соответствующей строке) составляет 5 единиц времени, для процесса В – 3 единицы времени, для процесса С – 6 единиц времени.
Таким образом, среднее время ожидания для этого алгоритма получается равным
(5 + 3 + 6)/3 = 4.7 (единицы времени)
Полное время выполнения для процесса А (количество непустых столбцов в соответствующей строке) составляет 9 единиц времени, для процесса В – 5 единиц, для процесса С – 13 единиц.
Среднее полное время выполнения оказывается равным
(9 + 5 + 13)/3 = 9 (единиц времени).
Как можно заметить, на производительность алгоритма RR сильно влияет величина кванта времени.
При очень малых величинах создается иллюзия того, что каждый из n процессов работает на собственном виртуальном процессоре с производительностью ~ 1/n от производительности реального процессора.
Правда, это справедливо лишь при теоретическом анализе при условии пренебрежения временами переключения контекста процессов.
В реальных условиях при слишком малой величине кванта времени и, соответственно, слишком частом переключении контекста накладные расходы на переключение резко снижают производительность системы.
Исходя из условий задачи и учитывая время переключения между процессами можно определить продолжительность цикла на первом этапе выполнения задач А, В, С
Т1ц = 20*3 +2*3 = 66 (мс)
Первой будет решена задача В. Время ее решения Тв = Т1б, с учетом времени решения задачи Тзб в монопольном режиме и кванта времени Ткв, можно найти следующим образом:
Т1б = (Тзб/Ткв)*Тц = (2*20*1000 /20) *66 = 39600 (мс) =396 (с) = 6.6(мин)
Итак, первый этап завершается решением задачи В, его продолжительность равна 6,6 мин. Задачи А и С на этом этапе также решались в течение двух минут.
На втором этапе решаются уже две задачи, поэтому Т2ц
Т2ц = 20*2 +2*2 = 44 (мс)
Далее из задач А и С будет решена задача А. Время ее решения на втором этапе Т2а будет следующим:
Т2а = (Тза – Тзв)/Ткв*Т2ц = ((4-2)*60*1000/20) * 44 = 264000 (мс) = 264(сек) = 4,4(мин)
Полное время решения задачи А с учетом первого и второго этапа Та:
Та = Т2а +Тв = 6,4 + 4,4 = 10,8
После завершения второго этапа решается в режиме квантования только задача С. Продолжительность цикла на на третьем этапе выполнения задач Т3ц
Т3ц = 20+2 = 22 (мс)
Задача С завершится через:
Т3с= ((Тзс-Тза) /Ткв*Т3ц = ((7-4)*60*1000 /20) *22 = 198000(мс) = 198(с) = 3,3 (мин)
А полное время решения задачи составит значение Тс:
Тс = Та + Т3с
Итак, среднее время Тср решения задач А, В, С
Тср = (Та + Тв + Тс)/3 = (11+6,6 +14,3) = 10,63 мин
