Планирование с циклическим перебором - Round-robin scheduling

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

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

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

Планирование процессов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

Рекомендации

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

внешняя ссылка