Оценка длительности пребывания процесса в множестве невозвратных состояний

Рассмотрим поведение цепи Маркова при росте числа шагов k. Из анализа структуры матрицы Р^к (3.10) следует, что процесс, стартовав из некоторого состояния S _i принадлежащего невозвратному множеству Т, на каждом шаге с вероятностями, определенными матрицей R, переходит вэргодическое множество Ť. Через определенное число шагов процесс окажется в Ť с вероятностью, как угодно близкой к единице.

При моделировании реальных систем с помощью конечных цепей Маркова часто бывает необходимо оценивать показатели продолжительности работы системы или трудоемкости процессов. Для этой цели нужно уметь рассчитывать число шагов, в течение которых процесс не покидает множество Т («время жизни» процесса), а также «время жизни» отдельных состояний этого множества.

Обозначим п_ij общее число моментов времени (тактов работы системы), проведенных процессом в состоянии Sj при условии, что он стартовал из состояния S_i (Si, Sj € T). Понятно, что n_ij - случайная величина, принимающая целочисленные значения 0, 1, 2,... с соответствующими вероятностями, которые мы будем обозначать p_ij(l),..., p_iJ(k),.... Таким образом Р_ij{к)= Рi{n_ij=k} - вероятность того, что система за все «время жизни» процесса находилась в состоянии Sj при старте из Si, k раз. При этом

∞

∑ Р_ij(k)=1. Зная распределение вероятностейможно вычислить все необходимые статистические

k=0

характеристики процесса - математическое ожидание, дисперсию и другие. Однако вычисление таких распределений в общемслучае - достаточно сложная задача, поэтому мы ограничимся в данном разделе рассмотрением трех более простых практически важных задач:

- оценки вида функции распределения r _ij (k);

- вычисления математического ожидания величин п_ij, т.е. M ë n_ij û и средних значений трудоемкости процесса;

- вычисления дисперсий п_ij, т.е. D ë n_ij û среднеквадратичных отклонений трудоемкости процесса.

1. Оценим вид функции распределения r _ij (k) случайных величин п_ij. Обратимся к матрице (3.11)

R(k) = || r_ij (k)||, S_i Î T, S_j Î Ť.

Элемент этой матрицы r_ij(к) представляет собой вероятность перехода в S_j Î Ť при старте из S_t Î T за k шагов. Разность r _ij(k) = r_ij(k)-r_ij(k-1) есть вероятность перехода в S_j Î Ť точно на k шаге при старте из S_i Î T. Эта разность всегда неотрицательна в силу структуры матрицы Р^k (3.10).

Задача нахождения вероятностей распределения Прощается, если рассматривать переходы не между отдельными состояниями, а между множествами Т и Ť. Граф цепи Маркова примет вид, показанный на рисунке 3.5.

Обозначим вероятность перехода между множествами T и Ť при старте из S_l Î Tза один шаг

где r_ij - элемент матрицы R (3.9); q_i =l-r, - вероятность того, что процесс останется в Т.

Для рассматриваемой системы матрица переходных вероятностей имеет вид

и для нее по формуле (3.11) нетрудно подсчитать вероятности перехода из T в Ť за kшагов и на k -м шаге.

Можно убедиться в том, что p_j(k) = r_iq_i^k-1 представляет собой функцию распределения случайной величины n_i.

В самом деле, все r_i(k)³ 0, кроме того, воспользовавшись формулой для суммы членов геометрической прогрессии, получим:

Полученное распределение носит название показательного. График этой функции имеет вид, показанный на рисунке 3.6.

Из графика видно, что наиболее вероятны малые значения п_i, а с ростом числа шагов вероятность r_i (k) монотонно убывает.

Математическое ожидание и дисперсия числа пребываний процесса в множестве Т определяется по известным формулам (промежуточные выкладки опущены):

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

2. Переходя к вычислению матожидания величины n_ij, начнем с изучения свойств матрицы Q^k, входящей в структуру P^k в формуле (3.10). Поскольку по определению все элементы матрицы Q р_ij ≤ 1, и

S n

∑ p_ij ≤ 1 (в отличие от матрицы Р, для которой ∑ p_ij = 1 S_i, S_j Î Т, то при больших k эта матрица

j=1 j=1

стремится к нулевой, т.е. Q^k —> Ø _S при k —> ∞). Здесь Ø _S - нулевая квадратная матрица 5-го порядка.

Для дальнейшего нам понадобится формула, оценивающая матрицу (I - Q)^-1. Рассмотрим тождество

Матрица (I-Q) неособенная, т.е. det(I-Q)≠ 0, в чем легко убедиться.

Следовательно, существует обратная матрица (I-Q) ^-1, которая играет большую роль при изучении марковских процессов с матрицей переходных вероятностей вида (3.9). Эту матрицу называют фундаментальной и обозначают

3. Перейдем теперь к оценке среднего «времени жизни» состояний процесса, относящихся к невозвратному множеству.

