MODIFICATION OF NVP ARCHITECTURE WITH NONRESTORABLE COMPONENTS

Abstract

Features N-version programming are considered. Modification of NVP architecture for the purpose of reliability in- crease is offered. The modified architecture advantages are shown.

Full Text

Для повышения надежности программного обес- печения (ПО) применяются различные методы. Осо- бую группу составляют мультиверсионные методы, одним из которых является N-версионное программи- рование (NVP). Суть N-версионного программирования заключа- ется в следующем: различными командами разработ- чиков создается несколько версий (не менее двух) программного обеспечения. В ходе эксплуатации эти версии выполняются параллельно на отдельных ком- пьютерах. Результаты работы версий сравниваются с помощью алгоритма голосования, задача которого заключается в выборе корректного выхода [1]. NVP архитектура представляет собой систему с параллельным соединением версий. Если предполо- жить, что алгоритм голосования является «абсолютно надежным»: корректный выход находится даже в слу- чае верного выполнения только одной версии, и вер- сии повторно не используются после отказа, - то на- дежность данной системы, состоящей из n версий, можно вычислить по формуле [2] n n будет установлена данная версия, этого требует NVP метод [1]. Оба варианта связаны с увеличением финан- сирования проекта по созданию надежного программ- ного обеспечения, которое зачастую ограниченно. Если заказчик предъявляет требования по обеспе- чению заданного уровня надежности ПО, то надеж- ность системы может быть повышена без использова- ния дополнительных версий или версий с меньшей интенсивностью отказа. Повышение надежности (уве- личение времени нахождения системы на заданном уровне надежности) достигается при помощи подклю- чения версий особым образом. Пусть R - требуемый уровень надежность, а T - время, в течение которого надежность системы не ниже, чем R. Хотя отказы носят случайный характер, но чем раньше версия будет включена в работу ПО (начнет обрабатывать данные), тем раньше произойдет ее от- каз. Заданный уровень надежности некоторое время может обеспечивать каждая версия в отдельности. Поэтому нет необходимости, чтобы все версии одно- временно начинали работать. P(t) = 1- Õ i =1 (1- pi (t)) = 1- Õ i =1 (1- e-lit ), (1) Предлагается следующий способ модификации NVP архитектуры. В начальный момент времени дангде P(t) - надежность системы (ПО) в момент времени t; pi(t) - надежность i-й версии в момент времени t; лi - интенсивность отказа i-й версии. Разрабатываемое программное обеспечение долж- но удовлетворять требованиям надежности, которые предъявляются заказчиком. Эти требования могут быть сформулированы в виде наработки на отказ, поддержания заданного уровня надежности в течение определенного времени и другими способами. Согласно формуле (1), такие требования могут быть выполнены либо с помощью изменения интен- сивности отказов версий, либо варьируя числом вер- сий. Значение интенсивности отказа связано с тести- рованием программы: чем тщательней проводится тестирование, тем больше может быть выявлено оши- бок и соответственно исправлено, и тем ниже будет интенсивность отказа; но в сложных программах ис- ключать наличие ошибок никогда нельзя. Для увели- чения числа версий, хотя бы на одну, понадобится создание дополнительной команды разработчиков и наличие дополнительного компьютера, на который ные начинает обрабатывать только одна версия, остальные версии бездействуют (находятся в состоянии ожидания). При этом алгоритм голосования выполня- ет функции приемочного теста, проверяя результат на приемлемость. Когда надежность системы снижается до критического уровня R, подключается новая вер- сия. Система уже состоит из двух параллельно рабо- тающих версий. Надежность системы в этот момент времени будет равна 1, так как время работы для вто- рой версии начинается с нуля. С течением времени надежность вновь снизится до уровня R, в этот момент подключается следующая версия. Таким образом, предлагается включать версии не все сразу, а последовательно в момент снижения на- дежности системы до заданного уровня R. Выбор вре- мени подключения версии является ключевой задачей, так как программное обеспечение должно удовлетво- рять требованиям надежности. Такой подход, с одной стороны, обеспечивает вы- полнение требований, а с другой - максимально ото- двигает время подключения версий и приводит к увеличению времени T. Чтобы отслеживать текущее со- стояние системы - ее надежность, в NVP архитектуре должен быть предусмотрен дополнительный меха- низм, в функции которого входила бы операция под- ключения дополнительных версий в нужное время. Рассчитаем время подключения каждой версии и надежность такого программного обеспечения. Пусть K = {k1,…, kn} - вектор размерности n, каж- дая координата которого определяет время включения соответствующей версии, за начало отсчета берется время начала обработки данных, поэтому k1 = 0. Время k2 определяется из условия равенства надежности пер- вой версии и требуемого уровня R: -li k2 могут быть использованы численные методы, напри- мер метод простой итерации. Таким образом, для определения надежности ПО в любой момент времени необходимо сначала определить все kj по формуле (6), а затем воспользоваться соответствующим уравнением системы (5). Все версии могут обладать различными характери- стиками, следовательно, влиять на надежность систе- мы они будут по-разному, поэтому кроме времени подключения версий на надежность системы влияет очередность их использования. Рассмотрим вероятность отказа системы Q, состоящей из параллельно выполняемых версий. Эта вероятность определяется по формуле [2] откуда p1 (k2 ) = e = R , (2) n Q(t) = Õqi (t), i =1 (7) k ln p1 (k2 ) ln R . (3) image 2 =- =l1 l1 где qi - вероятность отказа i-й версии. Вероятность отказа всей системы будет меньше вероятности отказа В момент времени k2 происходит подключение второй версии. ПО представляет собой систему с двусамой надежной версии (версии с наименьшей интен- сивностью отказа): мя параллельно работающими версиями, надежность Q(t) £ min qi (t). (8) такой системы будет P(t) = 1- (1- e-l1t )(1- e-l2 (t -k2 ) ) , t > k2. (4) Формула (4) описывает, что версия номер один продолжает работать, а для версии номер два время смещается на значение k2, которое определяет начало работы второй версии. Если система содержит еще незадействованные версии, то из уравнения (4) находится время k3 равное t, при котором надежность системы, состоящей из двух версий, равна R. Этот процесс продолжается до тех пор, пока не будет определено время включения каждой версии. В процессе функционирования число задейство- ванных версий программного обеспечения изменяется от 1 до n. Надежность системы, состоящей из l ≤ n версий, в общем виде может быть записана следующим образом: 2 ìe-l1t , l = 1, 0 £ t £ k , ï 1£i £n Предположим, что ПО состоит из двух версий с разными интенсивностями отказа. Пусть первая под- ключаемая версия имеет наибольшую интенсивность отказа. Надежность такой версии снизится до уровня R раньше по сравнению с другой версией. Подключе- ние второй версии увеличивает надежность системы, но со временем вклад первой версии в надежность системы уменьшается. Чем интенсивность отказа пер- вой версии выше, тем быстрее увеличивается вероят- ность ее отказа. Повышение вероятности отказа со- гласно формулам (7) и (8) приводит к тому, что Q оп- ределяется второй версией, а роль первой версии сни- жается до минимума. Другой вариант: первая версия является самой на- дежной, после достижения уровня R надежность вер- сии будет оставаться достаточно долго на высоком уровне, а это позволит вместе со второй версией под- держивать надежность системы не ниже R дольше, чем в первом случае. Таким образом, очередность подключения версий ï1 - (1- e-l1t )(1 - e-l2 (t -k2 ) ), l = 2, k 2 < t £ k3 , должна соответствовать упорядоченному набору вер- ï ï1 - ï í P(t) = ï ï 3 Õ i =1 j Õ (1 - e-li (t - ki ) ), l = 3, k 3 < t £ k4 , j j +1 (5) сий по возрастанию интенсивности отказа, первой используется версия с минимальной интенсивностью отказа (самая надежная). Рассмотрим предложенную модификацию NVP 1 - ï ï... ï ï1 - ïî i =1 n Õ i =1 (1 - e-li (t - ki ) ), l = j, k n (1 - e-li (t - ki ) ), l = n, k < t £ k , < t. метода на примерах. Пример 1. Пусть программное обеспечение состоит из трех версий, версии имеют интенсивность отказа 0,03; 0,05 и 0,08 соответственно. Заданный уровень надежности R = 0,7. Рассчитаем по формуле (6) время В системе (5) l определяет не только число версий, но и интервал времени, в котором применяется кон- кретная формула. подключения каждой версии: версия 1: k1 = 0; версия 2: Для нахождения времени подключения версии kj -l1 ( k2 -0) k = - ln 0,7 = - ln 0,7 = 11,89 ; необходимо решить уравнение j -1 P(k2 ) = e = 0,7 → 2 l1 0, 03 P(k j ) = 1- Õ i =1 image (1- e-li (k j - ki ) ) = R, j = 2, n. (6) версия 3: P(k3 ) = 1- (1- e -l1 (k3 -0) )(1- e -l2 (k3 -k2 ) ) = 0, 7 → k3 = 27,276. При большом числе версий аналитическое реше- ние уравнения (6) весьма затруднительно, поэтому Рассчитаем по формуле (1), когда надежность сис- темы при стандартной схеме подключения снизится до заданного уровня. Это время составляет 23,681, а при модифицированной схеме 38,554 (рассчитывается по формуле (5) или (6)), что почти на 15 единиц больше. image Построим по формулам (1) и (5) графики измене- ния надежности программного обеспечения (рис. 1). Рис. 1. График надежности ПО с тремя версиями: Ps - надежность стандартного NVP метода; Pm - надежность модифицированного NVP метода; Ts - время поддержания ПО на заданном уровне (стандартная схема); Tm - время поддержания ПО на заданном уровне (модифици- рованная схема) График надежности наглядно демонстрирует пре- имущество модифицированного NVP. Хотя на участке времени от 0 до k2 надежность ПО при модифициро- ванной схеме ниже, чем в обычном случае, но требо- вание по обеспечению заданного уровня надежности R выполняется, кроме того начиная с k2 надежность выше. Следует также сказать, что кроме времени T увеличивается и наработка на отказ всей системы. В рассмотренном примере версии включались в по- рядке увеличения интенсивности отказа. Покажем, что именно такой подход повышает надежность системы. Пример 2. Пусть ПО состоит из двух версий с ин- тенсивностями отказа 0,03 и 0,08; R = 0,7. Используя модифицированный NVP метод, построим два графи- ка изменения надежности системы. Первый график - для случая, когда первая используемая версия имеет минимальную интенсивность отказа (рис. 2) и вто- рой - когда первая версия имеет максимальную ин- тенсивность отказа (рис. 3). Хотя надежность второй версии (рис. 2) меньше по сравнению с первой, но включение ее последней обеспечивает повышение надежности на участке t от 12 до 50, далее ее надежность снижается практически до 0, и она уже не влияет на надежность системы. Надежность программного обеспечения при двух работающих версиях (рис. 3) примерно равна надеж- ности второй версии. Это происходит из-за того, что надежность первой версии на участке времени, когда она работает в паре со второй версией, достаточно мала, и поэтому она оказывает незначительное влия- ние на общую надежность системы. В данном случае первая версия фактически играет роль только до мо- мента включения второй версии. Рис. 2. График надежности ПО с двумя версиями: P1(t) - изменение надежность версии с л = 0,03; P2(t) - измене- ние надежность версии с л = 0,08; P(t) - изменение надежность ПО (л1 = 0.03, л2 = 0,08) image Рис. 3. График надежности ПО с двумя версиями: P1(t) - изменение надежность версии с л = 0,08; P2(t) - измене- ние надежность версии с л = 0,02; P(t) - изменение надежность ПО (л1 = 0,08, л2 = 0,03) Таким образом, предложенная модификация NVP архитектуры обеспечивает увеличение времени, в те- чение которого надежность программного обеспече- ния не ниже заданного уровня. Данный метод вклю- чения версий может быть применен не только для не- восстанавливаемых компонентов, но и для стандарт- ного варианта NVP архитектуры.