13. Алгоритм планирования rr. Анализ алгоритма с использованием простой модели очередности исполнения процессов. Влияние величины кванта времени на производительность процессов.

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

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

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

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

Влияние величины кванта времени на производительность процессов.

Планировщик операционной системы (scheduler) отвечает за очередность выполнения процессов в системе и размер выделяемой им доли процессорного времени. Время процессам выделяется квантами. По окончании кванта пользовательский процесс снимается с процессора, и на процессоре запускается следующий по очереди процесс. Этот механизм называется переключением контекста.

В различных ОС величина кванта времени существенно различается. Например:

• в ОС Solaris для стандартной диспетчерской таблицы квант убывает с 200 мс до 20мс и обычно колеблется между 20 и 40 мс.;

• в ОС HP-UX 11.11, 11.23, 11.31 квант равен 10 мс;

• в ОС Linux2.6 величина кванта составляет 200 мс и динамически изменяется в процессе выполнения.

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

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