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

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

применяются два принципиально различающихся подхода - восстановление

решения после отказа системы (или ее компонента) и предотвращение отказа

системы (отказоустойчивость).

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

и возвратное.

Прямое восстановление основано на своевременном обнаружении сбоя и

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

в корректное. Такое восстановление возможно только для определенного набора

заранее предусмотренных сбоев.

При возвратном восстановлении происходит возврат процесса (или

системы) из некорректного состояния в некоторое из предшествующих

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

. Потери производительности, вызванные запоминанием состояний,

восстановлением запомненного состояния и повторением ранее выполненной

работы, могут быть слишком высоки.

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

. Для некоторых компонентов системы восстановление в предшествующее

состояние может быть невозможно (торговый автомат).

Для восстановления состояния в традиционных ЭВМ применяются два

метода (и их комбинация), основанные на промежуточной фиксации состояния

либо ведении журнала выполняемых операций. Они различаются объемом

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

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

на следующие трудности:

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

состояния является серьезной теоретической проблемой;

. методы восстановления после отказов для некоторых систем непригодны из-

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

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

отказам. Такие системы либо маскируют отказы, либо ведут себя в случае

отказа заранее определенным образом.

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

компьютеры все чаще используются в критически важных приложениях,

разработчики создают новые ОС реального времени высокой готовности. Эти

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

инициируют предупреждения, запускают системную диагностику для того, чтобы

помочь выявить проблему, или автоматически переключаются на резервную

систему.

Обеспечение живучести – это использование специальных средств,

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

возникновении отказов ее программных и аппаратных компонентов с

возможностью деградации качества функционирования [2]. В отличие от

отказоустойчивости, где с отказом не связано качество работы ВС,

сравнительно сложные средства обеспечения живучести позволяют более

рационально расходовать вычислительные ресурсы и увеличивать среднее время

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

включает три основные функции: диагностика возникновения отказа,

локализация неисправности и перестройка системы. В основе толерантности

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

многопроцессорные системы с присущей им аппаратной избыточностью

потенциально позволяют создавать не только высокопроизводительные, но и

высоконадежные системы.

Другим основополагающим требованием является наличие механизма,

позволяющего агентам в каждом устройстве обмениваться топологической

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

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

управляющий агент должен поддерживать таблицу с локальной топологической

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

реальном времени модифицирующий содержимое базы данных и обеспечивающий

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

устройств либо реконфигурацией или отказом существующих узлов сети.

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

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

Под временной избыточностью понимается использование части

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

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

достоверности важных решений по управлению и обработке информации. Она

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

системы (так называемое N-версионное программирование).

Сопоставление результатов независимых решений одного и того же

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

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

источником диагностической информации о состоянии аппаратной части системы

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

широко используются при обеспечении отказоустойчивости - протоколы

голосования и протоколы принятия коллективного решения.

Протоколы голосования служат для маскирования отказов (выбирается

правильный результат, полученный всеми исправными исполнителями).

Протоколы принятия коллективного решения подразделяются на два

класса. Во-первых, протоколы принятия единого решения, в которых все

исполнители являются исправными и должны либо все принять, либо все не

принять заранее предусмотренное решение. Примерами такого решения являются

решение о завершении итерационного цикла при достижении всеми необходимой

точности, решение о реакции на отказ. Во-вторых, протоколы принятия

согласованных решений на основе полученных друг от друга данных. При этом

необходимо всем исправным исполнителям получить достоверные данные от

остальных исправных исполнителей, а данные от неисправных исполнителей

проигнорировать

Однако для систем на последней стадии их деградации (при отказе

предпоследнего узла сети) на первый план в качестве диагностической

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

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

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

операторов и нескольких версий программ;

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

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

суммам;

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

системного интерфейса;

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

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

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

контроллеров системного интерфейса.

Информационная избыточность состоит в дублировании исходных и

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

Часто для обнаружения состояния отказа используются тайм-ауты. В

обычных системах исполнения предусматривается три различных вида

обслуживания. Неблокирующее обслуживание всегда возвращает управление

немедленно вместе с достоверным кодом возврата (успех или неудача), однако,

в случае отсутствия данного вида обслуживания, обратившаяся к нему задача

может попасть в бесконечный цикл опроса. Блокирующее обслуживание избегает

