С заданным временем пребывания

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

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

    Время пребывания заявки на 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-ой группы типовых устройств.