6. Модель оценивания надежности программного обеспечения на основе форсирования процесса его тестирования

Целесообразно ли применение моделей ускоренных испытаний для оценивания надежности программных средств? Ответ на этот вопрос, на наш взгляд, положителен. Однако научно обоснованных моделей в настоящее время в технической литературе не содержится. В [28] под форсированием испытаний программного обеспечения понимается испытание повышением интенсивности искажений исходных данных, расширением варьирования их значений, а также специальным увеличением потоков информации и загрузки функционирующего программного обеспечения на средстве вычислительной техники выше нормальной. Планирование подобных испытаний должно предусматривать пересчет показателей надежности к нормальным условиям функционирования. Основной целью таких испытаний является испытание функционирования программного обеспечения при перегрузках памяти и производительности вычислительных средств, т.е. ресурсов их производительности.

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

Предположим, что длительность тестирования программного обеспечения на штатном вычислительном средстве с быстродействием Во равна t 0 единиц времени. Вероятность ошибки на одну команду в вычислительном средстве с быстродействием В равна , где b о – вероятность ошибки на одну команду в вычислительном средстве с быстродействием Во, а a – коэффициент пропорциональности вероятности ошибки быстродействию вычислительного средства. в есть быстродействие технологического (испытательного) вычислительного средства. Спрашивается, каково должно быть время тестирования программного обеспечения на технологическом средстве t Т с быстродействием В>Во, чтобы вероятность отсутствия ошибки на штатном средстве за время t о была бы равна вероятности отсутствия ошибки на технологическом средстве?

Считая вероятность ошибки на одну команду b малой величиной запишем выражение для вероятности отсутствия ошибки за время испытаний программы на технологическом средстве [29]:

. (75)

Вероятность отсутствия ошибки на штатном средстве за время испытаний t о будет равна

(76)

Приравнивая (75) и (76) находим

(77)

где kв = В/Во – коэффициент форсирования быстродействия. Рассмотрим пример. Пусть Тогда из (77) получим . Если a =0, тогда t Т = t 0/kв. Данный пример иллюстрирует возможность реализации процесса форсированного тестирования программного обеспечения на технологическом вычислительном средстве для обнаружения и устранения ошибок.

Модель пересчета (75)–(77) должна строится с учетом особенностей структуры программного обеспечения, штатного и технологического вычислительных средств.

7. Модель оценивания производительности сетевой структуры с ненадежными узлами

Закономерной тенденцией научно-технического прогресса является внедрение информационно-вычислительных сетей в самых различных областях человеческой деятельности [30]. В качестве основного показателя, характеризующего работоспособность сетей, как правило, используется их пропускная способность, производительность. Основным математическим аппаратом оценивания производительности сетей являются модели теории массового обслуживания [11,31] и др. Существенный недостаток этих моделей заключается в том, что затруднительно одновременно учитывать в них процессы отказов и восстановлений наряду со стохастичностью процессов обслуживания заявок в узлах сети. Это усугубляется еще и тем, что траектория информационного потока в сети случайна. Случайность выбора элемента траектории в сети определяется случайным выбором управляющего воздействия в зависимости от исхода результата предшествующей обработки информации в сети и др.

В качестве моделей исследования надежности сетей используются широко известные модели теории надежности [21,32] и др. с учетом принятия во внимание переменности структур информационных сетей или информационных направлений в системах связи [33].

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

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

