|
как произведение вероятности выполнения этой дуги и производящей функции моментов для времени выполнения операции, представленной этой дугой. В предыдущем разделе мы показали, как определить все петли замкнутого потокового графа. Для того чтобы применить эти результаты к открытой сети, необходимо ввести дополнительную дугу с ^-функцией wa(s), соединяющую сток t с источником s. W s ) Рис. 3.7. Замкнутая стохастическая сеть Затем для модифицированной сети нужно найти все петли (вплоть до максимально возможного порядка). Функция WA(s) необходима для того, чтобы найти эквивалентную ^-функцию для исходной сети. На рис. 3.7 исходная сеть изображена в виде «черного ящика» с Ж-функцией РТДз). Топологическое уравнение для замкнутых графов, известное также как правило Мейсона [53], имеет следующий вид: н = 1 1 Д Ы + £ П М Е Щ О + » + ( 1 ) 'Е Н О + ~ = о . (3.6) где YT(Li) — сумма эквивалентных коэффициентов пропускания для всех возможных петель /-го порядка. Таким образом, мы определили основные шаги процедуры вычисления эквивалентного коэффициента пропускания замкнутой сети. В качестве примера рассмотрим предыдущий рисунок. Данный замкнутый потоковый граф содержит одну петлю первого порядка с эквивалентным коэффициентом пропускания, равным fVA(s) Wr.{s). По правилу Мейсона получаем, что 1—JT4(.s)-0 или WA(s)=MWt{s). Отметим, 108 |
Пусть Zn, Z21, L„x — n не связанных между собой петель первого порядка заданной петли порядка п. Для каждой петли Lki первого порядка эквивалентный коэффициент пропускания 7* равен произведению коэффициентов пропускания ветвей, принадлежащих этой петле, т. е. ГК(3.2.5) Следовательно, для петли порядка п эквивалентный коэффициент пропускания T(L„) равен щ-„)=гк=п к=1 £=1 11*У (3.2.6) Основной результат (3.2.6) используется для определения стохастического поведения распределенных алгоритмов, которые могут быть описаны GERT-сетями. Цель использования системы GERT в стохастическом сетевом анализе алгоритмов и программ состоит в вычислении математического ожидания и дисперсии времени выполнения сети (которые рассматриваются здесь как общий параметр сети) и вероятности выполнения стока (или стоков). Очевидно, что коэффициент пропускания дуги GERT-сети есть соответствующая Ж-функция. Напомним, что Ж-функция дуги определяется как произведение вероятности выполнения этой дуги и производящей функции моментов для времени выполнения операции, представленной этой дугой. В предыдущем, разделе мы показали, как определить все петли замкнутого потокового графа. Для того чтобы применить эти результаты к открытой сети, необходимо ввести дополнительную дугу с Ж-функцией ^(s), соединяющую сток t с источником 5. Затем для модифицированной сети нужно найти все петли (вплоть до максимально возможного порядка). Функция Wa(s) необходима для того, чтобы найти эквивалентную PF-функцию для исходной сети. На рис. 3.2.2 исходная сеть изображена в виде «черного ящика» с Ж-функцией WE(s). 116 Рис. 3.2.2 Замкнутая стохастическая сеть Топологическое уравнение для замкнутых графов, известное также как правило Мейсона [...], имеет следующий вид: Н = 1 Z T(L{) + 2 T{L2 ) 2 T(L3 ) + ...+ (-1Г 2 T(Lm ) + ... = О, (3.2.8) где 'Y.T(Lj) — сумма эквивалентных коэффициентов пропускания для всех возможных петель г-го порядка. Таким образом, мы определили основные шаги процедуры вычисления эквивалентного коэффициента пропускания замкнутой сети. В качестве примера рассмотрим предыдущий рисунок. Данный замкнутый потоковый граф содержит одну петлю первого порядка с эквивалентным коэффициентом пропускания, равным WA(S) WE(s). По правилу Мейсона получаем, что 1—H/(s)=0 или WA(s)=l/WE(s). Отметим, что функция WA(s) содержится в топологическом уравнении, поскольку она является элементом, по крайней мере, одной петли первого порядка. Важность результата, полученного при рассмотрении данного примера, состоит в том, что если в топологическом уравнении WA(s) заменить на l/WE(s) и решить его относительно We(s), то будет получена эквивалентная ^-функция для исходной стохастической сети. Рассмотрим этап вычисления математического ожидания и дисперсии. Из топологического уравнения (3.2.8) было получено выражение для эквивалентной JF-функции WE(s) сети. Напомним, что ME(s)=l при 5 = 0. Поскольку f7E(s) = рЕ ME(s), то рЕ = ЙРХО), откуда следует, что 117 |