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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-         нарушения кодов записи программ в памяти команд;

-         стирания или искажения данных в оперативной или долговременной памяти;

-         нарушения нормального хода вычислительного процесса.

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

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

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

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

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

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

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

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

·        Нет гарантии, что сбой снова не повторится после восстановления.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

·        функциональный контроль вычислений с помощью специальных контрольных операторов и нескольких версий программ;

·        функциональный контроль входной и выходной информации;

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

·        контроль выходной информации по квитанции от приемника - абонента системного интерфейса;

·        контрольный тест аппаратуры процессора;

·        контрольные тесты аппаратуры внешнего и внутреннего интерфейсов.

·        встроенные аппаратные средства контроля процессорных элементов и контроллеров системного интерфейса.

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

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

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

отказоустойчивости N-1.

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

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

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

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

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

-      результатов «голосования» (сравнения) поступающей в данный ПЭ функциональной информации;

-      результатов оценки поступившей от других ОС узлов;

-      «результатов голосования» (т.е. «вывод» данного ПЭ о состоянии других ПЭ).

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

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

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

4. ОС должна обладать свойством масштабируемости, что в узком смысле означает обеспечение ее настраиваемости на поддержку функционирования сетевых ВС различной размерности N (для реальных систем в пределах 3 £ N £ 10). Причем правая граница изменения N (Nmax = 10) выбрана из практических соображений построения ВС с высокой степенью связности узлов сети при использовании конкретных процессорных модулей количеством линков (L) не более шести (L£6). При L=6 семиузловая сеть является полносвязанной и по мере увеличения N степень связности узлов сети уменьшается.

5. Времени для выполнения всех необходимых действий должно хватать с запасом 20-30% с учетом производительности аппаратной платформы.

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

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

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

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

·        разделение цикла работы системы на следующие периоды: ввод данных, решение ФЗ, обмен функциональными данными (ФД), обмен результатами голосования ФД, обмен предварительными выводами о состоянии системы, принятие консолидированного решения (КР) о состоянии системы, реконфигурация системы при обнаружении в рамках КР отказа части системы.

В дальнейшем этот перечень требований к ОСРВ будет продолжен и детализирован.

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

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

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

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

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

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

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

·    выбор и реализация механизма голосования. При этом механизм передачи/приема данных и голосования должен быть по возможности скрыт от прикладного программиста.

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

2.4.1. Описание системных таблиц

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

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

Таблица 2.1

Пример таблицы связности для полносвязной сети ПЭ

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

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

Рис. 2.1. Пример неполносвязной сети

Цифры в окружностях – номера процессорных элементов, вне – номера линков (физических каналов связи). Таким образом таблица связности имеет вид (таблица 2.2).

Таблица 2.2

Таблица связности для примера на рисунке 2.1

Таблицы рассылки для каждого ПЭ могут иметь вид (см. Таблицу 2.3, 2.4, 2.5, 2.6).

Таблица 2.3

Таблица рассылки для ПЭ №1

Таблица 2.4

Таблица рассылки для ПЭ №2

Таблица 2.5

Таблица рассылки для ПЭ №3

Таблица 2.6

Таблица рассылки для ПЭ №4

2.4.2. Модуль маршрутизатора

          Как уже отмечалось в подразделе 2.4.1 маршрутизатор выполняет следующие функции:

·        хранение текущей топологии многопроцессорной системы;

·        установление оптимальных статических маршрутов передач данных в системе и таблиц рассылки;

·        обработка сигналов изменения топологии системы от реконфигуратора.

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

Рис. 2.2. Модуль маршрутизации

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

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

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

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

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

3.     Увеличиваем счетчик длины маршрута на 1 единицу (передачу).

4.     По таблице рассылки находим очередной ПЭ, не имеющий связи с локальным. Если таких больше нет, шаг 8.

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

6.     Если он имеет связь с нужным ПЭ, запоминаем номер линка для связи его с локальным ПЭ и загрузку линка. Шаг 5.

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

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

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

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

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

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

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

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

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

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

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

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

2.    Проверяется, не остались ли изолированными оставшиеся узлы, если да, то они отключаются.

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

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

2.4.4. Модуль коммуникации

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

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

·        получение запроса на прием/передачу данных от функциональной задачи;

·        установление соответствия между передатчиком и приемником данных; 

·        передача сообщения и идентификаторов адресатов модулю пересылки информации;

·        хранение принимаемых данных;

·        проверка согласованности данных от резервированных источников (голосование);

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

·        передача согласованных данных ФЗ;

·        передача/прием системных сообщений.

Модуль пересылки информации:

·        формирование формата передаваемого сообщения;

·        идентификация принимаемых сообщений;

·        диагностика целостности принимаемых сообщений (проверка контрольной суммы);

·        определение отказов физической среды передачи данных (проверка подтверждений приема данных – “квитанций”);

·        формирование сигнала модулю ОС – реконфигуратору о неисправности среды передачи.

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

Рис. 2.4. Структура модулей коммуникации

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

Формат посылки состоит из заголовка и самого тела посылки. В заголовке используются следующие поля:

·       

·       

·       

·       

·       

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

2.4.5. Процедура голосования

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

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

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

Несовпадение результатов сравнения может быть вызвано сбоем или отказом физического канала связи. Этому может предшествовать сигнал о неисправности канала связи от модуля коммуникации. В противном случае (при отсутствии сигнала), сбой в линии связи может быть определен по полученным векторам состояния. Например ПЭ получены следующие вектора: (0,-1,0), (-1,0,0), (0,0,0), где каждому вектору и каждому элементу вектора поставлен в соответствие номер ПЭ (то есть ПЭ1, ПЭ2, ПЭ3). Анализ сравнения этих промежуточных результатов может сказать о неисправности канала связи между ПЭ1 и ПЭ2.

При таком построении системы сделано неявное допущение о том, что на протяжении одного цикла может отказать не более одного элемента системы, иначе поведение её в таком случае строго говоря недетерминировано. Впрочем данное допущение может быть аргументировано тем, что время наработки на отказ отдельного элемента системы составляет по крайней мере несколько тысяч часов, и считая возникновения отказов независимыми событиями, вероятность отказа одновременно двух элементов на протяжении цикла (порядка 10 - 100 мс) величина порядка 10^-17 - 10^-18.  Однако при возникновении такой ситуации выходом может быть применение методов помехоустойчивого статистического оценивания результатов расчета [10], проведение диагностических тестов и тд. для выбора корректного результата и принятия решения о выдаче того или иного управляющего воздействия на текущем цикле.

2.5. Организация отказоустойчивых вычислений

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

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

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

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

3.    При несовпадении ни одного результата счета под сомнение ставится все участвовавшие в обмене ПЭ и связи.

4.    Несовпадение контрольной суммы или тайм-аут при приеме данных трактуется как сбой ПЭ или канала связи ПЭ.

5.    Отсутствие квитанции трактуется как сбой ПЭ или канала связи ПЭ.

6.    Неверный код квитанции трактуется как сбой канала связи ПЭ.

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

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

2.5.1 Пример организации отказоустойчивых вычислений

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

Рис 2.5. Топология ВС

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

          2.5.1. Инициализация

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

Таблица 2.8

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

1.    ПЭ1 -> ПЭ2 и ПЭ3;

2.    ПЭ2 -> ПЭ3 и ПЭ4;

3.    ПЭ3 -> ПЭ4 и ПЭ5;

4.    ПЭ4 -> ПЭ5 и ПЭ1;

5.    ПЭ5 -> ПЭ1 и ПЭ2;

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

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

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

                                                                                              Таблица 2.9

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

Анализ информации ПЭ1 позволяет сделать вывод о работоспособности ПЭ3, поскольку сообщение о его неисправности не подтвердили ПЭ4 и ПЭ5, и выявить сбой в канале связи 3-1. Анализ ПЭ2, ПЭ3, ПЭ4, ПЭ5 полученной информации показывает на неисправность линка 3-1, поскольку работоспособность ПЭ1 подтверждается узлом ПЭ2 и наличием в памяти достоверной информации о состоявшемся сеансе связи с ПЭ1.

Таблица 2.10

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

1. Недостоверность переданной информации была вызвана кратковременным сбоем, при этом ПЭ1 получил достоверные результаты счета, а ПЭ3 – недостоверные.

          Решение: отключении канала связи 3-1 происходит только при троекратном повторении сбоя.

2. Сбой возник на этапе обмена результатами голосования.

Решение: сбой фиксируется наличием “мусора” вместо стандартных значений, но «полноценное» обнаружение сбоя (если он повторится) произойдет на следующем такте.

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

          После принятия окончательного решения об отказе связи 3-1, инициируется реконфигуратор, вносящий соответствующие изменения в таблицу связности (см таблицу 2.11).