такого опроса путём исключения вызывающей задачи из процесса

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

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

Механизм же таймаутов позволяет возвращать управление задаче, даже в

случае, если указанный сервис не предоставляется ей в течение определенного

периода времени.

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

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

В отказоустойчивых системах, построенных на N процессорных элементах,

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

функциональных элементов (ПЭ), после возникновения которых система

продолжает свое функционирование. Введем обозначение - N(m), которое

означает, что система содержит N узлов (ПЭ) и «держит» m отказов, т.е.

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

Следует заметить, что системы класса N(0) – относятся к самым

быстродействующим системам, а N(N-1) – к самым отказоустойчивым.

В дальнейшем в работе будем рассматривать концепции построения и

работы именно отказоустойчивых систем класса N(N-1). Данное ограничение

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

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

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

Таким образом, специализированные операционные системы,

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

обладать следующими свойствами:

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

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

сети ВС.

Информационная взаимосвязанность операционных систем узлов между

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

информации:

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

функциональной информации;

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

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

других ПЭ).

Все операционные системы узла идентичны и отличаются друг от друга

лишь своим номером и содержанием системных таблиц.

2. Внутренняя структура распределенной ОСРВ представляет собой

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

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

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

построения ОСРВ позволяет осуществлять ее расширение путем добавления новых

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

системы.

3. ОС должна обладать возможностью использования на различных

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

программ, то есть обладать свойством переносимости.

4. ОС должна обладать свойством масштабируемости, что в узком смысле

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

