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

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

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

. (75)

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

(76)

(77)

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

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

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

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

, (78)

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

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

(79)

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

(80)

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

(81)

(82)

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

. (83)

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

(84)

(85)

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

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

(86)

. (87)

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

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

, (88)

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

, (89)

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

. (90)

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

, (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.

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

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

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

, (93)

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

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

. (94)

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

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

, (95)

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

. (96)

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

. (97)

(98)

, (99)

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

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

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

(100)

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

(101)

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

и т.д. (102)

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

, (103)

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

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

. (104)

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

. (105)

, (106)

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

.

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

. (107)

В качестве простейшего примера прикладного характера рассмотрим задачу определения оценки средней скорости некоторого источника событий по выборке объема из N₀ источников. Измерялась скорость у всех N₀ источников. Предельное значение измеряемой скорости равно n. Распределение скорости источника экспоненциальное, но параметр его неизвестен. Значения скоростей n₁, n₂, n₃, …, n_r <n дали r источников, остальные N₀–r источников дали значение скорости больше величины п. Пользуясь выражением (103), на основании метода максимального правдоподобия получим оценку средней скорости источника

. (108)

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

.

, (109)

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

, (110)

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

, (111)

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

(112)

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

(113)

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

(114)

.

.

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

(115)

. (116)

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

(117)

. (118)

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

(119)

где .

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

(120)

где .

, (121)

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

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

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

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

(122)

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

. (123)

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

(124)

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

. (125)

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

. (126)

. (127)

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

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

. (128)

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

Пусть f_x (x, m_x), f_y (y, m_y) – плотности распределения производительностей (скоростей производства) предприятий, зависящие от значений m_x, m_y – чисел производственных единиц мощностей, на которые наложено ограничение m_xg_x + m_yg_y Ј G. Величины g_x, g_y – ограничительные параметры единицы мощности предприятий. Тогда, если Х, Y означают случайные производительности предприятий, средние потери системы производства за единицу времени будут равны

(129)

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

, (130)

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

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

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

(131)

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

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

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

(132)

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

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

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

Нужное: Услуги нянь Коллекционные куклы Уборка, мытье окон

Copyright © КОМПАНИЯ ОТКРЫТЫХ СИСТЕМ. Все права сохраняются. кция: -->января 24, 2012 20:38:15.