Содержание к диссертации
Введение
ГЛАВА 1. Анализ проблемы надежности и безопасности информационно-управляющих систем 22
1.1. Анализ требований к надежности и безопасности систем 23
1.1.1. Терминология надежности и безопасности 24
1.1.2. Основные показатели качества резервированных вычислительных систем 27
1.2. Основные методы повышения надежности вычислительных систем 30
1.2.1. Классификация методов резервирования 30
1.2.2. Методы структурного резервирования 32
1.2.3. Методы голосования 33
1.3. Основные методы анализа надежности вычислительных систем и устройств 34
1.3.1. Потоки отказов, используемые при анализе надежности 34
1.3.2. Логико-вероятностные методы расчета показателей надежности 36
1.3.3. Определение показателей надежности с использованием теории случайных процессов 37
1.4. Архитектуры вычислительных систем со структурным резервированием 39
1.4.1. Отказоустойчивый вычислительный кластер 39
1.4.2. Архитектура с раздельным резервированием процессора 41
1.5. Основные методы решения задачи синтеза вычислительной системы 42
1.5.1. Применение точных методов для решения задачи синтеза 43
1.5.2. Применение эвристических методов для решения задачи синтеза 44
1.6. Этапы решения задачи синтеза вычислительной системы с резервированием 45
Выводы 47
ГЛАВА 2. Формализованная модель информационно-управляющих систем со структурным резервированием 48
2.1. Анализ функциональной организации системы 49
2.1.1. Основные задачи информационно-управляющей системы со структурным резервированием 49
2.1.2. Функциональный состав системы и ее окружения 50
2.1.3. Принципы функционирования подсистемы коммутации и контроля 53
2.2. Основные предпосылки и принципы построения модели структуры информационно-управляющей системы со структурным резервированием в виде динамического типизированного графа 55
2.2.1. Идея использования модели. Требования к модели, основные принципы ее построения 55
2.2.2. Иллюстрация представления структуры вычислительной системы графом 57
2.2.3. Разбиение вершин па классы и типы 58
2.2.4. Изменение состояний вершин и графа 59
2.3. Правила построения и модификации динамического типизированного графа 61
2.3.1. Правила представления системы в виде динамического типизированного графа (группа I) 61
2.3.2. Правила соединений вершин динамического типизированного графа (группа II) 62
2.3.3. Правила введения типов вершин (группа III) 64
2.3.4. Правила изменения состояний вершин (группа IV) 66
2.3.5. Правила распространения отказа (группа V) 67
2.3.6. Правила изменения состояния динамического типизированного графа (группа VI) 70
2.4. Задача синтеза информационно-управляющей системы специального назначения с
использованием динамических типизированных графов 71
2.4.1. Общая постановка задачи синтеза 71
2.4.2. Представление задачи синтеза в терминах динамических типизированных графов 72
2.4.3. Необходимость упорядочения динамических типизированных графов при синтезе 74
Выводы 75
ГЛАВА 3. Упорядочение множества динамических типизированных графов по критериям надежности, безопасности и стоимости. доменные структуры резервированных систем 77
3.1. Отношения порядка на множестве динамических типизированных графов 78
3.1.1. Отношения порядка па множестве типов вершин 78
3.1.2. Принципы построения графов состояний системы по динамическому типизированному графу 79
3.1.3. Определение отношений порядка на множестве динамических типизированных графов 82
3.2. Упорядочение множества динамических типизированных графов по критерию безопасности 84
3.2.1. Распространение отказа из решающих вершин, лемма 85
3.2.2. Состояние динамического типизированного графа при аварии решающей вершины, лемма 86
3.2.3. Распространение отказа из формирующих вершин, лемма 87
3.2.4. Максимальные элементы по критерию безопасности, теорема 87
3.2.5. Динамические типизированные графы с несколькими решающими вершинами 89
3.3. Упорядочение множества динамических типизированных графов по критериям
надежности и стоимости 90
3.3.1. Устранение избыточных дуг, лемма 91
3.3.2. Устранение связей между однотипными вершинами, лемма 92
3.3.3. Устранение связей между независимыми участками графа, лемма 93
3.3.4. Разбиение на узлы доменов, теорема 95
3.3.5. Параметризация доменных структур 97
3.3.6. Распространение отказа из парных вершин, лемма ...99
3.3.7. Распространение отказа из вершин одного типа, теорема 100
3.3.8. Варианты оптимальных структур 100
3.3.9. Упорядочение множества динамических типизированных графов по комбинированному критерию 103
Выводы 104
ГЛАВА 4. Анализ надежностных характеристик вычислительных систем с доменной структурой. методика синтеза структур резервированных систем 106
4.1. Программа расчета вероятности безотказной работы по динамическому типизированному графу 108
4.1.1. Принцип автоматизированного расчета вероятности безотказной работы 108
4.1.2. Краткое описание программы расчета 109
4.1.3. Расчет показателей надежности варианта масштабируемой системы с резервированием 111
4.1.4. Расчет показателей надежности двухдоменной системы 112
4.2. Сравнительный анализ вариантов доменной организации резервированных систем 113
4.2.1. Зависимость показателей надежности и стоимости устройств коммутации и контроля от числа их входов 115
4.2.2. Сравнительный анализ структур с изменяющейся устойчивостью доменов... 116
4.2.3. Сравнительный анализ структур с изменяющимся размером доменов 120
4.2.4. Сравнительный анализ структур с изменяющимся числом доменов 123
4.2.5. Сравнительный анализ структур с различным распределением устройств между доменами 126
4.3. Синтез структуры системы с доменной организацией 130
4.3.1. Сводка полученных при анализе рекомендаций 130
4.3.2. Методика синтеза структур вычислительных систем с доменной организацией 131
Выводы 134
ГЛАВА 5. Реализация структурного метода обеспечения надежности на примере системы-прототипа 136
5.1. Функциональный состав и надежностные характеристики узлов системы-прототипа 137
5.1.1. Относительные надежностные характеристики компонентов вычислительной системы 137
5.1.2. Функциональный состав системы-прототипа 138
5.1.3. Подсистема коммутации и контроля 140
5.1.4. Функциональный состав высоконадежной платы 141
5.2. Синтез структуры системы с использованием разработанного подхода 142
5.2.1. Выбор количества доменов в системе 142
5.2.2. Распределение устройств между доменами 144
5.2.3. Структура системы с одним доменом 146
5.2.4. Структура системы с двумя доменами 149
5.2.5. Обобщенная структура системы с большим количеством доменов 152
5.2.6. Структурная схема системы-прототипа 154
5.3. Требования к устройствам системы-прототипа 155
5.3.1. Доменная шина 155
5.3.2. Доменный коммутатор 156
5.3.3. Контроллер связи 158
5.4. Основные проблемы доменной организации системы и подходы к их решению... 158
5.4.1. Проблема синхронизации вычислений 159
5.4.2. Проблема конфигурации и реконфигурации системы 161
Выводы 162
Заключение 163
Список использованных источников
- Терминология надежности и безопасности
- Основные задачи информационно-управляющей системы со структурным резервированием
- Принципы построения графов состояний системы по динамическому типизированному графу
- Принцип автоматизированного расчета вероятности безотказной работы
Введение к работе
Актуальность темы. Информационно-управляющие системы специального назначения (ИУССН) используются для автоматизации контроля и управления в сложных технических системах различного назначения: космических комплексах, летательных аппаратах разного класса, наземных станциях контроля и управления, судах различного назначения, энергетических комплексах и др.
Важнейшей характеристикой ИУССН является надежность. Надежность системы зависит от большого числа факторов: от се функциональной организации, от технологии изготовления элементов, узлов и соединений между узлами, от окружающей среды и др.
Основой создания узлов вычислительных систем в настоящее время стали СБИС, изготовленные по субмикронной технологии (в последнее время - и по нанотехнологии). С уменьшением проектной нормы быстро возрастает уровень интеграции СБИС, и все большее число соединений реализуется внутри кристалла. При переходе в область нанотехнологии появляются дополнительные виды сбоев и отказов внутри кристалла из-за влияния элементарных частиц космического излучения. Это обуславливает потребность резервирования узлов и устройств внутри кристалла. При использовании СБИС, выполненных по наиболее освоенной сейчас субмикронной технологии, возможно применение резервирования и на более высоких уровнях (уровень отдельных СБИС, уровень плат).
Проблема повышения надежности вычислительных систем изучается довольно давно. Первая работа на эту тему датируется 1952 годом и принадлежит Джону фон Нейману [38]. Сейчас широко разработанными являются задачи, связанные с повышением надежности отдельных компонент системы (работы У. Пирса, Д. Трайона, Э. Мура [29, 37, 46, 49, 57, 84, 85, 86]), с повышением надежности передачи данных (работы К.
Шеннона, М. Голея, Р. Хэмминга [26, 59, 65, 70, 72, 74, 75]), с определением
* надежностных характеристик вычислительных систем (работы И. А.
Рябинина, Г. Н. Черкесова, А. М. Половко [20, 22, 30, 47, 51, 55, 61, 62, 63]).
Разработан ряд стандартов и рекомендаций, связанных с надежностью
систем и их элементов [1,4].
ИУССН относятся к вычислительным системам, ошибка на выходе которых может иметь критические последствия для их окружения - иначе говоря, к системам высокой достоверности (ultradependable systems) [87]. При проектировании такого рода систем следует учитывать не только их надежность, но и их безопасность. Теория безопасности по сравнению с теорией надежности изучается не так давно, в этой области могут быть названы работы [51, 77] и стандарты [2, 3].
* По этой причине в ИУССН крайне важно своевременное обнаружение
отказа. Механизмы контроля надежности, применяющиеся в типовых
элементах системы, обычно недостаточны или отсутствуют. В этом случае
необходимо применение структурного резервирования, контроль надежности
осуществляется на системном уровне с помощью решающих элементов [30,
38,46,51,61,77,87].
При проектировании вычислительной системы с применением решающих элементов встает задача выбора структуры системы. Используемые готовые элементы и инструментарий проектирования постоянно и весьма динамично развиваются. С учетом этих факторов, актуально обеспечение надежности и безопасности системы на этапе ее проектирования.
При эвристическом подходе к проектированию вычислительной
системы основными источниками информации при синтезе служат сведения
I о системе-прототипе и ее недостатках, новые требования к вычислительной
системе, новые средства реализации системы. По мере развития средств
вычислительной техники, увеличения сложности вычислительных систем и
ужесточения требований к ним число возможных вариантов функциональной организации резервированных систем быстро возрастает.
Существующие автоматизированные подходы связаны с выбором оптимальной структуры из множества некоторого узкого класса - в частности, из множества последовательно-параллельных систем [78, 79, 80, 89] с различной кратностью. Недостаток такого подхода состоит в том, что оптимальная структура может не принадлежать выбранному множеству.
Поэтому требуется разработка модели вычислительных систем, обладающей полнотой порождения множества вариантов структуры ИУССН. В модели должна существовать возможность на уровне функциональной организации рассматривать процессы распространения отказов и определять условия, обеспечивающие свойства надежности и безопасности. Модель должна позволять осуществлять сравнительную оценку характеристик систем при ограниченной информации (без детальной проработки вариантов) и обоснованно уменьшать многообразие вариантов, требующих детальной проработки. На базе такой модели можно разработать методику синтеза структур вычислительных систем с требуемыми свойствами.
Объектом исследования является информационно-управляющая система специального назначения (ИУССН). В соответствии с распределенностью в пространстве оборудования технических систем ИУССН строятся как системы распределенной обработки данных, реализуемые в виде локальной вычислительной сети. Обычно сеть содержит пульт управления, приборы, распределенные по отдельным объектам, и, возможно, встраиваемые системы (интеллектуальные датчики и исполнительные устройства).
Особенностью многих ИУССН являются сравнительно умеренные требования к производительности в сравнении с суперкомпьютерами и системами с массовым параллелизмом [28, 33]. Как правило, производительности современного процессора вполне достаточно для
решения задач, определенных для одного прибора. Это ограничивает класс рассматриваемых в данной работе вычислительных систем. Рассматриваются следующие свойства системы.
Безопасность. Вероятность возникновения необнаруженного отказа должна быть не выше определенного уровня (поскольку наличие необнаруженного отказа может привести к ошибкам в результатах на выходе системы и, как следствие - к критическим последствиям для окружения системы).
Безотказность. Система должна обеспечивать требуемый уровень безотказности.
Типовые элементы. В составе системы могут быть использованы типовые (готовые) элементы с недостаточными характеристиками по надежности и безопасности.
Невосстанавливаемость элементов. Во время работы системы, отказавшие элементы не могут быть восстановлены.
Цель работы. Сокращение времени проектирования и повышение качества разработки системы со структурным резервированием путем автоматизации синтеза.
Задачи исследования.
Разработка модели для представления произвольных вариантов структуры системы с резервированием, позволяющей анализировать процессы распространения отказов. Разработка правил построения и модификации модели.
Разработка методики сравнительного анализа характеристик ИУССН по предложенной модели и отбрасывания заведомо бесперспективных структур с последующей параметризацией оставшихся структур.
Создание методики поиска наилучшей структуры из ограниченного множества вариантов.
4. Разработка функциональной схемы системы-прототипа с целью иллюстрации методики и решения последующих задач.
Методы и средства исследования. Для теоретических исследований
применяются методы теории отношений, теории графов, теории надежности,
логико-вероятностные методы, теории случайных процессов,
математического моделирования, математического программирования. Для
построения моделей устройств использовались системы
автоматизированного проектирования MAX+PLUS II, Quartus II и среда программирования Microsoft Visual Studio. Положения, выносимые на защиту.
Модель структуры ИУССН на основе введенных в работе динамических типизированных графов, обладающая возможностью рассмотрения процессов распространения отказов и полнотой представления множества вариантов структуры.
Выделение подмножества структур ИУССН, оптимальных по комбинированному критерию надежности, безопасности и стоимости -доменных структур, включающих множество независимых узлов доменов с голосующим устройством на входе каждого.
Методика синтеза структур ИУССН с доменной организацией.
Научная новизна работы.
Разработана модель структуры ИУССН - динамический типизированный граф. Модель обладает возможностью рассматривать на функциональном уровне процессы распространения отказов и полнотой представления множества вариантов структуры ИУССН. Разработана программа расчета вероятности безотказной работы системы по динамическому типизированному графу.
Предложена методика упорядочения структур по комбинированному показателю, учитывающему свойства надежности, безопасности и стоимости, с использованием динамических типизированных графов.
Методика позволяет осуществлять сравнительную оценку характеристик систем при ограниченной информации и обоснованно уменьшать многообразие вариантов, требующих детальной проработки.
С применением методики упорядочения структур выделено подмножество оптимальных структур и доказана возможность разделения структуры из данного множества на домены - наборы не связанных друг с другом узлов с голосующим устройством на входе и ациклической структурой.
Выделен новый класс из множества доменных структур ИУССН -масштабируемые структуры с резервированием. Главное преимущество данного класса структур заключается в возможности увеличения надежности системы путем увеличения числа однотипных устройств без изменения структуры голосующих устройств.
Разработана методика синтеза структуры ИУССН с доменной организацией, позволяющая осуществить обоснованный выбор числа доменов в системе, распределения устройств между доменами, числа однотипных устройств в системе и числа входов используемых голосующих устройств.
Достоверность результатов. Достоверность методики упорядочения структур и тезис о возможности разбиения оптимальной структуры на домены подтверждается доказательствами утверждений, положенных в основу методики, а также включением в полученное множество оптимальных структур известного множества последовательно-параллельных систем.
Достоверность зависимостей вероятности безотказной работы системы от характеристик доменной структуры подтверждается получением некоторых результатов двумя различными методами, совпадением результатов с известными частными случаями и использованием автоматизированного подхода при их получении.
Практическая значимость работы. Полученные в диссертационной работе методики синтеза и анализа структур позволяют снизить
трудоемкость и повысить качество проектирования, а также обосновать правильность принятых решений на системном этапе проектирования. С использованием предложенных методик разработан прототип ИУССН на основе СБИС ПЛ. Он позволяет проводить экспериментальные исследования в системном окружении и трансформировать разработанные блоки на отечественную базу БМК. Результаты диссертационной работы могут быть использованы в проектных организациях при создании отказоустойчивых вычислительных систем, а также в соответствующих дисциплинах при обучении студентов.
Реализация результатов работы. Результаты, полученные в диссертации, используются в учебном процессе на кафедре автоматики и вычислительной техники ГОУ ВПО «СПбГПУ» при чтении лекций по курсу «Проектирование аппаратных средств вычислительных систем», а также при выполнении практических занятий на экспериментальной установке системы-прототипа, спроектированной с использованием теоретических результатов работы.
Научно-исследовательские работы. Результаты диссертации были получены в ходе выполнения научно-исследовательских работ по следующим проектам.
Разработка методики и инструментария для проектирования и верификации высоконадежных специализированных процессоров на базе СБИС ПЛ. Программа министерства образования РФ, подпрограмма «Международное научно-образовательное сотрудничество», проект №1283 за 2003 год.
Разработка методики и инструментария для проектирования и верификации высоконадежных специализированных процессоров на базе СБИС ПЛ. Программа министерства науки и образования РФ, федерального агентства но образованию «Федерально-региональная
политика в науке и образовании», подпрограмма «Международное научно-образовательное сотрудничество», проект №1647 за 2004 год.
Создание центра по коммерциализации разработок Санкт-Петербургского государственного политехнического университета в области проектирования радиоэлектронной аппаратуры с использованием технологий FPGA и ASIC. Программа министерства науки и образования РФ, федерального агентства по образованию «Развитие научного потенциала высшей школы», подпрограмма 3 «Развитие инфраструктуры научно-технической и инновационной деятельности высшей школы и ее кадрового потенциала» на 2005 год.
Развитие центра трансфера технологий проектирования ASIC/FPGA на базе Санкт-Петербургского государственного политехнического университета для промышленности региона. Программа и подпрограмма п. 3, 2005 год.
Развитие международного центра трансфера технологий проектирования ASIC на базе Санкт-Петербургского государственного политехнического университета. Программа и подпрограмма п. 3,2005 год.
Апробация работы. Результаты работы докладывались и обсуждались на VIII Всероссийской конференции «Фундаментальные исследования в технических университетах» (2004 год) и на ежегодной конференции «Практические аспекты разработки отечественных СБИС класса «система на кристалле»» (2006 год).
Публикации. По результатам диссертационной работы опубликовано шесть печатных работ, в том числе в журнале «Научно-технические ведомости СПбГТУ» (входит в «Перечень ведущих рецензируемых научных журналов и изданий, выпускаемых в Российской Федерации»). Всего опубликовано три журнальных статьи и три тезиса конференций.
Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка используемых источников. Общий
объем работы составляет 173 печатные страницы, работа включает 50 рисунков, список источников из 89 наименований, одно приложение.
Первая глава диссертационной работы посвящена анализу проблемы надежности и безопасности информационно-управляющих систем. Определены ограничения при решении задачи синтеза системы. Рассмотрена терминология теории надежности и теории безопасности, основные показатели качества вычислительных систем с резервированием. Рассмотрены основные методы повышения надежности вычислительных систем, применимые в рамках данной работы. Приведены наиболее распространенные методы анализа надежности вычислительных систем и устройств. Выполнен краткий обзор архитектур вычислительных систем с резервированием, рассмотрены достоинства и недостатки различных архитектур. Рассмотрены основные постановки и методы решения задачи синтеза информационно-управляющей системы. Произведено разбиение задачи синтеза на отдельные этапы, сформулирован порядок ее решения. Определены основные задачи исследования.
Во второй главе рассматривается функциональная организация системы, разрабатывается модель представления структуры вычислительной системы с резервированием. Для этого вводится понятие динамического типизированного графа и система правил для работы с динамическими типизированными графами. Модель позволяет анализировать процессы распространения отказов в системе и рассчитывать характеристики надежности. Формулируется задача синтеза информационно-управляющей системы специального назначения в терминах модели динамических типизированных графов. Предлагаются пути решения задачи синтеза, развиваемые в двух следующих главах.
В третьей главе выделяется подмножество максимальных элементов в множестве динамических типизированных графов. С этой целью формулируются отношения порядка по критериям надежности, безопасности
и стоимости, а также комбинированный критерий оптимальности. Обосновываются требования к структуре, оптимальной по показателю безопасности. Анализируются и обосновываются возможные преобразования динамического типизированного графа, не ухудшающие показатели надежности и стоимости. Доказывается возможность разбиения графа, максимального по комбинированному критерию, на непересекающиеся узлы доменов с определенными свойствами. На основании данного разбиения, вводятся понятия домена и доменной структуры, вводится параметризация доменной структуры. Обосновывается структура домена с заданными параметрами. При анализе доменных структур с различными параметрами выделяется новый класс структур - масштабируемые структуры с резервированием.
В четвертой главе анализируются надежностные характеристики структур, входящих в состав выделенного подмножества максимальных элементов. Разрабатывается программа расчета вероятности безотказной работы системы по динамическому типизированному графу. Рассмотрены и проанализированы доменные структуры с изменяющимися характеристиками - числом доменов, устойчивостью доменов, размером доменов. Определены наиболее эффективные способы повышения надежности при разных сравнительных характеристиках устройств системы и связей между ними. Рассмотрены варианты структур с различным количеством доменов, проанализированы различные варианты коммутации доменов, получены надежностные характеристики различных вариантов доменных структур. На основании данных результатов обосновывается методика синтеза вычислительных систем с доменной структурой.
В пятой главе рассматривается практическая задача синтеза прототипа информационно-управляющей системы специального назначения на основе СБИС программируемой логики. Определяется функциональный состав системы-прототипа и надежностные характеристики элементов
системы. Синтезируется структура подсистемы коммутации и контроля с использованием разработанного подхода. Рассматриваются основные требования к устройствам системы-прототипа. Анализируются проблемы синхронизации и конфигурации системы и подходы к их решению.
В заключении формулируются основные результаты работы и направления дальнейших исследований.
Терминология надежности и безопасности
Под термином система в дальнейшем будем понимать совокупность действующих элементов, взаимосвязанных между собой и взаимодействующих как единое целое [51, 61]. Связи между элементами отличают систему от простого конгломерата частей. Под элементом системы будем понимать любой обьект, внутренняя структура которого на данном этапе анализа надежности не учитывается [61].
Комплексное свойство надежности заключается в сохранении во времени значения всех параметров системы, характеризующих ее способность выполнять требуемые функции в заданных режимах и условиях применения, технического обслуживания, хранения и транспортирования [1]. В зависимости от назначения системы, надежность может включать в себя безотказность, долговечность, ремонтопригодность и сохраняемость - или различные сочетания этих свойств. Свойство сохраняемости в первую очередь относится к хранению и транспортированию системы [1], и в данной работе не рассматривается.
Рассмотрим данную ситуацию с точки зрения окружения системы [76]. Окружение системы формирует для нее исходные данные и использует ее результаты. Это может быть человек, вводящий данные с клавиатуры и наблюдающий результаты на мониторе, либо это может быть система более высокого уровня, включающая в себя данную. В окружении системы функционируют ее операторы и пользователи [76].
Пользователи системы - потребители услуг, предоставляемых системой [76]. Под услугой здесь понимаются результаты, формируемые по строго определенному закону. Отсутствие результатов либо нарушение закона их формирования означает прекращение предоставления услуг, и, как следствие, нарушение требований к надежности системы, прежде всего - к ее безотказности, способности непрерывной работы в течение некоторого интервала времени [1].
Оператор наблюдает за работой системы и осуществляет ее обслуживание. С этой целью система предоставляет оператору данные о своем внутреннем состоянии. Обслуживание включает в себя включение и выключение системы, диагностику неисправностей, замену неисправных элементов системы на запасные и тому подобное. Выполнение таких свойств системы, как долговечность (сохранение работоспособного состояния в течение всего срока службы) и ремонтопригодность (приспособленность к выполнению технического обслуживания и ремонта), обычно требует вмешательства оператора на некоторых стадиях.
Сбои и отказы в работе системы можно рассматривать как случайные события либо в пространстве (среди множества элементов, входящих в систему), либо во времени (в течение срока функционирования системы) [46]. Отказ системы (или ее элемента) - это событие, после которого система (или ее элемент) утрачивает свою работоспособность, то есть теряет возможность предоставления услуг [51]. Отказ элемента системы может вести или не вести к отказу системы в целом. Сбой - самоустраняющееся (без вмешательства оператора или пользователя) прекращение системой предоставления услуг на относительно короткий интервал времени, иногда его называют самоустраняющимся отказом [30]. Сбой одного и того же характера может возникать несколько раз через относительно короткие промежутки времени -так называемый перемежающийся отказ [30].
Согласно [2, 3], безопасность - способность системы выполнять свои функции без травмирования и нанесения вреда здоровью окружающих людей. Это понятие может быть обобщено - способность выполнять свои функции без нанесения значительного ущерба [51] окружению системы. Под ущербом понимаются затраты, вызванные прекращением предоставления услуг системой.
Ущерб в теории безопасности подразделяется на ущерб большого масштаба, или коллапс, и ущерб допустимого масштаба, или вред [51]. Данное разделение весьма условно, многое здесь зависит от конкретной специфики системы. Как правило, коллапс связан с разрушением самой системы, или, еще хуже, окружения системы, опасностью для жизни людей, эксплуатирующих систему, а вред - с прекращением работы системы, не имеющим опасных последствий.
Отказы в зависимости от вызванного ими ущерба делятся на два класса. В теории безопасности используется следующая терминология [51]: неисправность, вызвавшая коллапс, называется отказом, неисправность, вызвавшая вред, называется дефектом. Однако в теории надежности принята несколько другая терминология (см. определение отказа выше - оба указанных класса неисправностей применительно к вычислительным системам называются отказами). В связи с этим в дальнейшем отказ, вызвавший коллапс, будем называть авария, отказ, вызвавший вред, будем называть остановка.
Важным свойством системы, часто позволяющим предотвратить аварии, является возможность обнаружения отказа. Отказ системы или ее элемента, успешно найденный подсистемой контроля непосредственно после его возникновения, называется явным, в противном случае он называется скрытым [1]. Для всей системы необходимо обнаружение только факта отказа, для элемента системы необходима также диагностика конкретного места возникновения отказа в системе. Обнаружение отказа системы позволяет изменить состояние ее выходов на особое состояние, не представляющее опасности для системы и ее окружения (например, в железнодорожных системах с этой целью включают красный свет на всех направлениях движения) - это означает, что обнаруженный отказ является остановкой, а не аварией. Необнаруженный отказ необязательно вызывает коллапс, но связан с риском [2, 3] его возникновения. Поскольку риск возникновения коллапса при необнаруженном отказе не всегда поддается точной оценке, в дальнейшем при оценке показателей безопасности аварией считается любой необнаруженный отказ.
Другим важным свойством, связанным с надежностью системы, является возможность предотвращения распространения отказа. Отказ элемента, ведущий к отказу других элементов системы (в том числе из-за передачи в них неправильных входных данных) и в перспективе приводящий к отказу всей системы, называется активным [76], в противном случае он называется пассивным. Последовательность из отказов элементов, каждый из которых является причиной следующего, называется траекторией распространения отказа. Сдерживание процесса распространения отказа (например, путем отключения от системы отказавшего элемента) называется маскированием отказа (fault masking) [76, 87].
Основные задачи информационно-управляющей системы со структурным резервированием
В процессе проектирования вычислительная система разбивается на подсистемы, каждая из которых решает одну или более из перечисленных выше задач. Однако разбиение системы на подсистемы может производиться различными способами.
Основной подсистемой является вычислительная подсистема, отвечающая за выполнение вычислительной задачи. В нее обычно входят процессоры, запоминающие устройства различного типа, устройства ввода-вывода.
Информационная связь между устройствами обеспечивается коммутирующей подсистемой, решающей задачу передачи данных и обычно также задачу синхронизации устройств. В нее входят магистрали и коммутаторы различных типов.
Остальные задачи специфичны для вычислительной системы с резервированием. В систему следует добавить подсистему контроля надежности, проверяющую корректность результатов различных устройств (например, путем сравнения их друг с другом), и решающую задачи обнаружения, маскирования и первичной диагностики отказов.
Кроме этого, в систему добавляется подсистема конфигурации, производящая анализ результатов, поступающих от подсистемы контроля надежности и принимающая решение об отключении неисправных устройств на его основе. Эта же подсистема обеспечивает тестирование работоспособности системы в неполных конфигурациях и замену неисправных устройств на исправные устройства. Таким образом, подсистема конфигурации решает задачи изоляции отказов, восстановления системы и вторичной диагностики отказов.
Основными элементами окружения системы являются пользователь и оператор. Пользователь (основной потребитель результатов работы системы) может быть человеком, наблюдающим на мониторе результаты анализа информации, либо исполнительным устройством, связанным с системой через устройство сопряжения с объектом. В любом случае, пользователь связывается с системой через устройства ввода-вывода. Некоторые из устройств ввода-вывода должны присутствовать в системе в единственном экземпляре - решение о корректности тех или иных результатов должно приниматься внутри вычислительной системы. Такие устройства ввода-вывода будем называть уникальными.
Оператор осуществляет замену неисправных устройств на исправные, проводит тестирование системы и ручную настройку ее конфигурации - если это требуется. Таким образом, оператор связан с подсистемой конфигурации. Подобное разбиение приводит к функциональной схеме системы, изображенной на рис. 2.1.
Однако приведенное разбиение на подсистемы при дальнейшей реализации наталкивается на некоторые проблемы. Прежде всего, они связаны с необходимостью передачи информации между подсистемами. Действительно, пусть процессор передает некоторые данные ЗУ. Первоначально данные поступают в коммутирующую подсистему. Чтобы удостовериться в их правильности, их нужно передать в систему контроля надежности. После этого подсистема конфигурации проверяет, не отказал ли данный процессор раньше, подсистема контроля надежности сравнивает его выходные данные с выходными данными, поступившими от других процессоров, и передает в коммутирующую подсистему решение -передавать данные или заблокировать их.
Таким образом, данные передаются от одной подсистемы к другой, что приводит к понижению производительности. На практике, сравнение нескольких результатов друг с другом и последующий выбор корректного результата из нескольких может быть выполнен одним устройством. Такое устройство принимает данные от нескольких входных устройств и передает их одному или нескольким выходным - сочетая, таким образом, в себе функции коммутирующей подсистемы и подсистемы контроля надежности.
Устройства конфигурации для отключения того или иного устройства из системы (задача изоляции отказов) передают информацию устройствам контроля надежности. Для принятия решения о неисправности устройства они также используют информацию от устройств контроля надежности (а также команды от оператора). В связи с этим, на практике удобнее производить автоматическую изоляцию отказов внутри устройства контроля надежности. Подсистема конфигурации при этом превращается в монитор, показывающий оператору текущее состояние системы и дающий ему возможность вручную отключать устройства системы.
Принципы построения графов состояний системы по динамическому типизированному графу
Для формулировки отношений на множестве графов необходимо знать, как соотносятся друг с другом характеристики различных устройств, входящих в систему. Поскольку набор вычислительных устройств при решении задачи синтеза считается заданным (раздел 2.4), соотношение их характеристик является известным. На данном этапе решения задачи достаточно знать, что вычислительные устройства, представленные однотипными основными вершинами, имеют одинаковые характеристики.
Характеристики устройств коммутации и контроля зависят от их сложности, которая определяется числом их связей. Для отражения этого факта определим отношение Q, на множестве типов промежуточных вершин (у вершин одного типа число связей одинаково). Сложность соответствующего устройства зависит от числа выходов данной вершины х, числа входов от разнотипных устройств у, числа входов от однотипных устройств z, поскольку разные типы связей влияют на характеристики по-разному. ЕСЛИ ЧИСЛО СВЯЗеЙ Промежуточных ВерШИН Vi И V2 раВНО (ХЬ уі, Z) и (х2, уг, z2) соответственно, то верно следующее утверждение. Справедливо v2C/,V/, если и только если х[ Х2, уі У2, zi z 2 и хотя бы одно неравенство является строгим (при большем числе связей характеристики хуже). Заданное отношение, очевидно, обладает всеми свойствами отношений строгого порядка.
Ввиду отсутствия резервирования внутри устройств коммутации и контроля их сложность определяет также их надежность и безопасность. То есть, менее сложное устройство в данном случае является одновременно более надежным и более безопасным.
Для сравнения характеристик надежности и безопасности системы по динамическому типизированному графу при деградации системы из-за распространения отказов необходим анализ последовательного изменения состояний его вершин. Наиболее удобными для этой цели являются графы состояний, используемые в теории случайных процессов. Сравнивая графы состояний двух систем, можно сделать вывод об их относительной надежности и безопасности.
В начальном состоянии системы (подраздел 2.3.4, п. 2), все вершины находятся в состоянии W (полная конфигурация, на графах состояний обозначается цифрой 0). Затем (подраздел 2.3.4, п. 4) происходят последовательные отказы вершин графа, причем каждый отказ переводит систему в другую конфигурацию (на графах состояний конфигурация обозначается набором отказавших вершин системы). Каждой конфигурации соответствует вершина графа состояний, а каждому отказу - дуга графа состояний. Рано или поздно система попадает в конфигурацию, соответствующую состоянию S или F - все такие конфигурации являются конечными.
Для определения показателей надежности системы объединим все конфигурации, соответствующие состоянию S или F, в одно конечное состояние Е (Error). Получим граф надежности системы. Отметим, что в графе надежности системы не имеет значения, был ли отказ обнаруженным или нет (если последовательность обнаруженных отказов выводит граф из состояния W, то последовательность необнаруженных отказов ведет к тому же эффекту - подраздел 2.3.5 п. 2, подраздел 2.3.6 п. 6). Поэтому на интенсивность переходов в графе надежности системы влияют только показатели надежности устройств системы.
Для определения безопасности системы выделим из графа надежности подграф, из которого исключены конфигурации, соответствующие состоянию S и ведущие в них дуги, а конфигурации, соответствующие состоянию F, объединены в одно конечное состояние Е. Получим граф безопасности системы. Дуги, соответствующие обнаруженным отказам, автоматически из него исключаются, поскольку не могут привести систему в состояние F либо повлиять на интенсивность переходов в него (подраздел Ъ 2.3.5 п. 2, подраздел 2.3.6 п. 6). Поэтому на интенсивность переходов в графе безопасности влияют только показатели безопасности устройств системы, что позволяет анализировать надежность и безопасность отдельно друг от друга. Рассмотрим в качестве примера граф системы, изображенный на рис. 3.1. К переходу в состояние F ведут только необнаруженные отказы вершин В и К. К выходу из состояния W ведут отказы вершин В и К, а также отказ двух из трех вершин типа А.
На рис. 3.2 состояние 0 - полная конфигурация, состояние Е -прекращение работы, состояние А - полная конфигурация без одной вершины типа А. Над дугами графов указано, отказы каких вершин ведут к переходу из состояния в состояние. Еще раз отметим, что в графе надежности принимаются во внимание любые отказы, в графе безопасности - необнаруженные отказы.
Решив систему дифференциальных уравнений Колмогорова-Чепмена [14, 27], получим вероятности нахождения системы в каждой конфигурации. Сложив вероятности всех конфигураций, кроме соответствующей состоянию Е, получим вероятность безотказной работы (для графа надежности) или вероятность безаварийной работы (для графа безопасности). Путем интегрирования, можно рассчитать среднюю наработку до отказа или до аварии.
Здесь же, нас будет интересовать характер изменения указанных показателей при небольшом изменении системы. Подобные зависимости рассмотрены в следующем подразделе.
Показатели надежности и безопасности системы подчиняются нескольким основным правилам, верным независимо от закона распределения отказов отдельных устройств. В качестве показателей надежности может использоваться как средняя наработка до отказа, так и вероятность безотказной работы в течение заданного интервала времени. Утверждения, сформулированные для критерия надежности, верны и для критерия безопасности - только вместо графа надежности необходимо рассматривать графы безопасности.
1. Лучшие характеристики. Пусть динамические типизированные графы gu g2 имеют графы надежности hi, h2. Пусть графы надежности имеют одинаковую структуру, причем дуга (А, В) в графе надежности hj соответствует отказу вершины К, а в графе надежности h2 соответствует отказу вершины L (здесь А, В - определенные конфигурации ДТГ). Пусть все остальные дуги в графах надежности соответствуют отказу однотипных вершин. Тогда, если КСЬЦ то giRbg2, и наоборот. Пояснение. В системе уравнений Колмогорова-Чепмена производные для вероятностей отдельных конфигураций в графе gi будут не меньше, чем те же производные в графе g2. Это означает, что вероятности отдельных конфигураций в графе gi будут уменьшаться не быстрее, чем те же вероятности в графе g2, а значит, показатель надежности для графа gi будет не ниже показателя надежности для графа g2. Поскольку в графе g, имеется одна конфигурация с большей производной, неравенство превращается в строгое. 2. Последовательное включение дуги. Пусть динамические типизированные графы gi и g2 имеют графы надежности h, и h2. Пусть А - корневая вершина графа h. Пусть граф h2 включает в себя граф h и дополнительную дугу (D, А) (рис. 3.3), все дуги в графах h, и h2, не совпадающие с дугой (D, А), соответствуют отказу однотипных вершин ДТГ. Тогда g2Rbgi- Пояснение. Переход из конфигурации D в конфигурацию А займет определенное время, а в остальном графы надежности совпадают - по этой причине, вероятность работоспособного состояния для графа g2 будет выше, чем для графа g. Обобщение. То же правило верно при последовательном включении дуги в другой участок графа g,.
Принцип автоматизированного расчета вероятности безотказной работы
В этом разделе определяются основные закономерности, связанные с отношениями порядка Rb и Сь на множестве G(P, D), и определяется множество максимальных элементов для данного отношения.
Анализ графов надежности существенно сложнее анализа графов безопасности. В графе безопасности важны только переходы динамического типизированного графа в состояние F, которые вызываются только отказами решающих вершин и их формирующих вершин (см. раздел 3.2). В графе надежности, однако, важны как переходы в состояние F, так и переходы в состояние S, причем последние могут быть вызваны несколькими отказами вершин различных типов. Кроме того, на практике выигрыш в надежности системы часто приводит к проигрышу в ее стоимости.
В первую очередь представляют интерес такие преобразования динамических типизированных графов gi" g2, которые обеспечивают одновременное выполнение условий g2Rbgi и g2Cbg. Граф g, входящий в множество максимальных элементов, не должен допускать ни одно из подобных преобразований.
Условие. Пусть в динамическом типизированном графе g присутствует дуга Ki- Lj, причем у вершины Lj нет других входных вершин типа К (рис. 3.8). Удалим дугу Kj- Lj из графа gt, получив, таким образом, граф g2 (модифицированные вершины Kj и Lj обозначим за Kj и Lj ). Если для графа g2 выполняется свойство сильносвязности (иначе говоря, граф g2 удовлетворяет правилам, установленным для динамического типизированного графа), то g2Rbgi и g2Q,gi. дуг.
Доказательство. Стоимость. Графы gi и g2 различаются только числом связей у вершин Kj и Lj - выполняются условия Kj CbKj и Lj CbLj (подраздел 3.1.1, п. 2). Поэтому, выполнено условие о вершинах меньшей стоимости (подраздел 3.1.3, п. 4). Поэтому g2Cbgi.
Надежность. В графе gi выход вершины Kf из состояния W повлечет за собой выход вершины Lj из состояния W, так как у вершины L, нет других входов типа К (подраздел 2.3.5, п. 2). В графе g2 выход вершины К, из состояния W может как привести к выходу Lj из состояния W, так и не привести к этому (в зависимости от структуры связей). В первом случае графы надежности для gi и g2 имеют одинаковую структуру, но вершины в графе g2 имеют лучшие характеристики (Kj CbKj и Ц СьЦ). Во втором случае в графе g2 также появляются дополнительные последовательные дуги, связанные с отказом вершины L, . По пи. 1-3 подраздела 3.1.3 выполняется g2Rbgi- Лемма доказала.
Условие. Пусть динамический типизированный граф gi включает в себя несколько однотипных вершин, входных друг для друга, каждая из которых также имеет входную вершину (рис. 3.9, слева). Заменим связи между однотипными вершинами Hj- Hj на связи с входными для них вершинами Aj- Hj , получив, таким образом, динамический типизированный граф g2 (рис. 3.9, справа). Тогда выполняется g?Rbgi и g2Q,gi.
Доказательство. Стоимость. Вершины типа Hj , по сравнению с вершинами типа Hj, имеют одинаковое количество входных связей и Меньшее КОЛИЧеСТВО ВЫХОДНЫХ. ПОЭТОМУ ВЫПОЛНЯеТСЯ уСЛОВИе Hj CbHj (подраздел 3.1.1, п. 2), выполнено условие о вершинах меньшей стоимости (подраздел 3.1.3, п. 4). Поэтому g2Cbg.
Надежность. Для графа gi, выход вершины Aj из состояния W ведет к выходу вершины Hj из состояния W (подраздел 2.3.5, п. 2). Для графа g2 выход вершины Aj из состояния W не всегда ведет к выходу вершины Hj из состояния W. Это означает, что в графе надежности для g2 имеются дополнительные последовательные дуги. Кроме того, вершины Hj имеют лучшие характеристики по сравнению с вершинами Hj. По пп. 1-3 подраздела 3.1.3 выполняется g2Rbgi- Лемма доказана.
Будем называть промежуточную вершину динамического типизированного графа сдерживающей вершиной, если у нее имеется два и более однотипных входов.
Условие. Пусть в динамическом типизированном графе gi имеется несколько сдерживающих вершин типа Н с входами типа А и несколько промежуточных (не сдерживающих) вершин типа К и L. Пусть цепи Hj- ...- Lj- ...- Kj не включают в себя других сдерживающих вершин для любого m (существование цепей обусловлено свойством сильносвязности) и существуют дуги Lj- Kf(i), такие, что Щ)ф\. Устраним дуги Lj-Жці) из графа gi, получив, таким образом, граф 2 (типы его вершин обозначим L , К ). Связи между вершинами типа А и вершинами типа Н в графе g2 могут быть переупорядочены так, чтобы сильносвязность графа g2 не нарушалась, и были выполнены условия: g2Rbgi, g2Q,gi.
Доказательство. Сильносвязность. В графе gi для любой пары вершин Kj и Aj существует соединяющая их цепь. В графе g2 часть этих цепей может быть разрушена, но для каждой вершины Kj по-прежнему существует хотя бы одна вершина Aj с цепью Kj - ...- Aj, и, наоборот, для любого Aj существует Kj с цепью Kj - ...- Aj. В противном случае, таких цепей не существует и в графе gi.
Тогда наличие в графе g2 цепей A(Kj )- Hf,j) обеспечивает его сильносвязность, так как существуют цепи Lj - Ki - ...- A(Kj ) и Hr(j)- ...- K-(j) , и, таким образом, восстанавливаются удаленные цени Li - .-.- K j) .
Если такие цепи в графе g2 отсутствуют, переупорядочим дуги, связывающие вершины типов А и Н, аналогично рис. 3.11 (каждая вершина А связывается с соответствующей ей вершиной Н и со следующей вершиной по кольцу). Если в графе gi у вершин Н было больше чем два входа, добавим предыдущую по кольцу вершину и так далее. Подобная структура связей обеспечивает наличие всех цепей Aj- Hj в графе g2 - в том числе и необходимых для наличия силыюсвязности.
