5.3.5. Алгоритм циклической диспетчеризации rr

При циклическом, или круговом, алгоритме RR (Round-Robin) (рис.5.2) диспетчеризация процессов осуществляется по принципу FIFS, однако каждый раз процессу предоставляется ограниченное количество времени центрального процессора, называемое временным квантом q . Если процесс не заканчивается до истечения выделенного ему кванта времени (или не был заблокирован), он снимается с процессора, а на процессор устанавливается следующий процесс из числа находящихся в состоянии готовности. Процесс, снятый с процессора, переходит в очередь готовых к выполнению процессов.

Рис. 5.2.­ Диспетчеризация по циклическому алгоритму RR

Если существует n готовых к исполнению или исполняющихся процессов, то каждый получит 1/ n часть процессорного времени. Такая форма равного обслуживания неявно отдает предпочтение коротким процессам, поскольку они будут заканчиваться быстрее, чем длинные, но без чрезмерного ущемления интересов длинных процессов. Из-за расходов на переключение процессов общее время ожидания может быть больше, чем при FCFS. Однако, если дисперсия времени выполнения процессов велика, то при циклическом механизме общее среднее время ожидания может быть меньше, чем при алгоритме FCFS. Циклический алгоритм диспетчеризации широко используется для работы с разделением времени, когда система должна гарантировать приемлемые времена ответа для всех интерактивных пользователей. Накладные расходы на диспетчеризацию здесь удается снизить за счет эффективных механи­змов контекстного переключения и благодаря предоставлению достаточного объема основной пам­яти, чтобы процессы могли раз­мещаться в ней одновременно.

Существенную роль играет размер кванта времени q . При большом значении q каждому процессу предоставляется практически столько времени, сколько ему требуется для завершения, так что цикли­­ческая диспетчеризация по сути вырождается в диспетчеризацию по алгоритму FCFS. Кроме того, с ростом q для любого процесса возрастает время ожидания между последовательными выделениями ему процессора, что является недостатком для интерактивных систем. Если квант времени становится очень маленьким, то накладные расходы на кон­текстные переключения начинают играть доминирующую роль, причем характеристики системы в к­онце концов настолько у­ху­дш­аются, что с какого-то момента основное время затрачивается на переключение процессора, так что лишь незначительная часть времени остается, если вообще остается, на выполнение вычислений для пользователей. В результате для q необходимо выбрать некоторое приемлемое значение. Величина подобного оптимального к­ванта времени меняется от системы к системе (в зависимости от нагрузок) и от процесса к процессу.

5.3.6. Сравнение алгоритмов диспетчеризации с одной очередью

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

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

Таблица 5.1

Номер процесса	Время поступления	Время выполнения
1 2 3 4 5	0 2 4 6 8	3 6 4 5 2

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

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

Среднее время ожидания для циклического алгоритма несколько уменьшается при увеличении кванта времени q .

Рис. 5.3. Сравнение алгоритмов диспетчеризации с одной очередью

Таблица 5.2

Алгоритм диспетче-ризации	Номер процесса Время поступления Время выполнения	1 0 3	2 2 6	3 4 4	4 6 5	5 8 2	Среднее значе-ние
FCFS	Время завершения Длительность цикла обработки Время ожидания	3 3 0	9 7 1	13 9 5	18 12 7	20 12 10	8,6 4,6
SPN	Время завершения Длительность цикла обработки Время ожидания	3 3 0	9 7 1	15 11 7	20 14 9	11 3 1	7,6 3,6
SRT	Время завершения Длительность цикла обработки Время ожидания	3 3 0	15 13 7	8 4 0	20 14 9	10 2 0	7,2 3,2
HRRN	Время завершения Длительность цикла обработки Время ожидания	3 3 0	9 7 1	13 9 5	20 14 9	15 7 5	8,0 4,0
RR q = 1	Время завершения Длительность цикла обработки Время ожидания	4 4 1	19 17 11	17 13 9	20 14 9	15 7 5	11,0 7,0
RR q = 4	Время завершения Длительность цикла обработки Время ожидания	3 3 0	19 17 11	11 7 3	20 14 9	17 9 7	10,0 6,0