Учебники

21) Круглый алгоритм планирования Робина

Декабрь 1, 2019

Что такое циклическое планирование?

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

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

Из этого руководства по операционной системе вы узнаете:

Характеристики кругового планирования

Вот важные характеристики кругового планирования:

  • Round Robin — это упреждающий алгоритм
  • Процессор переключается на следующий процесс после фиксированного интервала времени, который называется квантом времени / срезом времени.
  • Прерванный процесс добавляется в конец очереди.
  • Round Robin — гибридная модель с часовым механизмом
  • Временной интервал должен быть минимальным, который назначается для конкретной задачи, которую необходимо обработать. Тем не менее, он может отличаться от ОС к ОС.
  • Это алгоритм реального времени, который реагирует на событие в течение определенного времени.
  • Round Robin — один из самых старых, честных и простых алгоритмов.
  • Широко используется метод планирования в традиционных ОС.

Пример циклического планирования

Рассмотрим следующие три процесса

Очередь процессов Время взрыва
P1 4
P2 3
P3 5

Шаг 1) Выполнение начинается с процесса P1, который имеет время пакета 4. Здесь каждый процесс выполняется в течение 2 секунд. P2 и P3 все еще находятся в очереди ожидания.

Шаг 2 ) В момент времени = 2 P1 добавляется в конец очереди, и P2 начинает выполнение

Шаг 3) В момент времени = 4 P2 выгружается и добавляется в конец очереди. P3 начинает выполнение.

Шаг 4) В момент времени = 6 P3 выгружается и добавляется в конец очереди. P1 начинает выполнение.

Шаг 5) В момент времени = 8, P1 имеет время пакета 4. Он завершил выполнение. P2 начинает выполнение

Шаг 6) У P2 есть время пакета 3. Это уже выполнено в течение 2 интервалов. В момент времени = 9 P2 завершает выполнение. Затем P3 начинает выполнение до его завершения.

Шаг 7) Давайте посчитаем среднее время ожидания для приведенного выше примера.

Wait time 
P1= 0+ 4= 4
P2= 2+4= 6
P3= 4+3= 7

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

Вот преимущества / преимущества метода планирования в циклическом порядке:

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

Недостатки кругового планирования

Вот недостатки / недостатки использования циклического планирования:

  • Если время нарезки ОС мало, производительность процессора будет уменьшена.
  • Этот метод тратит больше времени на переключение контекста
  • Его производительность сильно зависит от кванта времени.
  • Приоритеты не могут быть установлены для процессов.
  • Планирование циклического перебора не дает особого приоритета более важным задачам.
  • Уменьшает понимание
  • Чем меньше квант времени, тем выше издержки переключения контекста в системе.
  • Поиск правильного кванта времени является довольно сложной задачей в этой системе.

Наихудший случай задержки

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

  • dt = обозначает время обнаружения, когда задача заносится в список
  • st = обозначает время переключения с одной задачи на другую
  • et = обозначает время выполнения задачи

Формула: 

Tworst = {(dti+ sti + eti ), + (dti+ sti + eti )2 +...+ (dti+ sti + eti )N., + (dti+ sti + eti  + eti) N} + tISR	
t,SR = sum of all execution times

Резюме:

  • Название этого алгоритма происходит от принципа циклического перебора, когда каждый человек получает равную долю чего-то по очереди.
  • Round Robin — один из самых старых, честных и простых алгоритмов и широко используемый метод планирования в традиционных ОС.
  • Round Robin — это упреждающий алгоритм
  • Самое большое преимущество метода циклического планирования состоит в том, что если вы знаете общее число процессов в очереди выполнения, то вы также можете предположить время ответа наихудшего случая для того же процесса.
  • Этот метод тратит больше времени на переключение контекста
  • Наихудшая задержка — это термин, используемый для обозначения максимального времени, затрачиваемого на выполнение всех задач.

 

310
Share: