<<
>>

Round Robin (RR)

Модификацией алгоритма FCFS является алгоритм, получивший название Round Robin (Round Robin — это вид детской карусели в США) или сокращенно RR. По сути дела, это тот же самый алгоритм, только реализованный в режиме вытесняющего планирования.
Можно представить себе все множество готовых процессов организованным циклически — процессы сидят на карусели. Карусель вращается так, что каждый процесс находится около процессора небольшой фиксированный квант времени, обычно 10-100 миллисекунд (см. рис. 3.4). Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться.

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

Рис. 3.4. Процессы на карусели


положенный в начале очереди, и устанавливает таймер для генерации прерывания по истечении определенного кванта времени. При выполнении процесса возможны два варианта:

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

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

Рассмотрим предыдущий пример с порядком процессов ро, pi, рг и величиной кванта времени, равной 4. Выполнение этих процессов иллюстрируется таблицей 3.2. Обозначение «И» используется в ней для процесса, находящегося в состоянии исполнение, обозначение «Г» — для процессов в состоянии готовность, пустые ячейки соответствуют завершившимся процессам. Состояния процессов показаны на протяжении соответствующей единицы времени, т. е. колонка с номером 1 соответствует промежутку времени от 0 до 1.

Таблица 3.2


Первым для исполнения выбирается процесс ро- Продолжительность его CPU burst больше, чем величина кванта времени, и поэтому процесс исполняется до истечения кванта, т. е. в течение 4 единиц времени. После этого он помещается в конец очереди готовых к исполнению процессов, которая принимает вид pi, рг, ро- Следующим начинает выполняться процесс рь Время его исполнения совпадает с величиной выделенного кванта, поэтому процесс работает до своего завершения. Теперь очередь процессов всостоянии готовность состоит из двух процессов — рг и ро. Процессор выделяется процессу рг. Он завершается до истечения отпущенного ему процессорного времени, и очередные кванты отмеряются процессу ро — единственному не закончившему к этому моменту свою работу. Время ожидания для процесса ро (количество символов «Г» в соответствующей строке) составляет 5 единиц времени, для процесса Р1 — 4 единицы времени, для процесса рг — 8 единиц времени. Таким образом, среднее время ожидания для этого алгоритма получается равным (5 + 4 + 8)/3 = 5,6 (6) единицам времени. Полное время выполнения для процесса ро (количество непустых столбцов в соответствующей строке) составляет 18 единиц времени, для процесса Р1 — 8 единиц, для процесса рг — 9 единиц. Среднее полное время выполнения оказывается равным (18 + 8 + 9)/3 = 11,6 (6) единицам времени.

Легко увидеть, что среднее время ожидания и среднее полное время выполнения для обратного порядка процессов не отличаются от соответствующих времен для алгоритма РСРБ и составляют 2 и 6 единиц времени соответственно.

На производительность алгоритма ЯЯ сильно влияет величина кванта времени. Рассмотрим тот же самый пример с порядком процессов ро, Рь рг для величины кванта времени, равной 1 (см. табл. 3.3). Время ожидания для процесса ро составит 5 единиц времени, для процесса р| — тоже 5 единиц, для процесса рг — 2 единицы. В этом случае среднее время ожидания получается равным (5 + 5 + 2)/3 = 4 единицам времени. Среднее полное время исполнения составит (18 + 9 + 3)/3 = 10 единиц времени.

Таблица 3.3


При очень больших величинах кванта времени, когда каждый процесс успевает завершить свой CPU burst до возникновения прерывания по времени, алгоритм RR вырождается в алгоритм FCFS. При очень малых величинах создается иллюзия того, что каждый из п процессов работает на собственном виртуальном процессоре с производительностью ~ 1/п от производительности реального процессора. Правда, это справедливо лишь при теоретическом анализе при условии пренебрежения временами переключения контекста процессов. В реальных условиях при слишком малой величине кванта времени и, соответственно, слишком частом переключении контекста накладные расходы на переключение резко снижают производительность системы.

<< | >>
Источник: В.Е. Карпов К.А. Коньков. Основы операционных систем. 2005 {original}

Еще по теме Round Robin (RR):

  1. 4.1. Определение и область применения
  2. Севереамериканская журналистика XVII-XIX веков
  3. Л.О. Доліненко, В.О. Доліненко, С.О. Сарновська. Цивільне право України, 2006
  4. ЦИВІЛЬНЕ ПРАВО УКРАЇНИ
  5. ПЕРЕДМОВА
  6. Частина І ПРОГРАМА КУРСУ «ЦИВІЛЬНЕ ПРАВО УКРАЇНИ»
  7. Розділ І. Загальні положення цивільного права
  8. Тема 1. Поняття цивільного права. Предмет та метод, система цивільного права. Функції та принципи цивільного права
  9. Тема 2. Цивільне законодавство України
  10. Тема 3. Поняття, елементи та види цивільних правовідносин
  11. Тема 4. Здійснення цивільних прав і виконання обов’язків
  12. Тема 5. Захист цивільних прав та інтересів
  13. Тема 6. Об’єкти цивільних прав
  14. Тема 7.ФІЗИЧНІ особи як суб’єкти цивільного права
  15. Тема 8. Юридичні особи