Обозначим, как и прежде, через n_ij общее число моментов времени, проводимых процессом в состоянии S_j при условии, что он начался из состояния S_i. Эта функция определена только для невозвратного множества, т.е. S_i, S_j Î T.

Можно показать, что матрица математических ожиданий чисел n _ij равна N, т.е.

Для того, чтобы в этом убедиться, введем вспомогательную переменную u^k_ij, которая принимает единичное значение, если процесс, стартовав при t = t₀ из S=S_i оказывается при t = t_k в S = S_j, т.е.

1, если S(t_k)=S_J | S(t₀)=S_i ,

u_i^k_j =

0 в противном случае.

Вероятность того, что u_i^k_j = 1, обозначим р_i^(k)_j.

∞

Легко видеть, что n_ij =∑ u_i^k_j.

k=0

Оценим теперь матожидание матрицы, образованной элементами п_ij:

Здесь р_i^(k)_j - элемент Р^k, S_i, S _j Î T.

Таким образом, среднее число шагов, которое проводит процесс в невозвратном состоянии, S _j, начавшись в S_i, всегда конечно и определяется i-й строкой матрицы (I - Q)^-1.

4. Рассмотрим другой вывод формулы (3.14), который понадобится в дальнейшем.

Величина п_ij на каждом временном шаге k может быть определена соотношением

Первая сумма в написанном выражении относится к случаю, когда состояния S_i, и Sj совпадают, кроме того, процесс на следующем шаге уходит в эргодическое множество Ť. Вторая сумма представляет собой вклад в величину п_ij за счет перехода в j -е состояние из i -го через промежуточные l-e состояния, а слагаемое δ ij - добавление 1, если S_i = S_j.

Раскроем скобки во втором слагаемом и учтем, что

Применив к этой формуле операцию математической ожидания и рассматривая предельный случай (k —> ∞ и n_kj^(k) —> n_kj), получим:

откуда N = (I - Q)^-1.

5. Напомним, что i-я строка матрицы N определяет среднее число тактов пребывания марковского процесса в различных состояниях невозвратного множества при старте из S_i. Поэтому если нас интересует только одно конкретное начальное состояние, то вычисление всей матрицы N дает избыточную информацию. В этом случае вычисления можно упростить.

Формулу N = (I-Q)^-1 можно переписать иначе:

В правой части системы уравнений единица стоит в i -й строке.

6. Рассмотрим теперь случай, когда система может стартовать из любого состояния S_tÎ T с заданной вероятностью, т.е. вектор начальных состояний имеет вид

где х_i⁰ - вероятность того, что марковский процесс начнется из S_t.

В этом случае величина N₁. - среднее число тактов пребывания процесса в состоянии S_l Î T - определяется взвешенной суммой элементов j -го столбца матрицы N:

Пример. Вернемся к рассмотренному ранее примеру. В нашей системе имеется одно поглощающее состояние, которое соответствует ожиданию сигнала оператора с клавиатуры,

остальные состояния - эргодические. Представим матрицу в виде

Здесь det{l -Q)=l-p₁~p₂- p₃ = р₄.

Матрица N показывает среднее число пребываний процесса в каждом из состояний S₀, S_l: S_? , S₃. Если процесс начинается с S_o, то, как видно по первой строке матрицы N,

в состоянии S_o процесс был в среднем — раз;

Р₄

Р₁

в состоянии S, процесс был в среднем —- раз;

Р₄

Р ₂

в состоянии S₂ процесс был в среднем —— раз;

Р₄

Р₃

в состоянии S₃ процесс был в среднем —— раз.

Р₄

Например,

пусть р₁ =0.8, р₂ = 0.05, p ₃ =0.1, p₄ =0.05.

Тогда в состоянии S₀ процесс был в среднем п₁₁ = 20 раз;

в состоянии S₁ процесс был в среднем п₁₂ = 16 раз;

в состоянии S₂ процесс был в среднем п₁₃ = 1 раз;

в состоянии S₃ процесс был в среднем п₁₄ - 2 раза.

Нетрудно проверить, что п₁₂ +п₁₃ +п₁₄ = 19, плюс система 1 раз перешла в состояние S₄, таким образом п₁₁ = 19 +1 = 20.

7. Зная среднее число пребываний процесса в невозвратном состоянии и трудоемкость каждого этапа, можно вычислить среднюю трудоемкость алгоритма в целом.

Если C₁,..., C_s - средние трудоемкости этапов, то при старте процесса из состояния S₁ общая средняя трудоемкость вычислительного процесса равна

Пусть C ₁ = 0.5с - среднее время работы процессора;

C₂= 0.75с - среднее время работы НЖМД;

С₃ = 2.5с - среднее время работы НГМД;

С₄=30с - среднее время работы принтера.

Тогда по формуле (1.19) общая средняя трудоемкость (продолжительность) одного цикла работы ВС при старте из состояния S_o составит