Постановка задачи. Рассмотрим структуру информационно-вычислительной сети, состоящей из М узлов, представимую в виде разомкнутой сети массового обслуживания. Изобразим сеть в виде ориентированного графа, нулевая вершина которого (исток) идентифицирует источник заявок, вершины 1, 2, ..., М-узлы сети, а (М+1)-я вершина – выход (сток) сети. Переходы заявки между узлами случайны, заданы стохастической матрицей вероятностей перехода (rij). Дисциплины обслуживания заявок в узлах произвольные. Очереди в узлах не ограничены. Потоки заявок, поступающие в узлы сети рекуррентны, взаимно независимы. Распределения времен обслуживания в узлах произвольны. Режим работы сети стационарный. Законы распределения времен до отказа узлов и времени их восстановления произвольны. Восстановление узлов придает им первоначальные свойства. Узлы сети статистически независимы. Контроль за состоянием узлов идеальный. Нарушением механизма прохождения заявки через узел из-за прерывания работы узла на время его восстановления и потери части заявок, пришедших за это время в узел, пренебрегаем. Требуется определить показатель качества работы любого узла и всей информационно-вычислительной сети для стационарного режима работы.

Модель узла сети. При длительном процессе эксплуатации стационарная вероятность непрерывной работы i-го узла сети в течение времени t находится по формуле [34]:

, (78)

где Тi, q i – средние времена работы узла до отказа и восстановления, Pi (z) – вероятность безотказной работы узла в течение времени z. Величину (78) в теории надежности называют коэффициентом оперативной готовности.

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

(79)

где d – дельта-функция Дирака. Плотность вероятности (79) является условной. Она справедлива для случая, когда начало отсчета – момент поступления заявки – попадает на интервал времени работоспособности узла. Использование (79) непосредственно представляет некоторые трудности математического характера, поэтому найдем значения начальных моментов величины Yi.

Изображение Лапласа (79) приводит к выражению

(80)

откуда j-й условный начальный момент случайной величины Y будет равен

(81)

а безусловный –

(82)

Из (82) запишем первые два начальных момента и коэффициент вариации безусловной случайной величины Yi:

. (83)

Для пояснения формул (81)–(83) рассмотрим простейший пример. Пусть . Тогда из (81) следует (индекс i в правой части формул опущен):

(84)

Из (82) получим

(85)

В формулах (84), (85) Кг означает коэффициент готовности узла. Через Кпр обозначено отношение , где y i – среднее время пребывания заявки в узле. В дальнейшем по аналогии с коэффициентом готовности будем называть этот коэффициентом “коэффициентом производительности узла”. Он принимает единичное значение в том случае, когда среднее время пребывания заявки в узле y i =0.С увеличением y i величина его уменьшается до нуля. Коэффициент Кс не имеет названия и вводится для кратности записи.

Величина уi,1=КгКпр есть среднее значение вероятности обслуживания заявки ненадежным узлом. Она равна произведению коэффициентов готовности и производительности узла.

В общем случае, когда распределения произвольны, среднее значение вероятности обслуживания заявки узлом находится по формуле:

(86)

Модель сети. Основана на вероятностной независимости узлов сети .Это оправдывается для стационарного режима функционирования сети. Рассмотрим матрицу

. (87)

Каждый элемент матрицы ri jPi равен произведению вероятности обслуживания заявки i-м ненадежным углом на вероятность перехода после обслуживания из i-го узла в узел j. Вероятности обслуживания заявки в 0 и (М+1) узлах принимают равными единице.

Вероятность обслуживания заявки от i-го до j-го узла сети будет равна элементу с номером (i, j) матрицы вида

, (88)

где I – единичная матрица. Элемент с номером (i, j)–Pi, j, будет равен

, (89)

где Аi, j – алгебраическое дополнение элемента с номером (i, j) матрицы IG, а R – ее определитель. Если нас интересует вероятность обслуживания заявки в сети, равная элементу с номером (0, М+1), то из (88) следует

. (90)

Таким образом, если известна топологическая структура информационно-вычислительной сети, задана стохастическая матрица передач (ri, j), распределения времени до отказа и времени восстановления, а также распределения времени пребывания заявки для всех узлов сети, то, пользуясь выражениями (86)–(90), можно найти вероятность обслуживания заявки в ненадежной сети в целом или, в частности, между двумя любыми ее узлами – вероятность обслуживания заявки нужным информационным направлением.

