Математической моделью СОО является разомкнутая стохастическая сеть массового обслуживания, в которую входят так называемые типовые и нетиповые устройства вычислительной техники.
Типовые устройства имеют фиксированную производительность и получение требуемой производительности достигается путём параллельной работы нескольких устройств. В данной лабораторной работе типовыми устройствами являются накопители на магнитном диске, магнитной ленте и селекторные каналы.
Время пребывания заявки на i-ом нетиповом устройстве определяется из формулы
U(i) = R(i) / (V(i) - In(i)*R(i)),
где U(i) - время пребывания заявки на i-ом нетиповом устройстве;
R(i) - трудоёмкость обслуживания заявки на i-ом нетиповом устройстве;
V(i) - быстродействие i-го нетипового устройства;
In(i) - интенсивность обращения к i-му нетиповому устройству.
Так как на типовых устройствах требуемая производительность достигается за счёт их одновременной работы над разными заявками, то можно считать, что входной поток заявок делится между этими устройствами поровну. С учётом вышесказанного, время пребывания на k-ом типовом устройстве определяется зависимостью вида
U(i) = T(k) / (1 - In(k)*T(k) / Z(k)),
где T(k) - время обслуживания одной заявки на k-ом типовом устройстве;
Z(k) - количество типовых устройств k-го типа.
Допущение о равномерном распределении заявок между типовыми устройствами справедливо всегда только в том случае, если любое из этих устройств может выполнить любую заявку. Например, все накопители на магнитных дисках хранят одну и ту же информацию и работают только в режиме чтения.
В общем случае, для решения одной программы требуется обратиться многократно к различным устройствам, входящим в вычислительную систему. Поэтому среднее время пребывания программы вычисляется по формуле:
N1 N2
U = å D(i)*R(i)/(V(i) - In(i)*R(i)) + å D(k)*Z(k)*T(k)/(Z(k) - In(k)*T(k)),
i=1 k=1
где N1 - количество нетиповых устройств в вычислительной системе;
N2 - количество типовых устройств в проектируемой СОО;
D(i) - количество обращений к i-му устройству за время одного прогона программы.
Стоимость вычислительной системы S в первом приближении можно вычислить по формуле
N1 N2
S = å DK(i)*V(i) +å Z(k)*S(k),
i=1 k=1
где DK(i) - стоимость единицы производительности на i-ом нетиповом устройстве;
S(k) - стоимость k-го типового устройства.
При построении последней формулы предполагалось, что стоимость нетипового устройства пропорциональна его быстродействию. Во многих случаях это допущение оправдывается.
С учётом введенных обозначений, синтез системы оперативной обработки с заданным временем пребывания при минимально возможной стоимости сводится к следующей математической задаче. Необходимо найти такие параметры вычислительной системы V(i) (i=1,2,...,N1), Z(k) (k=1,2,...,N2), при которых стоимость системы будет минимальной, а время пребывания задачи в системе не превысит некоторой предельной величины U’. Одним из методов решения задачи отыскания экстремума функции при наличии ограничений является метод неопределённых коэффициентов Лагранжа. В соответствии с указанным методом введём вспомогательную функцию G следующим образом:
G = S + q*(U - U’),
где q - неопределённый коэффициент метода Лагранжа.
Дифференцируя последнюю функцию по искомым параметрам V(i) и
Z(k), получим:
dG/dV(i) = DK(i) - q*D(i)*R(i)/(V(i) - In(i)*R(i))**2;
i = 1,2,...,N1;
dG/dV(k) = S(k) - q*D(k)*In(k)*(T(k)/(Z(k) - In(k)*T(k)))**2;
k = 1,2,...,N2.
Следует отметить, что по физическому смыслу параметр Z(k) является целым положительным числом и операция дифференцирования по этой величине в общем случае некорректна. Поэтому при получении окончательного результата необходимо быть чрезвычайно аккуратным.
Приравняв первые производные нулю, из последних уравнений получим:
V(i) = In(i)*R(i) + ;
i = 1,2,...,N1;
Z(k) = In(k)*T(k) + T(k)* ;
k = 1,2,...,N2.
Из анализа вышеприведенных формул вытекает, что первое слагаемое представляет собой минимальное быстродействие или минимальное количество устройств в вычислительной системе, при которых коэффициент загрузки устройств равен единице. Второе слагаемое определяет добавку к минимальному быстродействию или минимальному количеству устройств, которая позволит получить требуемое время ответа в синтезируемой СОО.
Для нахождения неопределённого коэффициента Лагранжа q будем исходить из очевидной предпосылки, что вычислительная система будет иметь минимальную стоимость, если время пребывания программы в системе будет точно равно заданному ограничению, т.е.
U = U’.
Выполнив соответствующие подстановки и элементарные преобразования, получим
N1
= (å + å T(k)* ) / U”,
i=1 k=1
N2
где U”= U’- å D(k)*T(k).
k=1
Величину U” можно трактовать как время пребывания задачи на нетиповых устройствах при условии, что количество всех типовых устройств устремилось к бесконечности. Если величина U” получится в результате расчётов отрицательной, то из этого факта вытекает, что построить СОО заданной производительности при выбранном алгоритме и типовых устройствах не представляется возможным. Можно заменить типовые устройства, т.е. уменьшить значение времени обслуживания T(k) для некоторых типовых устройств, изменить алгоритм решения задачи путём уменьшения числа обращений D(k) к типовым устройствам или снизить количество используемых типовых устройств N2, что соответствует изменению конфигурации вычислительной системы и, следовательно, её программного обеспечения.
Значения Z(k) округляется до целого числа, не меньшего значения In(k)*T(k). При округлении возникает некоторая задержка в решении задачи:
N2
U1= U’- å D(i)*Z(i)*T(i) / (Z(i) - In(i)*T(i)).
i=1
За счёт этой задержки корректируется быстродействие нетиповых устройств в соответствии с выражением:
N1
V(j)=In(j)*R(j)+ *(å )/U1
i=1
j = 1,2,...,N1.
Последнее является следствием вышеприведенных расчётных соотношений при N2 = 0.
Если количество типовых устройств k-го типа окажется меньше, чем количество устройств k-го типа в СОО с минимальной конфигурацией, то необходимо вычислить новое ограничение на время пребывания заявки в системе
U1’= U’- D(k)*Z(k)*T(k) / (Z(k) - In(k)*T(k))
и выполнить вычисления повторно без учёта k-ой группы типовых устройств.