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:
Объяснение решения примера
- Первый процесс 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].
Источники
- ↑ Особенности Round-robin // Quora [2019 — ]. Дата обновления: 25.12.2018. URL: https://www.quora.com/What-is-round-robin-scheduling (дата обращения: 05.04.2019).
- ↑ Преимущества и недостатки Round-robin // JavaTpoint [2011 — ]. URL: https://www.javatpoint.com/os-round-robin-scheduling-algorithm (дата обращения: 05.04.2019).
- ↑ Критерии планирования Round-robin // ResearchGate [2019 — ]. URL: https://www.researchgate.net/publication/50194216_An_Optimized_Round_Robin_Scheduling_Algorithm_for_CPU_Scheduling (дата обращения: 05.04.2019).
- ↑ Пример Round-robin // Tutorialwing [2017 — ]. URL: https://tutorialwing.com/round-robin-scheduling-algorithm-with-example/ (дата обращения: 05.04.2019).
ISSN 2542-0356
Следуй за Полисом
Оставайся в курсе последних событий
Лицензия
Если не указано иное, содержание этой страницы доступно по лицензии Creative Commons «Attribution-NonCommercial-NoDerivatives» 4.0, а примеры кода – по лицензии Apache 2.0. Подробнее см. Условия использования.