Получаемая вероятность обслуживания заявки в сети является средней величиной (условным математическим ожиданием) и определяется первыми начальными моментами трех рассматриваемых распределений. Распределение времени пребывания заявки в узле (первого начального момента) необходимо определять методами теории массового обслуживания.

Пример. Необходимо оценить вероятность обслуживания заявки в сети, стохастический граф которой изображен на рис.4. Решение поставленной задачи в общем виде на основании полученных выражений примет вид

, (91)

где

Поэтому

. (92)

Например, для числовых данных Кг1=0,8; Кг2=0,6; Кг3=0,9; Кпр1=0,9; Кпр2=0,95; Кпр3=0,99; р=0,3, из формулы (92) следует, что Р0, 4=0,51.

Рис.4

Мы рассмотрели только решение задачи оценивания искомой вероятности Р0, M+1. Если необходимо решить задачу обеспечения требуемой вероятности или достижения максимальной вероятности обслуживания заявки в сети в рамках определенных ограничений, тогда необходимо решить оптимизационную задачу так, как например, показано в п.2 на основе применения неопределенных множителей Лагранжа. Но в этом случае необходимо знать функциональные зависимости коэффициентов готовности и (или) коэффициентов производительности узлов сети от величин затрат, расходуемых на их изменение.

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

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

, (93)

где М, z – символ и переменная Меллина.

Тогда j-й начальный момент случайной величины находится по формуле:

. (94)

Естественно, что величина (94) может быть получена и из (80) путем j-кратного дифференцирования преобразования Лапласа плотности (79), домножения результата на (–1)j и приравнивания переменной s к нулю. Но, в отличие от (94), нас интересуют не моменты случайных величин узлов, а моменты случайной величины, присущей всей сети.

Если случайная величина, характеризующая качество сети, складывается из суммы случайных величин, присущих тем узлам сети, которые последовательно проходит обслуживаемая заявка на выбранной случайной траектории сети, то для нахождения ее плотности вероятности и начальных моментов следует в матрице вида (87) использовать преобразование Лапласа (80) для каждого ее элемента. Искомый результат, получаемый после преобразования матрицы, будет представлен также в преобразовании Лапласа, а моменты случайной величины находят, как и прежде, дифференцированием результата по переменной Лапласа. Подобным образом определяется случайная величина времени пребывания заявки в сети и ее моменты [11]. Выбор конкретной траектории следования заявки в сети определяется произведением соответствующих вероятностей перехода между узлами.

В нашем случае каждому узлу сети приписана случайная величина вероятность обслуживания заявки в нем. Определяется случайная величина вероятность обслуживания заявки в сети. Поэтому конкретная выбранная траектория следования заявки будет характеризоваться произведением случайных величин узлов, а выбор самой траектории, как и прежде, произведением соответствующих вероятностей перехода между узлами траектории. Таким образом, в матрице (87) вместо величин Рi следует помещать выражения для из (93). Матрицу Т и интересующий исследователя элемент сети находят по тем же правилам:

, (95)

которые ранее были указаны без индекса М. Начальный момент k-го порядка определяется из второй формулы (95) после подстановки в нее z=k+1. Так, для приведенного примера будем иметь

. (96)

Из (96) при z =2 получим выражение (91), а величина k-го момента вероятности обслуживания заявки в сети будет равна:

. (97)

8. Модель скоростного распределения вероятностей

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

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

В математической статистике для оценивания показателей надежности по результатам испытаний могут успешно использоваться так называемые фидуциальные распределения[35]. Идея построения подобных распределений принадлежит R.A.Fisher [36]. Она заключается в том, что у некоторых распределений вероятностей параметрического типа значение переменной может восприниматься как фиксированное значение параметра, а значение параметра распределения –как значение переменной. В качестве простого примера рассмотрим нормальную плотность

(98)

в которой -среднее значение и среднеквадратическое отклонение случайной величины Х, а х – переменная величина.

Для (98) фидуциальным распределением (плотностью) является

, (99)

