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

Циклический перебор (RR) - это один из алгоритмов, используемых планировщиками процессов и сетей в вычислениях . [1] [2] Поскольку этот термин обычно используется, временные интервалы (также известные как временные кванты) [3] назначаются каждому процессу равными частями и в циклическом порядке, обрабатывая все процессы без приоритета (также известные как циклические исполнительные ) . Планирование с циклическим перебором простое, легко реализуемое и исключает необходимость в голодании . Планирование с циклическим перебором может применяться к другим задачам планирования, таким как планирование пакетов данных в компьютерных сетях. Это концепция операционной системы .

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

Планирование процессов [ править ]

Основная статья: Планировщик процессов

Для справедливого планирования процессов планировщик циклического перебора обычно использует разделение времени , выделяя каждому заданию временной интервал или квант [4] (его отведенное время ЦП) и прерывая задание, если оно к тому времени не завершено. Работа возобновится в следующий раз, когда этому процессу будет назначен временной интервал. Если процесс завершается или меняет свое состояние на ожидание в течение своего приписанного кванта времени, планировщик выбирает первый процесс в очереди готовности для выполнения. В отсутствие разделения времени или если кванты велики по сравнению с размерами заданий, процесс, производящий большие задания, будет иметь преимущество перед другими процессами.

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

Например, если временной интервал составляет 100 миллисекунд, а для выполнения задания 1 требуется 250 мс, планировщик циклического перебора приостановит задание через 100 мс и предоставит другим заданиям их время на ЦП. Как только другие задания получат равную долю (100 мс каждое), задание 1 получит другое выделение процессорного времени, и цикл повторится. Этот процесс продолжается до тех пор, пока задание не завершится и не потребует больше времени на ЦП.

  • Job1 = Общее время для завершения 250 мс (квант 100 мс) .
  1. Первое выделение = 100 мс.
  2. Второе выделение = 100 мс.
  3. Третье выделение = 100 мс, но задание 1 само завершается через 50 мс.
  4. Общее время ЦП задания1 = 250 мс

Рассмотрим следующую таблицу со временем прибытия и времени выполнения процесса с квантовым временем 100 мс, чтобы понять циклическое планирование:

Имя процессаВремя прибытияВыполнить время
P00250
P150170
P213075
P3190100
P4210130
P535050
Планирование циклического перебора

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

Планирование сетевых пакетов [ править ]

Основная статья: Сетевой планировщик

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

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

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

Если предлагается гарантированное или дифференцированное качество обслуживания, то могут рассматриваться не только оптимальная связь, планирование дефицитного циклического перебора (DRR), планирование взвешенного циклического перебора (WRR) или взвешенная справедливая организация очереди (WFQ).

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

В централизованной беспроводной сети пакетной радиосвязи, где многие станции совместно используют один частотный канал, алгоритм планирования в центральной базовой станции может резервировать временные интервалы для мобильных станций циклически и обеспечивать справедливость. Однако, если используется адаптация линии связи, для передачи определенного количества данных «дорогим» пользователям потребуется гораздо больше времени, чем другим, поскольку условия канала различаются. Было бы более эффективно подождать с передачей, пока условия канала не улучшатся, или, по крайней мере, предоставить приоритет планирования менее дорогостоящим пользователям. Планирование с циклическим перебором не использует это. Более высокая пропускная способность и эффективность использования спектра системы могут быть достигнуты с помощью планирования, зависящего от канала, например, пропорционально справедливойалгоритм или планирование максимальной пропускной способности . Обратите внимание, что для последнего характерно нежелательное календарное голодание . Этот тип планирования является одним из самых основных алгоритмов для операционных систем на компьютерах, который может быть реализован через структуру данных кольцевой очереди.

См. Также [ править ]

  • Взвешенный круговой алгоритм
  • Круговая система дефицита
  • Многоуровневая очередь

Ссылки [ править ]

  1. ^ Arpaci-Dusseau, Remzi H .; Arpaci-Dusseau, Andrea C. (2014), Операционные системы: три простых элемента [Глава: Введение в планирование] (PDF) , Arpaci-Dusseau Books
  2. ^ Guowang Мяо , Jens Zander, Ки Вон Сун, и Бен Слиман, Основы сетей мобильных данных, Cambridge University Press, ISBN 1107143217 , 2016. 
  3. Перейти ↑ Stallings, William (2015). Операционные системы: внутреннее устройство и принципы проектирования . Пирсон. п. 409. ISBN 978-0-13-380591-8.
  4. ^ Зильбершатц, Авраам ; Гальвин, Питер Б .; Гань, Грег (2010). «Планирование процессов». Концепции операционной системы (8-е изд.). John Wiley & Sons (Азия). п. 194. ISBN 978-0-470-23399-3. 5.3.4 Планирование циклического перебора

Внешние ссылки [ править ]

  • Алгоритм циклического перебора с примером