С_1о =0.5 -20 + 0.75 -16 + 2.5 -1 + 30- 2- 84.5с.

8. Оценим теперь дисперсию числа пребываний процесса в множестве невозвратных состояний М ë n_ij û.

Этот показатель характеризует степень разброса величины п_ij относительно среднего.

В соответствии с определением дисперсии случайной величины n_ij имеем:

Перейдем к матрицам:

Второе слагаемое в (3.20) - это матрица, образованная из квадратов элементов матрицы N. Обозначим ее

Вычислим теперь первое слагаемое в (3.20). Оно представляет собой матрицу, составленную из матожиданий случайной величины п_ij². Для вычисления М\п₁²\ воспользуемся

приемом, который был применен в п. 3 настоящего параграфа, для вычисления M[n_jJ j.

Рассматривая предельный случай (к — > ∞), имеем

Здесь первое слагаемое определяет вклад в величину п₁². начального состояния, когда процесс, начавшись в S_i Î Т, сразу же перешел в S_k Î Ť. Второе слагаемое определяет вклад в величину n _ij за счет перехода в Sj из Si через промежуточное S_kÎ T

Добавка δ _kj. в круглой скобке относится к случаю, когда процесс стартовал из Sj Î T.

Раскроем скобки во втором слагаемом (3.22) и, проделав элементарные преобразования, получим:

В последнем преобразовании использована следующая цепочка тождеств:

где (QN)_dg - матрица, полученная обнулением всех элементов исходной матрицы вне главной диагонали (благодаря множителю δ _ij в последнем слагаемом (3.23)). Далее проделаем некоторые преобразования над матрицами. Перенося неизвестную матрицу ||M [п²_kj ||в левую часть равенства, имеем:

т.к. I_dg=I.

Возвращаясь к (3.20) с учетом. (3.21), получим окончательно:

Пример. Вернемся к нашему примеру и оценив дисперсии числа шагов вычислительного процесса. Как было получено ранее,

Эта матрица показывает дисперсию числа пребываний процесса в каждом из состояний. Мы видим, что вне зависимости от стартового состояния дисперсии числа пребываний в различных состояниях равны:

В ряде случаев исследователя интересует не дисперсия, а среднеквадратичное отклонение числа пребываний процесса от среднего, которое вычисляется по известной формуле

или в матричной форме

Таким образом, матрица среднеквадратичных отклонений получается извлечением квадратного корня из каждого элемента-матрицы D.

Пример. Для тех же численных значений вероятностей что рассматривались ранее

Располагая матрицей а, можно вычислить среднеквадратичное отклонение трудоемкости вычислительного процесса от среднего:

Для рассматриваемого примера

3.5. Исследование динамики цепей Маркова при большом числе шагов

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

Как было выяснено выше, динамика смены состояний однородной цепи Маркова определяется поведением матрицы P^k при к = 1, 2,.... Однако непосредственное применение формулы (3.5) для определения переходных характеристик этого процесса, в частности, скорости сходимости к предельным вероятностям пребывания в различных состояниях при k-> ∞, неудобно.

1. Для оценки скорости сходимости можно привести матрицу Р к диагональному виду с помощью линейного преобразования. Предположим, что матрица Р имеет п собственных чисел λ ,..., λ _п. Тогда ее можно привести к виду:

P = UΛ U^-1 (3.27)

где Λ - диагональная матрица

а матрица U составлена из собственных векторов матрицы Р так, что i -й столбец матрицы U является собственным вектором матрицы Р при собственном числе λ.

Напомним, что i-е собственное число матрицы Р λ, есть i -й корень алгебраического уравнения

det{P-λ l) = 0, (3.28)

а собственный вектор u_i, соответствующий собственному числу λ i, есть решения линейного уравнения

Pu_i = λ _iu _{i .} (3.29)

Преобразование (3.27) удобно тем, что при возведении степень матрицы фактически возводится в степень только диагональная матрица

Р^k =(U Λ U^-1)^k = U Λ ^k U^-1, (3.30)

причем

Таким образом, динамику изменения матрицы Р^k легко оценить по поведению λ ^k_i, i = 1,..., п.

Мы уже упоминали, что матрица Р, определяющая однородную цепь Маркова, является стохастической матрицей [14]. Особенностью этой матрицы является то, что ее максимальное собственное число равно 1, и ему соответствует собственный вектор, составленный из единиц: [1, 1,... l].

Пример. Продолжим рассмотрение динамики системы, изображенной на рисунке 3.2. Для упрощения расчетов объединим состояния S,, S_? , S₃, описывающие файловый обмен, в одно. Тогда система будет иметь три состояния: S, - работа процессора; S₂ - файловый обмен; S₃ - состояние поглощения, а матрица переходных вероятностей примет вид

где р = р₁ + р₂ + р₃ - вероятность выполнения операций файлового обмена после окончания работы процессора.

Приведем матрицу Р к виду (3.27). Для этого сперва определим собственные числа матрицы Р из уравнения (3.28):

откуда характеристическое уравнение примет вид

(1-λ)(λ ²-р)=0.

Нетрудно видеть, что корни этого уравнения (собственные числа матрицы Р) равны, соответственно, λ ₁= 1, λ ₂ = Ö p, λ ₃= -Ö p. Таким образом, матрица Λ примет вид

Определим теперь собственные векторы ui = ë uⁱ₁, uⁱ₂, uⁱ₃ û матрицы Р для каждого собственного числа λ _i (i = 1, 2, 3) из уравнения (3.29).

Для λ ₁=l имеем:

откуда, положив в полученной недоопределенной системе уравнений и¹₁=1, получим и¹₂ =и¹₃=1, т.е.

что соответствует отмеченному выше свойству стохастичесих матриц.

Аналогично для λ ₂ = Ö p, положив и₂² = 1, получим:

Таким образом, матрица Р приведена к форме (3.27), а ее k-я степень в соответствии с (3.30) имеет вид

Из полученного выражения для матрицы Р^k следует, что вероятности пребывания процесса в состояниях S_o и S₁, относящихся к невозвратному множеству, уменьшаются со скоростью, пропорциональной р.

Если произвести перемножение матриц и некоторые преобразования, то получим:

при нечетных k

при четных k

Нетрудно видеть, что вне зависимости от четности k

т.е. система при k -> ∞ приходит в поглощающее состояние с единичной вероятностью.

2. При анализе цепей Маркова, имеющих состояния, относящиеся к эргодическому множеству, типовой задачей является вычисление предельного вектора вероятностей нахождения процесса в каждом из состояний

Напомним, что вектор состояния X(t_k) определяется формулой (3.5)

X(t_k)=X(t₀)P^k

а k -я степень канонической стохастической матрицы имеется структуру (1.10)

При большом числе шагов, как мы установили, матрица Q^k-> Ø, а матрицы W^k и R(k) стремятся к некоторые предельным W ^k -> W_npeд, R(k) -» R _пред. Таким образом, в предельном случае

Матрицу Р_пред можно найти описанным выше способом, выполнив спектральное разложение матрицы Р и положив k —> ∞. Тогда

X_пред = X (t₀)∙ P_пред.

Однако существует более простой способ определения X_nptu. Он основан на том, что при большом числе шагов вектор X(t_k) сходится к Х_иред. Из соотношения

X(t_k+1) = X(t_k)-P, I

при k-* со следует, что X(t_k)-> X(t_k+])-> X_npeд и

X_пред = X_пред ∙ P (3-34)

Решая уравнение (3.34) относительно неизвестны x_{1 пред}, x_{2 пред}, …, x_{n пред}, при дополнительном условии

получим вектор X _пред.

Так, для предыдущего примера с матрицей (3.32) уравнение для предельных вероятностей (3.34) имеет вид:

.

Отсюда видно, что х_{1 пред} = х_{2 пред} = 0, х_3пред = 1, т.е.

X_пред=[0, 0, 1].

Этот же результат может быть получен на основе (3.33):

X _пред =X ₀ ∙ P _пред .

Понятно, что при любом Х₀ = ë x⁰₁x⁰₂x⁰₃ û (учитывая, что х⁰₁ +х⁰₂ +х⁰₃ = 1), получим то же значение вектора Х_првд.

3.6. Цепи Маркова с непрерывным временем

До сих пор мы рассматривали марковские процессы с дискретным временем. Однако в ряде случаев (например, при моделировании надежности аппаратуры) удобно иметь дело с ситуацией, когда система имеет конечное множество состояний S= {S₁,..., S_n}, а переходы из одного состояния в другое возможны в любые случайные моменты времени t. В этом случае множество моментов времени, в которые рассмат­ривается система, совпадает с числовой осью, т.е. Θ = R.

Случайный процесс с непрерывным временем называет непрерывной цепью Маркова, если поведение системы после произвольного момента времени t зависит только от состояния процесса в этот момент времени и не зависит от истории процесса, предшествующей моменту времени t.

Для непрерывной марковской цепи вероятности пребывания системы в состоянии S_i в момент

n

времени t обозначим, как и в п. 3.1. x, (t), i = l,..., n. При этом ∑ xi(t)=1, t Î Θ.

i=1

Эти вероятности образуют вектор X(t)= [x_l(t)...x_n(t)]. Предположим, что система в момент времени находится в состоянии S_i. Рассмотрим элементарный промежуток времени ∆ t, примыкающий к моменту времени t. Назовем плотностью вероятности перехода (или интенсивностью перехода) μ _ij (t) предел отношения вероятности перехода p _ij(∆ t) системы за время ∆ t из состояния S_i в состояние Sj к длине промежутка ∆ t:

Из формулы следует, что при малом ∆ t вероятность переходов с точностью до бесконечно малых высших порядков

p_ij(∆ t)≈ μ _ij (t)∙ ∆ t. (3.36)

Написанную формулу можно рассматривать как основную гипотезу теории цепей Маркова с непрерывным временем: вероятности перехода пропорциональны ∆ t и не зависят от предыстории процесса.

По аналогии с п. 3.1. назовем марковский процесс однородным, если μ _ij не зависят от времени, в противном случае имеет место неоднородный марковский процесс. Предположим, что марковский процесс однороден и известны плотности вероятностей перехода μ _ij для всех пар состояний S_i и S_j. Тогда, согласно (3.36), известны и величины p_ij(∆ t). По аналогии с формулой (3.3) имеем

или в векторной форме (по аналогии с (3.4)):

где P (∆ t)=|| p_ij (∆ t)|| - матрица переходных вероятностей на интервале М.

Вычтем из обеих частей (3.37) вектор X(t). Тогда эта формула примет вид:

где I - единичная матрица размерности п.

Поскольку сумма элементов в каждой строке матрицы P(∆ t) равна единице, т.е.

то матрицу I можно формально представить в виде

Подставив (3.39) в (3.38), приведем уравнение к виду

Поделив (3.40) на ∆ t и вычислив предел левой и правой частей этого выражения при ∆ t -> 0, имеем:

откуда получаем систему дифференциальных уравнений для вероятностей состояний:

где матрица Я имеет вид:

В координатной форме z-e уравнение системы (3.41) имеет вид:

Поскольку произведение \x_jix_i встречается в первом и во

_t0poM слагаемом правой части уравнения (3.43) с разными _а1сами, то его можно переписать иначе:

Система дифференциальных уравнений для вероятностей состояний (3.41), (3.42) или (3.44) носит имя ее автора - академика А.Н. Колмогорова.

Интегрирование этой системы по времени позволяет вычислить функции х_i(t). При этом можно

n

рассматривать систему из п -1 уравнения, поскольку ∑ x_i(t) = 1, t Î Θ.

i=1

Анализ формулы (3.44) позволяет сформулировать правила составления уравнений Колмогорова непосредственно по размеченному величинами μ _ij ориентированному графу системы. Для i-го узла графа в левой части уравнения записывается производная от вероятности х_i по времени, а в правой части - столько слагаемых, сколько дуг графа связано с рассматриваемым узлом. Каждое слагаемое равно произведению плотности вероятности перехода, соответствующей данной дуге графа, на вероятность того состояния, из которого исходит дуга графа. Если стрелка на дуге направлена к рассматриваемому узлу, то произведение берется со знаком плюс, если же стрелка направлена от рассматриваемого узла, то соответствующее произведение берется со знаком минус.

Пример. Вернемся к примеру, рассмотренному в п. 3.5 предположим, что система работает в непрерывном времени при этом вместо вероятностей p_i заданы плотности вероятностей μ _i. Плотности вероятностей μ _i, в системе непрерывным временем пропорциональны соответствующе вероятностям р_i в системе с дискретным временем. Применительно к нашей задаче положим, что

р = 1 соответствует плотность μ,

р₁ соответствует плотность μ ₁

р₂ соответствует плотность μ ₂.

Так как р₁ + р₂ = 1, то μ ₁ + μ ₂ = μ.

Размерность плотности вероятностей равна 1/с, таким образом, величина μ определяет масштаб времени динамической системы.

Граф системы показан на рисунке 3.7.

Решим данную систему дифференциальных уравнений и исследуем решение. Как уже было сказано выше, достаточно рассматривать два уравнения этой системы, например первое и второе, а x₃(t) определить из соотношения х₁+х₂+х₃ =1. Представим первые два уравнения в векторной форме:

Х = Хp, (3.47)

X(0)=X₀ ,

где в соответствии с (3.46) матрица p имеет вид

Решение системы (3.47) в матричной записи определяется формулой [14]

X(t)=X₀ ∙ e ^p. (3.49)

Воспользуемся спектральным разложением матрицы p (см. п. 3.5):

p = RΛ R^-1,

где Λ - диагональная матрица, составленная из собственных чисел матрицы p; R - матрица, составленная из собственных векторов матрицы p.

Составляем характеристическое уравнение для матрицы p:

det( p - λ I) = 0,

откуда

(μ + λ)2 = μ μ ₁,

Следовательно, λ ₁ = - μ + Ö μ μ ₁ , λ ₂ = - μ + Ö μ μ ₁.

Мы видим, что собственные числа матрицы p действительные и отрицательные.

Определим собственные векторы матрицы p:

Следовательно, матрица R имеет вид

а обратная к ней -

Таким образом, матричная экспонента примет вид

Возвращаясь к решению уравнения (3.47), представим формулу (3.49) в виде

X(t) = X₀Re^{Λ t}R^-1,

а с учетом формул (3.50), (3.51), (3.52) получим после перемножения матриц выражение для вероятностей x₁(t), x₂(t), x₃(t) в покомпонентной записи:

x₃(t)=1-x₁(t)-x₂(t).

Мы видим, что вероятности x₁(t) и x₂(t) с течением времени монотонно стремятся к нулю, а х₃(t)- к единице. Таким образом, система стремится к предельному состоянию, которое мы определили в п. 3.5. Предельные вероятности можно определить, и не решая систему дифференциальных уравнений (3.46), а положив в ней х₁ = х₂ = х₃ = 0 и рассмотрев полученную ^систему линейных алгебраических уравнений.

3.7. Моделирование надежности вычислительных систем

Рассмотрим важную область применения цепей Маркова совместно с сетями Петри - моделирование надежности систем.

Надежность - свойство объекта сохранять во времени в установленных пределах значение всех параметров, бактеризующих способность выполнять требуемые функции в заданных режимах и условиях применения, ремонта, хранения втранспортирования.

Не выходя за рамки специальности, мы ограничимся рассмотрением надежности вычислительных систем (ВС).

Для ВС отказы подразделяются на аппаратные и программного обеспечения (ПО). Аппаратный отказ - неисправность оборудования. Отказ ПО - следствие программных ошибок. Природа отказов ПО существенно отличается от природы отказов аппаратуры: ПО не подвергается износу. В силу этого хорошо разработанные методы анализа надежности технических систем нельзя автоматически переносить и использовать для анализа надежности ПО, нужны специальные методы. Время восстановления отказов ПО значительно больше, чем для аппаратной части. Восстановление, или точнее - исправление, ПО обычно производится непосредственно разработчиками ПО. Это длительная процедура, и в этом смысле отказ ПО можно воспринимать как «катастрофу».

Рассмотрим показатели надежности. которые характеризуют способность системы сохранять и восстанавливать свое исходное состояние.

Устойчивость ВС - ее способность противостоять воздействиям сбоев и отказов в работе аппаратуры и ошибок в исходных данных.

Надежность ВС - вероятность ее работы без отказа в течение определенного периода времени, рассчитанная с учетом весомости отказа для пользователя. Таким образом, надежность ВС определяется не только частотой отказа, но я последствиями, к которым приводит отказ.

Функциональная надежность - свойство системы обеспечивать получение достоверного результата или выполнение функционального задания в заданное время.

Отказ - событие, заключающееся в нарушений работоспособности объекта.

Сбой - кратковременный самоустраняющийся отказ.

Модель надежности ВС. При моделировании надежности систем приходится учитывать случайный характер отказов - событий, которые переводят систему из одного состояния (нормальной работы) в другие - неисправности, тестирования и др. В то же время причинно-следственные связи в терминах «условие - событие» удобно представлять в виде сети Петри. В соответствующей сети Петри необходимо предусматривать переходы, альтернативное срабатывание которых происходит с заданными вероятностями. Каждый из таких переходов при срабатывании порождает дерево маркировок, определяющих процессы, происходящие в системе при наступлении соответствующей альтернативы.

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

Проиллюстрируем сказанное на примере. Обратимся к рисунку 2.9 предыдущей главы, описывающему процесс обслуживания заявок в простейшей ВС, но дополнительно предположим, что в системе имеются средства тестирования. Эти средства при обслуживании каждой заявки определяют исправность системы, а в случае обнаружения неисправности включают устройство диагностики, которое определяет, является ли неисправность сбоем или отказом. В случае сбоя Происходит повторное обслуживание заявки, а при отказе сис­тема останавливается и выдает сигнал аварийного завершения.

Модель системы. Соответствующая обыкновенная сеть Петри PN приведена на рисунке 3.7. Здесь по сравнению рисунком 2.9 добавлены следующие элементы:

P₅ - ВС успешно прошла тестирование;

Р₆ - ВС не прошла тестирование;

р₇ - заявка на тестирование;

p₈ - заявка на диагностику;

р₉ - ВС находится в аварийном состоянии;

t₅ - неудачное завершение тестирования;

t₆ - удачное завершение тестирования;

t₇ - начало диагностики ВС;

t₈ - разрешение дальнейшей работы ВС (неисправность классифицируется как сбой);

t₉ - аварийное завершение работы ВС.

Начальная маркировка сети имеет вид

M₀=[ω, 0, 1, 0, 0, 0, 0, 0, 0].

В позиции pi мы предполагаем неограниченное число фишек, обозначаемое СО. Это означает, что число заявок на обслуживание всегда достаточно велико.

На рисунке 3.10 показано полное дерево маркировок рассматриваемой сети Петри, порождаемое маркировкой М₀. После 4 шагов сеть либо возвращается к начальной маркировке М₀, либо к тупиковой маркировке М₆, соответствующей аварийному состоянию ВС.

Инварианты сети. Для оценки структурных свойств построенной сети рассмотрим ее инварианты в соответствии с теорией, изложенной в пункте 2.1.6. На основе схемы рисунка 3.9 составим матрицу размерностью 9Х9:

Анализ показывает, что ранг этой матицы r_v равен 7, а дефект d_v, соответственно, равен 2. Таким образом, в рассматриваемой сети существуют два инварианта позиций два инварианта переходов.

Нетрудно убедиться, что для следующих двух векторов

выполняются условия (2.10): Y = Ǔ -V = Ø ₉. Это означает, что при работе сети сохраняется сумма фишек впозициях р₂ и р₃ (первый инвариант позиций) и в позициях р₃, р₅, р₆, р₇, р₈ и р₉ (второй инвариант позиций). В этом можно убедиться, проанализировав дерево маркировок.

Аналогично для следующих векторов-столбцов

выполняются условия (2.12) Z = V-Ŵ = Ø ₉. Это означает, что при последовательном срабатывании t₁, t₂, t₃, t₄, t₆ (первый инвариант переходов) и t₁, t₂, t₅, t₇, t₈ (второй инвариант переходов) восстанавливается первоначальная маркировка. Это также следует из дерева маркировок.

Вероятностные характеристики сети. Рассмотрим вероятностную оценку работы построенной модели. Предположим, что вероятность успешного тестирования равна P₁, соответственно, вероятность противоположного событий q₁=1-p₁. Таким образом, при маркировке М₁ вероятность срабатывания перехода t₅ и перехода к маркировке М₂, равна p₁, а, соответственно, срабатывания t₆ и перехода к М₃ равна q₁.

В случае неисправности системы вероятность сбоя при диагностике обозначим р₂, тогда вероятность аварийной остановки будет равна q₂=1-p₂. На рисунке 3.10 это выразится в том, что вероятность срабатывания перехода t₈ составит р₂, а срабатывания перехода t₉ - q₂.

Введем на дереве маркировок следующие цепочки условий и событий:

S₁ - цепочка M₀t₂M₁;

S₂ - цепочка M₂t₇M_t;

S₃ - цепочка M₃t₇M₅;

S₄ - маркировка М₆.

Отождествим указанные цепочки с состояниями системы, учтем введенные вероятности и предположим, что вероятности постоянны во времени и не зависят от предыстории процесса. В результате получим цепь Маркова, показанную на рисунке 3.11.

Матрица переходных вероятностей для данной цепи Маркова имеет вид

Мы видим, что состояния S₁, S₂, S₃ образуют множеств невозвратных состояний, а S₄ - поглощающее состояние. Можно оценить среднее число тактов пребывания в каждом из состоянийневозвратного множества

N = (I-Q)^-1, I

где Q - блок матрицы Р, описывающий переходы внутри невозвратного множества; N = ||п_ij||, где п_ij - среднее число тактов нахождения процесса в состоянии S_j при старте процессаиз состояния Si; I - единичная матрица.

В нашем случае

Рассматривая первую строку матрицы N, мы видим, что процесс в среднем будет находиться в состоянии

1 1 1

S ₁ n ₁₁ =—— раз, в состоянии S₂ n ₁₂ = —— раз, а в состоянии S₃ n ₁₃ = —— раз.

p ₁ q ₂ q₂ p₁q₂ 1

Этоозначает, что среднее время безаварийной работы системы (с учетом сбоев) составляет Т₁=п₁₁=——

1 p1q2

тактов, в том числе время безотказной работы T ₃ = п₁₂ = —. Число тактов, в которые наблюдаются сбои,

q ₂

q₁

T₃ = п₁₃ = ——. Нетрудно видеть, что Т₁ = Т₂ + T₃.

p₁q₂

Задачу моделирования надежности систем можно формулировать также в терминах цепей Маркова с непрерывным временем. Для этого вместо вероятностей наступления событий нужно учитывать плотности вероятностей перехода (интенсивность).

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

3.8. Структурный подход к моделированию систем на основе сетей Петри

Ниже кратко рассмотрены вопросы, связанные с исполь­зованием структурных методов при моделировании систем [27]. Более подробно студенты ознакомятся с этими методами в курсе по технологии разработки и САПР программных систем.

Сущность структурных методов при моделировании существующих или создаваемых систем заключается в разбиении этих систем на функциональные подсистемы, которые, в свою очередь, могут быть разбиты на более мелкие подсистемы и так далее - до получения элементарных процедур. При этом моделируемая система сохраняет целостное представление, в котором все компоненты системы взаимоувязаны. Базовыми принципами при структурном подходе являются следующие.

• Принцип декомпозиции, состоящий в разбиец_й сложных систем на более простые подсистемы, которые легь поддаются анализу и моделированию.

• Принцип иерархического упорядочения, заключающий в организации подсистем в иерархические древовидны структуры, в которых на каждом новом уровне детализиру_еТс структура предыдущего уровня.

В настоящее время структурный подход к моделир₀ ванию и проектированию систем стал общепринятым, и все перечисленные в первой главе (п. 1.4.) системы моделирования бизнес-процессов основаны на указанных выше принципах.

Цель настоящего параграфа - показать, как структурный подход может быть реализован при создании динамических моделей систем в терминах «условие-событие» на основе формализмов раскрашенных сетей Петри. Вероятностная интерпретация и исследование таких моделей могут осуществляться на базе теории цепей Маркова.

3.8.1. Основные понятия событийных моделей и их отображение в сетях Петри

Объект - реальная или виртуальная сущность, используемая в моделируемой системе. Каждый объект имеет имя и набор атрибутов.

Атрибут - характеристика объекта. Каждый атрибут имеет имя и характеризуется набором возможных значений атрибутов. Совокупность конкретных значений всех атрибутов называется состоянием объекта.

Событие - одномоментное изменение состояния объекта, состоящее в изменении значений атрибутов. Каждое событие имеет имя и может иметь собственные атрибуты события.

Процесс - устойчивая целенаправленная совокупность событий (взаимосвязанных видов деятельности, последовательность работ), которая преобразует состояние объектов.

Предусловие - значения атрибутов объектов, обходимые для наступления события; формально предусловие это логическое выражение, зависящее от значений атрибутов, истинность которого необходима для наступления события.

Постусловие - значения атрибутов после наступления события.

Рассмотрим теперь, как перечисленные понятия обозначаются в терминах раскрашенных сетей Петри.

• Процесс моделируется составным переходом (непримитивным событием).

• Объект моделируется позицией.

• Каждый атрибут моделируется цветовым множеством, а набор возможных значений атрибутов - набором цветов.

• Состояние объекта моделируется маркировкой позиции.

• Начальная маркировка соответствует состоянию системы при начале ее работы.

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

• Предусловия моделируются выражением на дугах типа р to t.

• Постусловия моделируются маркировкой позиций после срабатывания переходов.

3.8.2. Диаграммы условий и событий

Диаграммы моделей процессов строятся на базе так называемых элементарных сетей. Такая сеть состоит из входных и выходных позиций и единственного перехода, который в общем случае является составным. Пример элементарной сети сказан на рисунке 3.12. В сети имеется составной переход t, входные позиции р₁, р₂, выходная позиция р₃ и позиция р₄, которая является как входной, так и выходной.

Элементарная сеть моделирует наступление некоторого сложного («непримитивного») события при сложившихся предусловиях, в результате чего подсистема переходит в новое состояние, которое рассматривается как постусловия.

Формально работа элементарной сети состоит одномоментном преобразовании состояния входных выходных позиций при срабатывании перехода t, который д_а данном этапе детализации процесса может рассматриваться как простой переход.

Как и в других методологиях структурного анализа построение модели начинается с создания контекстной диаграммыв виде элементарной сети нулевого уровня. На этом этапе определяются:

• все внешние объекты системы, их атрибуты и возможные значения этих атрибутов;

• единственное событие, отражающее основную функцию системы;

• список предусловий, необходимых для наступления события в терминах значений атрибутов внешних объектов;

• список постусловий, складывающихся в результате наступления события, в терминах значений атрибутов внешних объектов.

Дальнейшее построение модели заключается в ее последовательной детализации, т.е. в раскрытии структуры составных переходов, которые также должны быть представлены в виде комбинации элементарных сетей. Введенные на предыдущем уровне детализации позиции становятся внешними на следующем уровне. Таким образом получаются диаграммы первого, второго и последующих уровней. На каждом уровне определяются вновь появившиеся объекты, их атрибуты, непримитивные события, пред- и постусловия.

Этот процесс завершается в том случае, когда разработчик все события на очередной диаграмме рассматривает как простые. При этом в модели не остается составных переходов.

По мере детализации диаграмм определяется и уточняется содержание ее элементов - объектов, атрибутов, условий, событий. Для сохранения единообразия при построении и использовании моделей рекомендуется придерживаться следующих правил.

• Условие определяется глаголом в совершенного вида в сочетании с поясняющими словами. В тех случаях, когда смысл условия очевиден, глагол может подразумеваться и поэтому опускается. Примеры условий: пароль проверен, сумма (оказалась) меньше запрошенной, список паролей (имеется).

• Событие определяется глаголом в несовершенного вида в сочетании с поясняющими словами. Например: пароль проверяется, клиент обслуживается.

При построении диаграмм следует придерживаться рекомендаций, которые являются общими для всех методо­логий структурного моделирования. Укажем некоторые из них:

• на каждой диаграмме должно быть от 3 до 6 элементарных сетей;

• выбирать ясные, отражающие суть дела имена объектов, атрибутов, условий и событий;

• не загромождать диаграммы несущественными на данном уровне деталями.

Полный список рекомендаций приводится в литературе по CASE технологиям [4].

Параллельно с построением иерархии диаграмм формируется описани