Алгоритм RR

В реальных системах оперативной обработки априорная информация о временах решения задач, как правило, отсутствует. Чтобы воспользоваться принципами планирования на основе алгоритма SPT, в систему вводятся средства, обеспечивающие выявление коротких и длинных работ непосредственно в ходе вычислительного процесса.

Простейшее правило планирования работ, обеспечивающее выполнение указанного требования, задается алгоритмом циклического обслуживания, или, иначе, алгоритмом RR (Round–Robin). Работа алгоритма иллюстрируется рисунком.

Заявки на выполнение работ поступают с интенсивностью l в очередь O, откуда они выбираются и исполняются процессором Пр. Для обслуживания отдельной заявки отводится постоянный квант времени q, достаточный для выполнения нескольких тысяч операций. Если работа была выполнена за время q, она покидает систему. В противном случае она вновь поступает в конец очереди и ожидает предоставления ей очередного кванта процессорного времени.

Оценим среднее время ожидания и пребывания работ в системе с циклическим планированием. Воспользуемся для этого аппаратом теории массового обслуживания. Для упрощения последующих выкладок предположим, что длительность кванта не постоянная величина, а случайная, распределенная по экспоненциальному закону с тем же средним значением q. Причем также, что на вход системы поступает простейший поток с интенсивностью l работ в единицу времени, и с вероятностями s или (1-s) работа не будет или соответственно будет завершена в текущем кванте. Из последнего предположения следует, что вероятность того, что работа будет выполнена точно за k квантов (не завершена за первые k-1 квантов и завершена в k-том варианте), описывается геометрическим распределением

Таким образом, если известны средняя трудоемкость работ Q и длительность q кванта, то среднее количество квантов, с одной стороны, равно Q/q, а с другой – полученному выше выражению, то есть

Определим среднее время ответа для работы J, требующей ровно t единиц времени обработки. Пусть m – наименьшее целое, при котором mqіt (т.е. m – число квантов, достаточное для обслуживания заявки). Рассмотрим состояние системы на момент поступления работы J. При поступлении работы J в системе в среднем находится W1 других работ. Значение N1 определяется как среднее число заявок в системе с бесприоритетным обслуживанием, на вход которой заявки поступают с интенсивностью

L=l+ls+ls2+ј+lsn+ј=l/(1-s)

(с учетом интенсивности поступления заявок на дообслуживание в последующих тактах) и обслуживаются по экспоненциальному закону со средним q. Для определения W1 требуется найти распределение вероятностей {pk} того, что в очереди будет ровно k заявок. ТогдаW1= S kpk.

Для определения pk составим систему дифференциальных уравнений Колмогорова с помощью графа переходов (m=1/q)

Здесь Si – состояние системы с i заявками в очереди (одна из них обслуживается). Тогда система уравнений имеет вид

p`i =Lpi-1 - mpi - Lpi + mpi+1,

или

p`i =Lpi-1 - (m+L)pi + mpi+1, i=1,2,...

p`0 = -Lp0 + mp1.

Кроме того, требуется соблюдение условия нормировки

Рассмотрим установившийся режим, т.е. считаем, что t®Ґ. Тогда вместо дифференциальных уравнений получаем алгебраические

Lpi-1 - (m+L)pi + mpi+1=0, i=1,2,...

- Lp0 + mp1=0,

p0 + p1 +... + pi +... =1.

Из второго уравнения выразим p1 через p0:

p1 = L/m* p0;

подставим это значение в первое уравнение с i=1. Тогда

Делаем индуктивное предположение:

Тогда из k-го уравнения получаем

Откуда

что подтверждает индуктивное предположение. Поэтому в соответствии с условием нормировки имеем

Где

На основании полученного выражения или pk имеем

С учетом допущения об экспоненциальности распределения кванта q время дообслуживания работы J, не зависит от этого момента и в среднем равно q. Таким образом, работа будет ожидать W1q единиц времени до получения первого кванта. За время W1q и первый квант выполнения работы J в систему поступит l новых работ. Кроме того, sW1 работ из их общего числа W1 вернутся обратно в очередь на довыполнение. Поэтому в следующем цикле работа J застанет в системе W2 работ:

W2 = lW1q + lq + sW1.

Подставляя в последнее выражение ранее полученное значение W1, получаем

В общем случае аналогично получаем

Wi = l Wi-1q + lq + s Wi-1 = r/(1-r).

Среднее время ожидания для работы J, время выполнения которой составляет m квантов, равно

Здесь среднее время ожидания wm определяется как время, необходимое для обслуживания всех Wi работ, стоящих впереди работы J в каждом из m циклов обслуживания. Среднее время ответа для работы J

Um = wm +mq = mq/(1-r),

где r = lq/(1-s) = lq/(q/Q) = lQ – загрузка системы. Из выражения для времени ожидания wm видно, что время ожидания обслуживания возрастает с увеличением трудоемкости t=mq задачи. В то же время при обслуживании задач в порядке поступления без прерываний среднее время ожидания w не зависит от трудоемкости и составляет

Из последнего выражения видно, что время ожидания длинных задач (mq>Q) больше, чем при обслуживании в порядке поступления, а время ожидания коротких задач (mq<Q) – меньше времени ожидания в режиме без прерываний.