The design of the UNIX Operating System 2 страница

Round Robin (RR)

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

Основы операционных систем

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

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

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

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

Рассмотрим предыдущий пример с порядком процессов p₀, p₁, p₂ и величиной кванта времени равной 4. Выполнение этих процессов иллюстрируется таблицей3.2. Обозначение "И" используется в ней для про-цесса, находящегося в состоянии исполнение, обозначение "Г" – для процессов в состоянии готовность, пустые ячейки соответствуют завершившимся процессам. Состояния процессов показаны на протяжении соответствующей единицы времени, т. е. колонка с номером 1 соответствует промежутку времени от 0 до

							Таблица 3.2.
Время 1		2	3	4	5	6	7	8	9	10 11 12 13 14 15 16 17 18
p ₀	И И И И Г Г Г Г Г И И И И И И И И И
p ₁	Г Г Г Г И И И И
p ₂	Г Г Г Г Г Г Г Г И