Round Robin

First come first served

Алгоритмы планирования.

Время ожидания для процесса P0=0 единиц, для P1=13 единиц, для P2=17 единиц. Таким образом, среднее время ожидания равно 10 единиц. Полное время выполнение для процесса P0=13единиц, для P1 =13+4=17,для P2=13+4+1=18. среднее полное время выполнения 16 единиц.

Время ожидания для P0=5 единиц, для P1=1, для P2=0. среднее время ожидания 2 единицы. В 5 раз эффективнее. Полное время выполнение для P0=5+13, P1=1+4, P2=1. среднее полное время 8 единиц.

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

Round Robin (R R)-это модификация предыдущего алгоритма. Это тот же алгоритм, реализованный в режиме вытесняющего планирования. Можно представить себе все множество готовых процессов организованных циклически. Процессы просто сидят на карусели. Карусель вращается так, что каждый процесс находится около процессора небольшой фиксированный квант времени от 10 до 100 мили секунд. Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться. Реализуется такой алгоритм также как и предыдущей с помощью организации процессов находящихся в состояние готовность. Планировщик выбирает для очередного исполнения процесс, находящийся в начале очереди и устанавливает таймер для генерации прерывания по истечению определенного кванта времени. При выполнение процесса возможны 2 варианта:

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

2.продолжительность остатка текущего CPU BIRST процесса, больше чем квант времени. Процесс вытеснен.

На производительность алгоритма RR сильно влияет величина кванта времени. При очень больших величинах кванта времени, когда каждый процесс успевает завершить свой CPU BIRST до возникновения прерывания по времени, алгоритм RR вырождается в алгоритм FIRST COME. В реальных условиях при слишком малой величине кванта и соответственно слишком частым переключением контекста, накладные расходы слишком резко возрастают, т.е снижается производительность системы.