сетевых ВС различной размерности N (для реальных систем в пределах 3 ( N (

10). Причем правая граница изменения N (Nmax = 10) выбрана из практических

соображений построения ВС с высокой степенью связности узлов сети при

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

более шести (L(6). При L=6 семиузловая сеть является полносвязанной и по

мере увеличения N степень связности узлов сети уменьшается.

5. Времени для выполнения всех необходимых действий должно хватать с

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

С учетом этого факта (достаточности ресурса производительности)

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

. синхронизация вычислений - по циклам выдачи управляющих сигналов

(команд), задаваемых таймером ведущего узла (с меньшим номером среди

активных узлов);

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

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

средства защиты от зацикливания (зависания) вычислительного

процесса;

. разделение цикла работы системы на следующие периоды: ввод данных,

решение ФЗ, обмен функциональными данными (ФД), обмен результатами

голосования ФД, обмен предварительными выводами о состоянии системы,

принятие консолидированного решения (КР) о состоянии системы,

реконфигурация системы при обнаружении в рамках КР отказа части системы.

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

детализирован.

Рассмотрим общую концепцию работы такой системы. После получения

результатов расчета на очередном цикле, система должна получить информацию

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

ПЭ системы. При этом следует отметить, что обмен результатами счета со

всеми узлами ВС в некоторой мере избыточен, так как для выявления

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

ординарности потока отказов). Таким образом, протокол голосования может

быть построен так, что результаты счета отдельного ПЭ в ВС троируются, т.е.

могут не присутствовать в некоторых узлах системы.

Во время сравнения ПЭ делает вывод о нормальном или неправильном

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

Результатами сравнения ПЭ обменивается со всеми узлами системы, и они

принимают консолидированное решение об отказе того или иного элемента или

делают заключение о нормальной работе системы.

В случае обнаружения отказа, на выход выдаются результаты, признанные

верными при голосовании. Отказавшему элементу предоставляется возможность

«исправиться» в течение следующих трех циклов. При этом сбойному ПЭ

передается контекст верно функционирующей задачи. Тройная попытка

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

отключения работоспособного ресурса системы. Если сбои в этом элементе

повторились, система считает элемент отказавшим, после чего производится

подключение к работе резервного ПЭ (если он предусмотрен изначальной

топологией сети) с передачей текущего контекста функциональных задач. При

отказе связей передача данных производится через транзитные связи. Если

элемент утратил все свои связи (линки), то он изолируется на логическом

или, если это возможно – на физическом уровне (отключение питания).

В настоящее время существуют различные ОСРВ, призванные решать задачи

организации вычислений в системах РВ. Однако ни одна из них не

удовлетворяет поставленным требованиям в полной мере. Поэтому встает вопрос

о необходимости расширения существующих ОСРВ или разработки новой ОС,

удовлетворяющей им. Поскольку создание ОС с удобными средствами создания и

отладки прикладного программного обеспечения - длительный и трудоемкий

процесс, единственным выходом является доработка существующих ОС.

В качестве основного подхода к обеспечению отказоустойчивости

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

системы. Данный подход предполагает решение следующих вопросов:

. дополнение ОС высокоуровневыми функциями обмена. Используемые в

большинстве ОС стандартные средства обмена данными, определенные

стандартом POSIX (каналы, сигналы, разделяемая память, семафоры), имеют

ограниченные возможности при взаимодействии процессов, не имеющих

родственных связей. Организация межпроцессного взаимодействия с помощью

механизма сокетов неудобна из-за необходимости привязки к конкретной

сетевой информации (IP- адрес узла, номер порта приложения) и своей

ориентированностью на модель клиент-сервер.

. введение приоритета для передаваемых сообщений. Важность сообщений,

передаваемых по сети, неодинакова. Например, сообщения об отказе какой-

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

оповестить узлы сети в кратчайшие сроки.

. выбор и реализация механизма голосования. При этом механизм

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

прикладного программиста.

Такая концепция построения операционной системы предусматривает

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

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

оптимальные маршруты для передачи функциональной и системной информации как

на начальном этапе инициализации системы, так и в процессе ее

функционирования при отказе тех или иных элементов и при подключении

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

при отказах и восстановлении работоспособности системы, модуль

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

данных. Рассмотрим их структуру и назначение подробнее.

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

Основная информация о функционировании операционной системы на данном

ПЭ размещена в системных таблицах.

Граф информационной связности процессорных элементов задаётся в

виде модифицированной матрицы связности. Отличие от стандартной матрицы

связности заключается в том, что в рамках одной строки, описывающей

связность данного ПЭ с другими, используется число «-1» в случае, если этот

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

связи (линка) по которому осуществляется эта связность в противном случае,

причем нумерацию линков для удобства можно начинать c m+1 узла, то есть для

узла m связь с узлом m+1 будет осуществляться линком с наименьшим номером.

Таблица 2.1

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

|№/№ |1 |2 |3 |4 |… |N |

|1 |-1 |0 |1 |2 |… |N-2 |

|2 |N-2 |-1 |0 |1 |… |N-3 |

|3 |N-3 |N-2 |-1 |1 |… |N-4 |

|4 |N-4 |N-3 |N-2 |-1 |… |N-5 |

|… |… |… |… |… |… |… |

|N |0 |1 |2 |3 |… |-1 |

В дополнение к таблице связности, должна существовать таблица

рассылки, в которой каждому ПЭ сопоставлен номер канала связи, по которому

надо передать пакет дальше, чтобы он в конечном счете дошёл до адресата.

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

если сеть неполносвязная или в ней произошли отказы связей, то таблица

рассылки, формируемая на этапе инициализации и реконфигурации системы,

позволит экономить время при обмене информацией или результатами

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

маршрутизации, структура и алгоритм работы которого будет рассмотрена ниже.

Приведем пример таблиц рассылки. Для наглядности возьмем сеть из

четырех ПЭ, представленную на рисунке 2.1.

[pic]

Рис. 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 маршрутизатор выполняет

следующие функции:

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

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

таблиц рассылки;

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

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

модуль маршрутизации можно представить в виде следующей упрощенной схемы:

[pic]

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

Во время инициализации, для каждого ПЭ составляется список текущих

соседних узлов системы для обмена результатами счета так, чтобы данные

каждого ПЭ присутствовали в тройном экземпляре в ВС.

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

по которому надо передать пакет дальше, формируются методом волны на основе

таблиц связности ПЭ. Маршрут выбирается минимальным по количеству рёбер

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

идентичны, то пакеты, проходящие через их связи можно считать одинаковыми.

Загрузка связи определяется по числу возможных транзитных передач через эту

связь, и транзитные передачи равномерно распределяются по узлам сети без

потерь на длине маршрута.

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

рассылки:

1. Заполняем таблицу рассылки в соотвествие со строкой с номером,

равным номеру процессорного элемента. Заполняем соответствующую

таблицу расстояний единицами (счетчик длины маршрута) в тех

ячейках, где есть прямая связь в таблице связности (>0).

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

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

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

локальным. Если таких больше нет, шаг 8.

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

маршрут был определен на предыдущем цикле. Если таких больше нет,

шаг 7.

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

его с локальным ПЭ и загрузку линка. Шаг 5.

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

в таблицу рассылки и таблицу расстояний.

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

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

Модуль реконфигурации активизируется и выполняет перестройку

системных таблиц ОС на основе информации о конкретном отказе. Рассмотрим

обработку отказа функциональной задачи, отказа канала связи и отказа

процессора целиком.

При этом приостановки работы системы в общем случае не должно

происходить из-за возможной необходимости в выдачи управляющих воздействий

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

этапе проектирования в зависимости от вычислительных ресурсов элементов

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

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

. Отказ канала связи. Первоначально корректируется матрица связности ПЭ.

При этом определяется, имеет ли отказавший канал связи отношение к

данному процессорному элементу. В случае, если после отказа канала связи,

какой-либо процессор оказывается изолированным, выполняется отключение

процессорного элемента.

. Отказ процессорного элемента. Обработка отказа всего процессорного

элемента выполняется посредством коррекции матрицы связности ПЭ, удаление

всех каналов связи.

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

элемента.

Реконфигуратор тесно связан с модулем маршрутизации и обращается к

нему сразу после изменения системных таблиц для коррекции таблиц рассылки и

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

может быть представлена на следующей схеме:

[pic]

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

После отказа функционального элемента, процесс реконфигурации

осуществляется по следующей схеме:

1. В таблице связности отказавший линк или линки отказавшего ПЭ

помечаются как недоступные.

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

да, то они отключаются.

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

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

резерва.

4. Производится активизация резервного ПЭ путем передачи ему кода

активизации, текущей таблицы связности и контекста задачи от

старшего ПЭ в ВС (например, от ПЭ с младшим номером).

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

Основной задачей этого модуля является организация информационного

обмена между процессами в системе, то есть передача информационных

сообщений между функциональными задачами и системных сообщений между

операционными системами разных ПЭ.

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

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

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

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

информации;

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

. проверка согласованности данных от резервированных источников

(голосование);

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

соответствующего сигнала модулю реконфигурации;

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

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

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

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

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

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

суммы);

. определение отказов физической среды передачи данных (проверка

подтверждений приема данных – “квитанций”);

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

передачи.

В своей работе модуль опирается на функции ввода-вывода нижележащего

модуля пересылки информации. Поскольку распределенная ОСРВ является

надстройкой над базовой ОС нижнего уровня, она не имеет доступа к

аппаратуре ПЭ и не может осуществлять ввод-вывод на основе обработки

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

1.3:

[pic]

Рис. 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), состоящей из пяти

