Диплом: Разработка отказоустойчивой операционной системы реального времени для вычислительных систем с максимальным рангом отказоустойчивости - текст диплома. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Диплом

Разработка отказоустойчивой операционной системы реального времени для вычислительных систем с максимальным рангом отказоустойчивости

Банк рефератов / Программирование

Рубрики  Рубрики реферат банка

закрыть
Категория: Дипломная работа
Язык диплома: Русский
Дата добавления:   
 
Скачать
Архив Zip, 683 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникальной дипломной работы

Узнайте стоимость написания уникальной работы

Введение В течение многих лет приложения на базе ОС реального време ни использовались во встроенных системах специального назначения , а с недавнего времени они стали применяться повсюду , от бортовых систем управления ЛА , до бытовых приборов. Разработка многопроцессорных вычислительных систем (ВС ) как правило , имеет своей ц елью повышение либо уровня надежности , либо уровня производительности системы до значений недоступных или труднореализуемых в традиционных ЭВМ . В первом случае на передний план встает вопрос о наличии специальных средств обеспечения отказоустойчивости выч ислительных систем , основной особенностью (и достоинством ) которых является отсутствие какого-либо единственного ресурса , выход из строя которого приводит к фатальному отказу всей системы . Таким образом , объектом исследования в рамках сетевой отказоустойч ивой технологии становится ОСРВ — управляющее программное обеспечение особого типа , которое используется для организации работы встроенных приложений , для которых характерны ограниченность ресурсов памяти , невысокая производительность , а также требования г арантированного времени отклика , высокого уровня готовности и наличия средств автомониторинга. Данная дипломная работа посвящена разработке специализированной распределенной операционной системы реального времени для отказоустойчивых ВС с рангом отказоусто йчивости N ( N -1), что означает способность системы функционировать даже в том случае , если произойдут отказы всех элементов системы за исключением одного . Для полного освещения выбранной темы были поставлены следующие задачи : 1. Провести анализ существующ их операционных систем реального времени , выделить основные функциональные требования к ним , дать сравнительную характеристику. 2. Раскрыть концепцию построения ОСРВ с рангом отказоустойчивости N -1, выделить основные модули операционной системы , функциона льные требования к ним и алгоритмы работы. 3. Раскрыть логику организации отказоустойчивых вычислений на примере конкретной реализации. 4. Провести анализ надежности отказоустойчивой ВС и дать рекомендации по организации ВС. 5. Создать программную модел ь вычислительной системы с распределенной операционной системой реального времени и отработать на ней различные режимы работы. 6. Рассмотреть возможность портирования (переноса ) ОСРВ на платформу TMS 320 c 30, рассмотреть специфические проблемы и сложности п ри осуществлении портации. В первой части работы дано краткое описание известных ОСРВ , описаны их функциональные возможности , структура , их направленность (специфические особенности ). Также приведена сравнительная характеристика и отмечены те решения , кото рые можно было бы использовать для разработки собственной специализированной ОСРВ. Во второй главе описана концепция построения распределенной ОСРВ , были сформулированы основные принципы функционирования перспективной вычислительной системы , включающие в с ебя многопроцессорность , обеспечение живучести , адаптацию к изменениям внутренних условий среды , поддержку реального масштаба времени , мобильность и открытость программного обеспечения . Предложен пример организации отказоустойчивых вычислений на примере п я ти-узловой полносвязной сети ПЭ в условиях постоянной деградации системы. Далее рассмотрена программная модель ВС и операционной системы , логика работы и взаимосвязь модулей . В последней главе рассматриваются особенности аппаратной платформы TMS 320 c 30, вопросы реализации вышеприведенных идей с помощью этой платформы , дополнение ОС специфическими для данной архитектуры модулями. Специальная часть 1. Операционные системы реального времени . ОС общего назначения , особ енно многопользовательские , ориентированы на оптимальное распределение ресурсов компьютера между пользователями и задачами (системы разделения времени ), В операционных системах реального времени (ОСРВ ), подобная задача отходит на второй план - все отступа е т перед главной задачей - успеть среагировать на события , происходящие на объекте. 1.1. Описание и общие требования к системам реального времени. Применение операционной системы реального времени всегда связано с аппаратурой , с объектом , с событиями , про исходящими на объекте . Система реального времени , как аппаратно-программный комплекс , включает в себя датчики , регистрирующие события на объекте , модули ввода-вывода , преобразующие показания датчиков в цифровой вид , пригодный для обработки этих показаний н а компьютере , и , наконец , компьютер с программой , реагирующей на события , происходящие на объекте . ОСРВ ориентирована на обработку внешних событий . Именно это приводит к коренным отличиям (по сравнению с ОС общего назначения ) в структуре системы , в функци я х ядра , в построении системы ввода-вывода . ОСРВ может быть похожа по пользовательскому интерфейсу на ОС общего назначения , однако устроена она совершенно иначе - об этом речь впереди . Кроме того , применение ОСРВ всегда конкретно . Если ОС общего назначени я обычно воспринимается пользователями (не разработчиками ) как уже готовый набор приложений , то ОСРВ служит только инструментом для создания конкретного аппаратно - программного комплекса реального времени . И поэтому наиболее широкий класс пользователей О С РВ - разработчики комплексов реального времени , люди проектирующие системы управления и сбора данных . Проектируя и разрабатывая конкретную систему реального времени , программист всегда знает точно , какие события могут произойти на объекте , знает критическ и е сроки обслуживания каждого из этих событий . Назовем системой реального времени (СРВ ) аппаратно-программный комплекс , реагирующий в предсказуемые времена на непредсказуемый поток внешних событий . Это определение означает , что : · Система должна успеть о треагировать на событие , произошедшее на объекте , в течение времени , критического для этого события . Величина критического времени для каждого события определяется объектом и самим событием , и , естественно , может быть разной , но время реакции системы долж н о быть предсказано (вычислено ) при создании системы . Отсутствие реакции в предсказанное время считается ошибкой для систем реального времени . · Система должна успевать реагировать на одновременно происходящие события . Даже если два или больше внешних собы тий происходят одновременно , система должна успеть среагировать на каждое из них в течение интервалов времени , критического для этих событий . Различают системы реального времени двух типов - системы жесткого реального времени и системы мягкого реального в ремени . Системы жесткого реального времени не допускают никаких задержек реакции системы ни при каких условиях , так как : · результаты могут оказаться бесполезны в случае опоздания , · может произойти катастрофа в случае задержки реакции , · стоимость опо здания может оказаться бесконечно велика . Примеры систем жесткого реального времени - бортовые системы управления , системы аварийной защиты , регистраторы аварийных событий . Системы мягкого реального времени характеризуются тем , что задержка реакции не кр итична , хотя и может привести к увеличению стоимости результатов и снижению производительности системы в целом . Основное отличие между системами жесткого и мягкого реального времени можно выразить так : система жесткого реального времени никогда не опоздае т с реакцией на событие , система мягкого реального времени - не должна опаздывать с реакцией на событие. Тогда операционная система реального времени - это такая ОС , которая может быть использована для построения систем жесткого реального времени . Это оп ределение выражает отношение к ОСРВ как к объекту , содержащему необходимые инструменты , но также означает , что этими инструментами еще необходимо правильно воспользоваться . 1.2. Параметры ОСРВ 1.2.1. Время реакции системы Почти все производители систем реального времени приводят такой параметр , как время реакции системы на прерывание (interrupt latency). В самом деле , если главным для системы реального времени является ее способность вовремя отреагировать на внешние события , то такой параметр , как врем я реакции системы является ключевым . События , происходящие на объекте , регистрируются датчиками , данные с датчиков передаются в модули ввода-вывода (интерфейсы ) системы . Модули ввода-вывода , получив информацию от датчиков и преобразовав ее , генерируют зап рос на прерывание в управляющем компьютере , подавая ему тем самым сигнал о том , что на объекте произошло событие . Получив сигнал от модуля ввода-вывода , система должна запустить программу обработки этого события. Интервал времени - от события на объекте и до выполнения первой инструкции в программе обработки этого события и является временем реакции системы на события . Обычно время реакции систем на прерывание составляет порядка 4-10 мкс. 1.2.2. Время переключения контекста В операционные системы реальн ого времени заложен параллелизм , возможность одновременной обработки нескольких событий , поэтому все ОСРВ являются многозадачными (многопроцессными , многонитиевыми ). Контекст задачи это набор данных , задающих состояние процессора при выполнении задачи . О бычно совпадает с набором регистров , доступных для изменения прикладной задаче . При переключении задач (процессов ) необходимо : 1. корректно остановить работающую задачу ; для этого а ) выполнить инструкции текущей задачи , уже загруженные в процессор , но е ще не выполненные ; б ) сохранить в оперативной памяти регистры текущей задачи ; 2. найти , подготовить и загрузить затребованную задачу ; 3. запустить новую задачу , для этого а ) восстановить из оперативной памяти регистры новой задачи (сохраненные ранее , если она до этого уже работала ); б ) загрузить в процессор инструкции новой задачи . Каждая из этих стадий вносит свой вклад в задержку при переключении контекста . Поскольку любое приложение реального времени должно обеспечить выдачу результата в заданное время , то эта задержка должна быть мала , детерминирована и известна . Это число является одной из важнейших характеристик ОСРВ . Обычно время переключения контекста в ОСРВ составляет 10-20 мкс . 1.2.3. Размеры системы Для систем реального времени важным па раметром является размер системы исполнения , а именно суммарный размер минимально необходимого для работы приложения системного набора (ядро , системные модули , драйверы и т . д .). Хотя , надо признать , что с течением времени значение этого параметра уменьша е тся , тем не менее , он остается важным и производители систем реального времени стремятся к тому , чтобы размеры ядра и обслуживающих модулей системы были невелики . 1.3. Механизмы реального времени Важным параметром при оценке ОСРВ является набор инстру ментов , механизмов реального времени , предоставляемых системой . 1.3.1. Система приоритетов и алгоритмы диспетчеризации Базовыми инструментами разработки сценария работы системы являются система приоритетов процессов (задач ) и алгоритмы планирования (ди спетчеризации ) ОСРВ . В многозадачных ОС общего назначения используются , как правило , различные модификации алгоритма круговой диспетчеризации , основанные на понятии непрерывного кванта времени ("time slice"), предоставляемого процессу для работы . Планиров щик по истечении каждого кванта времени просматривает очередь активных процессов и принимает решение , кому передать управление , основываясь на приоритетах процессов (численных значениях , им присвоенных ). Приоритеты могут быть фиксированными или меняться с о временем - это зависит от алгоритмов планирования в данной ОС , но рано или поздно процессорное время получат все процессы в системе . Алгоритмы круговой диспетчеризации неприменимы в чистом виде в ОСРВ . Основной недостаток - непрерывный квант времени , в т ечение которого процессором владеет только один процесс . Планировщики же ОСРВ имеют возможность сменить процесс до истечения "time slice", если в этом возникла необходимость . Один из возможных алгоритмов планирования при этом "приоритетный с вытеснением ". Мир ОСРВ отличается богатством различных алгоритмов планирования : динамические , приоритетные , монотонные , адаптивные и пр ., цель же всегда преследуется одна - предоставить инструмент , позволяющий в нужный момент времени исполнять именно тот процесс , котор ы й необходим . 1.3.2. Механизмы межзадачного взаимодействия Другой набор механизмов реального времени относится к средствам синхронизации процессов и передачи данных между ними . Для ОСРВ характерна развитость этих механизмов . К таким механизмам относятся : семафоры , мьютексы , события , сигналы , средства для работы с разделяемой памятью , каналы данных (pipes), очереди сообщений . Многие из подобных механизмов используются и в ОС общего назначения , но их реализация в ОСРВ имеет свои особенности - время исполне н ия системных вызовов почти не зависит от состояния системы , и в каждой ОСРВ есть по крайней мере один быстрый механизм передачи данных от процесса к процессу . 1.3.3. Средства для работы с таймерами Такие инструменты , как средства работы с таймерами , нео бходимы для систем с жестким временным регламентом , поэтому развитость средств работы с таймерами - необходимый атрибут ОСРВ . Эти средства , как правило , позволяют : · измерять и задавать различные промежутки времени (от 1 мкс и выше ), · генерировать преры вания по истечении временных интервалов, · создавать разовые и циклические будильники Здесь описаны только базовые , обязательные механизмы , использующиеся в ОСРВ . Кроме того , почти в каждой ОСРВ можно найти целый набор дополнительных , специфических только для нее механизмов , касающийся системы ввода-вывода , управления прерываниями , работы с памятью . Каждая система содержит также ряд средств , обеспечивающих ее надежность : встроенные механизмы контроля целостности кодов , инструменты для работы с таймерами. 1.4. Классы систем реального времени Монолитная архитектура ОСРВ с монолитной архитектурой можно представить в виде (рис . 1.1) · прикладного уровня : состоит из работающих прикладных процессов ; · системного уровня : состоит из монолитного ядра операцио нной системы , в котором можно выделить следующие части : интерфейс между приложениями и ядром (API), собственно ядро системы , интерфейс между ядром и оборудованием (драйверы устройств ). Рис . 1.1. ОСРВ с монолитной архитектурой Интерфейс в таких системах играет двойную роль : 1. управление взаимодействием прикладных процессов и системы , 2. обеспечение непрерывности выполнения кода системы (т.е . отсутствие переключения за дач во время исполнения кода системы ). Основным преимуществом монолитной архитектуры является ее относительная быстрота работы по сравнению с другими архитектурами . Однако , достигается это , в основном , за счет написания значительных частей системы на ассе мблере . Недостатки монолитной архитектуры . 1. Системные вызовы , требующие переключения уровней привилегий (от пользовательской задачи к ядру ), должны быть реализованы как прерывания или специальный тип исключений . Это сильно увеличивает время их работы . 2. Ядро не может быть прервано пользовательской задачей (non-preemptable). Это может приводить к тому , что высокоприоритетная задача может не получить управления из-за работы низкоприоритетной . 3. Сложность переноса на новые архитектуры процессора из-за значительных ассемблерных вставок . 4. Негибкость и сложность развития : изменение части ядра системы требует его полной перекомпиляции . Модульная архитектура (на основе микроядра ) Модульная архитектура появилась , как попытка убрать интерфейс между прило жениями и ядром и облегчить модернизацию системы и перенос ее на новые процессоры . Теперь микроядро играет двойную роль (рис 1.2): 1. управление взаимодействием частей системы (например , менеджеров процессов и файлов ), 2. обеспечение непрерывности выполн ения кода системы (т.е . отсутствие переключения задач во время исполнения микроядра ). Рис . 1.2. ОСРВ на основе микроядра Недостатки модульной архитектуры фактически т е же , что и у монолитной . Проблемы перешли с уровня интерфейса на уровень микроядра . Системный интерфейс по-прежнему не допускает переключения задач во время работы микроядра , только сократилось время пребывания в этом состоянии , проблемы с переносимостью микроядра уменьшились (в связи с сокращением его размера ), но остались. Объектная архитектура на основе объектов-микроядер В этой архитектуре интерфейс между приложениями и ядром отсутствует вообще (рис . 1.3). Взаимодействие между компонентами системы (м икроядрами ) и пользовательскими процессами осуществляется посредством обычного вызова функций , поскольку и система , и приложения написаны на одном языке (обычно C++). Это обеспечивает максимальную скорость системных вызовов . Рис . 1.3. Пример объектно-ориентированной ОСРВ Фактическое равноправие всех компонент системы обеспечивает возможность переключения задач в любое время . Объектно-ориентированный подход обеспечивает м одульность , безопасность , легкость модернизации и повторного использования кода . В отличие от предыдущих систем , не все компоненты самой операционной системы должны быть загружены в оперативную память . Если микроядро уже загружено для другого приложения , то оно повторно не загружается , а используется код и данные уже имеющегося микроядра . Все эти приемы позволяют сократить объем требуемой памяти . Поскольку разные приложения разделяют одни микроядра , то они должны работать в одном адресном пространстве . Сл е довательно , система не может использовать виртуальную память и тем самым работает быстрее (так как исключаются задержки на трансляцию виртуального адреса в физический ). 1.5. Обзор некоторых коммерческих ОСРВ Операционная система OS-9 OS -9 фирмы Microware относится к классу UNIX -подобных операционных систем реального времени . По своей сути OS -9 является многозадачной ОС с вытесняющей приоритетной диспетчеризацией , допускающая возможность многопользовательской работы . Объектно-орие нтированный модульный дизайн системы позволяет конфигурировать систему в очень широком диапазоне от встраиваемых систем до больших сетевых приложений . Согласно этой концепции все функциональные компоненты OS -9, включая ядро , иерархические файловые менеджер ы , драйвера устройств и т . д ., реализованы в виде независимых модулей . Все модули операционной системы позиционно-независимы и могут быть размещены в ПЗУ , а также могут удаляться из системы в процессе ее функционирования без какой-либо повторной инсталляц и и или перекомпоновки . На рисунке 1.4 приведена упрощенная структурная схема операционной системы. Структура операционной системы OS -9 Рис . 1.4 . Структура операционной системы OS -9 Ядро об еспечивает основной системный сервис , включая управление процессами и распределение ресурсов. Основные характеристики : 1. Архитектура : на основе микроядра 2. Стандарт : собственный , вызовы похожи на UNIX Свойства как ОСРВ : · Многозадачность : многопроцес сность · Многопроцессорность : да · Уровней приоритетов : 65535 · Время реакции : 3 мкс · Планирование : приоритетное , FIFO, специальный механизм планирования ; preemptive ядро 3. ОС разработки (host): UNIX/Windows 4. Процессоры (target): Motorola 68xxx, Intel 80x86, ARM, MIPS, PowerPC 5. Линии связи host-target: последовательный канал и ethernet 6. Минимальный размер : 16Kb 7. Средства синхронизации и взаимодействия : разделяемая память , сигналы , семафоры , события . Операционная система VxWorks VxWorks относится к операционным системам «жесткого» реального времени . Характерной чертой этой ОС является то , благодаря ее развитым сетевым возможностям , вся разработка ПО ведется на инструментальном компьютере (хост-системе ) с испо льзованием кросс-средств для последующего исполнения на целевой машине под управлением VxWorks . Отличительная черта системы - возможность управлять работой сложных комплексов реального времени и бортовых устройств , использующих процессорные элементы различ ных поставщиков . Три основных компонента данной ОС РВ образуют единую интегрированную среду : собственно ядро системы , управляющее процессором ; набор средств межпроцессорного взаимодействия ; комплект коммуникационных программ для работы с Ethernet или посл е довательными каналами связи . Основные характеристики : 1. Архитектура : монолитная 2. Стандарт : собственный и POSIX 1003 3. Свойства как ОСРВ : · Многозадачность : многопроцессность и многозадачность · Многопроцессорность : да · Уровней приоритетов : 256 · Время реакции : 4 мкс · Время переключения контекста : 15 мкс · Планирование : приоритетное ; preemptive ядро 4. ОС разработки (host): UNIX/Windows 5. Процессоры (target): Motorola 68xxx, Intel 80x86, Intel 80960, PowerPC, SPARC, Alpha, MIPS, ARM 6. Линии связи host - target : последовательный канал , ethernet , шина VME 7. Минимальный размер : 22Kb 8. Средства синхронизации и взаимодействия : семафоры POSIX 1003, очереди , сигналы… Операционная система QNX Операционная систем а QNX канадской компании QNX Software System Ltd . построена на основе иерархической микроядерной архитектуры . Упрощенная структурная схема этой ОС приведена на рисунке 1.5. Р ис . 1.5. Микроядерная структура QNX Микроядро QNX выполняет следующие функции : - межпроцессорный обмен ; - низкоуровневый сетевой обмен ; - диспетчеризация задач ; - низкоуровневая обработка прерываний. Основные характеристики : 1. Архитектур а : на основе микроядра 2. Стандарт : POSIX 1003 3. Свойства как ОСРВ : · Многозадачность : POSIX 1003 (многопроцессность и многозадачность ) · Многопроцессорность : да · Уровней приоритетов : 32 · Время реакции : 4,3 мкс · Время переключения контекста : 13 мкс · Планирование : FIFO, round robin, адаптивное ; preemptive ядро 4. Процессоры (target): Intel 80x86 5. Минимальный размер : 60Kb 6. Средства синхронизации и взаимодействия : POSIX 1003 (семафоры , mutex, condvar) Операционная система LynxOS Сис тема LynxOS выпускается фирмой Lynx Real Time Systems (Los Gatos, USA). ОСРВ из клона UNIX-систем , обеспечивающая детерминированное время отклика по запросам. Основные характеристики : 1. Архитектура : на основе микроядра 2. Стандарт : POSIX 1003 3. Свойст ва как ОСРВ : · Многозадачность : POSIX 1003 (многопроцессность и многозадачность ) · Многопроцессорность : да · Уровней приоритетов : 255 · Время реакции : 7 мкс · Время переключения контекста : 17 мкс · Планирование : FIFO, round robin, Quantum, preemptive ядро 4. Процессоры (target): Intel 80x86, Motorola 68xxx, SPARC, PowerPC 5. Минимальный размер : полной системы : 256Kb усеченной системы : 124Kb только ядра : 33Kb Систему можно записать в ROM. 6 . Средства синхронизации и взаимодействия : POSIX 1003 (семафоры , mutex, condvar) Операционная система pSOS Система pSOS выпускается Integrated Systems ( Santa Clara , USA ). Основные характеристики : 1. Архитектура : на основе микроядра 2. Стандарт : собст венный 3. Свойства как ОСРВ : · Многозадачность : многопроцессность и многозадачность · Многопроцессорность : да · Уровней приоритетов : 255 · Время реакции : 4 мкс · Время переключения контекста : 12мкс · Планирование : приоритетное ; preemptive ядро 4. ОС разработки (host): UNIX/Windows 5. Процессоры (target): Motorola 68xxx, Intel 80x86, Intel 80960, ARM, MIPS, PowerPC 6. Минимальный размер : 15Kb 8. Средства синхронизации и взаимодействия : семафоры , mutex, события , и тд. 1.6. Выводы к главе 1 О с новными отличиями ОСРВ от ОС общего назначения являются : · Ориентация на обработку внешних событий ; · Детерминированное время реакции на внешнее событие ; · Модульная организация ; · Небольшой размер системы. В главе были рассмотрены важнейшие параметры и механизмы ОСРВ , такие как : · Время реакции системы ; · Время переключения контекста ; · Виды диспетчеризации ; · Механизмы синхронизации и межзадачного взаимодействия Классификация ОСРВ позволяет выделить наиболее оптимальную структуру построения ОСРВ . Очевидно , что операционные системы с монолитной архитектурой , вследствие их направленности на конкретные процессорные платформы и характера взаимодействия с ядром , вряд ли могут быть использованы в качестве относительно универсальных ОСРВ для систем высо к ой готовности . ОСРВ на основе микроядра обладает рядом преимуществ по сравнению с монолитной архитектурой , а комбинация с объектно-ориентированным подходом , позволит системе стать аппаратно-независимой и обеспечить быструю реакцию на внешние события. В зак лючении были перечислены основные свойства некоторых распространенных ОСРВ. К сожалению , ни одну из рассмотренных операционных систем нельзя назвать сетевой в широком смысле этого слова , так как уровень сетевого обмена , заложенный в многих из них соответст вует уровню локальной сети . Многопроцессорная поддержка , введенная в VxWorks ориентирована только на системы с общей памятью . Отсутствие механизма отказоустойчивости , допускающего как отказы соединений (зачатки этого есть в QNX ), так и отказы процессорных элементов , необходимого для отказоустойчивых специализированных вычислительных систем , нет ни в одной из этих операционных систем . Таким образом , задачей разработчиков является добавление таких модулей существующим ОСРВ , которые позволили бы обеспечить от к азоустойчивость распределенных вычислительных систем. 2. Поддержка отказоустойчивости вычислительных систем средствами операционных систем реального времени Специфика применения некоторых систем обусловливает особые требования , предъявляем ые к надежности их функционирования . Отказ или сбой в их работе , повлекшие за собой неправильные результаты вычислений (или полное их отсутствие ), могут привести к катастрофическим последствиям . Преимущества использования отказоустойчивых вычислительных с и стем непосредственно вытекают из необходимости продолжительной работы системы в условиях , когда техническое обслуживание (ремонт , замена и тд .) невозможны , труднореализуемы или сопряжены с большими экономическими затратами . Поэтому ВС и специализированные операционные системы разрабатываются таким образом , чтобы система была толерантна (терпима ) к возникающим отказам . Особенно это актуально для автономных ЛА (например , космических аппаратов ). Сложность современных вычислительных средств такова , что практиче ски невозможно проверить готовые изделия при всех предполагаемых условиях и режимах их работы . Поэтому в вычислительных системах могут быть скрытые – не проявившиеся при проверке – ошибки программного обеспечения и (или ) неисправности аппаратуры , но благо д аря отказоустойчивости сбой , отказ отдельного элемента как правило не приводят к искажению выходных данных. В отличие от аппаратной части вычислительной системы появление ошибок в программе не связано с физическими процессами . Получение результатов , отличн ых от ожидаемых происходит в результате выполнения непроверенной части программы или в результате ошибки в программе. Таким образом , получение ответа , отличного от ожидаемого , в некоторый момент времени есть результат выполнения непроверенной части програм мы , содержащей ошибку , задания входных данных , для которых поведение программы неспецифицировано , а также влияния отказов в аппаратуре на работу программы. При рассмотрении надёжности вычислительной системы следует иметь ввиду , что она определяется надёжно стью аппаратной части и надёжностью программного обеспечения . Однако , понятие надёжности программного обеспечения неконструктивно , это означает , что на этапе тестирования программы не были выявлены все ошибки . В данной работе считается , что программа не с о держит ошибок , и получение результата , отличных от ожидаемого зависит от сбоев или отказов аппаратной части или иных факторов (например , влияние ЭМИ на содержание оперативной памяти ), а потому вопрос о надёжности программного обеспечения не ставится . Таки м образом , надёжность вычислительной системы определяется надёжностью аппаратуры и влиянием отказов в ней на отказы в вычислительной системе в целом. Предварительные исследования показали , что для элементной базы среднего качества (надежность 0.999 - “три д евятки после запятой” ) при оптимальном сочетании скорости получения результата на его надежность в вычислительной среде теоретически достижима достоверность получения правильных результатов машинного счета в “двести девяток после запятой” при замедлении т е мпа их получения в 300-400 раз [1], что эквивалентно увеличению надежности до 200 порядков величины при введении сравнительно небольшой вычислительной избыточности , приводящей к потере производительности не более чем на 2-3 порядка , что уже на современном уровне может компенсироваться подбором компьютеров требуемой производительности . 2.1. Понятие отказоустойчивости ВС . Отказоустойчивостью будем называть свойство системы , позволяющее продолжить выполнение заданных программой действий после возникновения одного или нескольких сбоев или отказов компонентов ВС. Отказом называется событие , заключающееся в нарушении работоспособности компонента системы . Последствия отказа могут быть различными . Отказ системы может быть вызван отказом (неверным срабатыванием ) к аких-то ее компонентов (процессор , память , устройства ввода /вывода , линии связи , или программное обеспечение ). Отказ компонента может быть вызван ошибками при конструировании , при производстве или программировании . Он может быть также вызван физическим по в реждением , изнашиванием оборудования , некорректными входными данными , и многими другими причинами . Отказы могут быть случайными , периодическими или постоянными . Случайные отказы (сбои ) при повторении операции исчезают . Причиной такого сбоя может служить , например , электромагнитная помеха . Другой пример - редкая ситуация в последовательности обращений к операционной системе от разных задач . Периодические отказы повторяются часто в течение какого-то времени , а затем могут долго не происходить . Примеры - пло х ой контакт , некорректная работа ОС после обработки аварийного завершения задачи . Постоянные (устойчивые ) отказы не прекращаются до устранения их причины - разрушения диска , выхода из строя микросхемы или ошибки в программе . 2.2. Причины и классификация о тказов и сбоев Отказы по характеру своего проявления подразделяются на византийские (система активна и может проявлять себя по-разному , даже злонамеренно ) и пропажа признаков жизни (частичная или полная ). Первые распознать гораздо сложнее , чем вторые. Апп аратная реализация узлов (процессорных модулей ) позволяет выделить основные классы отказов аппаратуры : - отказ процессора (центральной части ПЭ ); - отказ линка - связи между ПЭ ; Идентификация отказа процессора какого-либо узла сети классифицирует ся , как отказ всего узла : он изолируется от остальной сети на логическом уровне и при наличии соответствующей поддержки отключается на аппаратном уровне (выключается питание ). Идентификация отказа линка (связи ) приводит лишь к уменьшению степени связности узлов сети . Отказавший линк изолируется на логическом уровне путем изменения маршрутов передачи сообщений между узлами сети. Отказ при исполнении функционального программного обеспечения может проявиться вследствие : - нарушения кодов записи программ в па мяти команд ; - стирания или искажения данных в оперативной или долговременной памяти ; - нарушения нормального хода вычислительного процесса. Перечисленные искажения могут действовать совместно . Отказ может проявляться в виде программного останова или зац икливания , систематического пропуска исполнения некоторой группы команд , однократного или систематического искажения данных и тд . Программные отказы приводят к прекращению выдачи абонентам информации и управляющих воздействий или к значительному искажению ее содержания и темпа выдачи , соответствующих нарушению работоспособности. Основная особенность (и достоинство ) сетевой отказоустойчивой технологии - отсутствие какого-либо (даже самого незначительного ) единственного компонента (ресурса ), выход из строя к оторого приводит к фатальному отказу всей системы . Такая система не может содержать какого-либо "центрального " (главного ) узла , размещенного в одном из процессорных элементов системы , она может состоять только из "равноправных " частей , размещенных в каждо м узле сети . Таким образом можно говорить лишь о деградации качества системы при отказе одного или более ее элементов . В такой системе полный отказ наступает после выхода из строя только определенного количества ресурсов , определенного на этапе проектирова н ия. 2.3. Методы и средства обеспечения отказоустойчивости Для обеспечения надежного решения задач в условиях отказов системы применяются два принципиально различающихся подхода - восстановление решения после отказа системы (или ее компонента ) и предотвра щение отказа системы (отказоустойчивость ). Восстановление может быть прямым (без возврата к прошлому состоянию ) и возвратное. Прямое восстановление основано на своевременном обнаружении сбоя и ликвидации его последствий путем приведения некорректного состо яния системы в корректное . Такое восстановление возможно только для определенного набора заранее предусмотренных сбоев. При возвратном восстановлении происходит возврат процесса (или системы ) из некорректного состояния в некоторое из предшествующих коррект ных состояний . При этом возникают следующие проблемы : · Потери производительности , вызванные запоминанием состояний , восстановлением запомненного состояния и повторением ранее выполненной работы , могут быть слишком высоки. · Нет гарантии , что сбой снова не повторится после восстановления. · Для некоторых компонентов системы восстановление в предшествующее состояние может быть невозможно (торговый автомат ). Для восстановления состояния в традиционных ЭВМ применяются два метода (и их комбинация ), основанны е на промежуточной фиксации состояния либо ведении журнала выполняемых операций . Они различаются объемом запоминаемой информацией и временем , требуемым для восстановления. Применение подобных методов в распределенных системах наталкивается на следующие тру дности : · Для распределенных систем запоминание согласованного глобального состояния является серьезной теоретической проблемой ; · методы восстановления после отказов для некоторых систем непригодны из-за прерывания нормального функционирования и др ; Чт обы избежать эти неприятности , создают системы , устойчивые к отказам . Такие системы либо маскируют отказы , либо ведут себя в случае отказа заранее определенным образом. По мере того как операционные системы реального времени и встроенные компьютеры все чащ е используются в критически важных приложениях , разработчики создают новые ОС реального времени высокой готовности . Эти продукты включают в себя специальные программные компоненты , которые инициируют предупреждения , запускают системную диагностику для тог о , чтобы помочь выявить проблему , или автоматически переключаются на резервную систему. Обеспечение живучести – это использование специальных средств , позволяющих системе продолжать правильное функционирование при возникновении отказов ее программных и аппа ратных компонентов с возможностью деградации качества функционирования [2]. В отличие от отказоустойчивости , где с отказом не связано качество работы ВС , сравнительно сложные средства обеспечения живучести позволяют более рационально расходовать вычислите л ьные ресурсы и увеличивать среднее время наработки до наступления фатального отказа . Обеспечение живучести обычно включает три основные функции : диагностика возникновения отказа , локализация неисправности и перестройка системы . В основе толерантности лежи т избыточность как аппаратного , так и программного обеспечения . Поэтому многопроцессорные системы с присущей им аппаратной избыточностью потенциально позволяют создавать не только высокопроизводительные , но и высоконадежные системы. Другим основополагающим требованием является наличие механизма , позволяющего агентам в каждом устройстве обмениваться топологической информацией со своими соседями посредством эффективных протоколов , не перегружающих сеть широковещательным управляющим трафиком . Каждый управляющи й агент должен поддерживать таблицу с локальной топологической информацией . Кроме того , должен предоставляться механизм , практически в реальном времени модифицирующий содержимое базы данных и обеспечивающий правильное отображение топологических изменений , в ызванных установкой новых устройств либо реконфигурацией или отказом существующих узлов сети . Для обеспечения защиты вычислительного процесса программными методами используется программная , информационная и временная избыточности. Под временной избыточнос тью понимается использование части производительности для получения диагностической информации о состоянии системы . Программная избыточность используется для контроля и обеспечения достоверности важных решений по управлению и обработке информации . Она зак л ючается в применении нескольких вариантов программ в каждом узле системы (так называемое N -версионное программирование ). Сопоставление результатов независимых решений одного и того же фрагмента задачи называют элементарной проверкой , а совокупность всех п роверок образует систему голосования , которое является основным источником диагностической информации о состоянии аппаратной части системы и вычислительного процесса в каждом активном узле системы . Два механизма широко используются при обеспечении отказо у стойчивости - протоколы голосования и протоколы принятия коллективного решения. Протоколы голосования служат для маскирования отказов (выбирается правильный результат , полученный всеми исправными исполнителями ). Протоколы принятия коллективного решения под разделяются на два класса . Во-первых , протоколы принятия единого решения , в которых все исполнители являются исправными и должны либо все принять , либо все не принять заранее предусмотренное решение . Примерами такого решения являются решение о завершении и терационного цикла при достижении всеми необходимой точности , решение о реакции на отказ . Во-вторых , протоколы принятия согласованных решений на основе полученных друг от друга данных . При этом необходимо всем исправным исполнителям получить достоверные да нные от остальных исправных исполнителей , а данные от неисправных исполнителей проигнорировать Однако для систем на последней стадии их деградации (при отказе предпоследнего узла сети ) на первый план в качестве диагностической информации выходят приз наки исправности-неисправности , формируемые различными программно-аппаратными средствами контроля , такими как : · функциональный контроль вычислений с помощью специальных контрольных операторов и нескольких версий программ ; · функциональный контроль входной и выходной информации ; · контроль входной информации по специальным признакам и контрольным суммам ; · контроль выходной информации по квитанции от приемника - абонента системного интерфейса ; · контрольный тест аппаратуры процессора ; · контроль ные тесты аппаратуры внешнего и внутреннего интерфейсов. · встроенные аппаратные средства контроля процессорных элементов и контроллеров системного интерфейса. Информационная избыточность состоит в дублировании исходных и промежуточных данных , обрабатывае мых комплексом программ. Часто для обнаружения состояния отказа используются тайм-ауты . В обычных системах исполнения предусматривается три различных вида обслуживания . Неблокирующее обслуживание всегда возвращает управление немедленно вместе с достоверным кодом возврата (успех или неудача ), однако , в случае отсутствия данного вида обслуживания , обратившаяся к нему задача может попасть в бесконечный цикл опроса . Блокирующее обслуживание избегает такого опроса путём исключения вызывающей задачи из процесса д испетчеризации до тех пор , пока данный сервис не станет доступным . Если этого не произойдет , то задача рискует навсегда остаться заблокированной . Механизм же таймаутов позволяет возвращать управление задаче , даже в случае , если указанный сервис не предост а вляется ей в течение определенного периода времени. 2.4. Концепция построения и работы системы с рангом отказоустойчивости N -1. В отказоустойчивых системах , построенных на N процессорных элементах , рангом отказоустойчивости будем называть максимальное к оличество отказов функциональных элементов (ПЭ ), после возникновения которых система продолжает свое функционирование . Введем обозначение - N ( m ), которое означает , что система содержит N узлов (ПЭ ) и «держит» m отказов , т.е . нормально функционируют до тех пор , пока остаются исправными (N-m) узлов . Следует заметить , что системы класса N (0) – относятся к самым быстродействующим системам , а N ( N -1) – к самым отказоустойчивым. В дальнейшем в работе будем рассматривать концепции построения и работы именно отказоу стойчивых систем класса N ( N -1). Данное ограничение означает , что в каждом ПЭ системы должен присутствовать весь набор функционального программного обеспечения , то есть каждый цикл ПЭ осуществляет полную обработку входных данных без участия других ПЭ . Таки м образом , специализированные операционные системы , поддерживающие свойство отказоустойчивости для данного класса ВС , должны обладать следующими свойствами : 1. ОС представляет собой совокупность информационно взаимосвязанных и согласовано функционирующих о перационных систем каждого отдельного узла сети ВС . Информационная взаимосвязанность операционных систем узлов между собой обеспечивается за счет передачи каждой ОС всем остальным следующей информации : - результатов «голосования» (сравнения ) поступающей в данный ПЭ функциональной информации ; - результатов оценки поступившей от других ОС узлов ; - «результатов голосования» (т.е . «вывод» данного ПЭ о состоянии других ПЭ ). Все операционные системы узла идентичны и отличаются друг от друга лишь своим номе ром и содержанием системных таблиц. 2. Внутренняя структура распределенной ОСРВ представляет собой иерархию уровней в которой каждый уровень использует функциональные возможности предыдущего . Добавление или удаление модулей позволяет создавать системы разл ичных конфигураций . Кроме того , данный принцип построения ОСРВ позволяет осуществлять ее расширение путем добавления новых модулей , а расширение с минимальными изменениями подразумевает открытость системы. 3. ОС должна обладать возможностью использования н а различных аппаратных платформах с минимальными модификациями соответствующих программ , то есть обладать свойством переносимости. 4. ОС должна обладать свойством масштабируемости , что в узком смысле означает обеспечение ее настраиваемости на поддержку фун кционирования сетевых ВС различной размерности N (для реальных систем в пределах 3 N 10). Причем правая граница изменения N (Nmax = 10) выбрана из практических соображений построения ВС с высокой степенью связности узлов сети при использовании конкретных процессорных модулей количеством линков (L) не более шести (L 6). При L=6 семиузловая сеть является полносвязанной и по мере увеличения N степень связности у злов сети уменьшается. 5. Времени для выполнения всех необходимых действий должно хватать с запасом 20-30% с учетом производительности аппаратной платформы. С учетом этого факта (достаточности ресурса производительности ) диспетчеризация вычислений сводится к поддержке следующих процедур : · синхронизация вычислений - по циклам выдачи управляющих сигналов (команд ), задаваемых таймером ведущего узла (с меньшим номером среди активных узлов ); · полная обработка функциональной задачи в пределах одного цикла ; · использование сторожевого таймера во всех активных узлах сети как средства защиты от зацикливания (зависания ) вычислительного процесса ; · разделение цикла работы системы на следующие периоды : ввод данных , решение ФЗ , обмен функциональными данны ми (ФД ), обмен результатами голосования ФД , обмен предварительными выводами о состоянии системы , принятие консолидированного решения (КР ) о состоянии системы , реконфигурация системы при обнаружении в рамках КР отказа части системы. В дальнейшем этот перече нь требований к ОСРВ будет продолжен и детализирован. Рассмотрим общую концепцию работы такой системы . После получения результатов расчета на очередном цикле , система должна получить информацию о своем состоянии , для чего осуществляется обмен результатами с остальными ПЭ системы . При этом следует отметить , что обмен результатами счета со всеми узлами ВС в некоторой мере избыточен , так как для выявления некорректного результата достаточно двух верных (в предположении об ординарности потока отказов ). Таким о б разом , протокол голосования может быть построен так , что результаты счета отдельного ПЭ в ВС троируются , т.е . могут не присутствовать в некоторых узлах системы. Во время сравнения ПЭ делает вывод о нормальном или неправильном функционировании доступной ей подсистемы и выявляет ее причину . Результатами сравнения ПЭ обменивается со всеми узлами системы , и они принимают консолидированное решение об отказе того или иного элемента или делают заключение о нормальной работе системы. В случае обнаружения отказа , на выход выдаются результаты , признанные верными при голосовании . Отказавшему элементу предоставляется возможность «исправиться» в течение следующих трех циклов . При этом сбойному ПЭ передается контекст верно функционирующей задачи . Тройная попытка самоустр а нить сбой этого узла , должна практически исключать возможность отключения работоспособного ресурса системы . Если сбои в этом элементе повторились , система считает элемент отказавшим , после чего производится подключение к работе резервного ПЭ (если он пред у смотрен изначальной топологией сети ) с передачей текущего контекста функциональных задач . При отказе связей передача данных производится через транзитные связи . Если элемент утратил все свои связи (линки ), то он изолируется на логическом или , если это во з можно – на физическом уровне (отключение питания ). В настоящее время существуют различные ОСРВ , призванные решать задачи организации вычислений в системах РВ . Однако ни одна из них не удовлетворяет поставленным требованиям в полной мере . Поэтому встает в опрос о необходимости расширения существующих ОСРВ или разработки новой ОС , удовлетворяющей им . Поскольку создание ОС с удобными средствами создания и отладки прикладного программного обеспечения - длительный и трудоемкий процесс , единственным выходом яв л яется доработка существующих ОС. В качестве основного подхода к обеспечению отказоустойчивости предлагается использовать избыточность аппаратных и программных компонент системы . Данный подход предполагает решение следующих вопросов : · дополнение ОС высоко уровневыми функциями обмена . Используемые в большинстве ОС стандартные средства обмена данными , определенные стандартом POSIX (каналы , сигналы , разделяемая память , семафоры ), имеют ограниченные возможности при взаимодействии процессов , не имеющих родственн ых связей . Организация межпроцессного взаимодействия с помощью механизма сокетов неудобна из-за необходимости привязки к конкретной сетевой информации ( IP - адрес узла , номер порта приложения ) и своей ориентированностью на модель клиент-сервер . · введение приоритета для передаваемых сообщений . Важность сообщений , передаваемых по сети , неодинакова . Например , сообщения об отказе какой-либо компоненты системы должны иметь наивысший приоритет для того , чтобы оповестить узлы сети в кратчайшие сроки. · выбор и реализация механизма голосования . При этом механизм передачи /приема данных и голосования должен быть по возможности скрыт от прикладного программиста. Такая концепция построения операционной системы предусматривает наличие специальных средств обеспечения б ыстрого реагирования на отказ и реконфигурации системы . Ими являются модуль маршрутизации , обеспечивающий оптимальные маршруты для передачи функциональной и системной информации как на начальном этапе инициализации системы , так и в процессе ее функциониро в ания при отказе тех или иных элементов и при подключении резервных , модуль реконфигурации , служащий для перестройки системных таблиц при отказах и восстановлении работоспособности системы , модуль межпроцессорного обмена , для передачи информационных и сист е мных пакетов данных . Рассмотрим их структуру и назначение подробнее. 2.4.1. Описание системных таблиц Основная информация о функционировании операционной системы на данном ПЭ размещена в системных таблицах . Граф информационной связности проц ессорных элементов задаётся в виде модифицированной матрицы связности . Отличие от стандартной матрицы связности заключается в том , что в рамках одной строки , описывающей связность данного ПЭ с другими , используется число « -1» в случае , если этот процессор н ый элемент не связан с ПЭ , задаваемом столбцом , и номер канала связи (линка ) по которому осуществляется эта связность в противном случае , причем нумерацию линков для удобства можно начинать c m +1 узла , то есть для узла m связь с узлом m +1 будет осуществлят ься линком с наименьшим номером . Таблица 2.1 Пример таблицы связности для полносвязной сети ПЭ № /№ 1 2 3 4 … N 1 -1 0 1 2 … N-2 2 N-2 -1 0 1 … N-3 3 N-3 N-2 -1 1 … N-4 4 N-4 N-3 N-2 -1 … N-5 … … … … … … … N 0 1 2 3 … -1 В дополнение к таблице связности , должна существовать таблица рассылки , в которой каждому ПЭ сопоставлен номер канала связи , по которому надо передать пакет дальше , чтобы он в конечном счете дошёл до адресата . Для полносвязной сети такая информация может показаться избыточной , о днако если сеть неполносвязная или в ней произошли отказы связей , то таблица рассылки , формируемая на этапе инициализации и реконфигурации системы , позволит экономить время при обмене информацией или результатами голосования на каждом цикле . Составлением т аблиц рассылки занимается модуль маршрутизации , структура и алгоритм работы которого будет рассмотрена ниже. Приведем пример таблиц рассылки . Для наглядности возьмем сеть из четырех ПЭ , представленную на рисунке 2.1. Рис . 2.1. Пример неполносвязной сети Цифры в окружностях – номера процессорных элементов , вне – номера линков (физических каналов связи ). Таким образом таблица связности имеет вид (таблица 2.2). Таблица 2.2 Т аблица связности для примера на рисунке 2.1 № /№ 1 2 3 4 1 -1 0 -1 1 2 1 -1 0 -1 3 1 -1 -1 0 4 0 -1 1 -1 Таблицы рассылки для каждого ПЭ могут иметь вид (см . Таблицу 2.3, 2.4, 2.5, 2.6) . Таблица 2.3 Таблица рассылки для ПЭ № 1 № ПЭ 1 2 3 4 № Линка -1 0 0 1 Таблица 2.4 Таблица рассылки для ПЭ № 2 № ПЭ 1 2 3 4 № Линка 1 -1 0 0 Таблица 2.5 Таблица рассылки для ПЭ № 3 № ПЭ 1 2 3 4 № Линка 0 1 -1 0 Таблица 2.6 Таблица рассылки для ПЭ № 4 № ПЭ 1 2 3 4 № Линка 0 0 1 -1 2.4.2. Модуль маршрутизатора К ак уже отмечалось в подразделе 2.4.1 маршрутизатор выполняет следующие функции : · хранение текущей топологии многопроцессорной системы ; · установление оптимальных статических маршрутов передач данных в системе и таблиц рассылки ; · обработка сигналов изм енения топологии системы от реконфигуратора. При инициализации требуется исходная топология системы . Таким образом , модуль маршрутизации можно представить в виде следующей упрощенной схемы : Рис . 2.2. Модуль маршрутизации Во время инициализации , для каждого ПЭ составляется список текущих соседних узлов системы для обмена результатами счета так , чтобы данные каждого ПЭ присутствовали в тройном экземпляре в ВС . Таблицы расс ылки , в которой каждому ПЭ сопоставлен номер канала связи , по которому надо передать пакет дальше , формируются методом волны на основе таблиц связности ПЭ . Маршрут выбирается минимальным по количеству рёбер графа сети , с учетом загрузки связей . Так как оп е рационные системы узлов идентичны , то пакеты , проходящие через их связи можно считать одинаковыми . Загрузка связи определяется по числу возможных транзитных передач через эту связь , и транзитные передачи равномерно распределяются по узлам сети без потерь н а длине маршрута. Алгоритм определения статических маршрутов и заполнения таблицы рассылки : 1. Заполняем таблицу рассылки в соотвествие со строкой с номером , равным номеру процессорного элемента . Заполняем соответствующую таблицу расстояний единицами (сч етчик длины маршрута ) в тех ячейках , где есть прямая связь в таблице связности (>0). 2. Если обработаны все ПЭ , закончить. 3. Увеличиваем счетчик длины маршрута на 1 единицу (передачу ). 4. По таблице рассылки находим очередной ПЭ , не имеющий связи с лок альным . Если таких больше нет , шаг 8. 5. Среди имеющих связь ПЭ ищем по таблице расстояний того , у кторого маршрут был определен на предыдущем цикле . Если таких больше нет , шаг 7. 6. Если он имеет связь с нужным ПЭ , запоминаем номер линка для связи его с локальным ПЭ и загрузку линка . Шаг 5. 7. Сортируем найденные линки по наменьшей загруженности и заносим его в таблицу рассылки и таблицу расстояний. Если обработаны все ПЭ , закончить , иначе шаг 3. 2.4.3. Модуль реконфигурации Модуль реконфигурации активизируется и выполняет перестройку системных таблиц ОС на основе информации о конкретном отказе . Рассмотрим обработку отказа функциональной задачи , отказа канала связи и отказа процессора целиком . При этом приостановки работы системы в общем случае не должно происходить из-за возможной необходимости в выдачи управляющих воздействий в жестком цикле работы системы . Резервы времени должны предусматриваться на этапе проектирования в зависимости от вычислительных ресурсов элементов системы . Таким образом , р еконфигурация должна быть выполнена до начала выдачи результатов контроллерам приемников управляющей информации . · Отказ канала связи . Первоначально корректируется матрица связности ПЭ . При этом определяется , имеет ли отказавший канал связи отношение к д анному процессорному элементу . В случае , если после отказа канала связи , какой-либо процессор оказывается изолированным , выполняется отключение процессорного элемента. · Отказ процессорного элемента . Обработка отказа всего процессорного элемента выполняет ся посредством коррекции матрицы связности ПЭ , удаление всех каналов связи . · Отказ функциональной задачи трактуется так же , как и отказ процессорного элемента. Реконфигуратор тесно связан с модулем маршрутизации и обращается к нему сразу после изменения системных таблиц для коррекции таблиц рассылки и определения активных элементов системы . Обобщенная модель реконфигуратора может быть представлена на следующей схеме : Ри с . 2.3. Модуль реконфигурации После отказа функционального элемента , процесс реконфигурации осуществляется по следующей схеме : 1. В таблице связности отказавший линк или линки отказавшего ПЭ помечаются как недоступные. 2. Проверяется , не остались ли изо лированными оставшиеся узлы , если да , то они отключаются. 3. По таблице связности определяется новый список соседних узлов системы , определяется ПЭ , которого (которых ) необходимо вывести из резерва. 4. Производится активизация резервного ПЭ путем передач и ему кода активизации , текущей таблицы связности и контекста задачи от старшего ПЭ в ВС (например , от ПЭ с младшим номером ). 2.4.4. Модуль коммуникации Основной задачей этого модуля является организация информационного обмена между процессами в системе , то есть передача информационных сообщений между функциональными задачами и системных сообщений между операционными системами разных ПЭ . Таким образом , модуль коммуникации обеспечивает : · получение запроса на прием /передачу данных от функциональной зада чи ; · установление соответствия между передатчиком и приемником данных ; · передача сообщения и идентификаторов адресатов модулю пересылки информации ; · хранение принимаемых данных ; · проверка согласованности данных от резервированных источников (голо сование ); · выявление в результате голосования отказа компонент системы и посылка соответствующего сигнала модулю реконфигурации ; · передача согласованных данных ФЗ ; · передача /прием системных сообщений. Модуль пересылки информации : · формирование форм ата передаваемого сообщения ; · идентификация принимаемых сообщений ; · диагностика целостности принимаемых сообщений (проверка контрольной суммы ); · определение отказов физической среды передачи данных (проверка подтверждений приема данных – “квитанций” ) ; · формирование сигнала модулю ОС – реконфигуратору о неисправности среды передачи. В своей работе модуль опирается на функции ввода-вывода нижележащего модуля пересылки информации . Поскольку распределенная ОСРВ является надстройкой над базовой ОС нижне го уровня , она не имеет доступа к аппаратуре ПЭ и не может осуществлять ввод-вывод на основе обработки прерываний . Общая структура взаимодействия модулей представлена на рис . 1.3: Рис . 2.4. Структура модулей коммуникации В связи с этим для обеспечения приёма и передачи информации по каналам связи , для обслуживания каждого из них создаётся задача прослушивания . Прослушивание каналов связи осуществляется после отработки зада чи на очередном цикле . При этом должна происходить проверка , не является ли сообщение транзитным , и в случае транзитной передачи , немедленно осуществлять отсылку по нужному каналу связи из таблицы рассылки. Формат посылки состоит из заголовка и самого тела посылки . В заголовке используются следующие поля : · Получатель (номер ПЭ ); · Отправитель ; · Тип посылки (информационная или системная ); · Размер информационной части посылки (может быть нулевой ); · Контрольная сумма пакета. Передача информации происх одит сразу после завершения функциональной задачей процедуры расчета , и управление передается задаче прослушивания (модулю пересылки ), причем на это отводится фиксированное время (включается сторожевой таймер ), равное максимальному периоду обмена между пр о цессорными элементами в активной тройке . Максимальным временем в данном случае будет время с учетом транзитных передач через узлы ВС при отказе связей , которое может составлять до N -1 периодов записи. 2.4.5. Процедура голосования Под голосованием будем п онимать совокупность элементарных проверок (сопоставлений результатов ) независимых решений одного и того же фрагмента задачи . По результатам сравнения формируется вектор промежуточного состояния (предварительный вывод о состоянии системы ). Например , векто р может состоять из 0, если соответствующий узел исправен по результатам сравнения или – 1, при расхождении результатов сравнения . При этом , если данные текущего узла не совпадают с одинаковыми результатами соседних ПЭ , то текущий узел может прогнозироват ь собственный сбой. Далее следует обмен результатами сравнения по описанной выше схеме . Голосование проводится сравнением векторов промежуточного состояния всех активных ПЭ . Вывод о сбое или отказе того или иного узла делается при совпадении хотя бы двух пр омежуточных результатов. Несовпадение результатов сравнения может быть вызвано сбоем или отказом физического канала связи . Этому может предшествовать сигнал о неисправности канала связи от модуля коммуникации . В противном случае (при отсутствии сигнала ), с бой в линии связи может быть определен по полученным векторам состояния . Например ПЭ получены следующие вектора : (0,-1,0), (-1,0,0), (0,0,0), где каждому вектору и каждому элементу вектора поставлен в соответствие номер ПЭ (то есть ПЭ 1, ПЭ 2, ПЭ 3). Анализ с равнения этих промежуточных результатов может сказать о неисправности канала связи между ПЭ 1 и ПЭ 2. При таком построении системы сделано неявное допущение о том , что на протяжении одного цикла может отказать не более одного элемента системы , иначе поведени е её в таком случае строго говоря недетерминировано . Впрочем данное допущение может быть аргументировано тем , что время наработки на отказ отдельного элемента системы составляет по крайней мере несколько тысяч часов , и считая возникновения отказов независ и мыми событиями , вероятность отказа одновременно двух элементов на протяжении цикла (порядка 10 - 100 мс ) величина порядка 10 -17 - 10 -18 . Однако при возникновении такой ситуации выходом может быть применение методов помехоустойчивого статистического оценив ания результатов расчета [10], проведение диагностических тестов и тд . для выбора корректного результата и принятия решения о выдаче того или иного управляющего воздействия на текущем цикле. 2.5. Организация отказоустойчивых вычислений В данном разделе примем во внимание введенное ранее предположение об ординарности потока отказов , то есть на протяжении одного цикла (такта ) работы системы множественные отказы не возникают. Отметим , что реакция систем диагностирования отказов такова : 1. Несовпадение данн ых при элементарной проверке (сравнении ) результатов счета на очередном цикле диагностируется , как отказ ПЭ или канала связи этого ПЭ. 2. При несовпадении данных при элементарной проверке результатов счета , полученных с использованием транзитной передачи, под сомнение ставится вся цепочка , задействованная при передаче. 3. При несовпадении ни одного результата счета под сомнение ставится все участвовавшие в обмене ПЭ и связи. 4. Несовпадение контрольной суммы или тайм-аут при приеме данных трактуется как сбой ПЭ или канала связи ПЭ. 5. Отсутствие квитанции трактуется как сбой ПЭ или канала связи ПЭ. 6. Неверный код квитанции трактуется как сбой канала связи ПЭ. Напомним , что идея организации отказоустойчивых вычислений основана на использовании трех типо в избыточности : аппаратной , программной и информационной . Т.е . заданная задача реализуется на более чем трех процессорных элементах сети . Рабочая конфигурация сети состоит из трех ПЭ , результаты счета копия задачи отсылает в пределах рабочей конфигурации. На основании результатов голосования формируется информация о ходе вычислительного процесса и о состоянии аппаратуры (исправна - неисправна ) ВС . Этой информации достаточно (как правило с большей избыточностью ) для принятия решения о перестройке (реконфигу р ации ) сети при возникновении отказов аппаратуры ВС. Все копии функциональной задачи решаются с одинаковыми наборами входных параметров и поэтому (при отсутствии неисправностей ) формируют одинаковые результаты (голосование по совпадению кодов ). Проблемы вво да и вывода внешней по отношению к ВС информации не рассматриваются , при этом предполагается , что достоверная внешняя информация поступает в соответствующие узлы сети на входы копий задачи - приемников входной информации. 2.5.1 Пример организации отказоус тойчивых вычислений В рамках этих предположений , рассмотрим пример реализации отказоустойчивых вычислений на ВС (граф см . на рис 2.5), состоящей из пяти узлов . Каждый узел изначально отличается от остальных только своим номером в таблице связности. Рис 2.5. Топология ВС Физическая связь (линк ) под номером 4 используется каждым ПЭ для обмена с объектом управления и приема данных функциональной задачей для расчета на очередном цикле . В данной главе аспекты использования и надежности этих связей не рассматриваются , анализу подвергается только внутренняя структура ВС. 2.5.1. Инициализация Для инициализации работы процессорных элементов используются конфиг урационные файлы , содержащие номер ПЭ и таблицу связности (таблица 2.8). Таблица 2.8 № /№ 1 2 3 4 5 1 -1 0 1 2 3 2 3 -1 0 1 2 3 2 3 -1 0 1 4 1 2 3 -1 0 5 0 1 2 3 -1 На основе анализа таблицы связности определяется статические маршруты каждого П Э и текущая рабочая конфигурация каждого ПЭ по критерию связности , в данном случае обмен результатами счета осуществляется следующим образом : 1. ПЭ 1 -> ПЭ 2 и ПЭ 3; 2. ПЭ 2 -> ПЭ 3 и ПЭ 4; 3. ПЭ 3 -> ПЭ 4 и ПЭ 5; 4. ПЭ 4 -> ПЭ 5 и ПЭ 1; 5. ПЭ 5 -> ПЭ 1 и ПЭ 2; В штатном режиме функционирования ВС (при отсутствии неисправностей ) на выходе каждой копии функциональной задачи (т.е . в 5-и точках ) путем голосования на совпадение результатов подтверждается правильность реализации вычислительного процесса подсистемы. Пре дставим теперь , что произошел первый отказ аппаратуры . Пусть отказал канал связи между ПЭ 1 и ПЭ 3. Если при каком-либо отказе процессорный элемент вообще не выдает результаты счета , то голосование осуществляется с использованием соответствующих результатов систем диагностирования (проверка КС , квитанций ). Таким образом , в результате в узлах сети фиксируются следующие факты несовпадения результатов счета , представленные , для наглядности , в виде таблицы 2.9, в которой каждый линк обозначен с помощью двух цифр - номеров связываемых им процессорных элементов. Таблица 2.9 № ПЭ Получены данные от ПЭ № Данные от ПЭ № Не совпадают с данными от ПЭ № Возможная причина : Неисправность ПЭ № или Линк № 1 4 , 5 Нет неисправности 2 5 , 1 Нет неисправности 3 1 , 2 1 2 , 3 1 1-3 4 2 , 3 Нет неисправности 5 3 , 4 Нет неисправности После обмена результатами голосования , в узлах может оказаться противоречивая информация , представленная таблицей 2.10. Следует уточнить , что на каждом новом такте область памяти зарезервированная под результаты голосования соседних ПЭ переинициализируется , то есть содержит «мусор» до занесения вновь обновленной информации . Анализ информации ПЭ 1 позволяет сделать вывод о работоспособности ПЭ 3, поскольку сообщение о его неисправности не подтвердили ПЭ 4 и ПЭ 5, и выявить сбой в канале связи 3-1. Анализ ПЭ 2, ПЭ 3, ПЭ 4, ПЭ 5 полученной информации показывает на неисправность линка 3-1, по с кольку работоспособность ПЭ 1 подтверждается узлом ПЭ 2 и наличием в памяти достоверной информации о состоявшемся сеансе связи с ПЭ 1. Таблица 2.10 ПЭ№ Данные голосования от ПЭ № Возможная причина неисправности ПЭ № или Линк № Вывод Консолидированное решение 1 Нет неисправности 2 Нет неисправности 1 3 "мусор " Неисправен Линк 3-1 4 Нет неисправности 5 Нет неисправности 1 Нет неисправности 2 Нет неисправности 2 3 1 1-3 Неисправ ен Линк 3-1 4 Нет неисправности 5 Нет неисправности 1 "мусор " 2 Нет неисправности 3 3 1 1-3 Неисправен Линк 3-1 Неисправен Линк 3-1 4 Нет неисправности 5 Нет неисправности 1 Нет неисправности 2 Нет неисправности 4 3 1 1-3 Неисправен Линк 3-1 4 Нет неисправности 5 Нет неисправности 1 Нет неисправности 2 Нет неисправности 5 3 1 1-3 Неисправен Линк 3-1 4 Нет неисправности 5 Нет неисправности При появлении такой ситуации могут возникнуть следующие трудности : 1. Недостоверность переданной информации была вызвана кратковременным сбоем , при этом ПЭ 1 получил достоверные результаты счет а , а ПЭ 3 – недостоверные. Решение : отключении канала связи 3-1 происходит только при троекратном повторении сбоя. 2. Сбой возник на этапе обмена результатами голосования. Решение : сбой фиксируется наличием “мусора” вместо стандартных значений , но «полноце нное» обнаружение сбоя (если он повторится ) произойдет на следующем такте. В любом случае следует проводить еще один обмен в рабочей сети , для аккумуляции решений всех ПЭ , и определения достоверного вывода путем их сравнения. После принятия окончательного решения об отказе связи 3-1, инициируется реконфигуратор , вносящий соответствующие изменения в таблицу связности (см таблицу 2.11). Таблица 2.11 № /№ 1 2 3 4 5 1 -1 0 -1 2 3 2 3 -1 0 1 2 3 -1 3 -1 0 1 4 1 2 3 -1 0 5 0 1 2 3 -1 Далее реконфигур атор проводит проверку на нарушение связности в рабочей сети . В данном случае изменяются статические маршруты ПЭ и связь между ПЭ 1 и ПЭ 3 осуществляется через ПЭ 2. Предположим теперь , что отказал ПЭ 4. При этом ПЭ 4 может вести себя двояко : либо наступил фат альный отказ и ПЭ не выдает результатов , либо выдает искаженные результаты . Во втором случае так же может быть два варианта : ПЭ сохраняет способность правильно осуществлять обмен и голосование . В этом случае ПЭ способен диагностировать собственную ошибку. В противном случае считается , что сбойный узел выдает результаты , не несущие информативной нагрузки (“мусор” ). Проиллюстрируем все случаи. После этапа сравнения информации , в системе может оказаться следующая информация (таблица 2.12). Таблица 2.12 № ПЭ Получены данные от ПЭ № Данные от ПЭ № Не совпадают с данными от ПЭ № Возможная причина : Неисправность ПЭ № или Линк № 1 4 , 5 4 1 , 5 4 1-4 2 5 , 1 Нет неисправности 3 1 , 2 Нет неисправности 4 Вариант 1 2 , 3 «мусо р» 4 Вариант 2 2 , 3 4 2 , 3 4 4-3 , 4-2 5 3 , 4 4 3 , 5 4 5-4 После обмена результатами голосования , во всех узлах может оказаться информация , представленная таблицей 2.13. Таблица 2.13 Данные голосования от ПЭ № Возможная причина неисправности ПЭ № или Линк № Вывод Консолидированное решение 1 4 4-1 2 Нет неисправности 3 Нет неисправности 4 Вариант 1 «мусор» Неисправность ПЭ 4 Неисправность ПЭ 4 4 Вариант 2 4 4-3 , 4-2 5 4 5-4 Вариант 1 : Сообщение от ПЭ 4, содержит «мусор» , что говорит о неисправности ПЭ 4 или его каналов связи . Однако ПЭ 1 и ПЭ 5 приняли решение о неисправности ПЭ 4 или каналов связи 5-4, 4-1. П оскольку отказ сразу всех каналов связи ПЭ 4 и отказ ПЭ 4 события равнозначные , принимается решение об неисправности ПЭ 4. Вариант 2 : Сообщение ПЭ 4 подтверждает результаты голосования в тройке ПЭ 4, ПЭ 5, ПЭ 1 и принимается решение об отказе ПЭ 4. После двух отка зов (линка 3-1 и ПЭ 4) ВС имеет вид (рис . 2.6) Рис .2.6. Топология ВС после 2-х отказов Таблица связности , измененная реконфигуратором , представлена та блицей 2.14. Обмен результатами счета теперь осуществляется следующим образом : 1. ПЭ 1 -> ПЭ 2 и ПЭ 3; 2. ПЭ 2 -> ПЭ 3 и ПЭ 5; 3. ПЭ 3 -> ПЭ 5 и ПЭ 1; 4. ПЭ 5 -> ПЭ 1 и ПЭ 2; Таблица 2.14 Обновленная таблица связности № /№ 1 2 3 4 5 1 -1 0 -1 -1 3 2 3 -1 0 -1 2 3 -1 3 -1 -1 1 4 -1 -1 -1 -1 -1 5 0 1 2 -1 -1 Рассмотрим дальнейший процесс деградации системы . Отказ ПЭ 5 аналогично легко диагностируется , благодаря связям с каждым ПЭ в системе . Предположим теперь , что произошел отказ канала связи 2-3. Напомни м , что связь ПЭ 1 и ПЭ 3 осуществляется через ПЭ 2. Таким образом , в результате в узлах сети фиксируются следующие факты несовпадения результатов счета , представленные в таблице 2.15. Таблица 2.15 № ПЭ Получены данные от ПЭ № Данные от ПЭ № Не совпадают с данными от ПЭ № Возможная причина : Неисправность ПЭ № или Линк № 1 3,5 3 1 , 5 2 или 3 2-1 или 2-3 2 1,5 Нет неисправности 3 1,2 Нет совпадений Недостаточно дан ных 5 2,3 Нет неисправности После обмена результатами голосования , в узлах может оказаться информация , представленная таблицей 2.16. Таблица 2.16 ПЭ№ Данные голосования от ПЭ № Возможная причина неисправности ПЭ № или Линк № Вывод Консолидир ованное решение 1 2 или 3 2-1 или 2-3 2 Нет неисправности 1 3 "мусор " Неисправен Линк 2-3 5 Нет неисправности 1 2 или 3 2-1 или 2-3 2 Нет неисправности 2 3 "мусор " Неисправен Линк 2-3 5 Нет неисправности Неисправен Линк 2-3 1 "мусор " 2 "мусор " 3 3 Недостаточно данных Неисправен Линк 2-3 5 Нет неисправности 1 2 или 3 2-1 или 2-3 2 Нет неисправности 5 3 Недостаточно данных Неисправен Линк 2-3 5 Нет неисправности Анализ ПЭ 1, ПЭ 2 и ПЭ 5 возможных причин неисправности , показывает : 1. Результаты голосования от ПЭ 2 подтверждают работоспособность ПЭ 1, ПЭ 5, каналов 2-1 и 2-5. 2. Результаты голосования от ПЭ 5 подтвержд ают работоспособность ПЭ 3, ПЭ 2, каналов 3-5 и 2-5. 3. Данные ПЭ 5 от ПЭ 3 говорят о исправности канала связи 3-5. Таким образом ПЭ 1,ПЭ 2 и ПЭ 5 делают вывод о неисправности канала 2-3, маскируя неисправности по данным от ПЭ 1. Анализ ПЭ 3 возможных причин неисп равности , показывает : 1. Результаты голосования от ПЭ 5 подтверждают работоспособность ПЭ 3, ПЭ 2, каналов 3-5 и 2-5. 2. “Мусор” от ПЭ 1 может означать , что неисправен ПЭ 1 или ПЭ 2, или канал 1-2, или канал 2-3. 3. “Мусор” от ПЭ 2 может означать неисправность ПЭ 2 или канала 2-3. Из условия ординарности потока отказов , одновременная неисправность ПЭ 1 и ПЭ 2 невозможна , как невозможно и сочетание 1-2 и 2-3. Таким образом из пунктов 2 и 3 следует отказ либо ПЭ 2, либо канала 2-3. Пункт 1 опровергает отказ ПЭ 2. Дел ается вывод об отказе канала 2-3. Конфигурация , изображенная на рис . 2.6 является в какой-то мере критичной , поскольку используется транзитная связь через ПЭ 2. Рассмотрим отказ ПЭ 2 в этой же топологии . При этом , интерфейс обмена таков , что ПЭ 2 в случае фа тального отказа не передаст транзитную информацию (передаст «мусор» ), в противном случае передаст ее без изменений. В результате обмена результатами счета , в узлах сети могут фиксироваться следующие факты несовпадения , представленные в таблице 2.17. Таблица 2.17 № ПЭ Получены данные от ПЭ № Данные от ПЭ № Не совпадают с данными от ПЭ № Возможная причина : Неисправность ПЭ № или Линк № 1 Вариант 1 3,5 3 1 , 5 2 или 3 2-1 или 2-3 1 Вариант 2 3,5 Нет неисправности 2 Вариант 1 1,5 «мусор» 2 Вариант 2 1,5 2 1 , 5 2 1-2, 1-5 3 Вариант 1 1,2 Нет совпадений Недостаточно данных 3 Вариант 2 1,2 2 1 , 3 2 2-3 5 2,3 2 3 , 5 2 2-5 После обмена результатами голосования в зависимости от степени отказа ПЭ 2, в работоспособных узлах может оказаться информация , представленная таблицей 2.18. Таблица 2.18 ПЭ№ Данные голосования от ПЭ № Возмо жная причина неисправности ПЭ № или Линк № Вывод Консолидированное решение 1 2 или 3 2-1 или 2-3 1 Вариант 1 2 "мусор " 3 "мусор " 5 2 2-5 1 Нет неисправности Неисправен ПЭ 2 1 Вариант 2 2 2 1-2, 2-5 3 2 2-3 5 2 2-5 1 "мусор " 3 Вариант 1 2 "мусор " 3 Недостаточно данных 5 2 2-5 Неисправен ПЭ 2 1 Нет неисправности Неисправен ПЭ 2 3 Вариант 2 2 2 1-2, 2-5 3 2 2-3 5 2 2-5 1 2 или 3 2-1 или 2-3 5 Вариант 1 2 "мусор " 3 Недостаточно данных 5 2 2-5 1 Нет неисправности 5 Вариант 2 2 2 1-2, 2-5 Неисправен ПЭ 2 3 2 2-3 5 2 2-5 Рассмотрим процесс принятия решения ПЭ 1: Вариант 1 : «Мусор» от ПЭ 3 и данные ПЭ 2 говорят о неисправности ПЭ 2 или линка 2-1. Диагноз ПЭ 5 подтверждает неисправность ПЭ 2. Таким образом каждая запись в ПЭ 1 прямо или косвенно говорит о неисправности ПЭ 2 или его связей . В силу ординарности потока отказов принимается решение об отказе ПЭ 2. Вариант 2: Один противоречивый результат маскируется тремя подтверждениями неисправности ПЭ 2, так как одновременный отказ всех линков трактутся также как и отказ всего ПЭ 2. Аналогично в ПЭ 3 и ПЭ 5 в любом случае оказывается минимум два сообщ ения об отказе ПЭ 2 или его связей . Как было отмечено выше вероятность отказа одновременно нескольких каналов связи существенно меньше вероятности отказа ПЭ , и вследствие предположения об ординарности потока отказов , делается вывод об отказе ПЭ 2. Рассмотри м деградацию системы после отказа линка 2-3. Топология системы представлена на рис . 2.7. Рис . 2.7. Топология ВС после отказа линка 2-3. Маршрутизаторо м были определены новые статические маршруты , для связи ПЭ 1 и ПЭ 3 и ПЭ 2 через ПЭ 5. В данном случае отказ ПЭ 3 или линка 3-5 обнаруживается легко с помощью ПЭ 5. Аналогично обнаруживаются отказы ПЭ 1 и ПЭ 2. Рассмотрим отказ ПЭ 5. В результате обмена результата ми счета , в узлах сети могут фиксироваться следующие факты несовпадения , представленные в таблице 2.19. Таблица 2.19 № ПЭ Получены данные от ПЭ № Данные от ПЭ № Не совпадают с данными от ПЭ № Возможная причина : Неисправность ПЭ № или Линк № 1 Вариан т 1 3,5 5 1 , 3 5 1-5 1 Вариант 2 3,5 Нет совпадений Недостаточно данных 2 1,5 5 1 , 2 5 2-5 3 Вариант 1 1,2 Нет неисправности 3 Вариант 2 1,2 Нет совпадений Недостаточно данных 5 Вариант 1 2,3 5 2 , 3 5 1-5, 3-5 5 Вариант 2 2,3 “мусор” После обмена результатами голосования в зависимости от степени отказа ПЭ 5, в работоспособных узлах может оказаться информация , представленная таблицей 2.20. Таблица 2.20 ПЭ№ Данные голосования от ПЭ № Возможная причина неисправности ПЭ № или Линк № Вывод Консолидированное решение 1 Недостаточно данных 1 Вариант 1 2 5 2-5 3 "мусор " 5 "мусор " 1 5 1-5 Неисправен ПЭ 5 1 Вариан т 2 2 5 2-5 3 Нет неисправности 5 5 1-5, 3-5 1 Недостаточно данных 2 Вариант 1 2 5 2-5 3 "мусор " 5 "мусор " Неисправен ПЭ 5 1 5 1-5 Неисправен ПЭ 5 2 Вариант 2 2 5 2-5 3 Нет неисправности 5 5 1-5, 3-5 1 "мусор " 3 Вариант 1 2 "мусор " Недостаточно 3 Недостаточно данных данных 5 "мусор " 1 5 1-5 3 Вариант 2 2 5 2-5 Неисправен ПЭ 5 3 Нет неисправности 5 5 1-5, 3-5 Анализ работоспособными узлами причин отказа показывает : 1. При полном отказе ПЭ 5: · Анализ ПЭ 1 и ПЭ 2: “мусор” от ПЭ 3 и ПЭ 5 говорит о неисправнос ти ПЭ 5 или канала 1-5, а данные ПЭ 2 однозначно говорят об отказе ПЭ 5. · Анализ ПЭ 3: “мусор” от ПЭ 2, ПЭ 3 и ПЭ 5 говорит о неисправности ПЭ 5 или канала 3-5. В данном случае это уже не важно , так как результатами голосования ПЭ 3 обменяться ни с кем не сможет. В случае возникновения такой ситуации ПЭ анализирует – сколько узлов остается в системе , кроме него самого . Если больше двух , то он самостоятельно прекращает выдачу данных. 2. При отказе ПЭ 5, с сохранением способности обмена , информации для его диагности рования хватает с избытком. После обмена окончательными выводами ПЭ 1 и ПЭ 2 принимают решение об отключении ПЭ 5. После реконфигурации , маршрутизатор обнаруживает изолированность ПЭ 3 и посылает сигнал реконфигуратору об отключении ПЭ 3. Рассмотрим теперь фун кционирование ВС в составе трех ПЭ . Пусть остались функционировать ПЭ 1, ПЭ 2 и ПЭ 5. Рассмотрим отказ связи 2-5. В результате в узлах сети фиксируются следующие факты несовпадения результатов счета , представленные в таблице 2.21. Таблица 2.21 № ПЭ Получены данные от ПЭ № Данные от ПЭ № Не совпадают с данными от ПЭ № Возможная причина : Неисправность ПЭ № или Линк № 1 2,5 Нет неисправности 2 1,5 5 1 , 2 5 2-5 5 1,2 2 1 , 5 2 2-5 После обмена результатами голосования , в узлах может оказаться информация , представленная таблицей 2.22. Таблица 2.22 ПЭ№ Данные голосования от ПЭ № Возможная причина неисправности ПЭ № или Линк № Вывод Консолидированное решение 1 Нет неисправности 1 2 5 2-5 Неисправен 2-5 5 2 2-5 1 Нет неисправности 2 2 5 2-5 Неисправен 2-5 Неисправен 2-5 5 "мусор " 1 Нет неисправности 5 2 "мусор " Неисправен 2-5 5 2 2-5 Анализ ПЭ 1 предварительной информации подтверждает отказ линка 2-5, так как исправность ПЭ 2 и ПЭ 5 подтверждается информацией от ПЭ 1. Анализ ПЭ 2 и ПЭ 3 поступившей информации говорит о неисправности линка 2-5, в силу того , что ПЭ 1 подтверждает правильность результатов ПЭ 2 и ПЭ 5. Рассмотрим дальнейшее функционирование системы (рис . 2.9). Отказ ПЭ 5 и ПЭ 2 диагностируется также , как было показано выше , так как не нарушается связность между двумя ПЭ . Отказ связи 1-5 воспринимается ПЭ 1 и ПЭ 2, как отказ ПЭ 5. Аналогично , отказ связи 1-2 равносилен отказу ПЭ 2. В процессе функционирования в системе всегда существует старший ПЭ , который выдает объекту управления согласованные данные . Если после принятия консолидированного решения , обнаруживается сбой в старшем элементе , то старшим назначается другой ПЭ , имеющий максимальное количество связей или младший номер , если количество связей у всех ПЭ одинаково . В предыдущум примере (при изоляции ПЭ 3) этот прием позволяет прекратить выдачу данных с изолированно г о ПЭ. В данном варианте может возникнуть ситуация , когда ПЭ 2 при отказе линка 1-2 принимает решение об отказе ПЭ 1 и становится старшим элементом , как ПЭ с младшим номером . При этом он принимает решение об отключении ПЭ 5. Одновременно ПЭ 1 и ПЭ 5 принимают ре шение об отказе ПЭ 2 и в свою очередь исключают его из текущей конфигурации . Тогда наступает ситуация , когда одновременно на выход подаются два , возможно и разных варианта . Чтобы избежать такой ситуации , необходимы спецальные аппаратные или программно-аппа р атные средства , которые в рамках данной работы не рассматриваются. Если сделать предположение о равновероятности отказов в системе , изображенной на рис .2.9, то вероятность отказа линка 2-1, приводящая к неопределенности в системе , равна 0.2. Однако в реал ьных ВС вероятность отказа канала связи считается величиной на порядок меньшей , чем вероятность отказа ПЭ за этот же период времени. Отказ канала 1-5 не приведет к неопределенности . ПЭ 5 не станет старшим в любом случае и будет отключен . Отказ ПЭ 1 также не приведет к неопределенности , управление возьмет на себя ПЭ 2. На предпоследнем этапе деградации системы в системе остается 2 исправных ПЭ , соединенных одним каналом связи . При на первый план в качестве диагностической информации выходят признаки исп равности /неисправности , формируемые различными программно-аппаратными средствами контроля , такими как функциональный контроль вычислений с помощью специальных контрольных операторов , контроль входной информации по специальным признакам и контрольным суммам , контроль выходной информации по квитанции от приемника и тд . Следует отметить , что «жесткое» использование признаков неисправности , вырабатываемых контрольными тестами аппаратуры , может привести к появлению ошибок второго рода («ложная т ревога» ) и исключению из вычислительного процесса функционально-пригодной аппаратуры . Это приводит к необходимое применения гибких моделей совместного использования результатов голосования и признаков контрольных средств. 2.5.2. Методика анализа отказов Исходя из этого примера , помимо модуля голосования систему необходимо дополнить гибким механизмом анализа отказов. Подсистема анализа отказов должна инициироваться модулем коммуникации , по завершению обмена результатами голосования , и оперировать следующе й информацией : · Результатами голосования (предварительными выводами по результатам сравнения ) функциональной информации ; · Сигналами модуля коммуникации о неверной контрольной сумме пакета , о тайм-ауте при приеме пакета , об отсутствии или неверном коде квитанции. Логика выводов при анализе данных голосования и информации от модуля коммуникации такова : · Несовпадение данных при элементарной проверке результатов счета на очередном цикле диагностируется , как отказ ПЭ или канала связи этого ПЭ , при этом гол осование проводится каждым ПЭ (с номером m ) по результатам от ПЭ с номерами ( m -1) mod N и ( m -2) mod N . · При несовпадении данных при элементарной проверке результатов счета , полученных с использованием транзитной передачи , под сомнение ставится вся цепоч ка , задействованная при передаче. · При несовпадении ни одного результата счета под сомнение ставится все участвовавшие в обмене ПЭ и связи. · Несовпадение контрольной суммы или тайм-аут при приеме данных трактуется как сбой ПЭ или канала связи ПЭ. · От сутствие квитанции трактуется как сбой ПЭ или канала связи ПЭ. · Неверный код квитанции трактуется как сбой канала связи ПЭ. Для принятия решения об отказе (сбое ) того или иного элемента ВС (ПЭ , канала связи ) по набору выводов от каждого узла сети , был п редложен следующий эвристический алгоритм , при выполнении условия об ординарности потока отказов : 1. Создается матрица состояния ВС , которая размерностью идентична модифицированной матрице связности ПЭ , но по главной диагонали находятся данные о ПЭ , а в я чейках матрицы – о каналах связи. 2. Матрица состояния ВС инициализируется единицами. 3. После обмена предварительными результатами голосования , у каждого ПЭ оказывается результаты голосования от всех ПЭ ВС и диагностическая информация от модуля коммуник ации. 4. Последовательно , в соответствии с логикой , изложенной выше , делается вывод по каждой записи , и очередное предположение заносится в матрицу состояния ВС путем вычитания единицы из ячейки , соответствующей элементу ВС , не в пользу которого делается это предположение. 5. Если выводом по очередной записи становится отсутствие отказов по определенным элементам , то это предположение заносится в матрицу состояния ВС путем инкрементирования ячейки , соответствующей элементу ВС , в пользу которого делается э то предположение. 6. После обработки всех записей , матрица состояний ВС просматривается на предмет поиска минимального отрицательного значения. 7. Если такое значение есть , то соответствующий элемент признается отказавшим , иначе принимается решение об от сутствии оказов. Данный алгоритм создан так , что в матрице состояний после его завершения , не окажется больше двух минимальных отрицательных значений , причем эти значения не будут принадлежать одинаковым функциональным элементам (то есть одновременно 2-м П Э или 2-м каналам связи ). В случае присутствия одинаковых минимальных значений , делается выбор в пользу отказа канала связи. Проиллюстрируем его на примере ВС , изображенной на рис . 2.7, и отказа ПЭ 5 в этой конфигурации . Обмен для голосования в сети осущес твляется следующим образом : ПЭ 1->ПЭ 2, ПЭ 3; ПЭ 2->ПЭ 3, ПЭ 5; ПЭ 3->ПЭ 5, ПЭ 1; ПЭ 5->ПЭ 1, ПЭ 2. Обмен результатами голосования для принятия консолидированного решения – по всей ВС . Приведем логику анализа неисправности с точки зрения выбранной эвристики. Вариан т 1 : ПЭ 5 продолжает функционирование , обмен и голосование , но функциональная задача выполняется неверно . Таким образом , сигналов о неисправности от модулей коммуникации ПЭ сети поступать не будет. В таблице 2.23 представлены записи от всех ПЭ , расшифрован ные в соответствии с выбранной логикой. Таблица 2.23 ПЭ№ Данные голосования от ПЭ № Информация от модуля коммуникации Возможная причина неисправности ПЭ № или Линк № Вывод 1 Нет 5 1-5 1 2 Нет 5 2-5 Неисправен ПЭ 5 3 Нет Нет неисправности 5 Нет 5 1-5, 3-5 1 Нет 5 1-5 2 2 Нет 5 2-5 Неисправен ПЭ 5 3 Нет Нет неисправности 5 Нет 5 1-5, 3-5 1 Нет 5 1-5 3 2 Нет 5 2-5 Неисправен ПЭ 5 3 Нет Нет неисправности 5 Нет 5 1-5, 3-5 Составим матрицу состояния ВС , получившуюся у ПЭ 1 (см . таблицу 2.24). Таблица 2.24 № / № 1 2 3 5 1 2 1 2 -1 2 1 2 2 0 3 2 2 2 0 5 -1 0 0 - 2 Таким образом , делается вывод о неисправности ПЭ 5. Аналогичный вывод , судя по таблице 1, делают и ПЭ 1 и ПЭ 2. Вариант 2 : Наступил фатальный отказ ПЭ 5, при котором он прекращает обмен с ВС , либо выдает неинформативные данные. Таблица 2.25 содержит расшифровку записей всех ПЭ в этом случае. Таблица 2.25 ПЭ№ Данные голосования от ПЭ № Информация от модуля коммуникации Возможная причина неисправности ПЭ № или Линк № Вывод 1 Нет 1 или 3 или 5 3-5 или 1-5 1 2 Нет 5 2-5 Неисправен ПЭ 5 3 Тайм-аут или КС 3 или 5 3-5 или 1-5 5 Тайм-аут или КС 5 1-5 1 Нет 1 или 3 или 5 3-5 или 1-5 2 2 Нет 5 2-5 Неисправен ПЭ 5 3 Тайм-аут или КС 3 или 5 3-5 или 2-5 5 Тайм-аут или КС 5 2-5 1 Тайм-аут или КС 1 или 5 3-5 или 1-5 3 2 Тайм-аут или КС 2 или 5 3-5 или 2-5 Неисправен 3-5 3 Нет 1 или 2 или 3 или 5 3-5 или 1-5 или 2-5 5 Тайм-аут или КС 5 3-5 Таким образом : · В ПЭ 1 оказывается 4 голоса против ПЭ 5 и 3 голоса против канала связи 1-5. Решени е – отказ ПЭ 5. · В ПЭ 2 оказывается 4 голоса против ПЭ 5 и 3 голоса против канала связи 2-5. Решение – отказ ПЭ 5. · В ПЭ 3 оказывается 4 голоса против ПЭ 5 и 4 голоса против канала связи 3-5. Решение – отказ канала связи 3-5. Ситуация , аналогичная наступивше й в ПЭ 3, возникает , когда у ПЭ остается лишь один канал связи . После его утраты ПЭ становится изолированным и отключается. 2.6. Оценка надежностных характеристик отказоустойчивой ВС Выбранная концепция построения специализированной распределенной операцион ной системы реального времени позволит однородной системе функционировать при возникновении N -1 отказа ПЭ в системе. Если не учитывать вероятность отключения работоспособных процессорных модулей , то можно провести оптимистическую оценку вероятности отказа всей системы за определенный период функционирования и среднего времени наработки на отказ системы. Будем предполагать , что поток отказов в каждом узле системы является простейшим , т.е . стационарным , ординарным и без последствия , с показательным законом распределения длины интервала между соседними событиями (отказами ): (1) где : - вероятность того , что за время t произойдет ровно “ K” событий (отказов ); - параметр потока , интенсивность потока отказов ; T 0 – математическое ожидание длины интервала между соседними событиями – среднее время наработки на отказ ; P 0 (t) – вероятность того , что за время t не произойдет ни одного события (отказа ), вероятность безотказной работы. Обозначим через – среднее время наработки на отказ одного узла системы . Для отказоустойчивых систем под состоянием отказа бу дем понимать состояние фатального отказа , т.е . для ОС -N(m), это состояние , при котором произошел отказ более чем “ m” узлов системы (m+1, m+2, … ). В произвольный момент времени t мы можем застать систему в одном из двух состояний : - работоспособном , с веро ятностью R(t), - в состоянии фатального отказа , с вероятностью P(t). Если взглянуть на систему с учетом состояний работоспособности каждого из N ее элементов (узлов ), то в произвольный момент времени t мы можем застать систему в одном из 2 N состояний (см . рис . 2.10). Рис 2.10. Состояния N-узловой системы Если поставить в соответствие каждому узлу системы разряд двоичного N разрядного числа (0 – узел работает , 1 – узел отк азал ), то каждому такому состоянию системы можно поставить в соответствие свой номер , равный значению введенного двоичного N разрядного числа и каждому такому состоянию соответствует некоторая вероятность нахождения системы в момент времени t в этом состо я нии . Все 2 N состояний системы можно разбить на несколько групп состояний , каждое из которых отличается от других количеством отказавших узлов . Нулевая группа (группа с номером 0) содержит одно состояние ( = 1), в котором все узлы системы находятся в состоянии работоспособности , т.е . имеется ровно 0 отказавших элементов . Первая группа включает в себя все состояния , в которых отказал ровно один узел (двоичные номе ра этих состояний содержат лишь одну единицу в N разрядном двоичном коде ). Количество состояний , входящих в первую группу равно =N – числу сочетаний из N по 1 ( ). Вторую группу составляют состояния , в которых в системе имеется два отказавших элемента , таких состояний ровно и т.д . В i-ю группу включаются все состояния , в которых в системе отказало ровно i узлов , таких состояний . Предпоследняя (N-1) – я группа включает в себя состояний , т.е . N состояний. Последняя N-я группа содерж ит одно состояние ( =1), в котором отказали все N узлов системы. Т.к . в произвольный момент времени система может находится только в одном из всех 2 N состояний , то эти события являются несовместными . Поэтому вероятность нахождения системы в любом из состояний , относящихся к одной из упомянутых выше групп можно получить как сумму вероятностей нахождения системы во всех состояниях данной группы . А если учесть , чт о внутри каждой i-й группы все состояния характеризуются наличием ровно i отказавших узлов , то вероятности для всех состояний одной группы равны между собой , поэтому : (2) где : P i – вероятность нахождения системы (в произвольный момент времени t) в любом из состояний , отнесенных к i-й группе ; - вероятность нахождения системы в одном конкретном состоянии , отнесенном к i-й группе. Все состояния , отнесенные к i-й группе характеризуются наличием в системе (в произвольный момент времени t) ровно i отказавших узлов и ровно ( N -i) исправных узлов. В соответствии с введенным в ыше предположением о простейшем потоке отказов (1) вероятность можно оценить следующим образом : (3) где первая скобка соответствует тому , что (N-i) элементов находя тся в работоспособном состоянии , а вторая тому , что i элементов отказали . Подставляя (3) в (2) можно получить выражение для вычисления вероятностей P i . Очевидно , что для системы ОС -N(m) (N узловой системы с рангом отказоустойчивости m) все состояния систем ы , входящие в группы 0,1,2,… m относятся к тем состояниям , в которых система нормально функционирует . В этой связи вероятность R(t) можно оценить следующим образом : (4) Вероятность фатального отказа системы ОС – N(m) можно оценить как сумму вероятностей нахождения системы в состояниях , отнесенных к группам m+1, m+2, … N-1, N: (5) Критерием правильности предложенной методики является выполнение условия R(t)+P(t)=1 для любых систем и любых значений t. Объединяя выражения (2) (3) (4) и (5), получим окончательные формулы для вычисления вероятностей безотказной работы – R N(m) (t) и фатального отказа – P N(m) (t) систем ОС -N(m) для произвольного момента времени t: (6) Для практических расчетов целесообразно использоват ь одну из этих формул , а именно ту , у которой (в зависимости от значений N и m) меньше суммируемых членов , т.е . при целесообразно использовать формулу P N(m) ( t) в противном случае – формулу R N(m) (t). При этом второй параметр получается из соотношения R N(m) (t)+P N(m) (t)=1. Таким образом для систем типа N ( N -1) выражения (6) принимают вид : (6а ) Рассмотрим теперь определение среднего времени наработки на отказ T 0 N(m) отказоустойчивых систем ОС -N(m). Невосстанавливаемая N-узловая отказоустойчивая система m-го ранга (ОС -N(m)) может быть представлена марковской моделью с количеством состояний (N+1): где : 0 – состояние , в котором ни один узел системы не отказал ; 1 – состояние (объединяющее группу из состояний системы – см . рис . 2.4), в котором отказал ровно 1 узел ; 2 – состояние (объединяющее группу из состояний системы ), в котором отказали ровно 2 узла ; m – состояние (объединяющее группу из состояний системы ), в котором о тказало ровно m узлов и т.д. Переход из одного состояния в другое (по мере постепенной деградации системы ) определяется интенсивностью потока отказов , воздействующих на систему , находящуюся в соответствующем состоянии . Интенсивность потока отказов , воздейс твующих на систему , находящуюся в i-м состоянии , определяется количеством работоспособных узлов (N-i). Т.о . среднее время нахождения системы в i-м состоянии определяется следующим образом : (7) где : - интенсивность потока отказов одного узла системы. Фатальный отказ системы ОС -N(m) произойдет только при переходе с истемы из состояния m в состояние m+1, поэтому среднее время наработки системы ОС -N(m) на отказ равно среднему времени последовательного нахождения системы в состояниях 0,1,2… .m: (8) Выражение (8) получено на основании одного фундаментального свойства показательного закона распределения : «если промежуток времени , распределенный по показательному закону , уже длился некоторое время t, то это никак не влияет на закон распределения оставшейся части промежутка : он будет таким же , как и закон распределения всего промежутка» [12]. Это свойство показательного закона представляет собой , по существу , одну из формулировок для «отсутствия последействия» , которое является о сновным свойством простейшего потока , принятого нами в качестве модели потока отказов. Если ввести обозначение : (8а ) то этот «коэффициент надежности» в с оответствии с (8) представляет собой отношение T 0 N(m) к T 0 y : , и показывает , во сколько раз по сравнению с T 0 y – средним временем наработки на отказ одного узл а , изменилось среднее время наработки на отказ системы ОС -N(m) в целом . Используя формулы (6а ) и (8а ) можно производить оценку надежностных характеристик отказоустойчивых систем типа N ( N -1). Примем среднее время наработки на отказ узла =10 5 часов . В таблице 2.26 приведены характеристики , рассчитанные по формулам (6а ) и (8а ). Таблица 2.26 Харктиристики отказоустойчивых систем типа N ( N -1) №№ п /п N(N-1) – тип системы / Характеристика 1(0) 3(2) 4(3) 5(4) 6(5) 7(6) 8(7) 9(8) 10(9) 1 4 часа 4
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
- Подсудимый, зачем вы кинули камнем в продавца и разбили ей голову?
- Ваша честь, это был не камень, а её "свежая булочка".
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, диплом по программированию "Разработка отказоустойчивой операционной системы реального времени для вычислительных систем с максимальным рангом отказоустойчивости", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru