Введение

Втечение многихлет приложенияна базе ОС реальноговремени использовалисьво встроенныхсистемах специальногоназначения,а с недавнеговремени онистали применятьсяповсюду, отбортовых системуправленияЛА, до бытовыхприборов.

Разработкамногопроцессорныхвычислительныхсистем (ВС) какправило, имеетсвоей цельюповышение либоуровня надежности,либо уровняпроизводительностисистемы дозначений недоступныхили труднореализуемыхв традиционныхЭВМ.

Впервом случаена переднийплан встаетвопрос о наличииспециальныхсредств обеспеченияотказоустойчивостивычислительныхсистем, основнойособенностью(и достоинством)которых являетсяотсутствиекакого-либоединственногоресурса, выходиз строя которогоприводит кфатальномуотказу всейсистемы.

Такимобразом, объектомисследованияв рамках сетевойотказоустойчивойтехнологиистановитсяОСРВ — управляющеепрограммноеобеспечениеособого типа,которое используетсядля организацииработы встроенныхприложений,для которыххарактерныограниченностьресурсов памяти,невысокаяпроизводительность,а также требованиягарантированноговремени отклика,высокого уровняготовностии наличия средствавтомониторинга.

Даннаядипломнаяработа посвященаразработкеспециализированнойраспределеннойоперационнойсистемы реальноговремени дляотказоустойчивыхВС с рангомотказоустойчивостиN(N-1),что означаетспособностьсистемы функционироватьдаже в том случае,если произойдутотказы всехэлементовсистемы заисключениемодного. Дляполного освещениявыбранной темыбыли поставленыследующиезадачи:

Провестианализ существующихоперационныхсистем реальноговремени, выделитьосновныефункциональныетребованияк ним, датьсравнительнуюхарактеристику.
РаскрытьконцепциюпостроенияОСРВ с рангомотказоустойчивостиN-1, выделитьосновные модулиоперационнойсистемы, функциональныетребованияк ним и алгоритмыработы.
Раскрытьлогику организацииотказоустойчивыхвычисленийна примереконкретнойреализации.
Провестианализ надежностиотказоустойчивойВС и дать рекомендациипо организацииВС.
Создатьпрограммнуюмодель вычислительнойсистемы сраспределеннойоперационнойсистемой реальноговремени и отработатьна ней различныережимы работы.
Рассмотретьвозможностьпортирования(переноса) ОСРВна платформуTMS320c30,рассмотретьспецифическиепроблемы исложности приосуществлениипортации.

Впервой частиработы данократкое описаниеизвестных ОСРВ,описаны ихфункциональныевозможности,структура, ихнаправленность(специфическиеособенности).Также приведенасравнительнаяхарактеристикаи отмечены терешения, которыеможно было быиспользоватьдля разработкисобственнойспециализированнойОСРВ.

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

Далеерассмотренапрограммнаямодель ВС иоперационнойсистемы, логикаработы и взаимосвязьмодулей.

В последнейглаве рассматриваютсяособенностиаппаратнойплатформыTMS320c30,вопросы реализациивышеприведенныхидей с помощьюэтой платформы,дополнениеОС специфическимидля даннойархитектурымодулями.

Специальнаячасть

Операционныесистемы реальноговремени.

ОСобщего назначения,особенномногопользовательские,ориентированына оптимальноераспределениересурсов компьютерамежду пользователямии задачами(системы разделениявремени), Воперационныхсистемах реальноговремени (ОСРВ),подобная задачаотходит навторой план- все отступаетперед главнойзадачей - успетьсреагироватьна события,происходящиена объекте.

Описаниеи общие требованияк системамреальноговремени.

Применениеоперационнойсистемы реальноговремени всегдасвязано саппаратурой,с объектом, ссобытиями,происходящимина объекте.Система реальноговремени, какаппаратно-программныйкомплекс, включаетв себя датчики,регистрирующиесобытия наобъекте, модуливвода-вывода,преобразующиепоказаниядатчиков вцифровой вид,пригодный дляобработки этихпоказаний накомпьютере,и, наконец, компьютерс программой,реагирующейна события,происходящиена объекте.ОСРВ ориентированана обработкувнешних событий.Именно этоприводит ккоренным отличиям(по сравнениюс ОС общегоназначения)в структуресистемы, в функцияхядра, в построениисистемы ввода-вывода.ОСРВ может бытьпохожа попользовательскомуинтерфейсуна ОС общегоназначения, однако устроенаона совершенноиначе - об этомречь впереди.

Крометого, применениеОСРВ всегдаконкретно. ЕслиОС общего назначенияобычно воспринимаетсяпользователями(не разработчиками)как уже готовыйнабор приложений,то ОСРВ служиттолько инструментомдля созданияконкретногоаппаратно -программногокомплексареальноговремени. И поэтомунаиболее широкийкласс пользователейОСРВ - разработчикикомплексовреальноговремени, людипроектирующиесистемы управленияи сбора данных.Проектируяи разрабатываяконкретнуюсистему реальноговремени, программиствсегда знаетточно, какиесобытия могутпроизойти наобъекте, знаеткритическиесроки обслуживаниякаждого из этихсобытий.

Назовемсистемой реальноговремени (СРВ)аппаратно-программныйкомплекс, реагирующийв предсказуемыевремена нанепредсказуемыйпоток внешнихсобытий.

Этоопределениеозначает, что:

Системадолжна успетьотреагироватьна событие,произошедшеена объекте, втечение времени,критическогодля этого события.Величинакритическоговремени длякаждого событияопределяетсяобъектом исамим событием,и, естественно,может бытьразной, но времяреакции системыдолжно бытьпредсказано(вычислено)при созданиисистемы. Отсутствиереакции впредсказанноевремя считаетсяошибкой длясистем реальноговремени.
Системадолжна успеватьреагироватьна одновременнопроисходящиесобытия. Дажеесли два илибольше внешнихсобытий происходятодновременно,система должнауспеть среагироватьна каждое изних в течениеинтерваловвремени, критическогодля этих событий.

Различаютсистемы реальноговремени двухтипов - системыжесткого реальноговремени и системымягкого реальноговремени.

Системыжесткого реальноговремени недопускаютникаких задержекреакции системыни при какихусловиях, таккак:

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

Примерысистем жесткогореальноговремени - бортовыесистемы управления,системы аварийнойзащиты, регистраторыаварийныхсобытий.

Системымягкого реальноговремени характеризуютсятем, что задержкареакции некритична, хотяи может привестик увеличениюстоимостирезультатови снижениюпроизводительностисистемы в целом.

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

Тогдаоперационнаясистема реальноговремени - этотакая ОС, котораяможет бытьиспользованадля построениясистем жесткогореальноговремени. Этоопределениевыражает отношениек ОСРВ как кобъекту, содержащемунеобходимыеинструменты,но также означает,что этимиинструментамиеще необходимоправильновоспользоваться.

1.2. ПараметрыОСРВ

1.2.1.Время реакциисистемы

Почтивсе производителисистем реальноговремени приводяттакой параметр,как время реакциисистемы напрерывание(interrupt latency).

Всамом деле,если главнымдля системыреальноговремени являетсяее способностьвовремя отреагироватьна внешниесобытия, тотакой параметр,как время реакциисистемы являетсяключевым.

События,происходящиена объекте,регистрируютсядатчиками,данные с датчиковпередаютсяв модули ввода-вывода(интерфейсы)системы. Модуливвода-вывода,получив информациюот датчикови преобразовавее, генерируютзапрос на прерываниев управляющемкомпьютере,подавая емутем самым сигнало том, что наобъекте произошлособытие. Получивсигнал от модуляввода-вывода,система должназапуститьпрограммуобработки этогособытия.

Интервалвремени - отсобытия наобъекте и довыполненияпервой инструкциив программеобработки этогособытия и являетсявременем реакциисистемы насобытия.

Обычновремя реакциисистем на прерываниесоставляет порядка 4-10 мкс.

1.2.2.Время переключенияконтекста

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

Контекстзадачи этонабор данных,задающих состояниепроцессорапри выполнениизадачи. Обычносовпадает снабором регистров,доступных дляизмененияприкладнойзадаче.

Припереключениизадач (процессов)необходимо:

корректноостановитьработающуюзадачу;

дляэтого

а)выполнитьинструкциитекущей задачи,уже загруженныев процессор,но еще не выполненные;

б)сохранить воперативнойпамяти регистрытекущей задачи;

2.найти, подготовитьи загрузитьзатребованнуюзадачу;

3.запустить новуюзадачу, дляэтого

а)восстановитьиз оперативнойпамяти регистрыновой задачи(сохраненныеранее,

еслиона до этогоуже работала);

б)загрузить впроцессоринструкцииновой задачи.

Каждаяиз этих стадийвносит свойвклад в задержкупри переключенииконтекста.Поскольку любоеприложениереальноговремени должнообеспечитьвыдачу результатав заданноевремя, то этазадержка должнабыть мала,детерминированаи известна. Эточисло являетсяодной из важнейшиххарактеристикОСРВ. Обычновремя переключенияконтекста вОСРВ составляет10-20 мкс.

Размерысистемы

Длясистем реальноговремени важнымпараметромявляется размерсистемы исполнения,а именно суммарныйразмер минимальнонеобходимогодля работыприложениясистемногонабора (ядро,системныемодули, драйверыи т. д.). Хотя, надопризнать, чтос течениемвремени значениеэтого параметрауменьшается,тем не менее,он остаетсяважным и производителисистем реальноговремени стремятсяк тому, чтобыразмеры ядраи обслуживающихмодулей системыбыли невелики.

Механизмыреальноговремени

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

1.3.1.Система приоритетови алгоритмыдиспетчеризации

Базовымиинструментамиразработкисценария работысистемы являютсясистема приоритетовпроцессов(задач) и алгоритмыпланирования(диспетчеризации)ОСРВ.

ВмногозадачныхОС общего назначенияиспользуются,как правило,различныемодификацииалгоритмакруговойдиспетчеризации,основанныена понятиинепрерывногокванта времени("time slice"), предоставляемогопроцессу дляработы. Планировщикпо истечениикаждого квантавремени просматриваеточередь активныхпроцессов ипринимаетрешение, комупередать управление,основываясьна приоритетахпроцессов(численныхзначениях, имприсвоенных).Приоритетымогут бытьфиксированнымиили менятьсясо временем- это зависитот алгоритмовпланированияв данной ОС, норано или позднопроцессорноевремя получатвсе процессыв системе.

Алгоритмыкруговойдиспетчеризациинеприменимыв чистом видев ОСРВ. Основнойнедостаток- непрерывныйквант времени,в течение которогопроцессоромвладеет толькоодин процесс.Планировщикиже ОСРВ имеютвозможностьсменить процессдо истечения"time slice", если в этомвозникланеобходимость.Один из возможныхалгоритмовпланированияпри этом "приоритетныйс вытеснением".Мир ОСРВ отличаетсябогатствомразличныхалгоритмовпланирования:динамические,приоритетные,монотонные,адаптивныеи пр., цель жевсегда преследуетсяодна - предоставитьинструмент,позволяющийв нужный моментвремени исполнятьименно тотпроцесс, которыйнеобходим.

1.3.2.Механизмымежзадачноговзаимодействия

Другойнабор механизмовреальноговремени относитсяк средствамсинхронизациипроцессов ипередачи данныхмежду ними. ДляОСРВ характернаразвитостьэтих механизмов.К таким механизмамотносятся:семафоры, мьютексы,события, сигналы,средства дляработы с разделяемойпамятью, каналыданных (pipes), очередисообщений.Многие из подобныхмеханизмовиспользуютсяи в ОС общегоназначения,но их реализацияв ОСРВ имеетсвои особенности- время исполнениясистемныхвызовов почтине зависит отсостояниясистемы, и вкаждой ОСРВесть по крайнеймере один быстрыймеханизм передачиданных от процессак процессу.

Средствадля работы стаймерами

Такиеинструменты,как средстваработы с таймерами,необходимыдля систем сжестким временнымрегламентом,поэтому развитостьсредств работыс таймерами- необходимыйатрибут ОСРВ.Эти средства,как правило,позволяют:

измерятьи задаватьразличныепромежуткивремени (от 1мкс и выше),
генерироватьпрерыванияпо истечениивременныхинтервалов,
создаватьразовые ициклическиебудильники

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

Классы системреальноговремени

Монолитнаяархитектура

ОСРВс монолитнойархитектуройможно представитьв виде (рис. 1.1)

прикладногоуровня: состоитиз работающихприкладныхпроцессов;

системногоуровня: состоитиз монолитногоядра операционнойсистемы, в которомможно выделитьследующиечасти: интерфейсмежду приложениямии ядром (API), собственноядро системы,интерфейсмежду ядроми оборудованием(драйверыустройств).

Рис.1.1. ОСРВ с монолитнойархитектурой

Интерфейсв таких системахиграет двойнуюроль:

1.управлениевзаимодействиемприкладныхпроцессов исистемы,

2.обеспечениенепрерывностивыполнениякода системы(т.е. отсутствиепереключениязадач во времяисполнениякода системы).

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

Недостаткимонолитнойархитектуры.

1.Системныевызовы, требующиепереключенияуровней привилегий(от пользовательскойзадачи к ядру),должны бытьреализованыкак прерыванияили специальныйтип исключений.Это сильноувеличиваетвремя их работы.

2.Ядро не можетбыть прерванопользовательскойзадачей (non-preemptable).Это может приводитьк тому, чтовысокоприоритетнаязадача можетне получитьуправленияиз-за работынизкоприоритетной.

3.Сложностьпереноса нановые архитектурыпроцессораиз-за значительныхассемблерныхвставок.

4.Негибкостьи сложностьразвития: изменениечасти ядрасистемы требуетего полнойперекомпиляции.

Модульнаяархитектура(на основе микроядра)

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

Теперьмикроядроиграет двойнуюроль(рис 1.2):

1.управлениевзаимодействиемчастей системы(например, менеджеровпроцессов ифайлов),

обеспечениенепрерывностивыполнениякода системы(т.е. отсутствиепереключениязадач во времяисполнениямикроядра).

Рис.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

Ядрообеспечиваетосновной системныйсервис, включаяуправлениепроцессамии распределениересурсов.

Основныехарактеристики:

Архитектура:на основе микроядра
Стандарт:собственный,вызовы похожина UNIX

Свойствакак ОСРВ:

Многозадачность:многопроцессность

Многопроцессорность:да
Уровнейприоритетов:65535
Времяреакции: 3 мкс
Планирование:приоритетное,FIFO, специальныймеханизмпланирования;preemptive ядро

ОСразработки(host): UNIX/Windows
Процессоры(target): Motorola 68xxx, Intel 80x86, ARM, MIPS, PowerPC
Линиисвязи host-target: последовательныйканал и ethernet
Минимальныйразмер: 16Kb
Средствасинхронизациии взаимодействия:разделяемаяпамять, сигналы,семафоры, события.