Таблица 2.11

Далее реконфигуратор проводит проверку на нарушение связности в рабочей сети. В данном случае изменяются статические маршруты ПЭ и связь между ПЭ1 и ПЭ3 осуществляется через ПЭ2.

          Предположим теперь, что отказал ПЭ4. При этом ПЭ4 может вести себя двояко: либо наступил фатальный отказ и ПЭ не выдает результатов, либо выдает искаженные результаты. Во втором случае так же может быть два варианта: ПЭ сохраняет способность правильно осуществлять обмен и голосование. В этом случае ПЭ способен диагностировать собственную ошибку. В противном случае считается, что сбойный узел выдает результаты, не несущие информативной нагрузки (“мусор”). Проиллюстрируем все случаи.

После этапа сравнения информации, в системе может оказаться следующая информация (таблица 2.12).

Таблица 2.12

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

          Таблица 2.13

Вариант 1: Сообщение от ПЭ4, содержит «мусор», что говорит о неисправности ПЭ4 или его каналов связи. Однако ПЭ1 и ПЭ5 приняли решение о неисправности ПЭ4 или каналов связи 5-4, 4-1. Поскольку отказ сразу всех каналов связи ПЭ4 и отказ ПЭ4 события равнозначные, принимается решение об неисправности ПЭ4.

Вариант 2: Сообщение ПЭ4 подтверждает результаты голосования в тройке ПЭ4, ПЭ5, ПЭ1 и принимается решение об отказе ПЭ4.

После двух отказов (линка 3-1 и ПЭ4) ВС имеет вид (рис. 2.6)

Рис.2.6. Топология ВС после 2-х отказов

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

1.    ПЭ1 -> ПЭ2 и ПЭ3;

2.    ПЭ2 -> ПЭ3 и ПЭ5;

3.    ПЭ3 -> ПЭ5 и ПЭ1;

4.    ПЭ5 -> ПЭ1 и ПЭ2;

Таблица 2.14

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

Рассмотрим дальнейший процесс деградации системы. Отказ ПЭ5 аналогично легко диагностируется, благодаря связям с каждым ПЭ в системе. Предположим теперь, что произошел отказ канала связи 2-3. Напомним, что связь ПЭ1 и ПЭ3 осуществляется через ПЭ2.

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

                                                                                              Таблица 2.15

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

Таблица 2.16

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

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

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

3.    Данные ПЭ5 от ПЭ3 говорят о исправности канала связи 3-5.

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

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

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

2.    “Мусор” от ПЭ1 может означать, что неисправен ПЭ1 или ПЭ2, или канал 1-2, или канал 2-3.

3.    “Мусор” от ПЭ2 может означать неисправность ПЭ2 или канала 2-3.

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

          Конфигурация, изображенная на рис. 2.6 является в какой-то мере критичной, поскольку используется транзитная связь через ПЭ2. Рассмотрим отказ ПЭ2 в этой же топологии. При этом, интерфейс обмена таков, что ПЭ2 в случае фатального отказа не передаст транзитную информацию (передаст «мусор»), в противном случае передаст ее без изменений.

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

                                                                                              Таблица 2.17

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

Таблица 2.18

Рассмотрим процесс принятия решения ПЭ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

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

Таблица 2.20

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

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

·        Анализ ПЭ1 и ПЭ2: “мусор” от ПЭ3 и ПЭ5 говорит о неисправности ПЭ5 или канала 1-5, а данные ПЭ2 однозначно говорят об отказе ПЭ5.

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

2.    При отказе ПЭ5, с сохранением способности обмена, информации для его диагностирования хватает с избытком.

После обмена окончательными выводами ПЭ1 и ПЭ2 принимают решение об отключении ПЭ5. После реконфигурации, маршрутизатор обнаруживает изолированность ПЭ3 и посылает сигнал реконфигуратору об отключении ПЭ3.

          Рассмотрим теперь функционирование ВС в составе трех ПЭ. Пусть остались функционировать ПЭ1, ПЭ2 и ПЭ5.

Рассмотрим отказ связи 2-5. В результате в узлах сети фиксируются следующие факты несовпадения результатов счета, представленные в таблице 2.21.

                                                                                              Таблица 2.21

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

Таблица 2.22