где х – среднее значение случайной величины М, а m – переменная величина. В нашем понимании “инверсное” и фидуциальное распределения тождественны.

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

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

В рассматриваемых условиях поток событий А образует простой процесс восстановления [18] с функцией распределения интервалов между событиями В(t). Поэтому математическое ожидание числа восстановлений, математическое ожидание квадрата числа восстановлений и т.д. за время t будут соответственно равны:

(100)

……………………………………

Здесь Е – символ математического ожидания, Н(t) – функция восстановления.

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

Для упрощения решения поставленной задачи найдем стационарные значения этих плотностей. Воспользуемся выражением для производящей функции факториальных моментов простого процесса восстановления[18]:

(101)

где - изображение Лапласа плотности распределения времени между событиями потока А, s – переменная преобразования. Последовательно дифференцируя (101) по и приравнивая =1, а также устремляя s ® 0, получим значения начальных моментов искомой случайной величины скорости наступления события А в потоке:

и т.д. (102)

В выражениях (102) где i – номер производной по (101), а T=. Величина Т означает среднее значение времени между событиями А потока.

Используя метод моментов, можно найти по найденным начальным моментам скорости потока (102) стационарное аппроксимирующее распределение [37]. Очевидно из (102), что в данном случае оно будет экспоненциальным

, (103)

где n – число событий, наблюдаемых в единицу времени, переменная распределения, а Т – его параметр. В [37] это распределение было названо “инверсным” из-за неизвестности автору термина “фидуциальное распределение”.

Предположим, что начальные моменты случайной величины скорости не являются такими, как указано в (102). Тогда необходимо выполнить аппроксимацию плотности вероятности по известным моментам в некоторой базовой системе функций. Например, в [37] предложено использовать гиперэкспоненциальную аппроксимацию с комплексно-сопряженными коэффициентами и параметрами составляющих экспоненциальных плотностей. На наш взгляд, для этой же цели можно воспользоваться и методами теории случайных процессов[38].

В общем случае полагаем, что параметр Т может быть функцией скорости n (как интенсивность отказа l(t) является функцией времени t). Действительно, если положить, что относительное изменение дополнительной функции распределения значения скорости равно некоторому отрицательному значению параметра, зависящему от величины n, и выполнив решение полученного дифференциального уравнения при начальном условии РN (0)=1, будем иметь

. (104)

Таким образом, на основе нашего предложения в общем случае можно допустить существование скоростного распределения в виде (104).

Распределения (103), (104) являются непривычными для понимания, однако с ними можно работать как с любыми известными распределениями. Так, например, если скорость наступления события случайна и известно ее распределение (104), можно найти условную вероятность того, что скорость будет не менее n, если наблюдается ее значение n1

. (105)

Условная плотность распределения величины скорости определится как

, (106)

где а(n+n1) – безусловная плотность распределения величины скорости. Безусловная и условная интенсивности изменения скорости соответственно равны

.

Если производится суммирование случайных скоростей к источников, то вероятность того, что значение скорости n имеют все источники, с распределением для каждого из них (104), будет определяться в виде

. (107)

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

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

В качестве простейшего примера прикладного характера рассмотрим задачу определения оценки средней скорости некоторого источника событий по выборке объема из N0 источников. Измерялась скорость у всех N0 источников. Предельное значение измеряемой скорости равно n. Распределение скорости источника экспоненциальное, но параметр его неизвестен. Значения скоростей n1, n2, n3, …, nr <n дали r источников, остальные N0r источников дали значение скорости больше величины п. Пользуясь выражением (103), на основании метода максимального правдоподобия получим оценку средней скорости источника

. (108)

Тогда параметр распределения (103) будет равен

.

Рассмотрим следующий пример. Назовем величину показателя экспоненты (104) скоростным ресурсом источника и обозначим

, (109)

где e – режим работы источника (фактор внешних условий). Предположим, что существует такой класс режимов работы источника e О Е, что ресурс (109) является инвариантным внутри этого класса. Тогда по аналогии с физическим принципом надежности [16] можем утверждать, что

