Round Robin

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

Все множество готовых процессов организовано циклически - процессы как бы сидят на карусели, и она вращается таким образом, что каждый процесс находится около процессора небольшой фиксированный квант времени, обычно 10 - 100 миллисекунд (см. рисунок 2.1.). Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться.

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

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

Возможны два варианта при выполнении процесса:

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

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

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

Суть алгоритма

Пусть имеется N объектов, способных выполнить заданное действие, и M задач, которые должны быть выполнены этими объектами. Подразумевается, что объекты n равны по своим свойствам между собой, задачи m имеют равный приоритет. Тогда первая задача (m = 1) назначается для выполнения первому объекту (n = 1), вторая - второму и т. д., до достижения последнего объекта (m = M). Тогда следующая задача (m = N+1) будет назначена снова первому объекту и т. п. Проще говоря, происходит перебор выполняющих задания объектов по циклу, или по кругу (round), и по достижении последнего объекта следующая задача будет также назначена первому объекту. Решение задач может быть дополнительно разбито на кванты времени, причем для продолжения решения во времени нумерация объектов (и, соответственно, назначенные задачи) сдвигается по кругу на 1, то есть задача первого объекта отдается второму, второго - третьему, и т. д., а первый объект получает задачу последнего, либо освобождается для приема новой задачи. Таким образом, алгоритм Round Robin становится алгоритмом распределения времени или балансировки нагрузки.

Рассмотрим предыдущий пример с порядком процессов p0, p1, p2 и величиной кванта времени равной 4 (табл. 2.1).

Таблица 2.1.

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

Таблица 2.2.

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

Время ожидания для процесса p₀ (количество символов Г в соответствующей строке) составляет 5 единиц времени, для процесса p₁ – 4 единицы времени, для процесса p₂ – 8 единиц времени.

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

Полное время выполнения для процесса p₀ (количество непустых столбцов в соответствующей строке) составляет 18 единиц времени, для процесса p₁ – 8 единиц, для процесса p₂ – 9 единиц.

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

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

На производительность алгоритма RR сильно влияет величина кванта времени. Рассмотрим тот же самый пример c порядком процессов p₀, p₁, p₂ для величины кванта времени равной 1 (табл. 2.3).

Таблица 2.3.

Время ожидания для процесса p₀ составит 5 единиц времени, для процесса p₁ – тоже 5 единиц, для процесса p₂ – 2 единицы. В этом случае среднее время ожидания получается равным (5 + 5 + 2)/3 = 4 единицам времени.

Среднее полное время исполнения составит (18 + 9 + 3)/3 = 10 единиц времени.