Операционнаясистема 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канадскойкомпании QNXSoftwareSystemLtd.построена наоснове иерархическоймикроядернойархитектуры.Упрощеннаяструктурнаясхема этой ОСприведена нарисунке 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выпускаетсяIntegratedSystems(SantaClara,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

Средствасинхронизациии взаимодействия:семафоры, mutex,события, и тд.

1.6.Выводы к главе1

Основнымиотличиями ОСРВот ОС общегоназначенияявляются:

Ориентацияна обработкувнешних событий;
Детерминированноевремя реакциина внешнеесобытие;
Модульнаяорганизация;
Небольшойразмер системы.

Вглаве былирассмотреныважнейшиепараметры имеханизмы ОСРВ,такие как:

Времяреакции системы;
Времяпереключенияконтекста;
Видыдиспетчеризации;
Механизмысинхронизациии межзадачноговзаимодействия

КлассификацияОСРВ позволяетвыделить наиболееоптимальнуюструктурупостроенияОСРВ. Очевидно,что операционныесистемы с монолитнойархитектурой,вследствиеих направленностина конкретныепроцессорныеплатформы ихарактеравзаимодействияс ядром, врядли могут бытьиспользованы в качествеотносительноуниверсальныхОСРВ для системвысокой готовности.ОСРВ на основемикроядраобладает рядомпреимуществпо сравнениюс монолитнойархитектурой,а комбинацияс объектно-ориентированнымподходом, позволитсистеме статьаппаратно-независимойи обеспечитьбыструю реакциюна внешниесобытия.

Взаключениибыли перечисленыосновные свойстванекоторыхраспространенныхОСРВ. Ксожалению, ниодну из рассмотренныхоперационныхсистем нельзяназвать сетевойв широком смыслеэтого слова,так как уровеньсетевого обмена,заложенныйв многих из нихсоответствуетуровню локальнойсети. Многопроцессорнаяподдержка,введенная вVxWorksориентированатолько на системыс общей памятью.Отсутствиемеханизмаотказоустойчивости,допускающегокак отказысоединений(зачатки этогоесть в QNX),так и отказыпроцессорныхэлементов,необходимогодля отказоустойчивыхспециализированныхвычислительныхсистем, нет нив одной из этихоперационныхсистем. Такимобразом, задачейразработчиковявляется добавлениетаких модулейсуществующимОСРВ, которыепозволили быобеспечитьотказоустойчивостьраспределенныхвычислительныхсистем.

2.Поддержкаотказоустойчивостивычислительныхсистем средствамиоперационныхсистем реальноговремени

Спецификаприменениянекоторыхсистем обусловливаетособые требования,предъявляемыек надежностиих функционирования.Отказ или сбойв их работе,повлекшие засобой неправильныерезультатывычислений(или полное ихотсутствие),могут привестик катастрофическимпоследствиям.Преимуществаиспользованияотказоустойчивыхвычислительныхсистем непосредственновытекают изнеобходимостипродолжительнойработы системыв условиях,когда техническоеобслуживание(ремонт, заменаи тд.) невозможны,труднореализуемыили сопряженыс большимиэкономическимизатратами.Поэтому ВС испециализированныеоперационныесистемы разрабатываютсятаким образом,чтобы системабыла толерантна(терпима) квозникающимотказам. Особенноэто актуальнодля автономныхЛА (например,космическихаппаратов).

Сложностьсовременныхвычислительныхсредств такова,что практическиневозможнопроверитьготовые изделияпри всех предполагаемыхусловиях ирежимах ихработы. Поэтомув вычислительныхсистемах могутбыть скрытые– не проявившиесяпри проверке– ошибки программногообеспеченияи (или) неисправностиаппаратуры,но благодаряотказоустойчивостисбой, отказотдельногоэлемента какправило неприводят кискажениювыходных данных.

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

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

Прирассмотрениинадёжностивычислительнойсистемы следуетиметь ввиду,что она определяетсянадёжностьюаппаратнойчасти и надёжностьюпрограммногообеспечения.Однако, понятиенадёжностипрограммногообеспечениянеконструктивно,это означает,что на этапетестированияпрограммы небыли выявленывсе ошибки. Вданной работесчитается, чтопрограмма несодержит ошибок,и получениерезультата,отличных отожидаемогозависит отсбоев или отказоваппаратнойчасти или иныхфакторов (например,влияние ЭМИна содержаниеоперативнойпамяти), а потомувопрос о надёжностипрограммногообеспеченияне ставится.Таким образом,надёжностьвычислительнойсистемы определяетсянадёжностьюаппаратурыи влияниемотказов в нейна отказы ввычислительнойсистеме в целом.

Предварительныеисследованияпоказали, чтодля элементнойбазы среднегокачества (надежность0.999 - “три девяткипосле запятой”)при оптимальномсочетаниискорости получениярезультатана его надежностьв вычислительнойсреде теоретическидостижимадостоверностьполученияправильныхрезультатовмашинного счетав “двести девятокпосле запятой”при замедлениитемпа их полученияв 300-400 раз [1], чтоэквивалентноувеличениюнадежностидо 200 порядковвеличины привведении сравнительнонебольшойвычислительнойизбыточности,приводящейк потере производительностине более чемна 2-3 порядка,что уже насовременномуровне можеткомпенсироватьсяподбором компьютеровтребуемойпроизводительности.

ПонятиеотказоустойчивостиВС.

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

Отказомназываетсясобытие, заключающеесяв нарушенииработоспособностикомпонентасистемы. Последствияотказа могутбыть различными.Отказ системыможет бытьвызван отказом(невернымсрабатыванием)каких-то еекомпонентов(процессор,память, устройстваввода/вывода,линии связи,или программноеобеспечение).Отказ компонентаможет бытьвызван ошибкамипри конструировании,при производствеили программировании.Он может бытьтакже вызванфизическимповреждением,изнашиваниемоборудования,некорректнымивходными данными,и многими другимипричинами.

Отказымогут бытьслучайными,периодическимиили постоянными.Случайныеотказы (сбои)при повторенииоперации исчезают.Причиной такогосбоя можетслужить, например,электромагнитнаяпомеха. Другойпример - редкаяситуация впоследовательностиобращений коперационнойсистеме отразных задач.Периодическиеотказы повторяютсячасто в течениекакого-то времени,а затем могутдолго не происходить.Примеры - плохойконтакт, некорректнаяработа ОС послеобработкиаварийногозавершениязадачи. Постоянные(устойчивые)отказы непрекращаютсядо устраненияих причины -разрушениядиска, выходаиз строя микросхемыили ошибки впрограмме.

2.2.Причины иклассификацияотказов и сбоев

Отказыпо характерусвоего проявленияподразделяютсяна византийские(система активнаи может проявлятьсебя по-разному,даже злонамеренно)и пропажа признаковжизни (частичнаяили полная).Первые распознатьгораздо сложнее,чем вторые.

Аппаратнаяреализацияузлов(процессорныхмодулей)позволяетвыделить основныеклассы отказоваппаратуры:

-отказ процессора(центральнойчасти ПЭ);

-отказ линка- связи междуПЭ;

Идентификация отказа процессора какого-либо узла сетиклассифицируется,как отказ всегоузла: он изолируетсяот остальнойсети на логическомуровне и приналичии соответствующейподдержкиотключаетсяна аппаратномуровне (выключаетсяпитание).

Идентификацияотказа линка(связи) приводитлишь к уменьшениюстепени связностиузлов сети.Отказавшийлинк изолируетсяна логическомуровне путемизменениямаршрутовпередачи сообщениймежду узламисети.

Отказпри исполнениифункциональногопрограммногообеспеченияможет проявитьсявследствие:

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

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

Основнаяособенность(и достоинство)сетевой отказоустойчивойтехнологии- отсутствиекакого-либо(даже самогонезначительного)единственногокомпонента(ресурса), выходиз строя которогоприводит кфатальномуотказу всейсистемы. Такаясистема неможет содержатькакого-либо"центрального"(главного) узла,размещенногов одном изпроцессорныхэлементовсистемы, онаможет состоятьтолько из"равноправных"частей, размещенныхв каждом узлесети. Такимобразом можноговорить лишьо деградациикачества системыпри отказеодного илиболее ее элементов.В такой системеполный отказнаступает послевыхода из строятолько определенногоколичестваресурсов,определенногона этапе проектирования.

Методыи средстваобеспеченияотказоустойчивости

Дляобеспечениянадежногорешения задачв условияхотказов системыприменяютсядва принципиальноразличающихсяподхода - восстановлениерешения послеотказа системы(или ее компонента)и предотвращениеотказа системы(отказоустойчивость).

Восстановлениеможет бытьпрямым (безвозврата кпрошлому состоянию)и возвратное.

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

Привозвратномвосстановлениипроисходитвозврат процесса(или системы)из некорректногосостояния внекоторое изпредшествующихкорректныхсостояний. Приэтом возникаютследующиепроблемы:

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

Длявосстановлениясостояния втрадиционныхЭВМ применяютсядва метода (иих комбинация),основанныена промежуточнойфиксации состояниялибо ведениижурнала выполняемыхопераций. Ониразличаютсяобъемом запоминаемойинформациейи временем,требуемым длявосстановления.

Применениеподобных методовв распределенныхсистемахнаталкиваетсяна следующиетрудности:

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

методывосстановленияпосле отказовдля некоторыхсистем непригодны из-за прерываниянормальногофункционированияи др;

Чтобыизбежать этинеприятности,создают системы,устойчивыек отказам. Такиесистемы либомаскируютотказы, либоведут себя вслучае отказазаранее определеннымобразом.

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

Обеспечениеживучести –это использованиеспециальныхсредств, позволяющихсистеме продолжатьправильноефункционированиепри возникновенииотказов еепрограммныхи аппаратныхкомпонентовс возможностьюдеградациикачествафункционирования[2]. В отличие ототказоустойчивости,где с отказомне связанокачество работыВС, сравнительносложные средстваобеспеченияживучестипозволяют болеерациональнорасходоватьвычислительныересурсы и увеличиватьсреднее времянаработки донаступленияфатальногоотказа. Обеспечениеживучестиобычно включаеттри основныефункции: диагностикавозникновенияотказа, локализациянеисправностии перестройкасистемы. В основетолерантностилежит избыточностькак аппаратного,так и программногообеспечения.Поэтому многопроцессорныесистемы с присущейим аппаратнойизбыточностьюпотенциальнопозволяютсоздавать нетолько высокопроизводительные,но и высоконадежныесистемы.

Другимосновополагающимтребованиемявляется наличиемеханизма,позволяющегоагентам в каждомустройствеобмениватьсятопологическойинформациейсо своими соседямипосредствомэффективныхпротоколов,не перегружающихсеть широковещательнымуправляющимтрафиком. Каждыйуправляющийагент долженподдерживатьтаблицу с локальнойтопологическойинформацией.Кроме того,должен предоставлятьсямеханизм, практическив реальномвремени модифицирующийсодержимоебазы данныхи обеспечивающийправильноеотображениетопологическихизменений,вызванныхустановкойновых устройствлибо реконфигурациейили отказомсуществующихузлов сети.

Дляобеспечениязащиты вычислительногопроцесса программнымиметодами используетсяпрограммная,информационнаяи временнаяизбыточности.

Подвременнойизбыточностьюпонимаетсяиспользованиечасти производительностидля получениядиагностическойинформациио состояниисистемы. Программнаяизбыточностьиспользуетсядля контроляи обеспечениядостоверностиважных решенийпо управлениюи обработкеинформации.Она заключаетсяв применениинесколькихвариантовпрограмм вкаждом узлесистемы (такназываемоеN-версионноепрограммирование).

Сопоставлениерезультатовнезависимыхрешений одногои того же фрагментазадачи называютэлементарнойпроверкой, асовокупностьвсех проверокобразует системуголосования,которое являетсяосновным источникомдиагностическойинформациио состоянииаппаратнойчасти системыи вычислительногопроцесса вкаждом активномузле системы.Два механизмашироко используютсяпри обеспеченииотказоустойчивости- протоколыголосованияи протоколыпринятияколлективногорешения.

Протоколыголосованияслужат длямаскированияотказов (выбираетсяправильныйрезультат,полученныйвсеми исправнымиисполнителями).

Протоколыпринятияколлективногорешения подразделяютсяна два класса.Во-первых, протоколыпринятия единогорешения,в которых всеисполнителиявляются исправнымии должны либовсе принять,либо все непринять заранеепредусмотренноерешение. Примерамитакого решенияявляются решениео завершенииитерационногоцикла при достижениивсеми необходимойточности, решениео реакции наотказ. Во-вторых,протоколыпринятиясогласованныхрешенийна основе полученныхдруг от другаданных. Приэтом необходимовсем исправнымисполнителямполучить достоверныеданные от остальныхисправныхисполнителей,а данные отнеисправныхисполнителейпроигнорировать

Однакодля систем напоследнейстадии их деградации(при отказепредпоследнегоузла сети) напервый план в качестве диагностической информации выходят признакиисправности-неисправности, формируемые различными программно-аппаратнымисредствамиконтроля, такимикак:

функциональныйконтроль вычисленийс помощьюспециальныхконтрольныхоператорови несколькихверсий программ;
функциональныйконтроль входнойи выходнойинформации;
контрольвходной информациипо специальнымпризнакам иконтрольнымсуммам;
контрольвыходной информациипо квитанцииот приемника- абонентасистемногоинтерфейса;
контрольныйтест аппаратурыпроцессора;
контрольныетесты аппаратурывнешнего ивнутреннегоинтерфейсов.
встроенныеаппаратныесредства контроляпроцессорныхэлементов иконтроллеровсистемногоинтерфейса.

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

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

Концепцияпостроенияи работы системыс рангом

отказоустойчивости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» в случае,если этотпроцессорныйэлемент несвязан с ПЭ,задаваемомстолбцом, иномер каналасвязи (линка)по которомуосуществляетсяэта связностьв противномслучае, причемнумерациюлинков дляудобства можноначинать cm+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. Модуль маршрутизации

Вовремя инициализации,для каждогоПЭ составляетсясписок текущихсоседних узловсистемы дляобмена результатамисчета так, чтобыданные каждогоПЭ присутствовалив тройном экземплярев ВС.

Таблицырассылки, вкоторой каждомуПЭ сопоставленномер каналасвязи, по которомунадо передатьпакет дальше,формируютсяметодом волнына основе таблицсвязности ПЭ.Маршрут выбираетсяминимальнымпо количествурёбер графасети, с учетомзагрузки связей.Так как операционныесистемы узловидентичны, топакеты, проходящиечерез их связиможно считатьодинаковыми.Загрузка связиопределяетсяпо числу возможныхтранзитныхпередач черезэту связь, итранзитныепередачи равномернораспределяютсяпо узлам сетибез потерь надлине маршрута.

Алгоритмопределениястатическихмаршрутов изаполнениятаблицы рассылки:

Заполняемтаблицу рассылкив соотвествиесо строкой сномером, равнымномеру процессорногоэлемента. Заполняемсоответствующуютаблицу расстоянийединицами(счетчик длинымаршрута) втех ячейках,где есть прямаясвязь втаблице связности(>0).
Еслиобработанывсе ПЭ, закончить.
Увеличиваемсчетчик длинымаршрута на1 единицу (передачу).
Потаблице рассылкинаходим очереднойПЭ, не имеющийсвязи с локальным.Если такихбольше нет,шаг 8.
Средиимеющих связьПЭ ищем по таблицерасстоянийтого, у кторогомаршрут былопределен напредыдущемцикле. Еслитаких большенет, шаг 7.
Еслион имеет связьс нужным ПЭ,запоминаемномер линкадля связи егос локальнымПЭ и загрузкулинка. Шаг 5.
Сортируемнайденныелинки по наменьшейзагруженностии заносим егов таблицу рассылкии таблицурасстояний.

Еслиобработанывсе ПЭ, закончить,иначе шаг 3.

2.4.3.Модуль реконфигурации

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

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

Отказканала связи.Первоначальнокорректируетсяматрица связностиПЭ. При этомопределяется,имеет ли отказавшийканал связиотношение кданному процессорномуэлементу. Вслучае, еслипосле отказаканала связи,какой-либопроцессороказываетсяизолированным,выполняетсяотключениепроцессорногоэлемента.

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

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

Рис.2.3. Модульреконфигурации

Послеотказа функциональногоэлемента, процессреконфигурацииосуществляетсяпо следующейсхеме:

Втаблице связностиотказавшийлинк или линкиотказавшегоПЭ помечаютсякак недоступные.
Проверяется,не осталисьли изолированнымиоставшиесяузлы, если да,то они отключаются.
Потаблице связностиопределяетсяновый списоксоседних узловсистемы, определяетсяПЭ, которого(которых) необходимовывести изрезерва.
ПроизводитсяактивизациярезервногоПЭ путем передачиему кода активизации,текущей таблицысвязности иконтекстазадачи от старшегоПЭ в ВС (например,от ПЭ с младшимномером).

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. Организацияотказоустойчивыхвычислений

Вданном разделепримем во вниманиевведенное ранеепредположениеоб ординарностипотока отказов,то есть на протяженииодного цикла(такта) работысистемы множественныеотказы не возникают.

Отметим,что реакциясистем диагностированияотказов такова:

Несовпадениеданных приэлементарнойпроверке (сравнении)результатовсчета на очередномцикле диагностируется,как отказ ПЭили каналасвязи этогоПЭ.
Принесовпаденииданных приэлементарнойпроверке результатовсчета, полученныхс использованиемтранзитнойпередачи, подсомнение ставитсявся цепочка,задействованнаяпри передаче.
Принесовпадениини одного результатасчета под сомнениеставится всеучаствовавшиев обмене ПЭ исвязи.
Несовпадениеконтрольнойсуммы или тайм-аутпри приемеданных трактуетсякак сбой ПЭили каналасвязи ПЭ.
Отсутствиеквитанциитрактуетсякак сбой ПЭили каналасвязи ПЭ.
Неверныйкод квитанциитрактуетсякак сбой каналасвязи ПЭ.

Напомним,что идея организацииотказоустойчивыхвычисленийоснована наиспользованиитрех типовизбыточности:аппаратной,программнойи информационной.Т.е. заданнаязадача реализуетсяна более чемтрех процессорныхэлементах сети.Рабочая конфигурациясети состоитиз трех ПЭ,результатысчета копиязадачи отсылаетв пределахрабочей конфигурации.На основаниирезультатовголосованияформируетсяинформацияо ходе вычислительногопроцесса и осостоянииаппаратуры(исправна -неисправна)ВС. Этой информациидостаточно(как правилос большейизбыточностью)для принятиярешения о перестройке(реконфигурации)сети при возникновенииотказов аппаратурыВС.

Всекопии функциональнойзадачи решаютсяс одинаковыминаборами входныхпараметрови поэтому (приотсутствиинеисправностей)формируютодинаковыерезультаты(голосованиепо совпадениюкодов). Проблемыввода и выводавнешней поотношению кВС информациине рассматриваются,при этом предполагается,что достовернаявнешняя информацияпоступает всоответствующиеузлы сети навходы копийзадачи - приемниковвходной информации.

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-> ПЭ2 и ПЭ3;
ПЭ2-> ПЭ3 и ПЭ4;
ПЭ3-> ПЭ4 и ПЭ5;
ПЭ4-> ПЭ5 и ПЭ1;
ПЭ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-> ПЭ2 и ПЭ3;
ПЭ2-> ПЭ3 и ПЭ5;
ПЭ3-> ПЭ5 и ПЭ1;
ПЭ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 возможныхпричин неисправности,показывает:

Результатыголосованияот ПЭ2 подтверждаютработоспособностьПЭ1, ПЭ5, каналов2-1 и 2-5.
Результатыголосованияот ПЭ5 подтверждаютработоспособностьПЭ3, ПЭ2, каналов3-5 и 2-5.
ДанныеПЭ5 от ПЭ3 говорято исправностиканала связи3-5.

Такимобразом ПЭ1,ПЭ2и ПЭ5 делаютвывод о неисправностиканала 2-3, маскируянеисправностипо данным отПЭ1.

АнализПЭ3 возможныхпричин неисправности,показывает:

Результатыголосованияот ПЭ5 подтверждаютработоспособностьПЭ3, ПЭ2, каналов3-5 и 2-5.
“Мусор”от ПЭ1 можетозначать, чтонеисправенПЭ1 или ПЭ2, иликанал 1-2, или канал2-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

Анализработоспособнымиузлами причинотказа показывает:

Приполном отказеПЭ5:

АнализПЭ1 и ПЭ2: “мусор”от ПЭ3 и ПЭ5 говорито неисправностиПЭ5 или канала1-5, а данные ПЭ2однозначноговорят оботказе ПЭ5.
АнализПЭ3: “мусор”от ПЭ2, ПЭ3 и ПЭ5говорит онеисправностиПЭ5 или канала3-5. В данном случаеэто уже не важно,так как результатамиголосованияПЭ3 обменятьсяни с кем не сможет.В случае возникновениятакой ситуацииПЭ анализирует– сколько узловостается всистеме, кроменего самого.Если большедвух, то онсамостоятельнопрекращаетвыдачу данных.

Приотказе ПЭ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.
Принесовпаденииданных приэлементарнойпроверке результатовсчета, полученныхс использованиемтранзитнойпередачи, подсомнение ставитсявся цепочка,задействованнаяпри передаче.
Принесовпадениини одного результатасчета под сомнениеставится всеучаствовавшиев обмене ПЭ исвязи.
Несовпадениеконтрольнойсуммы или тайм-аутпри приемеданных трактуетсякак сбой ПЭили каналасвязи ПЭ.
Отсутствиеквитанциитрактуетсякак сбой ПЭили каналасвязи ПЭ.
Неверныйкод квитанциитрактуетсякак сбой каналасвязи ПЭ.

Дляпринятия решенияоб отказе (сбое)того или иногоэлемента ВС(ПЭ, канала связи)по набору выводовот каждого узласети, был предложенследующийэвристическийалгоритм, привыполненииусловия обординарностипотока отказов:

Создаетсяматрица состоянияВС, котораяразмерностьюидентичнамодифицированнойматрице связностиПЭ, но по главнойдиагоналинаходятсяданные о ПЭ, ав ячейках матрицы– о каналахсвязи.
Матрицасостояния ВСинициализируетсяединицами.
Послеобмена предварительнымирезультатамиголосования,у каждого ПЭоказываетсярезультатыголосованияот всех ПЭ ВСи диагностическаяинформацияот модулякоммуникации.
Последовательно,в соответствиис логикой,изложеннойвыше, делаетсявывод по каждойзаписи, и очередноепредположениезаносится вматрицу состоянияВС путем вычитанияединицы изячейки, соответствующейэлементу ВС,не в пользукоторого делаетсяэто предположение.
Есливыводом поочереднойзаписи становитсяотсутствиеотказов поопределеннымэлементам, тоэто предположениезаносится вматрицу состоянияВС путем инкрементированияячейки, соответствующейэлементу ВС,в пользу которогоделается этопредположение.
Послеобработки всехзаписей, матрицасостояний ВСпросматриваетсяна предметпоиска минимальногоотрицательногозначения.
Еслитакое значениеесть, то соответствующийэлемент признаетсяотказавшим,иначе принимаетсярешение оботсутствииоказов.

Данныйалгоритм создантак, что в матрицесостояний послеего завершения,не окажетсябольше двухминимальныхотрицательныхзначений, причемэти значенияне будут принадлежатьодинаковымфункциональнымэлементам (тоесть одновременно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” событий(отказов);

l- параметр потока,интенсивностьпотока отказов;

T₀– математическоеожидание длиныинтервала междусоседнимисобытиями –среднее времянаработки наотказ;

P₀(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₀^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₀^N(m)к T₀^y:

ипоказывает,во сколько разпо сравнениюс T₀^y– средним временемнаработки наотказ одногоузла, изменилосьсреднее времянаработки наотказ системыОС-N(m) в целом.

Используяформулы (6а) и(8а) можно производитьоценку надежностныххарактеристикотказоустойчивыхсистем типаN(N-1).Примем среднеевремя наработкина отказ узла

=10⁵часов. В таблице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∙10^-5	6,4∙10^-14	2,56∙10^-18	1,0∙10^-22	4,1∙10^-27	1,6∙10^-31	6,5∙10^-36	2,62∙10^-40	1,05∙10^-44
2		24часа	2.4∙10^-4	1,38∙10^-11	3,31∙10^-15	8,0∙10^-19	1,9∙10^-22	4,6∙10^-26	1,1∙10^-29	2,64∙10^-33	6,3∙10^-37
3		1год=	0.084	5,91∙10^-4	4,96∙10^-5	4,2∙10^-6	3,5∙10^-7	2,9∙10^-8	2,46∙10^-9	2∙10^-10	1,7∙10^-11
		8766час
4		5лет=	0.355	0,047	1,586∙10^-2	5,6∙10^-3	2∙10^-3	7,1∙10^-4	2,5∙10^-4	8,9∙10^-5	3,16∙10^-5
		43830час
5		10лет=	0.584	0,2	0,116	0,068	0,04	0,023	0,0135	7,9∙10^-3	4,6∙10^-3
		87660час
6		11,4г.=	0.632	0,252	0,16	0,1	0,064	0,04	0,025	0,016	0,01
		10⁵час
7		15лет=	0.73	0,391	0,286	0,21	0,153	0,11	0,082	0,06	0,044
		131490час
8	K_N(_N_-1)		1	1,83	2,08	2,28	2,45	2,59	2,72	2,82	2,92

Дляупрощенияанализа таблицыпостроим дваграфика, отражающихувеличениенадежностисистемы снаращиваниемаппаратнойчасти (рис. 2.10 ирис. 2.11).

Рис.2.10. Коэффициентнадежности.

Рис2.11. Вероятностьотказа ВС типаN(N-1)за 10 лет.

Анализкривых показывает,что среднеевремя безотказнойработы увеличиваетсяв 2-3 раза по сравнениюсо среднимвременем безотказнойработы одногоПЭ при наращиваниивычислительныхресурсов в 5-7раз и далеестабилизируетсяи возрастаетнезначительно.Вероятностьотказа системс рангом отказоустойчивостиN(N-1)резко уменьшаетсяпри рассмотренииВС типа 5(4) – 7(6) идалее ее снижениенезначительно.

Такимобразом, припостроенииотказоустойчивыхвычислительныхсистем рекомендуетсявыбирать системыс характеристиками5(4) – 7(6), с учетомограничениямассы, энергопотребленияи др. характеристик.

2.7.Выводы к главе2

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

Дляобеспечениянадежногорешения задачв условияхотказов применяютсядва подхода– восстановлениеи предотвращениеотказа системы(отказоустойчивость).При созданииспециализированнойОСРВ, предпочтениеотдано второмуподходу, посколькувосстановлениев ряде случаевможет бытьсвязано созначительнымизатратамипроцессорноговремени и (или)прерываниемвычислительногопроцесса. Всвязи с этимрассмотренымеханизмыобеспеченияотказоустойчивости,основными изкоторых являютсяпротоколыголосованияи принятияколлективногорешения.

Введенопонятие рангаотказоустойчивости,описана структураОСРВ и концепцияработы системыс рангом отказоустойчивостиN(N-1).Дано описаниесистемныхтаблиц, структурыи взаимодействиямодулей ОСРВтаких какмаршрутиатор,реконфигуратор,модуль коммункации, голосованияи анализа отказов.

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

Взаключениипроизведенаоценка надежностныххарактеристикВС с рангомотказоустйчивостиN(N-1)и рассчитаныхарактеристикисистем 1(0) – 10(9). Анализхарактеристиквыявил значительнеувеличениевремени безотказнойработы системыс увеличениемчисла ПЭ и уменьшениевероятностиотказа всейсистемы. Например,вроятностьотказа системы5(4) за 10 лет с временембезотказнойработы одногоПЭ 10000 часов составила0,068, что меньшевероятностиотказа одногоПЭ за тот жепериод в 8,5 раз.Исходя из этихрезультатовбыли сделанырекомендациипо выбору типаВС при ее проектировании.

3.Программноеобеспечениемодели отказоустойчивойВС

Основнымизадачами приразработкепрограммноймодели отказоустойчивойВС, функционирующейпод управлениемраспределеннойОСРВ, сталиследующие:

Реализоватьаппаратно-независимыемодули обеспеченияотказоустойчивостиОСРВ.
МоделироватьВС любой топологии(3-10 ПЭ).
Возможностьобеспечитьлогику проверкимодулей ОСРВс помощью командоператора.
Обеспечитьработу моделив условиях«мягкого»реальноговремени.

Такимобразом, программноеобеспечениебыло разбитона две части:

ПОузла ВС Proc.
ПОподсистемыпроверки Host.

3.1 Программноеобеспечениемодели узлаВС

Структурапрограммногообеспечениямодели узлаВС представленана рис 3.1. В общемвиде функционированиеПО узла ВСосуществляетсяпо графу управления(циклограмме),представленнойна рис. 6.3 технологическойчасти, а логикаработы подробноописана в главе2.

Дляреализациимодели былавыбрана ОСWindows98/2000, так как наданном этапене ставиласьзадача тестированияПО ВС в условияхжесткого реальноговремени, асемантическимеханизмыобеспечениямногопроцессности,синхронизации,ввода-выводапрактическиидентичнымеханизмамбольшинстваОСРВ.

Рис.3.1. Взаимодействиемодулей узлаВС

ПОузла ВС разбитона модули, структуракоторых представленав таблице 3.1.Описание функций,реализующихданные модули,представленов таблицах 3.2,3.3, 3.4, 3.5.

Таблица3.1

Описаниесоставляющихмодулей текстовогоредактора

Модуль	Описание
Main.cpp	Центральныймодуль. Запускинициализациисистемы. Запускмаршрутизатора.Запуск модуляэмуляции каналовсвязи. ЗапускФЗ.
Router.cpp	Функциимаршрутизатора
Commun.cpp	Функциимодуля коммуникации
Vote.cpp	Функцииголосованияи анализатораотказов.
task.cpp	Функциональнаязадача.

Таблица3.2

Функции,реализующиемаршрутизатор

Имя	Описание
voidrouter()	Формированиетаблиц рассылкиметодом волны
voidGetRoute(intCpuNum)	Поисквсех кратчайшихпо числу транзитныхпередач путейв графе ВС доузла CpuNum.

Таблица3.3

Функции,реализующиемодуль коммуникации

Имя	Описание
intInitLinkEmul(const char IniFile)*	Инициализациямодуля эмуляцииканалов связипо файлу инициализацииIniFile,выделениебуферов приемаинформациидля каждогоканала, созданиеи соединениеканалов связи(неименованныеканалы илисокеты). Возвращает0 в случае успеха,-1 – в случаеошибки в файлеIniFile.
voidFinishLinkEmul (void)	Завершениеработы модуляэмуляции каналовсвязи.
staticSOCKET ConnectServerSocket (const char ServName, int Port)*	Созданиеклиентскогосокета номеромPort и соединениеего с сервером.
staticSOCKET CreateServerSocket (SOCKET PrimSock, int Port)*	Созданиесерверногосокета номеромPort и ожиданиесоединенияс клиентом.
staticint CreatePipeServer (int Port, HANDLE pipeRead, HANDLEpipeWrite)	Созданиесерверногонеименованногоканала с номеромPort. По указателямpipeRead и pipeWriteвозвращаютсяфайловыедескрипторына чтение изапись.
staticint CreatePipeClient (int Port, HANDLE pipeRead, HANDLEpipeWrite)	Созданиеклиентскогонеименованногоканала с номеромPort. По указателямpipeRead и pipeWriteвозвращаютсяфайловыедескрипторына чтение изапись.
intLinkOut (int Link, void Addr, int Length)*	Посылкаданных позаданномуканалу связиLink,начинаяс адреса Addr,Length байтс приемомквитанции отадресата.
intLinkIn (int Link,void Addr, int Length)*	Приемданных позаданномуканалу связиLink,вбуфер начинаяс адреса Addr,Length байтс контролемцелостностипакета и отправкойквитанции.
intReceive (int Chan, int From, void DataAddr, int DataLength)*	Выборкаданных изканальногобуфера Chan,пришедших отПЭ From, начинаяс адреса Addr,Length байт.
intSend (int Chan, void DataAddr, int DataLength)*	Посылкаданных по каналуChan, начиная садреса DataAddr, длинойDataLength байт.
staticDWORD WINAPI LinkThreadFunc (LPVOIDlpvThreadParm)	Задачапрослушиванияканала связиlpvThreadParm в фоновомрежиме, расшифровказаголовкапакета, приеминформационныхчастей посылки,запись в канальныйбуфер, выдачасигнала о приходеданных.

Таблица3.4

Функции,реализующиемодуль голосованияи анализатораотказов

Имя	Описание
voidInitializeVoteBuffers()	Переинициализациябуферов голосования
voidRestoreCpuFault()	Сбросинформациио накопленныхотказах ПЭ
voidRestoreLinkFault()	Сбросинформациио накопленныхотказах каналовсвязей
intcompare(struct BUFFER b1,struct BUFFER b2)	Провестиэлементарнуюпроверку(сравнение)буферов функциональнойинформации
intTrippleFault()	Определениесбоя одногои того же элементаВС на протяжениитрех циклов.
voidconsolidate()	Функцияанализа отказов,принятиеконсолидированногорешения, активизацииреконфигуратора.
voidVoteThread()	Задачаголосования,активизирующаясяпо заполнениюканальныхбуферов, активизирующаяобмен в сетирезультатамиголосованияи передающаяуправлениеанализаторуотказов.

Таблица3.5

Функции,реализующиереконфигуратор

Имя	Описание
staticint CheckCpuLinks (int Cpu)	ПроверкаизолированностиПЭ Cpu.
voidreconfig(struct SYSTEM* M)	Процедурареконфигурации,путем изменениясистемныхтаблиц поинформацииоб отказе.Активизациямаршрутизаторадля перестройкисистемныхтаблиц.

Таблица3.6

Функции,реализующиефункциональнуюзадачу

Имя

Описание

voidTaskLoop()

ФункцияисполненияФЗ (на данномэтапе ФЗ – наборпоследовательныхпростейшихоператоров)по информацииот объектауправления.Завершаетсяотсылкойрезультатовдля голосованиядругим ПЭ ипередачейуправлениязадачам прослушиванияи голосования.

Дополнительныефункции, обеспечивающиемоделированиеотказов в рамкахсвоего ПЭ,представленыв таблице 3.7.

Таблица3.7

Функции,реализующиемоделированиеотказа

Имя

Описание

voidKillCpu( int Cpu, int type )

type=1–фатальныйотказ ПЭ, приостановкавсех канальныхпотоков и ФЗ.

type=0–отказ ФЗ, внесениеискаженийпри вычисленииФЗ.

voidKillLink(intLink, int type )

Завершаетсоответствующийканальныйпоток, в случаефатальногоотказа (type=0),или дает указаниемодулю коммуникацииотсылать ошибочныепакеты (type=1).

Диспетчеризацияпроцессов вПЭ происходитна уровнеоперационнойсистемы, передачауправленияпроисходитс помощью такихмеханизмов,как семафорыи события. Вовремя ожиданияна прием управлениязадачи находятсяв спячке, почтине занимаяпроцессорноговремени. Процесспередачи управленияприведен нарис. 3.2. При этом:

Процесс1: Функциональнаязадача;

Процесс2: Прослушиваниеканала связис ОУ;

Процесс3: Процесс голосованияи анализа отказов;

Процесс4: Реконфигурация;

Процесс5: Отправкасогласованныхданных;

Процесс6 .. N+6:ПрослушиваниеNканалов связис ПЭ ВС;

Рис.3.2.Диспетчеризацияпроцессов.

Посколькуиспользуютсяфункции блокирующеговвода-выводабазовой ОС, вслучае отсутствияданных на входезадача прослушиванияканала связипомещаетсяв состояниеспячки, практическине занимая приэтом процессорноговремени, иактивизируетсятолько по приходуданных. Послеэтого загружаетсятело посылки.Далее определяетсяадресат, и еслипосылка предназначенадругому ПЭ, топосылка передаётсядальше по информацииот маршрутизатора,в противномслучае производитсяконтроль заголовка(ошибочныепосылки игнорируются).При наличииместа данныепопадают всоответствующийбуфер. При наличииданных во всехпредварительныхбуферах, производитсяголосованиеи запись результатаво входнойбуфер канала.

3.2 Программноеобеспечениеподсистемыпроверки

Данныймодуль призванобеспечитьследующиефункции:

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

Дляобеспеченияудобного интерфейса,приложениебыло сделанов виде диалоговогоокна с помощьюбиблиотекиклассов WindowsMFC (MicrosoftFoundation Classes).

Рис.3.3. Диалоговоеокно программыHost.

Функциональноеназначениеэлементовдиалоговогоокна представленов таблице 3.6.

Таблица3.6

Назначениеи функции элементовдиалога

Элемент	Описание
Панель«Отказ линка»	Содержиттри связанныхэлемента: Переключатели(RadioGroup)задания видаотказа линка,при этом «Фатальныйотказ» означаетполное прекращениепередачиинформации,а «Некорректнаяпередача» -искажениепередаваемыхпакетов. Поля«ПЭ» и «Линк»задают номерПЭ и номер каналасвязи длямоделированияотказа. Кнопка«Задать»активизируетпередачууправляющейинформациизаданномуПЭ.
Панель«Отказ ПЭ»	Содержитдва связанныхэлемента: Переключателизадания видаотказа ПЭ, приэтом «Фатальныйотказ» означаетполное прекращениефункционирования(напримерзависание),а «Отказ ФЗ»- неправильныйрасчет ФЗ, ссохранениемфункций обменаи голосования. Поле«ПЭ» задаетномер ПЭ длямоделированияотказа. Кнопка«Задать»активизируетпередачууправляющейинформациизаданномуПЭ.
Полевывода (RichEdit)«Топология»	Обеспечиваетотображениетекущей топологическойинформациив виде модифицированнойматрицы связности(текстовыйвид), обновляющейсяна каждом тактеработы ВС.
Полевывода «Процесс»	Обеспечиваетвывод в текстовомили графическомвиде согласованныхрезультатовсчета ФЗ.
Кнопка«ПУСК»	Понажатию обеспечиваетсозданиеконфигурационныхфайлов длякаждого ПЭ,запуск процессов,моделирующихВС, связываниеканалов связис каждым ПЭи вывод из спячкиканальныхпотоков прослушивания.
Кнопка«Выход»	Обеспечиваетосвобождениепамяти, уничтоженияпотоков исполнения,завершениепрограммы.

Длякаждой кнопкидиалоговогоокна существуетсвой обработчик,выполняющийвышеописанныефункции. Помимоэтого функцияInitInstance(), инициализирующаяработу диалога,выполняетанализ топологииВС, создаетприостановленныепотоки прослушиванияканалов длясвязи с каждымПЭ, аналогичныеописанным втаблице 3.3. Модулькоммуникациивыполнен также, как и модулькоммуникацииПЭ ВС.

Приработе с интерфейсомзадания отказа,канальныепотоки прослушиванияприостанавливаются,и возобновляютсяпосле отсылкиинформацииВС. На каждомцикле модулькоммуникацииобеспечиваетприем текущейтопологии ВС,согласованныерезультатысчета ФЗ и передаетих на отображениев соответствующиеполя вывода.

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

4.ПортированиеОСРВ на платформуTMS320C30

Подпортированием(от англ. porting)понимаетсяизменениепрограммногообеспечениядля функционированияв услвиях разныхархитектурпроцессорныхэлементов.

4.1Основныехарактиристикии область примененияпроцессораTMS320C30

Унивеpсальностьи pабота в pеальноммасштабе вpеменипpоцессоpовсемействаTMS320 позволяютиспользоватьих в шиpокомкpуге pазpаботок,таких как:

ЦОСОБЩЕГО НАЗНАЧЕНИЯ:

цифpоваяфильтpация;
свертка;
коppеляция;
пpеобpазованиеГильбеpта;
быстpоепpеобpазованиеФуpье;
адаптивнаяфильтpация идр.

ИНСТРУМЕНТАЛЬНЫЕСРЕДСТВА :

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

ВОЕННАЯТЕХНИКА, управляющиесистемы и др.

секpетнаясвязь;
обpаботкасигналов pадаpа;
навигация;
упpавлениеpакетами;
автоматическиесистемы;
бортовыесистемы и др.

Поддеpжкаязыков высокогоуpовня легкоpеализуетсяблагодаpяиспользованиюоснованнойна pегистpахаpхитектуpы,большому адpесномупpостpанству,мощной системеадpесации, гибкомунабоpу команди поддеpжкеаpифметики сплавающейточкой.

Нижепеpечисленыосновные параметрыTMS320C30:

60нс вpемя выполненияоднотактнойкоманды

33.3MFLOPS (миллион операцийс плавающейточкой в секунду)
16.7MIPS (миллион инструкцийв секунду)

БлокПЗУ 4К х 32 двойногодоступа безтакта ожидания
Дваблока ОЗУ 1К х32 двойного доступабез такта ожидания
Кэш-памятькоманд 64 х 32
32-pазpядныеслова данныхи команд, 24-pазpядныйадpес
40/32-битплавающаяточка/целыечисла умножительи АЛУ
32-pазpядныйкольцевойсдвиговыйpегистp
Восемьpегистpов pасшиpеннойточности(аккумулятоpы)
Дваадpесных генеpатоpас восемьювспомогательнымиpегистpами идва аpифметическихблока вспомогательныхpегистpов
Внутpикpистальныйконтpоллеp пpямогодоступа в память(DMA) для независимыхопеpаций ввода/выводаи центpальногопpоцессоpногоблока
Целочисленные,с плавающейточкой и логическиеопеpации
Двух-и тpехопеpандныекоманды
Паpаллельнаяpабота АЛУ иумножителяв одном такте
Возможностьповтоpенияблоков команд
Циклыс нулевыминепроизводительнымииздержкамии пеpеходы заодин цикл
Условныепереходы ивозвраты
Командыдля поддеpжкимультипpоцессоpнойpаботы
Двапоследовательныхпорта для обмена8/16/32 - pазpяднымисообщениями
Два32-pазpядных таймера
Двавнешних флагаобщего назначения,четыре внешнихпрерывания

4.2Обзор базовыхОСРВ для платформыTMS320C30

Дляпостроенияотказоустойчивойсистемы реальноговремени на базепроцессораTMS320C30необходимыбазовые механизмыи средства,которые былиперечисленыв главе 1. В настоящеевремя существуетдостаточномного базовыхОСРВ для процессоровсерии TMS320.Качественноони мало чемотличаютсядруг от друга,различия могутвозникать из-заспецификипримененияэтих ОСРВ. Приведемхарактеристикиодной из самыхизвестных ОСРВ,переносимыхна TMS320C30.

Операционнаясистема SPOX.

SPOXподдерживаетнесколькоразличныхвариантовархитектур:

дополнительныевычислительныесреды для рабочихстанций;
однородныевстраиваемыесистемы;
неоднородныевстраиваемыесистемы;
персональныекомпьютерыс процессоромIntelPentiumпод управлениемMicrosoftWindows95.

СредаSPOXсостоит изчетырех основныхкомпонентов(рис. 4.1):

ядроSPOX(SPOX-KNL)обеспечиваетвытесняющуюприоритетнуюмногозадачность,высокоскоростнуюобработкупрерываний,распределениепамяти, различныемеханизмымежзадачногообмена информациейи синхронизации,а также независимыйот устройствввод-вывод.РезультатамитестированияSPOX-KNLстали следующиецифры:

Времязахвата семафора– 7.9 мкс;
Времяпереключениязадач одинаковогоприоритета– 15 мкс;
Времяреакции напрерывание– 33 мкс;
Времязавершенияпрерывания– 1.4 мкс;
Задержкадиспетчеризации(время вытеснениязадачи с большимприоритетомзадачу с меньшим)– 12.24 мкс;
Времяпереключенияконтекста –7 мкс;
Минимальныйразмер системы1532 слова.

модульSPOX-LINKподдерживает«прозрачное»взаимодействиемежду целевойплатформойи хост-системойи дающее доступк основнымресурсамхост-машины,таким как консоли,файловые системыи сети;
библиотека(SPOX-MATH)содержит свыше175 математическихфункций;
высокоуровневыйотладчик SPOX-DBUG.

Рис.4.1. Структурнаясхема ОС SPOX

Всечетыре подсистемыреализованыкак библиотекиC-вызываемыхперемещаемыхмодулей. Приэтом системныефункции SPOXподключаютсяк объектномукоду приложенияна этапе связывания.

Спомощью дополнительногомодуля SPOX-MPстановитсявозможноймногопроцессорнаяобработкасигналов. Настройкана конкретнуюконфигурациюсети процессорныхэлементовзадается вконфигурационномфайле, что позволяетне привязыватьсяк конкретнойтопологии впроцессе разработкиприложения.SPOX-MPобеспечиваетдинамическуюпередачу данныхи сообщенийпо сети процессорныхэлементов,глобальноепространствоимен, а такжелавинообразнуюпервоначальнуюзагрузку сети.

Такимобразом ОСРВSPOXимеет необходимыемеханизмы длясозданияотказоустойчивойраспределеннойоперационнойсистемы реальноговремени, концепцияпостроениякоторой описанав главе 2.

4.3Аппаратно-зависимыекомпонентыОСРВ

Модулимаршрутизации,реконфигурации,голосованияреализованыкак аппаратно-независимыепроцедурыоперационнойсистемы. Модулиоперируютданными, заданнымив конфигурационномфайле, что непривязываетих к конкретнойтопологии.Реализованныеметодом структурногопрограммированияна языке Си,модули могутбыть перенесенына большинствоплатформ, включаяи TMS320C30.

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

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

4.3.1.Модуль диагностикиПЭ

Модульдиагностики,реализованныйв виде наборафункций, возвращающихкод ошибки,призван решатьследующиезадачи:

Наэтапе инициализации:

Тестированиерегистровобщего назначенияпроцессора;
Проверкаправильностивыполненияарифметических,логическихи др. операций;
Занесениев соответствующуютаблицу контрольныхсумм неизменныхво время выполненияпрограмм областейпамяти (исполняемыйкод, константы),размещениекоторых в памятипроводитсяна этапе сборкирабочего кодав соответствиис картой памяти;

Вовремя рабочегоцикла, тестированиеможет проводитьсякак с прерываниемвычисленийфункциональныхзадач, так инепосредственново время ихвыполнения,если предусмотренопроцессорноевремя на выполнениеэтих тестов.При этом можетосуществляться:

Тестированиерегистровобщего назначение;
Проверкаправильностивыполненияарифметических,логическихи др. операций;
Вычислениеконтрольныхсумм указанныхобластей памятии сопоставлениеих с вычисленнымина этапе инициализации.

4.3.1.1.Тестированиерегистровобщего назначения

Этоттест выполняетсяпервым дляпроверки регистровповышеннойточности (R0-R7)и вспомогательныхрегистров(АR0-АR7).Тестированиесводится кпроверке регистровна запись/чтениеиз памяти/впамять и проверкеправильностиперемещенияданных из регистрав регистр. Тестразбиваетсяна два этапа:

Проверкавспомогательныхрегистров(целочисленныезначения). Проверкареализованапо следующемуалгоритму:

Инициализироватьдве целочисленныепеременныеначальным иожидаемымзначениемтестирования;
Загрузитьначальноезначение врегистры (АR0-АR7).
Произвестиоперацию сложениятак, что в каждомпоследующемрегистре оказаласьсумма предыдущих.
Записьв стек модифицированныхрегистров.
Произвестиоперацию сдвигавлево содержимогостека на Nразрядов всоответствиис номеромзаписанногорегистра.
Записатьданные из стекав регистры.
Произвестиоперацию сложениятак, что в каждомпоследующемрегистре оказаласьсумма предыдущих.
Сравнитьсодержимоерегистра АR7с ожидаемым,заранее рассчитаннымзначением.

Проверкарегистровповышеннойточности (значенияс плавающейточкой) проводитсяаналогично.

Функцияregister_testреализованана языке Ассемблерв соответствиис архитектуройи системойкоманд TMS320C30.

4.3.1.2.Проверка правильностивыполненияарифметических,логическихи др. операций

Данныйтест разделенна три различныхмодуля. Вместеони проверяютследующиечисловые операции:

1.Логические,сдвиг, циклическийсдвиг.

2.Операции сплавающейзапятой, выполненныенад одним значениеми соответствующиепараллельныекоманды.

3.Операции сплавающейзапятой ицелочисленные,выполняющиесложение, вычитание,и умножениеи соответствующиепараллельныекоманды.

Втестах проверяютсякоманды, перечисленныев Таблице 4.1.

Таблица4.1

Переченьтестируемыхкоманд

Тест	Команды
1	2
Тест1	ROL– циклическийсдвиг влево, ROLC– циклическийсдвиг влевочерез перенос, ROR– циклическийсдвиг вправо, RORC– циклическийсдвиг вправочерез перенос, AND3\|\| STI – поразрядноелогическоеИ с сохранением, LSH3\|\| STI – логическийсдвиг с сохранением, NOT\|\| STI – дополнениес сохранением, OR3\|\| STI – поразрядноелогическоеИЛИ с сохранением, XOR3\|\| STI – поразрядноеисключающееИЛИ с сохранением, ABSI\|\| STI – абсолютноезначение целогос сохранением, NEGI\|\| STI – отрицаниецелого с сохранением, ASH3\|\| STI – арифметическийсдвиг с сохранением,
1	2
	NOT– поразрядноелогическоедополнение, ABSI– абсолютноезначение целогочисла, NEGB– отрицаниецелого с заемом, ASH– арифметическийсдвиг, NEGI– отрицаниецелого, TSTB3– проверкабитовых полей, CMPI3– сравнениецелых, STI\|\| STI – сохранениецелых, LDI\|\| LDI – загрузкацелых, XOR– поразрядноеисключающееИЛИ.
Тест2	STF– сохранитьзначение сплавающейточкой, LDF– загрузитьзначение сплавающейточкой, LDE– загрузказначенияэкспонентыс плавающейточкой, LDM– загрузказначения мантиссыс плавающейточкой, FIX– преобразованиев целое, FLOAT– преобразованиев значение сплавающейточкой, ABSF– абсолютноезначение числас плавающейточкой, NEGF– отрицаниезначения сплавающейточкой, NORM– нормированиезначения сплавающейточкой, RND– округлениезначения сплавающейточкой, POPF– выталкиваниезначения сплавающейточкой из стека, PUSHF– загрузка встек значенияс плавающейточкой, ABSF\|\| STF – абсолютноезначение числас плавающейточкой с сохранениемзначения сплавающейточкой, FIX\|\| STI – преобразованиев целое с сохранением, FLOAT\|\| STF – преобразованиев значение сплавающейточкой с сохранениемзначения сплавающейточкой, PUSH– загрузкацелого в стек, POP– выталкиваниецелого из стека, LDF\|\| STF – загрузитьзначение сплавающейточкой с сохранениемзначения сплавающейточкой,
1	2
	NEGF\|\| STF – отрицаниезначения сплавающейточкой с сохранениемзначения сплавающейточкой, STF\|\| STF – сохранениязначений сплавающейточкой, LDF\|\| LDF – загрузказначений сплавающейточкой.
Тест3	SUBF3– вычитаниезначений сплавающейточкой, SUBF3\|\| STF – значенияс плавающейточкой с сохранениемзначения сплавающейточкой, SUBB– вычитаниецелых с заемом, SUBC– условноевычитаниецелых, SUBF– вычитаниезначений сплавающейточкой, SUBRB– вычитаниецелых в обратномпорядке с заемом, SUBRF- вычитаниес плавающейточкой в обратномпорядке, SUBI3\|\| STI – вычитаниецелых с сохранением, ADDC– сложениецелых с переносом, ADDF– сложениезначений сплавающейточкой, ADDF3– сложениезначений сплавающейточкой, ADDF3\|\| STF – значенийс плавающейточкой с сохранениемзначения сплавающейточкой, ADDI3\|\| STI – сложениецелых с сохранением, MPYF-умножениезначений сплавающейточкой, MPYF3– умножениезначений сплавающейточкой, MPYI– умножениецелых, MPYF3\|\| STF – умножениезначений сплавающейточкой с сохранениемзначения сплавающейточкой, MPYF3\|\| ADDF3 – умножениеи сложение сплавающейточкой, MPYF3\|\| SUBF3 умножениеи вычитаниес плавающейточкой, MPYI3\|\| STI – умножениецелых с сохранением, MPYI3\|\| ADDI3 – умножениеи сложениецелых, MPYI3\|\| SUBI3 – умножениеи вычитаниецелых, CMPF– сравнениезначений сплавающейточкой, CMPF3- сравнениезначений сплавающейточкой.

Проверкаосуществляетсяс помощьюфиксированногонабора значенийс целью тестированиякоманд в различныхпределах. Выводо успехе/неуспехеделается наоснове контрольногосуммированиярезультатови сопоставленияс ожидаемымзначением.

4.3.1.3.Проверка содержимогопамяти

Данныйтест формируетпо одному изсамых простыхалгоритмовтак называемыйCRC(Cyclic Redundancy Check) блока памяти,указанный впараметрахтеста. Правильный(ожидаемый) CRCподтверждаетправильностьданных (кода)в указанной,неизменной(nonvolatile)в процессеисполнениязадач областипамяти.

ФормированиеCRCпроисходитпо следующемуалгоритму:

Инициализацияначальногозначения CRCнулем; маскаконтрольныхбитов выбираетсяпроизвольно,например -80200003(Н).
Наложитьмаску на CRCи суммироватьпо модулю двазначения контрольныхбитов.
СдвинутьCRCвлево на 1 разряди прибавитьрезультат шага2.
Сложитьрезультат сочереднымсловом блокатестируемыхданных.
Еслиблок закончилсяшаг 6, иначе шаг2.
СравнитьполученныйCRCс ожидаемым.

Ожидаемыезначения могутбыть полученына этапе инициализации.Функция crc_testреализованана языке Ассемблерв соответствиис архитектуройи системойкоманд TMS320C30.

5.ПерспективыразвитияспециализированныхотказоустойчивыхОСРВ

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

Очевидно,что созданиеотказоустойчивых,адаптивныхсистем необходимодля надежногофункционированиякритическиважных приложениймножестваразличныхуправляющихсистем. Однакоусложнениеструктурывычислительныхсистем, а соответственнои алгоритмовподдержкиотказоустойчивости(а в общем случаеи живучести),ведет к увеличениюразмера ОС иее времениреакции. Поэтому,следует по-прежнемупридерживатьсяструктурногоподхода припроектированииуправляющихсистем и использоватьзаранее определенныефункции ОСРВ,характерныедля данноговида системуправления.

Дальнейшеенаращиваниефункций ОСРВможет вестисьв несколькихнаправлениях:

Голосование,проводимоена уровнеэлементарнойпроверки, вобщем случаеможет не удовлетворятьусловиямфункционированияуправляющихсистем вследствиепогрешностейи возможногоотличия функциональнойинформации,поступающейна обработкув ФЗ разныхПЭ. Поэтомупри голосовании,особенно напоследнихстадиях деградациицелесообразноприменятьпомехоустойчивоеоценивание,например методомнаименьшихквадратов(МНК).

Основныетрудностисвязаны с ошибочнымиизмерениямиили невернымрезультатомФЗ при вызывающейсбой комбинациивходных данных.Применениеметодов устойчивогооцениванияк решению этойпроблемы поможетизбежать потерьвремени наповторныеизмерения ирасчет ФЗ, атакже поможетвнести определенностьпри несогласованностиданных в процессеголосования.

Усовершенствованиеподсистемысбора и анализаотказов длядиагностированиямножественныхотказов наодном тактеработы системы.Однако, следуетучесть, чтообнаружениебольшего числаотказов требуетпропорциональноеувеличениечисла обменовмежду модулямиголосования,а также числапроцессорныхэлементов,участвующихпри голосовании.
РасширитьвозможностисамодиагностированияПЭ подсистемойпромежуточныхтестов ввода-вывода,тестом таймерови др.
ПредусмотретьвозможностирезервированияФЗ или отдельныхее частей дляпрограммногообнаруженияотказа, локализациии передачиуправлениядублирующемуфрагменту ФЗ.

Представленныйв работе материалявляется попыткойсистематизироватьи реализоватьосновные принципыразработкисистемногопрограммногообеспечениядля отказоустойчивыхвычислительныхсистем. Частичноили полностью,эти принципыреализуютсяразработчикамиОСРВ для обеспеченияотказоустойчивостисетевых приложений.Дальнейшееразвитиереализованныхв представленнойработе принциповв еще болеесложные системыпозволит решатьеще более широкийкруг задач врамках обеспечениянадежностивычислительныхсистем.

Заключение

Врамках решенияпоставленнойзадачи, порезультатаманалитическихисследований,были выделеныосновные свойстваи механизмыраспределенныхоперационныхсистем реальноговремени, необходимыхдля работыкритическиважных приложений.Это:

Времяреакции системы;
Времяпереключенияконтекста;
Наличиесредств диспетчеризации;
Наличиесредств синхронизации,межзадачногои межпроцессорноговзаимодействия;

Однакотребования,предъявляемыек надежностивычислительныхсистем, таковы,что этих средствзачастую оказываетсянедостаточно.В ходе аналитическойработы, быладоказананеобходимостьи описана структуратаких встроенныхмеханизмовобеспеченияотказоустойчивостиОСРВ, как:

Средствамаршрутизациипакетов данныхв сети ПЭ;
Средствавысокоуровневогомежпроцессорногообмена;
Протоколголосования,анализа отказовв ВС, и принятияконсолидированногорешения;
СредствареконфигурацииВС.

Входе дальнейшихисследований,был рассмотренпример организацииотказоустойчивыхвычислений,и на основелогики принятияконсолидированногорешения, предложенэвристическийалгоритм анализарезультатовголосованияузлов (ПЭ) ВСи средствдиагностики.

Далеебыла предложенавероятностнаямодель отказоустойчивойВС, рассчитаныее надежностныехарактеристики,показавшиеувеличениесреднего временинаработки ВСна отказ в 2,5 –3,5 раз с расширениемВС до 5-7 узлов,даны рекомендациипо выбору типаВС при ее проектировании.

Входе практическойреализациисвойств отказоустойчивости,была созданапрограммнаямодель, имитирующаямногопроцессорнуюВС, управляемуюраспределеннойОСРВ. СтруктураПО модели включаетв себя ПО узлаВС и ПО системыконтроля идиалога спользователем.Модель позволилаотработатьлогику организацииотказоустойчивыхвычисленийи проверитьее в различныхситуациях.

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

Наличиеглобальногосистемногоцикла, задаваемогоорганизациейвнешних устройствили объектауправления.
Использованиемеханизмовмежзадачноговзаимодействия(семафоры, события,мьютексы) дляорганизациициклов и передачиуправленияи диспетчеризациипроцессов.

Прямаяработа с таймерами.Программированиетаймеровпроизводитсяна низком уровне(функциямиоперационнойсистемы), этотребованиедиктуетсярамками жесткогореальноговремени - необходимостичеткого удержаниясистемногоцикла.

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

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

Данырекомендациипо портированиюсистемногоПО на платфртмуTMS320C30.Выбор платформыосуществлялсяпо таким критериям,как: наличиеширокого спектрасовместимыхбазовых ОСРВ,оптимизациямикропроцессорапод задачиуправления,тактовая частотамикропроцессора,объем оперативнойпамяти, наличиесред разработкии отладки ит.д. Реализованыаппаратно-зависимыемодули ПО вчасти процедурсамодиагностикипроцессораи памяти.

Взаключение,перечисленыосновные перспективынаращиваниявозможностейсистемногоПО и усложненияпринципов егоработы.

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

Технологическаячасть

6.Технологическаячасть

Даннаяглава посвященатехнологииразработкипрограммногообепечениямодели отказоустойчивойраспределеннойвычислительнойсистемы и переносу(портированию)основных модулейотказоустойчивойОСРВ на платформуTMS320C30.

Программноеобеспечениемодели ВС состоитиз двух частей,разработанныхдля функционированияна базе персональногокомпьютерас процессоромPentium-100и выше с операционнойсистемой Windows98 ивыше. Перваячасть предназначенадля генерациисистемныхфайлов процессорныхэлементов ВСна основе заданнойтопологии,запуска моделиВС, имитацииобъекта управленияи генерациисистемнойинформациио сбоях ВС. Втораячасть предназначенадля моделированияузла ВС.

Программноеобеспечение,переносимоена платформуTMS320C30, на данномэтапе состоитиз набора функций,которые являютсянадстройкойнад базовойОСРВ.

6.1.Системныеисследования

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

Общаяструктурасистемы, моделируемаяразрабатываемымпрограммнымпродуктом,представленана рис. 6.1.

Такимобразом, программноеобеспечениемодели системыразбиваетсяна две части.Первая – этоПО, в задачикоторой входит:моделированиеобъекта управления(обмен информациейс ВС), инициализацияВС на основезаданнойтопологическойинформации,моделированиесбоев и отказовэлементов ВСдля отладкимодулей обеспеченияотказоустойчивостиВС.

Рис.6.1. СтруктураВС

Втораячасть служитдля моделированияПЭ системы ипредназначенадля отработкиалгоритмовобеспеченияотказоустойчивостив процессенепрерывногофункционированияВС.

Анализтребованийк функционированиюВС предопределилструктурураспределеннойоперационнойсистемы ВС,которая состоитиз идентичных операционныхсистем узловсети, отличныхдруг от другалишь своимномером и содержаниемсистемныхтаблиц, обусловленныхразмещениемузла в сети ПЭ.СтруктурараспределеннойОС представленана рис. 6.2.

Рис.6.2. СтруктурараспределеннойОС

ЗадачейПО являетсяобеспечениеобмена междуобъектом управленияи ПЭ, обменафункциональнойи системнойинформациейвнутри ВС, выполнениефункциональнойзадачи согласноинформацииот объектауправления,реакции на сбоии отказы в системе,выявление илокализацииотказавшихучастков ВСконсолидированнымрешением рабочейконфигурациейсети, реконфигурациясистемы в реальномвремени всоответствиис принятымрешением.

ПлатформаTMS320C30,для реализациивыбраннойконцепциипостроенияОСРВ, была выбрана,исходя из аппаратныххарактеристик,наличия большогокласса базовыхОСРВ, совместимыхс данной платформой,удобных средствразработкии отладки.

6.2. Разработкаспецификации

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

6.2.1.Требованияк ПО управляющейчасти

Программноеобеспечениеслужит дляинициализацииработы ВС, имитацииобъекта управления,демонстрацииработы ВС вусловияхвозникновенияотказов и должносостоять измодулей, обеспечивающих:

АнализтопологиимоделируемойВС:

вводи считываниемодифицированнойматрицы связностиВС;
созданиефайлов инициализациидля узлов ВСна основетопологическойинформации.

Запусксистемы;
Обменфункциональнойинформациейс ВС:

выдачаинформациидля обработкиВС на очередномцикле;
приемобработаннойинформацииот ВС на очередномцикле.

Моделированиеотказов и сбоевкомпонент ВС:

формированиесигнала наполный отказопределенногоканала связиПЭ (прекращениефункционирования);
формированиесигнала насбой определенногоканала связиПЭ (искажениеинформациипри передаче);
формированиесигнала наполный отказПЭ (прекращениефункционирования,“зависание”);
формированиесигнала насбой ПЭ (неверныйрасчет функциональнойзадачи).

6.2.2. Требованияк ПО узлов сети

Враспределеннойоперационнойсистеме организацияпрограммногообеспеченияследующая.Каждый модульсодержит копиюОС, котораяспроектированотак, чтобы обеспечитьстандартныйинтерфейс сдругими модулямив системе. ПрикладноепрограммноеобеспечениераспределеннойОС выступаеткак набор параллельновзаимодействующихпроцессов, аОС узла обеспечиваетвысокоуровневую структуру дляобслуживаниямежпроцессорныхсвязей, а такжесодержит процедурыдиагностикии локализацииотказов, реконфигурациии замены отказавшегоэлемента.

Такимобразом, ПОузла должнообеспечивать:

Определениестатическихмаршрутовпередачи информациив ВС, исходяиз текущейтопологии ВС;
Расчетфункциональнойзадачи на очередномцикле;
Обменфункциональнойи системнойинформациейвнутри ВС:

приеми передачафункциональнойинформациипосле завершениярасчета функциональнойзадачей;
приеми передачаинформациио результатахэлементарныхпроверокфункциональнойинформации;
приеми передачаинформациио результатахголосования(консолидированногорешения).
приеми передачаинформацииинициализациипри заменеотказавшегоэлемента;
обеспечениетранзитнойпередачи информациипри отказеканала связи.

Сравнениепоступающейфункциональнойинформации(элементарнаяпроверка) иформированиепромежуточногорешения о состояниисистемы.
Голосованиеи принятиеконсолидированногорешения о наличии(отсутствия)отказов в системе.
РеконфигурациюВС в соответствиис результатамиголосования.
Синхронизациюработы ВС.
Обменинформациейс объектомуправления:

приемфункциональнойинформацииот объектауправленияв начале очередногоцикла;
выдачуфункциональнойинформациив конце очередногоцикла;
приемуправляющегосигнала намоделированиеотказа ПЭ илиодного изиканалов связи;

Диагностированиесостояния ПЭ.

6.3. Разработкаалгоритмов

Разработкаалгоритмоввелась с учетомпостроеннойна этапе системныхисследованийструктуройПО (см. рис. 6.2) итребованийк нему.

Наибольшееприменениек настоящемувремени получилструктурныйподход к технологиипрограммирования,предполагающийнисходящуюразработку,структурноепрограммированиеи сквознойструктурныйконтроль. Принисходящейразработкепроектированиеи программированиеведутся сверхувниз. Для восходящегоподхода характеренряд трудностей,которых можноизбежать принисходящемподходе:каждый элементарныймодуль можетправильноработать сосвоей отладочнойпрограммой,но все модуливместе могути не работатьвследствиенесогласованностиили различнойинтерпретацииспецификацийкаждого модуля.

6.3.1. Структурапрограммы

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

Исходяиз графа управления,общая структурапрограммногопродукта быларазбита на двечасти, а они всвою очередь- на модули потехнологиисверху внизметодом декомпозиции.Далее, в пределахнекоторыхмодулей применялсяподход снизувверх с применениемструктурногопрограммированиядля подключенияновых функциймодуля, удовлетворяющихспецификации.

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

Внутренняяструктурамодулей проектироваласьструктурировано,по критериюминимизациимежмодульныхсвязей и циклов.Модули оперируютсистемнойинформациейнезависимоот характеравыходных данныхпредыдущихмодулей.

Алгоритмыи функционированиемодулей ОСРВдетально рассмотреныв главе 2 и 3.

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

Впроцессе дальнейшихисследованийпредполагаетсядальнейшеенаращиваниефункций отладочногомеханизма потехнологииснизу вверх.

6.4.Кодирование

Выборязыка программированияопределяется,с одной стороны,требованиямик программномуобеспечению(например, размери скоростьисполнениякода), с другойстороны, наличиемсред разработки,компиляторов,отладчикови других инструментовразработчика.

Дляреализациимодели отказоустойчивойВС использовалсяязык С и средаразработкиMicrosoft Visual С++ 6.0. Выборсреды разработкиобусловленналичием у неешироких возможностейпо использованиюмеханизмовWindows 98/2000 в качествеподдержкибазовых функцийОСРВ. Windows 98/2000 неявляется операционнойсистемой реальноговремени, однакоимеет достаточномощные механизмы(pipes – обменданными междупроцессами,многозадачностьи многопоточность,средствасинхронизации– семафоры,мьютексы, события,таймеры) вомногом схожиес механизмамиОСРВ, и достаточныедля реализациимодели.

ЯзыкС, поддерживаемыйбольшинствомсред разработкии трансляторовразличных ОСРВ,используемыйпри разработкемодели, позволяетсоздаватьаппаратно иоперационно-независимыефрагментыпрограмм, непривязанныхк механизмамWindows.

Выборязыка С былобусловлентакже следующимифакторами:

повсеместнымприменениемязыка С дляаппаратногопрограммирования,так как он обладаетхорошей оптимизируемостьюкода, и эффективностью,сравнимым сАссемблером.
наличиембольших библиотек,поставляемыхвместе со средствамиразработки,которые значительнооблегчают иоптимизируюттруд разработчиков.
навыкамиразработчиков.

ДляпрограммированияплатформыTMS320C30 использоваласьсреда разработкиCode Composer 3.0 с трансляторомязыка С, вомногом напоминающаяVisual C++. Выборданной средыразработкибыл обусловленследующимифактороми:

сочетаниеинтегрированнойсреды разработкис симулятороми мощной системойотладки;
Windows-интерфейс;
большойнабор настроекпроекта, в томчисле настройкакарт памяти;
симуляторс широким наборомвозможностей;
наличиемощной системыотладки.

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

6.5.Тестированиеи отладка

Наэтапе разработкии программированиябыли выбраныследующиеметоды и средстватестированияи отладки:

встроенныйотладчикинтегрированнойсреды разработкиVisual C++ 6.0;
отладочно-демонстрационнаяпрограммамоделированияотказов ВС;
сквознойструктурныйконтроль навсем этапепрограммирования.
встроенныйотладчикинтегрированнойсреды разработкиСоde Composer 3.0;

6.5.1.Метод сквозногоструктурногоконтроля

Основнаяидея сквозногоструктурногоконтроля -регулярнаявзаимная проверкапрограммныхмодулей наэтапе программирования.Такой контрольнеобходим дляобнаруженияи исправленияошибок какможно раньше,пока стоимостьисправленияошибок минимальна.При отладкинаписанныхпрограмм важнотщательнопровести тестированиепрограммногопродукта. Цельтестированиясостоит в том,чтобы убедиться,что программарешает действительноту задачу, длякоторой предназначена,и выдает правильныйрезультат прилюбых условиях.

6.5.2.Встроенныйотладчикинтегрированнойсреды разработкиMicrosoftVisual C++ 6.0

Встроенныйотладчикпредоставляетследующиевозможности:

Возможностьпошаговогоисполненияпрограммы,
Возможностьустановкибрейкпоинтов(точекостанова программы)в необходимыхместах,
Возможностьпросмотра иизменениязначений переменных,
Возможностьприостановкии запуска процессови др.

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

6.5.3.Встроенныйотладчикинтегрированнойсреды разработкиCodeComposer 3.0

Встроенныйотладчикпредоставляетследующиевозможности:

Возможностьпошаговогоисполненияпрограммы,
Возможностьустановкибрейкпоинтов;
просмотрсостоянияпроцессора(содержимоерегистров ифлагов, сегментыкода и данных);
просмотрзначений локальныхи глобальныхпеременных;
просмотрсодержимогостека и историивызовов;
дизассемблированиепрограммы;
возможностьподключенияв ключевыхточках программыввода-выводас помощью текстовыхфайлов, такимобразом симулируетсятрансфер данныхчерез памятьпроцессора;
возможностьподключенияграфическогоаппарата,представленного4-мя различнымивариантамидиаграмм дляпостроенияграфиков различнойсложности иотслеживаниясигналов реальноговремени;
наличиепрофайлера,позволяющегопроизводитьзамер производительностипроцессорана критическихучастках кодаи др.

Сего помощьюотслеживаласьправильностьвыполнениямодулей ОСРВ,переносимыхна платформуTMS320C30,и процедурыаппаратно-зависимойдиагностики.

6.5.4.Отладочнаяпрограмма

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

Спомощью отладочнойпрограммыпроводилосьследующеетестирование:

проверкаправильностиреакции системына отказ илисбой каналовсвязи;
проверкаправильностиреакции системына отказ илисбой ПЭ;
проверкаправильностиперестройки(реконфигурации)системы послеотказа;
проверкаправильностивыдаваемыхсистемой результатовв условияхпостояннойдеградациисистемы.

6.5.5.Отладка итестированиемодулей ОСРВ

Напервом этапедля всех модулейтестировалисьвсе разветвленияна графе управленияпрограммойкак с помощьювстроенногоотладчика(правильнаяобработка всехкоманд), так истохастически,то есть с помощьюгенерацииразличнойпоследовательностивходных данных,и проверкирезультатовсравнениемс эталоннымизначениями.Далее проверкапроизводиласькомплексно,исследоваласьреакция ивзаимодействиемодулей.

Приведемописание процессатестированиядля некоторыхмодулей.

Модульмаршрутизации:Отладка итестированиеэтого модуляпроводиласьсначала с помощьюотладчика, навход подаваласьпростейшаятопология сети,при этом отслеживалосьправильноевыполнениестатическихкоманд и командперехода иветвления.После полученияудовлетворительныхрезультатов,тестированиепродолжалосьстохастически,проверкоймодуля на различныхвходных топологиях.Дальнейшеетестированиепроводилоськомплексно,с подключениеммодуля реконфигурации.

Модульреконфигурации:Проверка выполнениявсех ветвейпроводиласьс помощью отладчика,на вход алгоритмаподавалисьнужные значенияи с помощьютрассировкипроверяласьправильностьвыбора и выполнениянужной ветви.Дальнейшаястохастическаяотладка модуляпроводиласькак с использованиемотладчика, таки отладочнойпрограммы, спомощью генерацииразличногорода информацииоб отказах ипроверкойрезультатовработы данногомодуля сравнениемс ожидаемымрезультатом.

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

Комплекснаяотладка модулейпроводиласьорганизациейвзаимодействиямодулей всоответствиис логикой работыВС, отслеживалисьданные межзадачноговзаимодействия,синхронизация,и последовательностьдействий спомощью специальновводимых текстовыхсообщений включевых узлахпрограмм.

Список литературы

1.ЗатуливетерЮ.С. Введениев проблемупараметризованногосинтеза программдля параллельныхкомпьютеров.-М., 1993 (Препринт/Институтпроблем управления).

2.Харченко В.С.,Лысенко И.В.,Мельников В.А.Оценка и обеспечениеживучестиинформационно-вычислительныхи управляющихсистем техническихкомплексовкритическогоиспользования.Зарубежнаярадиоэлектроника.1996. №1.

3.Э.В. Евреинов.Однородныевычислительныесистемы и среды.–М. Радио и связь,1981.

4.А. Вильямс. Системноепрограммированиев Windows2000.–СПб. Питер,2001.

5.С. Кейслер.Проектированиеоперационныхсистем длямалых ЭВМ,-М.,Мир, 1986.

6. А. Шоу.Логическоепроектированиеоперационныхсистем.-М.,Мир,1981.

7.К.А.Иыуду, С.А. Кривощеков,Математическиемодели отказоустойчивыхВС. –М., МАИ, 1989.

8.К.А. Иыуду. Надежность,контроль идиагностикавычислительныхмашин и систем.-М., Высшая школа,1989.

9.Л.П.Глазунов и др.Основы теориинадежностиавтоматическихсистем управления.-М.,Энергоатомиздат,1984.

10.Р.Л. Лонер, Г.Н.Уилкинсон,Устойчивыестатистическиеметоды оценкиданных: Москва,Машиностроение,1984

11.Артамонов Г.Т.,Тюрин В.Д. Топологиясетей ЭВМ имногопроцессорныхсистем. — М.: Радиои связь, 1991.

12.Е.С. Вентцель,Теория вероятностей.М. НАУКА, 1969.

13.В.Н. Агафонов.Спецификацияпрограмм. –М.,Наука, 1987.

14.А. Мешков, Ю.Тихомиров.VisualC++ иMFC.–СПб. БХВ-Санкт-Петербург,2001.

15.Л.Б. Богуславский.Управлениепотоками данныхв сетях ЭВМ.-М., Энергоатомиздат,1984.

16.В.И. Матов и др.Теория проектированиявычислительныхмашин системи сетей. –М., МАИ,1999.

17.В.В. Липаев.НадежностьпрограммногообеспеченияАСУ. -М., Энергоиздат,1981.

17.Д.И.Козлов и др.,Управлениекосмическимиаппаратамизондированияземли. – М.:Машиностроение,1998.

18.Б. Страуструп.ЯзыкпрограммированияС++. – Киев. ДиаСофт,1993.

19.А.Г. Додонов идр. Введениев теорию живучестивычислительныхсистем. – Киев,Наук. Думка,1990.

20.Э.М. Мамедли,Р.Я. Самедов,Методы восстановлениявычислительногопроцесса вотказоустойчивыхцифровых системуправленияреальноговремени, ПрепринтИнститутаПроблем УправленияРоссийскойАкадемии Наук,Москва, 1998.

21.Гуляев В.А., ДодоновА.Г. , ПелеховС.Л. Организацияживучих вычислительныхструктур.- Киев.:Наукова Думка, 1987

22.Гришин Ю.П.,Казаринов Ю.М.Динамическиесистемы, устойчивыек отказам.- М.:Радио и связь,1985.

23.Транспьютеры.Архитектураи программноеобеспечение:Пер. с англ. Подред. Г.Харпа.-М.:Радио и связь,1993

24.TMS320C3x User's Guide, Texas Instruments, Inc., Dallas, Texas, 1994

25.Дейтел Г., Введениев операционныесистемы. М, Мир,1987.

26.Дансмур М., ДейвисГ. Операционнаясистема UNIX ипрограммированиена языке Си. М."Радио и связь".1989.

27.К.Ю.Богачев.Операционныесистемы реальноговремени.М.2001.

28.Артамонов Г.Т.Топологиярегулярныхвычислительныхсетей и сред.— М.: Радио и связь,1985.

29.МартинДж. Программированиедля вычислительныхсистем реальноговремени. – М.:Наука, 1975.

Экономическоеобоснованиедипломныхпроектов.Методическоепособие. –М.,МАИ, 1991.
РуководствоР2.2.013-94 Гигиеническиекритерии оценкиусловий трудапо показателямвредности иопасностифакторовпроизводственнойсреды, тяжестии напряженноститрудовогопроцесса.
ЮдинЕ.Я., Белов С.В.и др. Охранатруда в машиностроении.М.:Машиностроение,1983, 432с.
ГОСТ27954 - 88 Видеомониторыперсональныхэлектронныхвычислительныхмашины. Типы,основные параметры,общие техническиетребования.
СаНПин2.2.2.542-96. Гигиеническиетребованияк видеодисплейнымтерминалам(ВДТ). персональнымэлектронно-вычислительныммашинам (ПЭВМ)и организацииработы. М.:Информационно-издательскийцентр ГоскомэпиднадзораРоссии, 1996. 65 с.
ГОСТ12.1.006 - 84 Электромагнитныеполя радиочастот.Допустимыеуровни на рабочихместах и требованияк проведениюконтроля. Изменениек ГОСТ.
ГОСТ12.1.005-88. Воздух рабочейзоны. Общиесанитарно -гигиеническиетребования.М.: Изд-во стандартов,1990. 14 с.
СНиП23-05-95 Естественноеи искусственноеосвещение.
www.pcweek.ru
www.osp.ru
www.realtime-info.be
www.rtsoft-training.ru
www.ti.com
www.windriver.com
www.eonic.com

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

Операционныесистемы реальноговремени.

Описаниеи общие требованияк системамреальноговремени.

1.2. ПараметрыОСРВ

1.2.1.Время реакциисистемы

1.2.2.Время переключенияконтекста

Размерысистемы

Механизмыреальноговремени

1.3.1.Система приоритетови алгоритмыдиспетчеризации

1.3.2.Механизмымежзадачноговзаимодействия

Средствадля работы стаймерами

Классы системреальноговремени

Операционнаясистема OS-9

ОСразработки(host): UNIX/Windows

Операционнаясистема VxWorks

Операционнаясистема QNX

Операционнаясистема LynxOS

Таблица 2.8

Таблица 2.11

Таблица2.13

Таблица2.14

Обновленнаятаблица связности

Анализработоспособнымиузлами причинотказа показывает:

Таблица2.23

Таблица2.24

Таблица2.25

2.7.Выводы к главе2

Таблица3.1

Таблица3.2

Функции,реализующиемаршрутизатор

Имя

Формированиетаблиц рассылкиметодом волны

Таблица3.3

Функции,реализующиемодуль коммуникации

Имя

Таблица3.4

Функции,реализующиемодуль голосованияи анализатораотказов

Имя

Переинициализациябуферов голосования

Таблица3.5

Функции,реализующиереконфигуратор

Имя

ПроверкаизолированностиПЭ Cpu.

Таблица3.6

Функции,реализующиефункциональнуюзадачу

Имя

Таблица3.7

Функции,реализующиемоделированиеотказа

Имя

type=1–фатальныйотказ ПЭ, приостановкавсех канальныхпотоков и ФЗ.

Завершаетсоответствующийканальныйпоток, в случаефатальногоотказа (type=0),или дает указаниемодулю коммуникацииотсылать ошибочныепакеты (type=1).

Таблица3.6

Назначениеи функции элементовдиалога

Элемент

Содержиттри связанныхэлемента:

Таблица4.1

Команды