Анализ ПЭ1 предварительной информации подтверждает отказ линка 2-5, так как исправность ПЭ2 и ПЭ5 подтверждается информацией от ПЭ1.

Анализ ПЭ2 и ПЭ3 поступившей информации говорит о неисправности линка 2-5, в силу того, что ПЭ1 подтверждает правильность результатов ПЭ2 и ПЭ5.

          Рассмотрим дальнейшее функционирование системы (рис. 2.9).

Отказ ПЭ5 и ПЭ2 диагностируется также, как было показано выше, так как не нарушается связность между двумя ПЭ. Отказ связи 1-5 воспринимается ПЭ1 и ПЭ2, как отказ ПЭ5. Аналогично, отказ связи 1-2 равносилен отказу ПЭ2.

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

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

Если сделать предположение о равновероятности отказов в системе, изображенной на рис.2.9,  то вероятность отказа линка 2-1, приводящая к неопределенности в системе, равна 0.2. Однако в реальных ВС вероятность отказа канала связи считается величиной на порядок меньшей, чем вероятность отказа ПЭ за этот же период времени.

Отказ канала 1-5 не приведет к неопределенности. ПЭ5 не станет старшим в любом случае и будет отключен. Отказ ПЭ1 также не приведет к неопределенности, управление возьмет на себя ПЭ2.

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

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

2.5.2. Методика анализа отказов

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

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

·        Результатами голосования (предварительными выводами по результатам сравнения) функциональной информации;

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

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

·        Несовпадение данных при элементарной проверке результатов счета на очередном цикле диагностируется, как отказ ПЭ или канала связи этого ПЭ, при этом голосование проводится каждым ПЭ (с номером m) по результатам от ПЭ с номерами (m-1) mod N и  (m-2) mod N.

·        При несовпадении данных при элементарной проверке результатов счета, полученных с использованием транзитной передачи, под сомнение ставится вся цепочка, задействованная при передаче.

·        При несовпадении ни одного результата счета под сомнение ставится все участвовавшие в обмене ПЭ и связи.

·        Несовпадение контрольной суммы или тайм-аут при приеме данных трактуется как сбой ПЭ или канала связи ПЭ.

·        Отсутствие квитанции трактуется как сбой ПЭ или канала связи ПЭ.

·        Неверный код квитанции трактуется как сбой канала связи ПЭ.

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

1.    Создается матрица состояния ВС, которая размерностью идентична модифицированной матрице связности ПЭ, но по главной диагонали находятся данные о ПЭ, а в ячейках матрицы – о каналах связи.

2.    Матрица состояния ВС инициализируется единицами.

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

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

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

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

7.    Если такое значение есть, то соответствующий элемент признается отказавшим, иначе принимается решение об отсутствии оказов.

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

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

          ПЭ1->ПЭ2, ПЭ3;

ПЭ2->ПЭ3, ПЭ5;

ПЭ3->ПЭ5, ПЭ1;

ПЭ5->ПЭ1, ПЭ2.

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

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

          В таблице 2.23 представлены записи от всех ПЭ, расшифрованные в соответствии с выбранной логикой.

Таблица 2.23

Составим матрицу состояния ВС, получившуюся у ПЭ1 (см. таблицу 2.24).

                                                          Таблица 2.24

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

          Вариант 2: Наступил фатальный отказ ПЭ5, при котором он прекращает обмен с ВС, либо выдает неинформативные данные.

          Таблица 2.25 содержит расшифровку записей всех ПЭ в этом случае.

Таблица 2.25

Таким образом :

·        В ПЭ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 не произойдет ни одного события (отказа), вероятность безотказной работы.

Обозначим через

В произвольный момент времени t мы можем застать систему в одном из двух состояний:

-     работоспособном, с вероятностью R(t),

-     в состоянии фатального отказа, с вероятностью P(t).

Если взглянуть на систему с учетом состояний работоспособности каждого из N ее элементов (узлов), то в произвольный момент времени t мы можем застать систему в одном из 2^N состояний (см. рис. 2.10).

Рис 2.10. Состояния N-узловой системы

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

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

Вторую группу составляют состояния, в которых в системе имеется два отказавших элемента, таких состояний ровно  и т.д.

В i-ю группу включаются все состояния, в которых в системе отказало ровно i узлов, таких состояний

Предпоследняя (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). Примем среднее время наработки на отказ узла ⁵ часов. В таблице 2.26 приведены характеристики, рассчитанные по формулам (6а) и (8а).