Алгоритм одного розыгрыша

Моделирование надежности программного обеспечения

Автор:

Ханджян А.О.

Постановка задачи

Имеется программный комплекс (ПК) типа клиент-сервер. Сервер обслуживает запросы от N клиентов. В ПК равномерно по области определения входных данных (ООД) (A , B) расположены Er ошибок. Сервер сложнее клиентов с точки зрения разработки ПК в S раз. S – коэффициент сложности сервера по отношению к клиентам. Каждый k-ый (k = 1, 2, …, N) клиент порождает пуассоновский поток данных к серверу интенсивностью l _обр. Данные от клиента распределены по области определения данных (ООД) по нормальному закону с характеристиками m_k и s _k, где m_k распределено между клиентами равномерно по всей области входных данных, 3 s _k – распределено равномерно на меньшем из участков отсекаемых m_k на оси области данных (это нужно для имитации неравномерности использования ООД при малом количестве клиентов).

На запрос клиента сервер отвечает данными, которые распределены равномерно по всей области определения данных (A , B).

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

Рисунок 1 – «Распределение запросов k-го клиента на области данных»

Входными данными для розыгрыша являются:

P – количество программистов, обслуживающих систему;

K - количество программ-клиентов (далее просто клиенты);

a - ширина одного запроса клиента как доля от ООД (от 0 до 1, где 1 – это вся ООД);

D t - шаг итерации (сутки);

s - коэффициент сложности сервера по сравнению с программой-клиентом;

l _обр - интенсивность потока обращений одного клиента к серверу (1/сутки);

l_испр - интенсивность потока исправления ошибки одним программистом (1/сутки);

l_внес - интенсивность внесения ошибки при исправлении одним программистом (1/сутки) или

p_внес – вероятность внести ошибку при исправлении одним программистом;

M - количество итераций;

К – количество розыгрышей для усреднения;

Er - начальное количество ошибок.

В программе также есть возможность оценить первоначальное количество ошибок по следующему алгоритму: Принимаем ООД за единицу. Каждый клиент в запросе генерирует долю a от ООД. За время D t клиент обратиться к серверу ( D t * l_обр) раз. За время D t все клиенты обратятся к серверу ( D t * l_обр * K) раз. И объем данных, который будет затронут в ООД при этом равен ( D t * l_обр * K * a). Так как в нашей модели ошибки распределены равномерно по ООД, то за время D t будет обнаружено ( D t * l_ош), где l_ош – первоначальная интенсивность ошибок в системе. Если бы за время D t клиенты затронули всю ООД, то было бы обнаружены все Er ошибок. Поэтому можно записать следующую пропорцию: . Отсюда находим Er: . При этом считаем, что каждый из K клиентов обратился к серверу с запросом с данными непересекающимися в ООД. Но на самом деле это не так, т.к. чаще сего клиенты обращаются к серверу с однотипными запросами, поэтому полагаем K = 1. И тогда окончательная формула для оценки первоначального количества ошибок будет: ;

Программа предупреждает, если задается интенсивность такая, что на интервал времени D t приходится больше одного события (т.е (D t * l) должно быть меньше единицы) – для соблюдения условия ординарности потока событий.

Алгоритм одного розыгрыша

При одном розыгрыше выполняются следующие шаги:

1.Разыгрывается размещение Er ошибок в клиентах на ООД, распределенных на ней равномерно;

2.Разыгрывается размещение ( s * Er _к )/10 ошибок в сервере на ООД, распределенных на ней равномерно;

3.Для каждого из K клиентов разыгрывается в начале и только один раз m_ki и s _ki.

4.Далее итеративно с шагом D t для каждого клиента:

a. Если клиент исправен, то он может обращается с запросами к серверу с интенсивностью l_обр. Вероятность обращения клиента к серверу равна . В случае обращения клиента к серверу разыгрывается случайная величина x_i, распределенное по нормальному закону с параметрами m_ki и s _ki – входное данное для запроса к серверу. Область, занимаемая входными данными запроса от одного клиента к серверу на ООД, есть случайная величина, распределенная равномерно на отрезке от 0 до a /2 (обозначим ее как Rand( a /2))

b. Если в интервал (x _i ± Rand( a /2)) попадает хотя бы одна ошибка на ООД, то считается, что в клиенте обнаружена ошибка, и он выводится из эксплуатации для ее исправления одним из свободных программистов. Если свободных программистов нет, то неисправный клиент становится в очередь и ожидает, когда один из программистов освободится.

c. Если в запросе клиента к серверу ошибки нет, то этот запрос направляется серверу на обработку и ответа. При этом разыгрывается ответ от сервера клиенту аналогично a), только объем данных есть случайная величина, распределенная равномерно на отрезке от 0 до a *10/2 (обозначим ее как Rand( a *10/2)). Если в область (x_i ± Rand( a *10/2)) попадает хотя бы одна ошибка из списка ошибок сервера, то считается, что в сервере произошла ошибка. В этом случае работа системы останавливается и все программисты пытаются исправить эту ошибку в сервере со скоростью l_испр каждый. Вероятность исправления ошибки одним программистом равна .

d. Если в клиенте есть ошибка и есть свободный программист, то свободный программист пытается исправить ошибку в клиенте с вероятностью .

e. Если ошибка исправляется, то она удаляется из списка ошибок клиента или сервера соответственно. Таким образом, эта ошибка уже не может возникнуть в других клиентах. При этом если есть клиенты, в которых была обнаружена такая же ошибка, то эти клиенты считаются тоже исправленными. При исправлении ошибки каждый программист может внести новую ошибку с вероятностью  или p_внес. Причем, если программист внес ошибку в программу, то он может внести туда еще одну ошибку с вероятностью равной квадрату вероятности внесения предыдущей ошибки. Вновь внесенные ошибки вносятся в список ошибок клиентов или сервера соответственно. При этом эти новые ошибки не считаются обнаруженными в клиенте или сервере, то есть если обнаруженная ошибка исправляется, то клиент или сервер считается исправленными даже, если при этом были сделаны новые ошибки.

f. За один временной такт D t разыгрывается сценарий обмена данными для всех работающих на этот момент времени клиентов. Для неисправных клиентов или неисправного сервера разыгрывается вероятностный процесс исправления ошибки в них.

5.В результате разыгрывается M итераций согласно п. 4, и получаем одну реализацию случайных функций ,  и  (средние численности работающих, неработающих, клиентов и вероятность работы сервера) на временном интервале M* D t.

6.Испытания проводим еще K раз и таким образом получаем K реализаций случайных функций , ,  и . Для каждого момента времени t _j (для j = 1, … M) с шагом D t находим статистическое среднее для этих функций и получаем средние функции , ,  и .

7.Также в процессе розыгрыша производится:

- расчет текущего времени наработки до отказа;

- расчет среднего времени наработки до отказа за все время розыгрыша;

- расчет вероятности отказа ПО в единицу времени как P = (<объем запроса> * <количество ошибок в клиентах и сервере> * (<количество работающих клиентов> + 1) * <интенсивность обращение> * <шаг итерации по времени>;

- расчет коэффициента готовности: К_г = 1 - <время простоя всей программы> / <время работы>

Количество ошибок в сервер рано количеству ошибок в клиентах * коэффициент сложность /10.