, (110)

при условии P(n1, e 1)=P(n2, e 2); P(n, e ) означает вероятность того, что скорость источника в режиме e будет не менее n. Выражение (110) означает, что остаточные дополнительные распределения скоростей двух источников, работавших в различных режимах e 1 и e 2 и выработавших одинаковый скоростной ресурс (109), будут одинаковыми. Соотношения (110) могут подтверждаться или отвергаться экспериментальным путем для различных источников. Подобный подход может быть применен для оценки качества работы источника в переменных условиях среды, а также в решении задачи форсированного испытания источников [22].

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

, (111)

где l (t) – параметр распределения (интенсивность наступления события). Предполагаем, что начальные моменты распределения (111) конечны. Требуется построить скоростное распределение

(112)

где Т(n) – параметр распределения (среднее время до наступления события).

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

(113)

где А, В, a , b – неизвестные параметры. Значения этих параметров найдем из системы нелинейных алгебраических уравнений:

(114)

.

Распределения (111), (112) по форме аналогичны, но имеют различное смысловое содержание. Оба распределения будут равными, если показатели их экспонент равны. О совпадении начальных моментов этих распределений такого утверждения сделать нельзя. Моменты первого распределения измеряются единицей времени, моменты второго – единицей, обратной времени.

Для простейшего случая получим следующий очевидный результат. Если плотности будут , то соответствующие начальные моменты равны:

.

Если значения параметров удовлетворяют равенству l =1/Т, то нетрудно заметить, что справедливо выражение

(115)

Пусть – изображения Лапласа плотностей вероятностей распределений (111), (112). Тогда, при условии существования у них начальных моментов, справедливы разложения:

. (116)

Принимая во внимание то, что переменная Лапласа s в обоих разложениях размерна, имеет обратную размерность, соответствующие моменты имеют обратную размерность, а одноимённые члены разложений безразмерны, можем утверждать, что выражение (115) будет справедливо и в общем случае, т.е. для произвольных показательных распределений (111), (112). Поэтому справедлив следующий алгоритм получения значений моментов скоростного распределения (112). Сначала определяются значения моментов для (111) – . Составляется система уравнений (114).Затем в правые части системы вместо значений моментов ставятся, согласно (115), значения . Система решается относительно неизвестных , c помощью которых из выражения (113) получается выражение для плотности вероятности распределения (112). Точность аппроксимации в общем случае будет определяться числом учитываемых моментов .

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

(117)

Требуется построить . Решая систему (114) как показано в [40], с учётом (115), получаем

. (118)

Подставляя значения (118) в (113), получим искомое решение. В частном случае, например, когда k=2, будем иметь:

(119)

где .

Пример 2. Плотность временного распределения задана в виде

Требуется найти плотность скоростного распределения, пользуясь тремя начальными моментами. Определив моменты , подставив в (114) значения

и решив данную систему уравнений, получим

Согласно (113) приближённое значение плотности скоростного распределения

(120)

где .

Здесь мы только показываем принцип построения скоростного распределения по временному распределению, но не обсуждаем детально точностные аспекты построения. Поэтому гиперэкспоненциальное распределение выбрано лишь для демонстрации принципа построения. Известно [37] множество способов аппроксимации распределений. Выбор необходимого способа может зависеть от ряда факторов, таких как форма распределения, величина коэффициента вариации и других его параметров. В каждом конкретном случае такой выбор должен осуществляться самим исследователем. Однако, независимо от выбранного способа аппроксимации распределения, следует сделать одно замечание о связи коэффициентов вариации временного и скоростного распределений, обусловленной зависимостью (115). После очевидных преобразований с учётом (115) получим следующее уравнение

, (121)

где – коэффициенты вариации скоростного и временного распределений.

