Круговое планирование
Round-robin ( RR ) — один из алгоритмов, используемых планировщиками процессов и сетей в вычислениях . [ 1 ] [ 2 ] В общепринятом смысле этого слова временные интервалы (также известные как кванты времени) [ 3 ] назначаются каждому процессу равными частями и в циклическом порядке, обрабатывая все процессы без приоритета (также известный как циклический исполнитель ). Циклическое планирование просто, легко реализовать и не приводит к голоданию . Циклическое планирование можно применять и к другим задачам планирования, например, к планированию пакетов данных в компьютерных сетях. Это концепция операционной системы .
Название алгоритма происходит от принципа циклического обслуживания, известного из других областей, где каждый человек по очереди берет равную долю чего-либо.
Планирование процессов
[ редактировать ]Для справедливого планирования процессов циклический планировщик обычно использует разделение времени , давая каждому заданию временной интервал или такт. [ 4 ] (его выделение процессорного времени) и прерывание задания, если оно не завершено к тому времени. Задание возобновляется в следующий раз, когда этому процессу будет назначен временной интервал. Если процесс завершается или меняет свое состояние на ожидание в течение назначенного ему кванта времени, планировщик выбирает для выполнения первый процесс в очереди готовности. В отсутствие разделения времени или если бы кванты были большими по сравнению с размерами заданий, процесс, создающий большие задания, имел бы преимущество перед другими процессами.
Алгоритм циклического перебора — это упреждающий алгоритм, поскольку планировщик вытесняет процесс из ЦП после истечения временной квоты.
Например, если временной интервал составляет 100 миллисекунд, а общее время выполнения задания 1 составляет 250 мс, планировщик циклического перебора приостановит задание через 100 мс и отдаст другим заданиям свое время на ЦП. Как только другие задания получат равную долю (по 100 мс каждое), задание 1 получит еще одно распределение процессорного времени, и цикл повторится. Этот процесс продолжается до тех пор, пока задание не завершится и не потребует больше времени на процессор.
- Job1 = Общее время выполнения 250 мс (квант 100 мс) .
- Первое выделение = 100 мс.
- Второе выделение = 100 мс.
- Третье выделение = 100 мс, но задание 1 самозавершается через 50 мс.
- Общее время ЦП задания 1 = 250 мс
Рассмотрим следующую таблицу со временем прибытия и временем выполнения процесса с квантовым временем 100 мс, чтобы понять циклическое планирование:
| Имя процесса | Время прибытия | Время выполнения |
|---|---|---|
| Р0 | 0 | 250 |
| П1 | 50 | 170 |
| П2 | 130 | 75 |
| П3 | 190 | 100 |
| П4 | 210 | 130 |
| П5 | 350 | 50 |
Другой подход состоит в том, чтобы разделить все процессы на равное количество тактовых квантов так, чтобы размер кванта был пропорционален размеру процесса. Следовательно, все процессы заканчиваются одновременно.
Планирование сетевых пакетов
[ редактировать ]При с максимальной эффективностью коммутации пакетов и другом статистическом мультиплексировании циклическое планирование может использоваться в качестве альтернативы организации очередей в порядке очереди .
Мультиплексор, коммутатор или маршрутизатор, обеспечивающий циклическое планирование, имеет отдельную очередь для каждого потока данных, где поток данных может быть идентифицирован по адресу источника и назначения. Алгоритм позволяет каждому активному потоку данных, имеющему пакеты данных в очереди, по очереди передавать пакеты по общему каналу в периодически повторяющемся порядке. Планирование экономит работу , а это означает, что если в одном потоке нет пакетов, его место займет следующий поток данных. Следовательно, планирование пытается предотвратить неиспользование ресурсов канала.
Циклическое планирование обеспечивает максимальную и минимальную справедливость , если пакеты данных имеют одинаковый размер, поскольку поток данных, ожидавший наибольшее время, получает приоритет планирования. Это может быть нежелательно, если размер пакетов данных сильно варьируется от одного задания к другому. Пользователь, создающий большие пакеты, будет иметь преимущество перед другими пользователями. В этом случае справедливая организация очереди предпочтительнее будет .
Если предлагается гарантированное или дифференцированное качество обслуживания, а не только связь с максимальными усилиями, планирование дефицитного циклического перебора (DRR), взвешенное циклическое планирование (WRR) или взвешенную справедливую организацию очереди можно рассмотреть (WFQ).
В сетях множественного доступа , где несколько терминалов подключены к общей физической среде, циклическое планирование может обеспечиваться с помощью с передачей маркера, схем доступа к каналу таких как Token Ring , или путем опроса или резервирования ресурсов с центральной станции управления.
В централизованной беспроводной сети пакетной радиосвязи, где многие станции совместно используют один частотный канал, алгоритм планирования в центральной базовой станции может резервировать временные интервалы для мобильных станций в циклическом порядке и обеспечивать справедливость. Однако, если используется адаптация канала , передача определенного объема данных «дорогим» пользователям займет гораздо больше времени, чем другим, поскольку условия канала различаются. Было бы более эффективно подождать с передачей до тех пор, пока условия канала не улучшатся, или, по крайней мере, отдать приоритет планирования менее затратным пользователям. В циклическом планировании это не используется. Более высокая пропускная способность и эффективность использования спектра системы могут быть достигнуты за счет каналозависимого планирования, например, пропорционально справедливого алгоритма или планирования максимальной пропускной способности . Отметим, что для последнего характерно нежелательное планирование голодания . Этот тип планирования является одним из базовых алгоритмов операционных систем компьютеров, который может быть реализован посредством структуры данных кольцевой очереди.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Арпачи-Дюссо, Ремзи Х.; Арпачи-Дюссо, Андреа К. (2014), Операционные системы: три простых части [Глава: Введение в планирование] (PDF) , Arpaci-Dusseau Books
- ^ Гуован Мяо , Йенс Зандер, Ки Вон Сон и Бен Слиман, «Основы сетей мобильной передачи данных», Cambridge University Press, ISBN 1107143217 , 2016.
- ^ Столлингс, Уильям (2015). Операционные системы: внутреннее устройство и принципы проектирования . Пирсон. п. 409. ИСБН 978-0-13-380591-8 .
- ^ Зильбершац, Авраам ; Гэлвин, Питер Б.; Ганье, Грег (2010). «Планирование процессов». Концепции операционной системы (8-е изд.). Джон Уайли и сыновья (Азия). п. 194. ИСБН 978-0-470-23399-3 .
5.3.4 Планирование циклического перебора
| Одиночные узлы массового обслуживания | |
|---|---|
| Процессы прибытия | |
| Сети массового обслуживания | |
| Политика обслуживания | |
| Ключевые понятия | |
| Предельные теоремы | |
| Расширения | |
| Информационные системы | |
