Интерес к проектированию отказоустойчивых вычислительных систем /ОУВС/ обусловлен наличием рада областей применения, в которых отказ вычислительной системы приводит к катострофичес-ким или тяжелым экономическим последствиям. Наряду с традиционным мажоритарным подходом к обеспечению отказоустойчивости, в современных многомашинных и мультипроцессорных системах достижение отказоустойчивости возможно также за счет динамического резервирования замещением отказавших элементов системы — за счет организации самовосстановления системы.
Реализация резервирования замещением требует, кроме наличия резервных элементов, избыточных аппаратных и программных средств обеспечения надежности /СОН/, выполняющих контроль работоспособного состояния системы, автоматический поиск и устранение влияния неисправности. Проектирование средств обеспечения надежности в самовосстанавливающихся ОУВС представляI ет собой не менее трудоемкую задачу, чем проектирование аппаратных средств, направленных на непосредственное выполнение вычислений.
Надежность функционирования самовосстанавливающихся ОУВС определяется интенсивностью отказов основных элементов системы и качеством работы СОН, а разработка методов проектирования средств обеспечения надежности является актуальной ввиду возможности получения более высоких технических и экономических показателей класса самовосстанавливающихся ОУВС по сравнению с обычными системами.
Для проектирования средств обеспечения надежности самовосстанавливающихся ОУВС могут быть применены итеративные,.
— 5 прямые и комбинированные методы проектирования. Ввиду отсутствия накопленного опыта проектирования средств обеспечения надежности самовосстанавливающихся ОУБС, для надежностного проектирования самовосстанавливающихся систем более предпочтительной является классическая итеративная схема «синтеза через анализ». Схема «синтеза через анализ» предполагает выбор первоначального варианта построения СОН, формализацию описания структуры СОН, построение модели функционирования системы, анализ выбранных показателей надежности аналитическими или имитационными методами, и, наконец, принятие решения о продолжении или прекращении поиска варианта построения СОН.
Возможность применения описанной выше схемы не для отдельной самовосстанавливающейся системы, а для целого ряда систем, образующих класс самовосстанавливающихся отказоустойчивых вычислительных систем, опирается на построение обобщенной модели структуры средств обеспечения надежности и разработку универсальной модели работоспособности самовосстанавливающихся систем, что является основной целью предлагаемой работы.
В настоящее время в литературе обобщены и описаны типовые схемы построения функционального и тестового диагностирования, описаны также методы и технические приемы самовосстановления. Однако, обобщенной модели структуры средств обеспечения надежности самовосстанавливающихся ОУБС, автору не известно.
Анализу показателей надежности самовосстанавжвающихся систем посвящено значительное количество работ, в которых предложены модели, позволяющие оценивать различные аспекты функционирования самовосстанавжвающихся систем при разжчных ограничивающих допущениях. Наиболее универсальная из известных автору моделей анажза отказоустойчивых систем — модель /¡-ДМ^.
— 6 которая более подробно будет изложена в первой главе, учитывает эффективность функционирования ССН обобщенным эмпирическим параметром вероятности успешного самовосстановления и не раскрывает его значения. Вследствии этого, указанная модель не может быть применена для проектирования средств обеспечения надежности. Для преодоления указанного ограничения, автором, на базе полумарковских регенерирующих случайных процессов, предложена модель работоспособности самовосстанавливающихся ОУВС.
Получение точных оценок показателей надежности /в частности, вероятности безотказной работы/ систем, описываемых полумарковским процессом с числом состояний более 5−6 аналитическими методами практически невозможно. Аналитические выражения, однако, раскрывают влияние внутренних параметров структуры СОН на показатели надежности всей системы. Поэтому, с целью получения аналитических оценок показателей надежности самовосстанавливающихся ОУВС, автор воспользовался асимптотическим подходом А. Д. Соловьева, дающим способ получения приближенных аналитических выражений для вероятности безотказной работы и среднего времени до первого отказа систем, поведение которых описывается полумарковским регенерирующим процессом. Асимптотический метод дает возможность получить простые аналитические выражения основных показателей надежности самовосстанавливающихся ОУВС, позволяющие оценивать варианты построения СОН на начальных этапах цикла «анализ — синтез» .
С целью уточнения асимптотических оценок, разработаны также имитационные алгоритмы расчета показателей надежности самовосстанавливающихся ОУВС. Программная реализация имитационньк алгоритмов позволила вшолешть анализ точности предложенных асимптотических оценок.
На защиту выносятся следующие элементы диссертационной работы, образующие ее научную новизну и практическую ценность:
— обобщенная модель структуры средств обеспечения надежности самовосстанавливающихся систем, а, также, формализация описания обобщенной структуры;
— универсальная модель работоспособности класса самовосстанавливающихся ОУБС;
— общее асимптотическое решение задачи оценки показателей надежности и частное решение для случая экспоненциальных распределений наработок на отказ элементов системы;
— асимптотические оценки показателей надежности систем с функциональным и тестовым самодиагностированием;
— имитационные алгоритмы расчета показателей надежности самовосстанавливающихся ОУВС;
— анализ точности предложенных асимптотических оценок.
Автор считает необходимым выразить признательность кандидату технических наук, доценту кафедры Системотехники МЭИ Ладыгину Игорю Ивановичу. Участие в научно-исследовательской работе кафедры, выполнявшейся под руководством И. И. Ладыгина, обсуждение направления диссертационной работы, советы и замечания в ходе исследования оказали существенное влияние на формирование научного мировоззрения автора и достигнутые результаты.
I. СОДЕРЖАТЕЛЬНОЕ ОПИСАНИЕ ПРОЦЕССА ПРОЕКТИРОВАНИЯ СРЕДСТВ ОБЕСПЕЧЕНИЯ НАДЕЖНОСТИ ОТКАЗОУСТОЙЧИВЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ.
Первая глава посвящена содержательному описанию процесса проектирования средств обеспечения надежности отказоустойчивых вычислительных систем /надежностное проектирование ОУВС/,.
Выполнен обзор литературы по 4 основным направлениям теории и практики надежностного проектирования вычислительных систем, на которые опирается диссертационная работа. Изложены методы достижения отказоустойчивости вычислительных систем, причем основное внимание уделено методу динамического замещения, используемого в самовосстанавливающихся ОУВС, которые являются предметом исследования предлагаемой работы. На содержательном уровне описан процесс проектирования средств обеспечения надежности самовосстанавливающихся систем и более детально раскрыты направления исследования диссертационной работы. Заключает главу описание одной из наиболее универсальных моделей для анализа показателей надежности отказоустойчивых систем, указаны ее ограничения и пути преодоления ограничений.
1.1. Обзор литературы.
Можно вцделить следующие 4 основные области теория и практики проектирования вычислительных систем, на которые опирается данная работа.
Первую группу образуют работы в области общей теории систем, теории проектирования вычислительных: систем, проектирования средств обеспечения надежности вычислительных систем. Ко второй группе отнесены работы, в которых описан и частично систематизирован фактический материал, касающийся практики надежностного проектирования отказоустойчивых вычислительных систем. Работы по математическим основам теории надежности и построению универсальных аналитических моделей для анализа надежности составляют 3 группу. Последними сгруппированы работы по основам имитационного моделирования, моделированию надежностного функционирования вычислительных систем, универсальным программным системам для анализа показателей надежности.
Основные понятия используемой в работе общей теории систем, такие как система, структура, элемент, функционирование системы, модель системы, общее понятие эффективности функционирования системы изложены в работах И. В. Блауберга и Э. Г. Юдина /I/, лекциях по теории сложных систем Н. П. Бусленко, В. В. Калашникова, И. Н. Коваленко /2/, а также в работе зарубежных ученых М. Месаровича, Д. Макол и И. Такахара /3/- среди работ последних лет следует упомянуть работу по основам системолопш Б. С. Флейшмана /4/.
Итерационный метод проектирования по схеме «синтеза через анализ» подробно описан в работе Н. П. Бусленко /5/. Для решения наиболее важного вопроса в процессе проектирования вычислительных машин — формализации описания системы — академиком В. М. Глушковым был разработан язык алгоритмических алгебр /6/, развитие и применение которого для надежностного проектирования вычислительных систем можно найти в работах И. В. Сафонова /7,8/ и В.А.1уляева /9-П/. В частности, работы И. В. Сафонова посвящены формализации надежностного проектирования структурно-алгоритмических систем, основным результатом которых явилась разработка математических моделей и построение расчетных соотношений для канонических форм алгоритмов, а именно, линейного, дизъюнктивного, итеративного и параллельного регулярных алгоритмов. В работах В.А.1уляева на основе языка алгоритмических алгебр предпринята попытка формализации синтеза комплексных систем контроля и диагностирования вычислительных систем.
Математические основы прямых методов проектирования, использующих схемы дискретной оптимизации развиты в работах B.C. Михалевич, В. В. Шкурбы, А. И. Кукса, В. Л. Волкович, Д.Б.К}цина и др. /12−16/. Применительно к проектированию вычислительных машин и систем данное направление развито в работах А. Г. Шигина, Г. Л. Кемельмахера, В. А. Федина, В. В. Андрианова /17−19/. Автоматизации поискового конструирования посвящена книга под общей редакцией А. И. Половинкина /20/. Среди работ зарубежных авторов можно назвать книгу Бэзанта /21/, посвященную машинно-ориентированным методам конструирования и производства.
Трудно назвать первые работы, посвященные вопросам надежностного проектирования вычислительных машин и систем. Из ранних работ по данной тематике следует назвать работы Б. В. Гнеденко по исследованию дублированных вычислительных систем /22,23/, Б. А. Козлова по изучению резервированных систем с вое.
— II становлением /24/, работы Н. Д. Путинцева /25/, Г. Н. Ушаковой /26/, Я. А. Хетагурова /27/ посвященные анализу и синтезу аппаратных схем контроля.
Понятие отказоустойчивая вычислительная система /ОУВС/ появилось на Первом Международном симпозиуме по отказоустойчивым вычислительным системам /1970 год/, проходящем затем ежегодно. Отказоустойчивыми вычислительными системами, следуя /28/, называют вычислительные системы, способные продолжать выполнение предписанных программой действий и после возникновения в физической структуре системы неисправностей. Термин «отказоустойчивость» наиболее близок к применявшемуся ранее термину «живучесть» .
Зарубежный опыт проектирования ОУВС до 1ЪЪ года описан в специальном выпуске Трудов Института инженеров по электротехнике и радиоэлектронике /29/, содержащем описание 6 отказоустойчивых систем, большинство из которых построено по мажоритарному принципу. Ряд более современных отказоустойчивых. систем описан также в /30/. Систематизации опыта проектирования ОУВС посвящены обзоры Е. С. Согомоняна и М. Ф. Каравай /31/, А. Д. Волкова, В. А. Ведешенкова и Г. Б. Семенова /32/, обзор и сравнение путей достижения отказоустойчивости содержится в /33,34/.
Логическая и аппаратная организация функционального и тестового диагностирования и самовосстановления дискретных систем наиболее полно описана в двухтомнике под общей редакцией П. П. Пархоменко /35,36/. Решению проблемы ядра средств обеспечения надежности за счет построения самопроверяемых схем встроенного контроля в значительной степени посвящена вторая книга двухтомника, где описаны общие методы построения самопроверяемых схем и приведены конкретные реализации самопроверяемых схем, встроенного контроля для типовых дискретных устройств, таких как схемы контроля по модулю 2, счетчики, сумматоры и т. д. Примеры построения самопроверяемых схем контроля для различных устройств. вычислительной системы можно найти. такжев книге Уэкерли /37/. ;
Техническая организации самовосстановлениям вычислительных системах описана. в статье В. А. Ведешенкова и др./38/. Основные принципы диагностированияи. реконфигурации ОУВС на, основе сверхбольших интегральных схем изложены в /39/, где предложены специальные етет реконфигурации процессора и местной памяти: на основе байтовых слоев. Пути достижения отказоустойчивости универсальных ЦВМ на СБИС-компонентах исследовались в /40/- основу рассмотренного подхода составляет детальное функциональное диагностирование, узлов. ЦВМ до уровня корпуса СБИС с использованием самопроверямых схем встроенного контроля. Диагностическая система. микропроцессорных систем, содержащая резидентные диагностические программы для обнаружения простых: однократных неисправностей, внешние диагностические программы для более. глубокого и детального поиска однократных и многократных неисправностей. иубавляющую программу — диагностический супервизор — описана в /41/.(Потенциальные возможности распределенных вычислительных систем, такие как отсутствие. централизованной части аппаратного и программного обеспечения, явно выделенный.минимальный.замещаемый блок./целая микро-ЭВМ/,. простота обнаружения и диагностирования относительно микро-ЭВМ, легкость реконфигурации ввиду стандартности интерфейса отмечены в /42/;
Описание традиционных. методов аппаратного • и программногоконтроля можно найти с-/учебншсе.ДП. Журавлева, Л. А. Котелюка и' Н. И. Циклинского /43/. Оргализадии систем диагностирования, — вычислит ельныхмашн и систем посвящена работа В. А. Гуляева /10/. Исследованиюспецифйга' пассивного резервирования с—учетом сов-' < ременнож интегральной схемотехники посвщен ряд статей, а также книга Ю. А. Чернышева и И. С. Аббакумова /44−46/.
Математические основы теории надежности заложены работами Гнеденко Б. В., Соловьева А. Д., Беляева. Ю. К. /47/, Барлоу Р., Прошан Ф. /48/, Королюка B.C. /49−50/, Коваленко И. Н. /51/, Кокс Д., Смит В. /52/. В наиболее систематизированном виде расчетные методы анализа надежности отражены в справочнике Б. А. Козлова и И. А. Ушакова /53/, а также в книге И. Б. Шубинского, Е. Н. Пивень /54/, работе К. А. Иыуду /97/.
Для анализа надежности вычислительных, машин и систем, в зависимости от их сложности и структуры, применяют 3 группы методов. Простые неразветвленные структуры, типа последовательно-параллельных, поддаются анализу на основе перечисления: событий успешного функционирования и сложения/перемножения их вероятностей.
Для невоостанавливаемых систем с разветвленной структурой, у которых возможно описать. связи между элементами матрицей непосредственных связей и указать условие нормального функционирования, логическое выражение условия работоспособности может быть получено, например, возведением матрицы связей в степень /55/. Для перехода же к вероятностной функции., работоспособности, разработан ряд-алгоритмов, в частности, метод ортогонали-зации 756/ и скобочная запись формулы сложения вероятностей совместных событий /57/. Наиболее г систематизированное изложе-. ние логико-вероятностных методов содержится в работе /58/. ;
Анализ надёжности восстанавливаемых систем и систем с различными уровнями эффективности функционирования в различныхсостояниях выполняется на основе представления процесса функционирования системы каким-либо типом случайного процесса. Наибольшие результаты достигнуты в настоящее время с помощью марковского и полумарковского процессов / 9, 27−29, 60−63/. Большое практическое значение для анализа показателей надежности систем имеет метод, асимптотических оценок /64−68/, и в частности, оценка А. Д, Соловьева, дающая приближенное выражение для вероятности безотказного функционирования и среднего времени до первого отказа восстанавливаемых систем, поведение которых возможно описать регенерирующим йодумарковским процессом /66−68/.
Различные аспекты функционирования, вычислительных систем > с динамическим резервированием отказавших элементов /самовосстанавливающихся ОУВС/ могут быть проанализированы с помощью моделей В. А. Гуляева / 9/, дающих приближенное выражение среднего времени до первого момента пропуска ошибок за счет отказа элементов схем контроля и принятия решения, модели Л.А.ЯЬ-телюка и В. А. Трусова /62/, позволяющей оценивать достоверностьфункционирования процессора с комплексной системой контроля, полумарковской модели Л. И. Кульбак, А. Г. Шоник для резервирс>ванных, систем с мгновенным замещением отказавшего элемента /63/, моделей организации профилактического обслуживания И.В.Герц-бах /69/- Временной аспект процесса переключения может быть учтен рядом моделей и асимптотических оценок, полученных: Черкесовым Г. Н. /70/ и Б. П. Креденцером /71/.
Исследованию ряда типовых структур отказоустойчивых вычислительных систем /дублированной, дуплексной, с постепенной деградацией/ с точки зрения обеспечения показателей надежности и.
— 15 «производительности посвящена работа японских ученых /72/. Модель для анализа деградирующих систем, для которых наиболее целесообразными являются комплексные критерии надежности/производительности, построена Беадри /73/- в модели, однако из рассмотрения исключен сам процесс замещения, описанный эмпирическим параметром вероятности успешного самовосстановления.
Наиболее универсальными моделями для прогнозирования показателей надежности отказоустойчивых вычислительных систем на настоящее время являются модели fi RIES /74/ -и SURF /75/. Как. ограничения моделей следует отметить их марковский характер /только экспоненциальные законы распределения наработки на отказ/, наличие трудно поддающихся оценке эмпирических параметров /вероятность успешного самовосстановления/, а, также, сложность вычислительной процедуры, возможной только при использовании ЭВМ /о0ъем программы SURF составляет г. .ЗООО' о’йераторов языка 'PL — I /.
Наряду с аналитическим моделированием показателей надежности ОУВС, преимуществами которого является получение в некоторых случаях аналитической зависимости показателя надежности от выделенных параметров, а, следовательно, и возможность проведения параметрической оптимизации, исследование и синтез средств обеспечения надежности отказоустойчивых систем может быть выполнен также с привлечением метода имитационного моделирования. Метод имитационного /статистического/ моделирования как универсальный метод. исследования сложных систем описан в работах Н. П. Бусленко /10/, Ю. Полляк /76/- статистические алгоритмы исследования надежности разрабатывались Л. К. Горским /77/, алгоритмы моделирования показателей надежности вычислительных машин и систем можно найти в книге под общей редакци.
— 16 ей Н. А. Шишонка /78/- обобщенные алгоритмы прогнозирования. систем с временной избыточностью описаны Б. П. Креденцером /71/. Обзор методов повышения эффективности моделирования, сглаживающих основной недостатак метода — необходимость набора значительного /измеряемого тысячами/ числа реализаций случайного процесса для получения требуемой точности оценок можно найти в /79−81/.
Большинство описанных выше универсальных аналитических методов расчета и имитационных алгоритмов имеют законченную программную реализацию. Из ранних работ в этом направлении можно назвать программные системы LBRt /82/, RELCQMP /83/,. ТЕСТ /84/, уже упоминались программные системы ARIES и SURF /74,75/, универсальная имитационная программа ГРАСП описана в /85/.
Подводя итоги описанию истоков и достигнутых: результатов в области надежностного проектирования вычислительных систем, касающихся также класса отказоустойчивых вычислительных систем, можно. резюмировать следующее:
— во-первых, для актуального на сегодняшний день класса самовосстанавливающихся отказоустойчивых вычислительных, систем отсутствуют адекватные аналитические модели, раскрывающие взаимосвязь, и влияние внутренних параметров структуры системы и ее средств обеспечения надежности на показатели надежности;
— существующие универсальные имитационные алгоритмы слишком общи и непригодны для проектирования средств, обеспечения надежности самовосстанавливающихся ОУВС;
— отсутствует программное обеспечение надежностного про-евтирования самовосстанавливающихся ОУВС.
ЗАКЛЮЧЕНИЕ
.
Таким образом, в диссертационной работе исследован класс самовосстанавливающихся отказоустойчивых вычислительных систем и на основе предложенной полумарковской модели работоспособности получены аналитические оценки и разработаны имитационные алгоритмы прогнозирования показателей надежности, позволяющие проектировать средства обеспечения надежности самовосстанавливающихся систем.
За основу методики проектирования средств обеспечения надежности самовосстанавливающихся систем в диссертационной работе принята итеративная схема «синтеза через анализ», возможность использования которой для целого класса самовосстанавливающихся систем достигнута построением обобщенной модели структуры средств обеспечения надежности, модель функционирования которой /модель работоспособности/ позволяет получить достаточно универсальные оценки показателей надежности.
Предложенная в диссертационной работе обобщенная структура средств обеспечения надежности самовосстанавливающихся ОУВС построена на основе анализа типовых средств функционального и тестового самодиагностирования и самовосстановления отказоустойчивых структур с динамическим замещением отказавших элементов.
Выполненное формализованное описание обобщенной структуры предполагает задание функций распределения наработок на отказ элементов системы, параметров эффективности функционального и тестового диагностирования, степеней самопроверяемости локальных средств диагностирования и временных характеристик процессов самодиагностирования и самовосстановления, задавав.
— 129 мых функциями распределения периодичности тестового контроля и функциями распределения времени поиска и устранения неисправности .
Для получения аналитических оценок показателей надежности самовосстанавливающихся систем предложена полумарковская модель работоспособности, учитывающая отказы как основных элементов самовосстанавливающейся системы, так и средств обеспечения надежности, реальные эффективности процессов функционального и тестового диагностирования, затраты времени на процессы самодиагностирования и самовосстановления. Допущением при ¦ построении модели работоспособности явилась идеальность резервных элементов, практически достигаемая постоянным тестовым контролем и ручным восстановлением.
На основе асимптотических оценок А. Д. Соловьева для полумарковских регенерирующих процессов, в диссертационной работе получено общее асимптотическое решение задачи определения основных показателей надежности, а, также, частное решение для случая' экспоненциальных распределений наработок на отказ элементов системы, выражающее показатели надежности через X-характеристики элементов системы и параметры описания обобщенной структуры средств обеспечения надежности.
Особенностью полученного аналитического решения явилась возможность выделения обобщенного критерия качества функционирования самовосстанавливающихся структур — коэффициента разряжения потока отказов базовой безызбыточной системы средствами обеспечения надежности. Через коэффициент разряжения, с одной стороны, вместе с X-характеристиками базовой системы, выражаются основные показатели надежности самовосстанавливающихся систем — вероятность безотказной работы, средняя.
— 130 наработка до отказа, коэффициент готовности, а, с другой стороны — коэффициент разряжения зависит только от параметров описания обобщенной структуры средств обеспечения надежности. Следовательно, коэффициент разряжения может использоваться для относительного сравнения вариантов построения средств обеспечения надежности и выбора лучшего варианта построения, что определяет практическую значимость полученных аналитических решений.
Предложенные аналитические оценки показателей надежности самовосстанавливающихся систем обладают, однако, погрешностью, не позволяющей различать «близкие» варианты построения средств обеспечения надежности. Кроме этого, аналитическое решение достаточно просто только для¦экспоненциальных законов распределения наработок на отказ. Для преодоления указанных недостатков аналитического моделирования самовосстанавливающихся структур в диссертационной работе предложены имитационные алгоритмы.
Аналитико-статистический алгоритм AI позволяет прогнозировать среднее время наработки до отказа, коэффициент готовности и коэффициент разряжения потока отказов самовосстанавливающихся структур. Разработанный имитационный алгоритм А2, основанный на непосредственном моделировании случайного процесса функционирования самовосстанавливающихся систем, предназначен для расчета вероятности безотказной работы и коэффициента оперативной готовности.
Программная реализация имитационных алгоритмов выполнена на языке ФОРТРАН. Общий объем разработанных программ составляет приблизительно 450 ФОРТРАН-операторов и распределяется следующим образом: 150 операторов основной части алгоритма А1, 200 операторов основной части алгоритма А2 и 100 операторов общих для алгоритмов А1 и А2 подпрограмм. Структурирование и незначительный объем имитационных алгоритмов позволили использовать для имитационного моделирования ЭВМ типа СМ-4, Время прохождения имитационных алгоритмов не превышает 20 минут.
Созданные программные средства позволили выполнить анализ точности аналитических оценок, который показал практическую применимость асимптотических оценок для проектирования отказоустойчивых вычислительных систем по критерию вероятности безотказного функционирования. При проектировании систем по критерию среднего времени наработки до отказа погрешность аналитической оценки может достигать значительных величин /до 30 $/, что делает необходимым применение имитационных методов оценки.
Полученные асимптотические оценки, разработанные имитационные алгоритмы, созданные программные средства были использованы при надежностном проектировании специализированных вы-, числительных систем в ряде организаций г. Москвы, что подтверждено актами о внедрении результатов диссертационной работы.
