ВСТРОЕННЫЕ ИНФОРМАЦИОННО- УПРАВЛЯЮЩИЕ СИСТЕМЫ РЕАЛЬНОГО ВРЕМЕНИ Лекция 8: Механизмы обеспечения отказоустойчивости ВМиК МГУ им. М.В. Ломоносова, Кафедра АСВК, Лаборатория Вычислительных Комплексов, Ассистент Волканов Д.Ю.

2 2 План лекции Задача оптимизации надёжности ВИУС РВ Цели применения методов повышения надёжности Методы обеспечения отказоустойчивости

3 Неформальная постановка задачи оптимизации надёжности ВС Пример вычислительной системы:

4 Дано: –N – количество подсистем –Ch ij, Cs ij – стоимость использования аппаратного/программного компонента j для подсистемы i –Rh ij, Rs ij – надёжность аппаратного/программного компонента j для подсистемы i –Prv, Pd, Pall – вероятности отказа нескольких версий программных компонентов, вероятность отказа схемы принятия решений, вероятность отказа сразу всех версий программного компонента Необходимо найти: –Оптимальный набор компонентов и МОО, на котором R RTES max Ограничения: –C RTES < Cost Классическая постановка задачи оптимизации надёжности ВС

5 Самый многочисленный вид ВС Ограничения на массу, габариты и энергопотребление Критичность времени работы некоторых задач Сотни различных устройств, входящих в состав РВС РВ Невозможность представления функционирования РВС РВ в аналитическом виде Особенности современных ИУС РВ

6 Дано: –N – количество подсистем –Ch ij, Cs ij – цена использования аппаратного/программного компонента j для подсистемы i –Rh ij, Rs ij – надёжность аппаратного/программного компонента j для подсистемы I –Prv, Pd, Pall – вероятности отказа нескольких версий программных компонентов, вероятность отказа схемы принятия решений, вероятность отказа сразу всех версий программного компонента Необходимо найти: –Оптимальный набор компонентов и МОО, на котором R RTES max Ограничения: –C RTES < Cost –T k < D k –M RTES < Mass –D RTES < Dimension –E RTES < Energy Задача оптимизации надёжности

7 Дано: –N – количество подсистем –M – модель поведения ИУС РВ –Ch ij, Cs ij – цена использования аппаратного/программного компонента j для подсистемы i –Rh ij, Rs ij – надёжность аппаратного/программного компонента j для подсистемы I –Prv, Pd, Pall – вероятности отказа нескольких версий программных компонентов, вероятность отказа схемы принятия решений, вероятность отказа сразу всех версий программного компонента Необходимо найти: –Оптимальный набор Cr, на котором R RTES max Ограничения: –C RTES < Cost –T k < D k –M k < Mass –E k < Energy Задача оптимизации надёжности

8 Принятые ограничения Все компоненты являются неремонтируемыми Моменты появления отказов для аппаратуры статистически независимы Все аппаратные компоненты ИУС РВ являются активными Количество доступных версий для всех компонентов фиксировано Интенсивность отказов постоянно

9 Особенности задачи NP-трудная Аргументы и значения функции надежности являются дискретными Многоэкстремальная область допустимых решений Область допустимых решений несвязна Функция надежности нелинейная Функция стоимости линейна Каждый модуль вычислительной системы имеет свой доступный набор механизмов обеспечения отказоустойчивости

10 Методы решения задачи Алгоритмы муравьиных колоний Генетические алгоритмы Имитация отжига Иммунные алгоритмы Прочие эвристики Поиск с отсечением Динамическое программирование Другие точные методы

11 Цели Отказоустойчивая компьютерная система должна предоставлять сервисы в случае ошибок Отказы могут возникать, так как дефекты присутствуют в компонентах системы Система с отказоустойчивостью надёжней системы без отказоустойчивости, но больше затрачивается ресурсов на обеспечение отказоустойчивости

12 Проблемы … Традиционные подходы к отказоустойчивости в аппаратных системах основываются на копировании с использованием особенностей отказов физических компонентов. Большинство аппаратных методов отказоустойчивости не могут быть применены напрямую в ПО, где почти все ошибки разработчика.

13 Примерck Правильный ответ должен быть 8779 Но при обычной реализации возвращается 0

14 История … Защитное программирование: –ad-hoc методы минимизирующие ущерб который может возникнуть из-за ошибок Метод двух версий: –Создание двух независимых версий ПО и запуск их. По любому расхождению в версиях включается триггер

15 Методы обеспечения отказоустойчивости Обнаружение ошибок Диагностическое тестирование Изоляция ошибок Маскировка ошибок Корректирование ошибок Устранение ошибок

16 Требования к компонентам

17 Организация резервирования Общие подходы –Организация глобального времени –Выделение изолированных регионов –Отказы в разделяемых компонентах Программное резервирование –Пространственное резервирование –Временное резервирование Функциональный сдвиг во времени Информационный сдвиг во времени Аппаратное резервирование –Пространственное резервирование –Кодирование

18 Механизмы обнаружения ошибок Программные –Приемочные тесты –Отказоустойчивые алгоритмы –Проверки Временные Кодовые Реверсные Семантические Структурные Аппаратные –Диагностическое тестирование

19 Приемочные тесты

20 Отказоустойчивые алгоритмы. Попарное тестирование

21 Отказоустойчивые алгоритмы. Голосование

22 Механизмы устранения ошибок Программные –Одноверсионное программирование Контрольная точка и перезапуск Парные прогоны –Многоверсионное программирование Восстановление блоками N-версионное программирование N-самотестируемое программирование Аппаратные –Резервирование компонент –Переконфигурирование системы

23 Схемы голосования голосов отель сравнивает результаты двух и более функционально эквивалентных компонентов ПО и определяет корректный результат Схемы голосования: –Большинство –Консенсус –2-из-N

24 Контрольная точка и перезапуск

25 Парные прогоны

26 Восстановление блоками

27 N-версионное программирование

28 N-самотестируемое программирование

29 N-версионное программирование. Примеры

30 Космический шаттл

31 Зависимость надежности от количества версий

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

33 Литература Kuo W., Wan R. Recent advances in optimal reliability allocation //Computational Intelligence in Reliability Engineering. – Springer Berlin Heidelberg, – С ( online.de/static/content/catalog/newbooks/978/354/0 37/ / _Excerpt_001. pd f) Pullum L. L. Software fault tolerance techniques and implementation. – Artech House, 2001.

34 Спасибо за внимание!