На рис.5 показана зависимость h N от h T для положительных их значений. Из графика следует, что большому значению коэффициента вариации одного распределения соответствует малое значение коэффициента вариации другого распределения. Справедливо и обратное в силу симметричности приведённой зависимости. Это обстоятельство накладывает определённые требования к выбору аппроксимирующего распределения. Если временному распределению присущ достаточно большой коэффициент вариации, то аппроксимирующее скоростное

Рис.5

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

Некоторые приложения скоростного распределения.

Приложение 1.

Источник формирует в единицу времени случайное число заявок на обслуживание. Заявки могут обслуживаться одновременно несколькими объектами. Число обслуживаемых заявок в единицу времени одним объектом является случайной величиной. Случайные производительности (скорости) источника заявок и объекта обслуживания определены плотностями вероятности Значения параметров известны: T3=0,5 мин, Т0=1 мин. Требуется определить необходимое число объектов обслуживания k, чтобы математическое ожидание вероятности обслуживания случайного числа заявок источника было не менее 0,97.

Так как все объекты обслуживания идентичны, то плотность вероятности значения суммы скоростей k объектов

(122)

а вероятность того, что суммарная скорость будет не менее n

. (123)

Но в (123) величина потребной скорости n является величиной случайной, так как она определяется случайной величиной скорости источника заявок. Заметим, что вероятность (123) является монотонно убывающей функцией от n и монотонно возрастающей функцией от k. Поэтому плотность вероятности величины (123) можно представить в виде:

(124)

Вероятность того, что случайная величина Y і n будет равна

. (125)

Вычислить (125) в замкнутом виде затруднительно. Потому ограничимся нахождением математического ожидания искомой вероятности. Применяя к (124) преобразование Лапласа по переменной y, получим

. (126)

Из (126) найдём величину математического ожидания

. (127)

где индекс (1) – номер первого момента вероятности как случайной величины, а s в (126) – переменная Лапласа.

Подставляя в (127) выражения для Р0, k из (122) и f3(n), производя простые преобразования, получим

. (128)

Из (128) для заданных значений параметров Т3, Т0 находим, что kі 5. Ещё раз напомним, что приведенное решение получено с точностью математического ожидания вероятности обслуживания заявок. Под заявками и объектами обслуживания могут пониматься различные системные элементы.

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

Пусть fx (x, mx), fy (y, my) – плотности распределения производительностей (скоростей производства) предприятий, зависящие от значений mx, my – чисел производственных единиц мощностей, на которые наложено ограничение mxgx + mygy Ј G. Величины gx, gy – ограничительные параметры единицы мощности предприятий. Тогда, если Х, Y означают случайные производительности предприятий, средние потери системы производства за единицу времени будут равны

(129)

где сx, сy – удельные стоимостные потери системы производства за единицу времени, – средние значения скоростей производства продукции, а P(X Y) – вероятности несоответствия скорости производства предприятий. Необходимо достичь минимума потерь в единицу времени (129) при ограничении G. Эту задачу можно решить методом неопределённых множителей Лагранжа [39]. Составляют функцию Лагранжа

, (130)

где g – неопределённый множитель.

Решение выполняют по следующему алгоритму. Находят вероятности P(X Y) и значения по известным плотностям fx (x), fy ( y). Дифференцируя (130) по mx, my, g и приравнивая результаты дифференцирования к нулю, получают систему трёх уравнений. Решая данную систему, определяют значения – числа производственных мощностей предприятий, минимизирующие суммарные потери производства. Подставляя эти числа в (129), находят величину производственных потерь. Численное решение данной задачи для различных видов fx (x), fy ( y) и значений их параметров не представляет трудностей.

Приложение 3. При исследовании качества вычислительных сетей необходимо решать задачу оценивания их производительности (прямая задача) и задачу обеспечения заданной производительности (обратная задача). Прямая задача успешно решается матричным методом [11]. При этом, как правило, определяются начальные моменты случайного времени пребывания заявки в сети по начальным моментам времени пребывания заявки во всех узлах сети и вероятностям переходов между узлами сети.

