Round-robin

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 16:15, 5 июня 2019.

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

Особенности

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

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

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

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

Недостатки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечание №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[Источник 4].

Источники

  1. Особенности Round-robin // Quora [2019 — ]. Дата обновления: 25.12.2018. URL: https://www.quora.com/What-is-round-robin-scheduling (дата обращения: 05.04.2019).
  2. Преимущества и недостатки Round-robin // JavaTpoint [2011 — ]. URL: https://www.javatpoint.com/os-round-robin-scheduling-algorithm (дата обращения: 05.04.2019).
  3. Критерии планирования Round-robin // ResearchGate [2019 — ]. URL: https://www.researchgate.net/publication/50194216_An_Optimized_Round_Robin_Scheduling_Algorithm_for_CPU_Scheduling (дата обращения: 05.04.2019).
  4. Пример Round-robin // Tutorialwing [2017 — ]. URL: https://tutorialwing.com/round-robin-scheduling-algorithm-with-example/ (дата обращения: 05.04.2019).