Лекция 9. Модели надёжности ПО. Оптимизация надёжности ВС (Лекции)

НАДЁЖНОСТЬ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯЛекция 9:Модели надёжности ПООптимизация надёжности ВСВМиК МГУ им. М.В. Ломоносова,Кафедра АСВК, Лаборатория Вычислительных КомплексовАссистент Волканов Д.Ю.План лекции•••••••Основные свойства МНПОПуассоновские моделиМарковские моделиБайесовские моделиПример выбор модели оценкиЗадача оптимизации надёжности ВСМетоды обеспеченияотказоустойчивостиЭпиграфЕсли отладка — процесс удаленияошибок, то программирование должнобыть процессом их внесения.Эдсгер ДейкстраЛитература• Birolini A.

Reliability engineering. – Berlin : Springer,2007. – Т. 5. (Глава 2 – Reliability Analysis During theDesign Phase)• Lyu M. R. et al. Handbook of software reliabilityengineering. – CA : IEEE computer society press, 1996.– Т. 222.(Глава 3 - Software Reliability Modeling Survey)(http://www.cse.cuhk.edu.hk/~lyu/book/reliability/pdf/Chap_3.pdf)• A.Wood Software Reliability Growth Models. TechnicalReport, 1996(http://www.hpl.hp.com/techreports/tandem/TR96.1.pdf)Литература (2)• Kuo W., Wan R. Recent advances in optimalreliability allocation //ComputationalIntelligence in Reliability Engineering.

–Springer Berlin Heidelberg, 2007. – С. 1-36.(http://content.schweitzeronline.de/static/content/catalog/newbooks/978/354/037/9783540373674/9783540373674_Excerpt_001.pdf)• Pullum L. L. Software fault tolerancetechniques and implementation. – ArtechHouse, 2001.НадёжностьаппаратурыНадёжность ПООсобенности оценкинадёжности ПО• Оценка надёжности сложная проблема,так как не понятна природа ПО• Непонятно как измерять размер ПООценка числа ошибок впрограммеЗадачи:оценить число оставшихся дефектов в текущейверсии программы.оценить вероятность отказа компонента илисистемыоценить среднее время до следующего отказаВозможны два пути:Статический анализ кодаАнализ статистики тестированияПример статистикитестированияНеделя Проект 1 Проект 2 Проект 3 Проект 41613161813262721128404131948615442757846953260958163610490739112968411179994210010Наша задача – описать процесс обнаружения ошибокматематической модельюПример статистикитестирования (2)Данные:Время отказаИнтервал между отказамиПример статистикитестирования (3)Данные:Зависимые отказы кзаданному времениОтказы во временнойинтервалМодели надёжностиКонечная цель – оценить надежностьпрограммы, основываясь на данных,полученных при тестировании.Суть моделей надёжности - подобратьадекватную модель, описывающуюколичество обнаруженных ошибок спомощью известных вероятностныхраспределений.Принцип применениямоделей надёжностиСобрать данные об отказахПроверить данные (выбрать видраспределения)Выбрать модельОценить параметры моделиНастроить модель с выбраннымипараметрамиПроверка критерия согласияОценить требуемые параметрыМодели надёжности ПО• С 1970х годов предложено более 200моделей но как определить надёжностьПО вопрос открытый• Одну модель нельзя использовать вовсех ситуациях• Нет полной модели или даже болееменее репрезентативнойМодели надёжности ПО (2)• Предположения• Факторы• Математическая функцияВиды моделейПуассоновскиеМарковскиеБайесовскиеКомбинированныеМодели надёжности ПО (3)Модели надёжности ПО (4)Модели надёжности ПО (5)Основная теорема опуассоновском процессеВ каждый момент временито есть имеет распределение Пуассона.Λ называется интенсивностью потока.

Врассматриваемом случае интенсивностьесть количество ошибок, найденных кданному моменту.Экспоненциальная модельНаиболее простаяиз выпуклыхмоделейm(t )  a(1  e bt)Оценка параметров:линейная регрессияПроисходитминимизациясуммыквадратоврасстояний донекой прямой.Ограничения для SRGMОшибки исправляются сразу послеобнаруженияПри исправлении новых ошибок непоявляетсяВ период тестирования не появляетсянового кодаТестирование централизовано, то есть вкаждый момент одна версия программытестируется одной группой тестеров.Ошибки не зависят друг от друга.ПримерыусовершенствованныхмоделейДанная модельпозволяет избавитьсяот ограничения назависимость ошибокдруг от друга1 r (r ) r(1  e  bt )m(t )  a *1   (r )e btПараметр r есть отношение количестваошибок, которые можно обнаружить втекущий момент, к общему количествуошибок.

При r = 1 получаемстандартную экспоненциальнуюмодель.Модель YamadaКривая становится S-изогнутой, и происходящееможно рассматривать как модель для тестирования,при котором умения тестера постепенноувеличиваются.m(t )  a(1  (1  bt)e  bt )Обзор остальных моделейМодель Вейбулла – учитываеткачество тестированияМодель Парето – учитывает, чтоболее серьезные ошибкиисправляются раньше...Особенностипуассоновских моделейПо пуассоновским моделям многоработ, их применяли в разныхпроектах множество раз, и получалиадекватные результаты. Возможность исследовать несколькопараллельных независимыхисточников ошибок Изначально, пуассоновские процессыиспользовались для моделированияотказов оборудования.Модель Jelinski-MorandaРассматриваем процесс тестирования какмарковскую цепь с неизвестным начальнымсостоянием.

Полагая, что надежностьлинейно зависит от количества ошибок,можно считать время между обнаружениемдвух ошибок случайной величиной сэкспоненциальным распределением.Модель Jelinski-MorandaПусть в программе a ошибок, вначальный момент интенсивностьравна a*b, где b – положительныйпараметр. Ti – время междупоявлением i-й и i-1 ошибок имеетпоказательное распределение синтенсивностью (a – i + 1)*bБайесовский подходБайесовскими называют различныемодели, учитывающие новые данные длякорректировки существующих гипотез.Если в описанных выше моделяхиспользуются некоторые предположения охарактере распределения a priori, то прииспользовании байесовских методов этипараметры меняются в зависимости отновых измерений.Частота в LV-моделиЧастота – скорость изменения интенсивности, т.е.

m'(t).Открытый вопросНе решена проблема выбора междусуществующими SRGM. Критерииприменимости той или иной SRGM кконкретному проекту до конца несформулированыПример входных данныхИнтенсивность• Две модели "basic execution timemodel“ и "logarithmic Poisson executiontime model" (e.g. Musa et al. 1987).Basic Execution TimeModel• Basic Execution Time Model– Интенсивность отказов λ(τ) за время τ:– где λ0 начальная интенсивность и ν0ожидаемоеколичество отказов.Logarithmic Poisson executiontime model• где μ(τ) среднее время междуоткзами к времени τ.Пример (2)• В этом случаеLogarithmicPoisson Modelлучшеприближаетthe BasicExecutionTime Model.• В некоторыхдругихпроектах BEmodelприближаетлучше чем LPмодель.Выводы• Нет универсальной модели• Измерения очень важны длянахождения корректной модели• Результаты тестирования необходимоиспользовать и не один раз• Модели надёжности ПО не так простыкак описаны здесь Неформальная постановка задачиоптимизации надёжности ВСПример вычислительной системы:31S122H13H33S21,S22,S24H23S324S41,S43H42•Классическая постановказадачи оптимизациинадёжностиВСДано:– N – количество подсистем– Chij , Csij – стоимость использования аппаратного/программногокомпонента j для подсистемы i– Rhij , Rsij – надёжность аппаратного/программного компонента jдля подсистемы i– Prv, Pd, Pall – вероятности отказа нескольких версийпрограммных компонентов, вероятность отказа схемы принятиярешений, вероятность отказа сразу всех версий программногокомпонента• Необходимо найти:– Оптимальный набор компонентов и МОО, на котором RRTES max• Ограничения:– CRTES < CostПринятые ограничения• Все компоненты являютсянеремонтируемыми• Моменты появления отказов дляаппаратуры статистически независимы• Все аппаратные компоненты ВС являютсяактивными• Количество доступных версий для всехкомпонентов фиксировано• Интенсивность отказов постоянноОсобенности задачи• NP-трудная• Аргументы и значения функциинадежности являются дискретными• Многоэкстремальная область допустимыхрешений• Область допустимых решений несвязна• Функция надежности нелинейна• Функция стоимости линейна• Каждый модуль вычислительной системыимеет свой доступный набор механизмовобеспечения отказоустойчивостиМетоды решения задачи••••••••Динамическое программированиеТочные методыАлгоритмы муравьиных колонийГенетические алгоритмыИмитация отжигаИммунные алгоритмыПрочие эвристикиПоиск с отсечениемЦели• Отказоустойчивая компьютерная системадолжна предоставлять сервисы в случаеошибок• Отказы могут возникать, так как дефектыприсутствуют в компонентах системы• Система с отказоустойчивостью надёжнейсистемы без отказоустойчивости, нобольше затрачивается ресурсов наобеспечение отказоустойчивостиПроблемы …• Традиционные подходы котказоустойчивости в аппаратныхсистемах основываются накопировании с использованиемособенностей отказов физическихкомпонентов.• Большинство аппаратных методовотказоустойчивости не могут бытьприменены напрямую в ПО, где почтивсе ошибки разработчика.Пример6x  y   xi  yii 1y  10, 2111,10 x  1020 ,1223,1024 ,1018 , 3 ,  102130, 2 ,  1026 ,102219• Правильный ответ должен быть 8779• Но при обычной реализации возвращается0История …• Защитное программирование:– ad-hoc методы минимизирующие ущербкоторый может возникнуть из-за ошибок• Метод двух версий:– Создание двух независимых версий ПО изапуск их.