Решение обратной задачи встречает определённые трудности. Это обуславливается главным образом использованием при решении временных распределений. На наш взгляд, использование принципа дуальности и скоростных распределений вероятностей вместо временных распределений позволяет обе указанные задачи решать значительно проще. Поясним это на примере для несложной вычислительной сети, изображённой на рис.6. Стохастический граф содержит пять узлов, из которых нулевой узел является истоком, а четвёртый – стоком заявок. Остальные три узла являются системами обслуживания. Каждый узел имеет свою плотность вероятности времени пребывания заявки в нём, состоящем из времени ожидания в очереди и времени обслуживания заявки. Вероятности переходов между узлами показаны на рис.6.

Рис.6

Пользуясь матричным методом находят изображение Лапласа плотности распределения времени пребывания заявки в сети (между узлами 0, 4):

(131)

где – изображение Лапласа плотности распределения времени пребывания заявки в i-м узле сети, i =1, 2, 3; , а p – фиксированное значение вероятности перехода. Выражение (131) соответствует нахождению суммы случайных величин – времён пребывания в узлах сети с учётом реализации возможной траектории переходов. Оно служит в качестве исходного выражения для нахождения начальных моментов времени пребывания в сети. Находя эти моменты, строят функцию распределения времени пребывания заявки в сети. Видно, что даже решение прямой задачи – задачи анализа – достаточно громоздко. Решение обратной задачи оказывается ещё более затруднительным и не очевидным.

В п.2 матричным методом решались прямая и обратная задачи надёжности сложных программных комплексов, состоящих из модулей программ, связанных вероятностными переходами. Отличительной особенностью решения задач надёжности от решения задач производительности сети является то, что вместо функций в конечном выражении стоят вероятности Pi (ti, ti), вероятность Pi (ti, ti) есть вероятность безошибочной работы i-го модуля программного комплекса в течении времени ti при условии, что до начала своего функционирования в комплексе модуль тестировался в течении времени ti с целью устранения в нём ошибок. Это означает, что в модели оценивания производительности находилось распределение суммы случайных величин в преобразовании Лапласа, а в модели оценивания надёжности – распределение минимума случайных величин во временной области. Поэтому модель надёжности программного комплекса очевиднее и проще модели производительности сети.

Представляет интерес свести формально задачу оценивания производительности сети к задаче оценивания надёжности п.2. Очевидно, что это можно сделать на основе использования скоростного распределения. Для этого необходимо каждому i-му модулю сети сопоставить соответствующую вероятность Pi (n) – вероятность того, что его производительность (скорость) будет не менее n . Тогда вероятность того, что производительность сети, изображённой на рис.6, будет не менее n

(132)

Таким образом, решается прямая задача – задача оценивания производительности сети. Независимость работы отдельных модулей сети при необходимости может быть снята.

Обратная задача – задача распределения требований в сети – может решаться так же, как показано в Приложении 2. Действительно, пусть вероятности Pi (n) зависят от количества используемых в узлах сети ресурсов {mi}, т.е. имеют вид Pi (ni, mi) Тогда, накладывая ограничение на совокупный ресурс сети , можно методом неопределённых множителей Лагранжа найти такое его распределение {mi0}, которое максимизирует величину производительности сети. Либо для заданной производительности сети можно найти минимум ограничения на совокупный ресурс. При этом скоростные распределения можно находить способом, указанным в п. “Приближённое построение скоростного распределения...”. На наш взгляд, подобный подход позволит решать и другие задачи оптимизации систем обслуживания.

На оглавление

 

Назад

Только подписка гарантирует Вам оперативное получение информации о новинках данного раздела


Желтые стр. СИРИНА - Новости - подписка через Subscribe.Ru

Copyright © КОМПАНИЯ ОТКРЫТЫХ СИСТЕМ. Все права сохраняются.
Последняя редакция: Декабрь 09, 2009 13:42:41.