узлов. Каждый узел изначально отличается от остальных только своим номером

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

[pic]

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

Физическая связь (линк) под номером 4 используется каждым ПЭ для

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

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

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

внутренняя структура ВС.

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

Для инициализации работы процессорных элементов используются

конфигурационные файлы, содержащие номер ПЭ и таблицу связности (таблица

2.8).

Таблица 2.8

| |№/№ |1 |2 |3 |4 |5 |

| |1 |-1 |0 |1 |2 |3 |

| |2 |3 |-1 |0 |1 |2 |

| |3 |2 |3 |-1 |0 |1 |

| |4 |1 |2 |3 |-1 |0 |

| |5 |0 |1 |2 |3 |-1 |

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

каждого ПЭ и текущая рабочая конфигурация каждого ПЭ по критерию связности,

в данном случае обмен результатами счета осуществляется следующим образом :

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

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

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

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

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

В штатном режиме функционирования ВС (при отсутствии неисправностей)

на выходе каждой копии функциональной задачи (т.е. в 5-и точках) путем

голосования на совпадение результатов подтверждается правильность

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

Представим теперь, что произошел первый отказ аппаратуры. Пусть

отказал канал связи между ПЭ1 и ПЭ3. Если при каком-либо отказе

процессорный элемент вообще не выдает результаты счета, то голосование

осуществляется с использованием соответствующих результатов систем

диагностирования (проверка КС, квитанций).

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

несовпадения результатов счета, представленные, для наглядности, в виде

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

Страницы: 1, 2, 3, 4, 5