Round-robin

Round-robin - это алгоритм, занимающийся распределением нагрузки распределенной вычислительной системы, использующий упорядочение ее элементов по круговому циклу. Данный алгоритм является одним из важных алгоритмов планирования в планировании заданий. Это превентивный алгоритм планирования. Round Robin использует временной интервал (фиксированный период времени) для выполнения процесса, называемого квантом времени.

Особенности

• Самый популярный алгоритм из всех.
• Практически осуществим.
• Реализуем с базовыми структурами данных, такими как очередь
• Чрезвычайно меньшее голодание.
• Оптимальная эффективность может быть установлена путем контроля кванта времени.
• Алгоритм циклического перебора будет непрерывно переключаться между процессами, если процесс в ЦП (в процессе выполнения) превышает ограничение по времени, установленное ОС, которое называется квантом времени.

Преимущества и недостатки алгоритма

Преимущества

• Фактическая возможность осуществления в системе, поскольку нет зависимости от времени пакета.
• Отсутствует проблема возможного голодания.
• Все работы получают распределение ресурсов процессора.

Недостатки

• Чем выше квант времени, тем выше время отклика в системе.
• Чем меньше квант времени, тем выше издержки переключения контекста в системе.
• Выбор идеального кванта времени - действительно очень сложная задача в системе.

Критерии планирования

Переключение контекста

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

Пропускная способность

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

Время оборота

Время оборота - это сумма периодов, потраченных на ожидание попадания в память, ожидание в очереди готовности, выполнение на процессоре и ввод-вывод. Это должно быть меньше.

Время ожидания

Время ожидания - это время, которое процесс ожидал в очереди готовности. Алгоритм планирования ЦП не влияет на количество времени, в течение которого процесс выполняется или выполняет ввод-вывод; это влияет только на количество времени, которое процесс проводит в очереди ожидания.

Время отклика

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

Вывод по критериям планирования

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

• Минимальные контекстные переключатели.
• Максимальное использование процессора.
• Максимальная пропускная способность.
• Минимальное время выполнения заказа.
• Минимальное время ожидания.
• Минимальное время отклика.

Важные примечания

Примечание №1

С уменьшением значения кванта времени:

• Количество переключений контекста увеличивается.
• Время отклика уменьшается.
• Вероятность голода уменьшается.

  Таким образом, меньшее значение кванта времени лучше с точки зрения времени отклика.

Примечание №2

С увеличением значения кванта времени:

• Количество переключений контекста уменьшается.
• Время отклика увеличивается.
• Вероятность голода увеличивается.

  Таким образом, чем выше значение кванта времени, тем лучше с точки зрения количества переключений контекста.

Примечание №3

• Производительность планирования Round Robin сильно зависит от значения кванта времени.
• Значение кванта времени должно быть таким, чтобы оно не было ни слишком большим, ни слишком маленьким.

Пример

Предположим, что есть 5 процессов с идентификатором процесса (P) и временем всплеска, указанным ниже:

PID	Время всплеска
P1	6
P2	5
P3	2
P4	3
P5	7

Квант времени: 2. Предположим, что весь процесс прибывает в 0. Теперь мы рассчитаем среднее время ожидания для завершения этих процессов.

Решение примера

Мы можем представить выполнение вышеуказанных процессов с помощью диаграммы Ганта, как показано на рисунке 1:

Рисунок 1 – Выполнение процессов с помощью диаграммы Ганта

Объяснение решения примера

• Первый процесс P1 выбирается из очереди готовности и выполняется в течение 2 раз за единицу времени (интервал времени = 2).
• Если время прибытия недоступно, оно ведет себя как FCFS с интервалом времени.
• После выполнения P2 в течение 2 раз за единицу времени P3 берется из очереди готовности. С тех пор как P3 время всплеска равно 2, он сразу завершит выполнение процесса.
• Как и при выполнении процесса P1 и P2, P4 и P5 выполнят 2 временных среза, а затем снова начнут из P1 такой же, как и выше.

Время ожидания = время поворота - время всплеска:

• P1 = 19 - 6 = 13.
• P2 = 20 - 5 = 15.
• P3 = 6 - 2 = 4.
• P4 = 15 - 3 = 12.
• P5 = 23 - 7 = 16.

Среднее время ожидания = (13 + 15 + 4 + 12 + 16) / 5 = 12.