Разработка программно–алгоритмических средств для определения надёжности программного обеспечения на основании моделирования работы системы типа "клиент

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

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

Допустим, что каждый модуль может быть в любом из n возможных состояний: x1, x2, …, xn, а состояние системы S в каждый момент времени характеризуется числом элементов (модулей), находящихся в каждом из этих состояний. Исследуем процесс, протекающий в системе S. Отвлечемся от возможных состояний системы в целом (а именно, SN, 0, …, 0 – все модули находятся в состоянии x1, а в других состояниях нет ни одного элемента; SN–1, 1, …, 0 – один элемент находится в состоянии x2, все остальные – в состоянии x1 и так далее. Очевидно, таких состояний будет очень много – N!), поэтому рассмотрим отдельный модуль x (так как все модули одинаковы) и рассмотрим для него граф состояний (рис.9).

Введем в рассмотрение случайную величину Xk(t) – число модулей, находящихся в момент времени t в состоянии xk. Будем ее называть для краткости численностью состояния xk в момент t. Очевидно, что для любого момента времени t сумма численностей всех состояний равна общей численности модулей:

Xk(t) для любого фиксированного момента времени t представляет собой случайную величину, а в общем случае – случайную функцию времени. Найдем для любого t основные характеристики случайной величины – ее математическое ожидание mk(t) = M[Xk(t)] и дисперсию Dk(t) = D[Xk(t)].

Рисунок 9 – Граф состояний одного модуля

Для того, чтобы найти эти характеристики, нам надо знать интенсивности всех потоков событий, переводящих модуль (элемент) (не всего комплекса программ, а именно модуль) из состояния в состояние (см. рис.9). Тогда численность каждого состояния Xk(t) можно представить как сумму случайных величин, каждая из которых связана с отдельным (i–тым) модулем, а именно: равна единицы, если этот модуль в момент времени t находится в состоянии xk, и равна нулю, если не находится в этом состоянии:

(1)

Очевидно, для любого момента времени t общая численность состояния xk равна сумме случайных величин (1):

По теореме сложения математических ожиданий и теореме сложения дисперсий получаем:

(2)

Найдем основные характеристики – математическое ожидание и дисперсию – случайной величины

, заданной выражением (1). Эта величина имеет два возможных значения: 0 и 1. Вероятность первого из них равна pk(t) – вероятности того, что модуль находится в состоянии xk (так как программные модули одинаковы, то для всех эта вероятность одинакова). Ряд распределения каждого из случайных величин

один и тот же и имеет вид:

возможное значение (xj):	0	1
вероятность (pj):	1–pk(t)	pk(t)

Математическое ожидание случайной величины, заданное таким рядом, равно:

А дисперсия:

Подставляя эти вероятности в формулы (2), найдем математическое ожидание и дисперсию численности каждого состояния Xk(t):

(3)

(4)

Таким образом, нам удалось для любого момента времени t найти математическое ожидание и дисперсию численности состояния xk. Зная их, можно для любого момента времени t указать ориентировочно диапазон практически возможных значений численности:

Итак, не определяя вероятностей состояний программной системы S в целом, а опираясь только на вероятности состояний отдельных модулей, можно оценить, чему равна для любого момента времени t численность каждого состояния. Если мы знаем вероятности всех состояний одного модуля p1, p2, …, pn, как функции времени, то нам известны и средние численности состояний m1, m2, …, mn и их дисперсии D1, , D2, …, Dn.

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

Заметим, что вместо дифференциальных уравнений для вероятностей состояний удобнее писать уравнения непосредственно для средних численностей состояний, что видно из (3).

2.3.2 Модель с заменой вероятностей состояний на средние численности состояний

Пусть программа S состоит из N одинаковых модулей (или потоков) и граф состояния каждого модуля представлен на рисунке:

Рисунок 10 –Граф состояний модуля

В начальный момент времени t = 0 все модули находятся в состоянии x1.

Непосредственно по графу (см. рис. 10) составляем уравнения Колмогорова для вероятностей состояния;

(5)

Умножим левую и правую части каждого из уравнений (5) на число модулей N и введем в левых частях N под знак производной, а также учтем (3), тогда:

(6)

В системе уравнений (6) (которые называются уравнениями динамики средних) неизвестными функциями являются уже непосредственно средние численности состояний (точнее математические ожидания численности состояний). Как видно, эти уравнения составлены по тому же правилу, что и уравнения для вероятностей состояний. Поэтому их можно было составить сразу, минуя промежуточный этап.

Очевидно, что для каждого момента времени t средние численности состояний удовлетворяют нормировочному условию:

(7)

И поэтому одно (любое) из уравнений системы (6) можно отбросить. Отбросим, например, третье уравнение из (6), а в остальные уравнения вместо m3 подставим выражение согласно (7):

Тогда окончательно получим:

(8)

Эту систему нужно решать при начальном условии: t = 0; m1 = N; m2=m3=m4=0.

Решение такой системы дифференциальных уравнений (а для стационарного режима – системы алгебраических уравнений) легко провести на ЭВМ методом численного интегрирования.

Предположим, что это осуществлено и нами получены четыре функции m1(t), m2(t), m3(t) и m4(t). Найдем дисперсии численностей состояний D1(t), …, D4(t).

Из (3) и (4) следует:

где k = 1, … – число состояний модуля(9)

Зная математические ожидания и дисперсии численности состояний, мы получаем возможность оценить и вероятности различных состояний системы в целом, то есть вероятность того, что численность какого–то состояния будет заключена в определенных пределах. Действительно, так как число модулей N в программной системе велико, то по закону больших чисел можно полагать, что численность k–го состояния приближенно распределено по нормальному закону. И, следовательно, вероятность того, что случайная величина Xk (численность k–го состояния) будет заключена в границах от a до b, будет выражаться формулой: