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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Получатель (номер ПЭ);

Отправитель;

Тип посылки (информационная или системная);

Размер информационной части посылки (может быть нулевой);

Контрольная сумма пакета.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4.1 Инициализация

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

Таблица 2.8

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

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

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

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

Таблица 2.9

№ ПЭ	Получены данные от ПЭ №	Данные от ПЭ №	Не совпадают с данными от ПЭ №	Возможная причина: Неисправность ПЭ № или Линк №
1	4 , 5			Нет неисправности
2	5 , 1			Нет неисправности
3	1 , 2	1	2 , 3	1 1-3
4	2 , 3			Нет неисправности
5	3 , 4			Нет неисправности

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

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

Таблица 2.10

ПЭ№	Данные голосования от ПЭ №	Возможная причина неисправности ПЭ № или Линк №	Вывод	Консолидированное решение
	1	Нет неисправности
	2	Нет неисправности
1	3	"мусор"	Неисправен Линк 3-1
	4	Нет неисправности
	5	Нет неисправности
	1	Нет неисправности
	2	Нет неисправности
2	3	1 1-3	Неисправен Линк 3-1
	4	Нет неисправности
	5	Нет неисправности
	1	"мусор"
	2	Нет неисправности
3	3	1 1-3	Неисправен Линк 3-1	Неисправен Линк 3-1
	4	Нет неисправности
	5	Нет неисправности
	1	Нет неисправности
	2	Нет неисправности
4	3	1 1-3	Неисправен Линк 3-1
	4	Нет неисправности
	5	Нет неисправности
	1	Нет неисправности
	2	Нет неисправности
5	3	1 1-3	Неисправен Линк 3-1
	4	Нет неисправности
	5	Нет неисправности

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

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

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

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

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

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

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

Таблица 2.11

	№/№	1	2	3	4	5
	1	-1	0	-1	2	3
	2	3	-1	0	1	2
	3	-1	3	-1	0	1
	4	1	2	3	-1	0
	5	0	1	2	3	-1

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

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

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

Таблица 2.12

№ ПЭ	Получены данные от ПЭ №	Данные от ПЭ №	Не совпадают с данными от ПЭ №	Возможная причина: Неисправность ПЭ № или Линк №
1	4 , 5	4	1 , 5	4 1-4
2	5 , 1			Нет неисправности
3	1 , 2			Нет неисправности
4 Вариант 1	2 , 3			«мусор»
4 Вариант 2	2 , 3	4	2 , 3	4 4-3 , 4-2
5	3 , 4	4	3 , 5	4 5-4

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

Таблица 2.13

Данные голосования от ПЭ №	Возможная причина неисправности ПЭ № или Линк №	Вывод	Консолидированное решение
1	4 4-1
2	Нет неисправности
3	Нет неисправности
4 Вариант 1	«мусор»	Неисправность ПЭ4	Неисправность ПЭ4
4 Вариант 2	4 4-3 , 4-2
5	4 5-4

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

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

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

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

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

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

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

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

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

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

	№/№	1	2	3	4	5
	1	-1	0	-1	-1	3
	2	3	-1	0	-1	2
	3	-1	3	-1	-1	1
	4	-1	-1	-1	-1	-1
	5	0	1	2	-1	-1

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

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

Таблица 2.15

№ ПЭ	Получены данные от ПЭ №	Данные от ПЭ №	Не совпадают с данными от ПЭ №	Возможная причина: Неисправность ПЭ № или Линк №
1	3,5	3	1 , 5	2 или 3 2-1 или 2-3
2	1,5			Нет неисправности
3	1,2		Нет совпадений	Недостаточно данных
5	2,3			Нет неисправности

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

Таблица 2.16

ПЭ№	Данные голосования от ПЭ №	Возможная причина неисправности ПЭ № или Линк №	Вывод	Консолидированное решение
	1	2 или 3 2-1 или 2-3
	2	Нет неисправности
1	3	"мусор"	Неисправен Линк 2-3
	5	Нет неисправности
	1	2 или 3 2-1 или 2-3
	2	Нет неисправности
2	3	"мусор"	Неисправен Линк 2-3
	5	Нет неисправности		Неисправен Линк 2-3
	1	"мусор"
	2	"мусор"
3	3	Недостаточно данных	Неисправен Линк 2-3
	5	Нет неисправности
	1	2 или 3 2-1 или 2-3
	2	Нет неисправности
5	3	Недостаточно данных	Неисправен Линк 2-3
	5	Нет неисправности

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 2.17

№ ПЭ	Получены данные от ПЭ №	Данные от ПЭ №	Не совпадают с данными от ПЭ №	Возможная причина: Неисправность ПЭ № или Линк №
1 Вариант 1	3,5	3	1 , 5	2 или 3 2-1 или 2-3
1 Вариант 2	3,5			Нет неисправности
2 Вариант 1	1,5			«мусор»
2 Вариант 2	1,5	2	1 , 5	2 1-2, 1-5
3 Вариант 1	1,2		Нет совпадений	Недостаточно данных
3 Вариант 2	1,2	2	1 , 3	2 2-3
5	2,3	2	3 , 5	2 2-5

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

Таблица 2.18

ПЭ№	Данные голосования от ПЭ №	Возможная причина неисправности ПЭ № или Линк №	Вывод	Консолидированное решение
	1	2 или 3 2-1 или 2-3
1 Вариант 1	2	"мусор"
	3	"мусор"
	5	2 2-5
	1	Нет неисправности	Неисправен ПЭ2
1 Вариант 2	2	2 1-2, 2-5
	3	2 2-3
	5	2 2-5
	1	"мусор"
3 Вариант 1	2	"мусор"
	3	Недостаточно данных
	5	2 2-5		Неисправен ПЭ2
	1	Нет неисправности	Неисправен ПЭ2
3 Вариант 2	2	2 1-2, 2-5
	3	2 2-3
	5	2 2-5
	1	2 или 3 2-1 или 2-3
5 Вариант 1	2	"мусор"
	3	Недостаточно данных
	5	2 2-5
	1	Нет неисправности
5 Вариант 2	2	2 1-2, 2-5	Неисправен ПЭ2
	3	2 2-3
	5	2 2-5

Рассмотрим процесс принятия решения ПЭ1:

Вариант 1: «Мусор» от ПЭ3 и данные ПЭ2 говорят о неисправности ПЭ2 или линка 2-1. Диагноз ПЭ5 подтверждает неисправность ПЭ2. Таким образом каждая запись в ПЭ1 прямо или косвенно говорит о неисправности ПЭ2 или его связей. В силу ординарности потока отказов принимается решение об отказе ПЭ2.

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

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

Рассмотрим деградацию системы после отказа линка 2-3. Топология системы представлена на рис. 2.7.

Рис. 2.7. Топология ВС после отказа линка 2-3.

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

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

Таблица 2.19

№ ПЭ	Получены данные от ПЭ №	Данные от ПЭ №	Не совпадают с данными от ПЭ №	Возможная причина: Неисправность ПЭ № или Линк №
1 Вариант 1	3,5	5	1 , 3	5 1-5
1 Вариант 2	3,5		Нет совпадений	Недостаточно данных
2	1,5	5	1 , 2	5 2-5
3 Вариант 1	1,2			Нет неисправности
3 Вариант 2	1,2		Нет совпадений	Недостаточно данных
5 Вариант 1	2,3	5	2 , 3	5 1-5, 3-5
5 Вариант 2	2,3			“мусор”

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

Таблица 2.20

ПЭ№	Данные голосования от ПЭ №	Возможная причина неисправности ПЭ № или Линк №	Вывод	Консолидированное решение
	1	Недостаточно данных
1 Вариант 1	2	5 2-5
	3	"мусор"
	5	"мусор"
	1	5 1-5	Неисправен ПЭ5
1 Вариант 2	2	5 2-5
	3	Нет неисправности
	5	5 1-5, 3-5
	1	Недостаточно данных
2 Вариант 1	2	5 2-5
	3	"мусор"
	5	"мусор"		Неисправен ПЭ5
	1	5 1-5	Неисправен ПЭ5
2 Вариант 2	2	5 2-5
	3	Нет неисправности
	5	5 1-5, 3-5
	1	"мусор"
3 Вариант 1	2	"мусор"	Недостаточно
	3	Недостаточно данных	данных
	5	"мусор"
	1	5 1-5
3 Вариант 2	2	5 2-5	Неисправен ПЭ5
	3	Нет неисправности
	5	5 1-5, 3-5

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

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

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

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

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

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

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



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

Таблица 2.21

№ ПЭ	Получены данные от ПЭ №	Данные от ПЭ №	Не совпадают с данными от ПЭ №	Возможная причина: Неисправность ПЭ № или Линк №
1	2,5			Нет неисправности
2	1,5	5	1 , 2	5 2-5
5	1,2	2	1 , 5	2 2-5

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

Таблица 2.22

ПЭ№	Данные голосования от ПЭ №	Возможная причина неисправности ПЭ № или Линк №	Вывод	Консолидированное решение
	1	Нет неисправности
1	2	5 2-5	Неисправен 2-5
	5	2 2-5
	1	Нет неисправности
2	2	5 2-5	Неисправен 2-5	Неисправен 2-5
	5	"мусор"
	1	Нет неисправности
5	2	"мусор"	Неисправен 2-5
	5	2 2-5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 2.23

ПЭ№	Данные голосования от ПЭ №	Информация от модуля коммуникации	Возможная причина неисправности ПЭ № или Линк №	Вывод
	1	Нет	5 1-5
1	2	Нет	5 2-5	Неисправен ПЭ5
	3

Страница:

•  1 
•  2 
•  3 

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

Подобные документы

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

  Основные характеристики систем реального времени, типы архитектур. Система приоритетов процессов (задач) и алгоритмы диспетчеризации. Понятие отказоустойчивости, причины сбоев. Отказоустойчивость в существующих системах реального времени (QNX Neutrino).
  
  контрольная работа [428,8 K], добавлен 09.03.2013
  

• Программирование реального времени

  Характеристики, основы применения, архитектура жестких и операционных систем реального времени. Последовательное программирование задач реального времени. Структура и языки параллельного программирования, мультипрограммирования и многозадачности.
  
  курсовая работа [195,9 K], добавлен 17.12.2015
  

• Основные понятия и программное обеспечение систем реального времени

  Классификация систем реального времени. Ядра и операционные системы реального времени. Задачи, процессы, потоки. Преимущества и недостатки потоков. Свойства, планирование, синхронизация задач. Связанные задачи. Синхронизация с внешними событиями.
  
  реферат [391,5 K], добавлен 28.12.2007
  

• Разработка системы реального времени в виде планировщика исполнения заданий

  Обзор требований проблемной области. Особенности управления задачами. Исполнительные системы реального времени. Программирование на уровне микропроцессоров. Модели и методы предметной области. Реализация прототипа системы реального времени.
  
  курсовая работа [263,1 K], добавлен 15.02.2005
  

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

  Рассмотрение основных принципов и методов проектирования систем реального времени. Описание конструктивных и функциональных особенностей объекта управления, построение диаграммы задач. Выбор аппаратной архитектуры, модели процессов-потоков, интерфейса.
  
  курсовая работа [1,2 M], добавлен 19.01.2015
  

• История развития операционных систем

  Операционные системы пакетной обработки, разделения времени, реального времени. Особенности алгоритмов управления ресурсами. Поддержка многопользовательского режима. Вытесняющая и невытесняющая многозадачность. Операционные системы и глобальные сети.
  
  реферат [55,0 K], добавлен 11.12.2011
  

• Управление задачами

  Планирование задач в операционной системе реального времени. Основные виды планирования применительно к задачам реального времени. Выбор приемлемого алгоритма планирования при проектировании RTS. Статическое прогнозирование с использованием таблиц.
  
  контрольная работа [40,7 K], добавлен 28.05.2014
  

• Работа с фильтрами в MS Excel

  Понятие и функции операционной системы. Основная особенность операционных систем реального времени. Работа с электронными таблицами. Фильтрация записей в таблице MS Excel. Установка пользовательского автофильтра в оборотную ведомость движения товаров.
  
  контрольная работа [547,8 K], добавлен 21.11.2013
  

• Применение SCADA-систем

  Современные SCADA-системы и их безопасность. Диспетчерское управление и сбор данных. Основные компоненты SCADA-систем. Система логического управления. База данных реального времени. Автоматическая конвертация проектов для разных операционных систем.
  
  реферат [253,7 K], добавлен 25.11.2014
  

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

  Определение необходимости применения средств промышленной автоматизации, контроллеров, промышленных сетей и компьютеров, операционных систем реального времени для повышения производительности предприятия. Концепция построения "интеллектуальных" зданий.
  
  контрольная работа [689,6 K], добавлен 13.10.2010
  

• Разработка методов оптимального проектирования ГРИД-систем

  Сущность концепции ГРИД-системы как типа суперкомпьютера, ее проектирование и эксплуатация, обзор существующих разработок. Подход к моделированию, описание образов состояний в пространстве признаков. Оценка отказоустойчивости, надежности и эффективности.
  
  дипломная работа [1,8 M], добавлен 16.05.2017
  

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

  Характеристика устройств реального времени: принципы их создания, виды, практическое применение к операционным системам для персональных компьютеров. Основные свойства системы LynxOS, поддержка приложений, сетевые возможности. Средства кросс-разработки.
  
  реферат [33,1 K], добавлен 02.12.2013
  

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

  История развития вычислительной техники. Понятие высокой готовности и отказоустойчивости системы. Разработка функциональной схемы отказоустойчивого кластера и структурной схемы виртуального стенда. Технико-экономическое обоснование объекта проектирования.
  
  дипломная работа [2,7 M], добавлен 26.02.2013
  

• Открытые магистрально-модульные системы реального времени

  Признаки открытой магистрально-модульной системы. Требования к УЭВМ. Основные группы открытых стандартов и протоколов ОММС. Требования к аппаратным средствам, модель и свойства архитектуры. Принципы работы шин. Конструктивное исполнение магистралей.
  
  презентация [2,0 M], добавлен 23.07.2015
  

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

  Инструментальные средства проектирования интеллектуальных систем. Анализ традиционных языков программирования и представления знаний. Использование интегрированной инструментальной среды G2 для создания интеллектуальных систем реального времени.
  
  контрольная работа [548,3 K], добавлен 18.05.2019
  

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

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

• Формирование дизайн-проекта в среде Apartment Environment с помощью Microsoft Robotics Developer Studio

  Визуальная среда моделирования в масштабе реального времени, типичные проблемы разработки робототехнических систем. Описание среды Apartment Environment, перемещение камеры по осям координат. Описание системы координат и алгоритма перемещения объектов.
  
  контрольная работа [2,1 M], добавлен 20.09.2010
  

• Фиксация времени выполнения программ

  Общая характеристика задач фиксации времени выполнения программ: выполнение процессов реального времени, профилирование. Программируемый интервальный таймер как весьма сложная система. Анализ основных функций, возвращающих стандартное время Windows.
  
  курсовая работа [82,7 K], добавлен 18.05.2014
  

• Особливості операційних систем реального часу

  Основні вимоги до операційних систем реального часу, забезпечення передбачуваності або детермінованості поведінки системи в найгірших зовнішніх умовах. Процеси, потоки та завдання, планування та пріоритети, пам'ять, переривання, годинники і таймери.
  
  реферат [29,4 K], добавлен 21.05.2010
  

• Создание программного комплекса для повышения доступности и отказоустойчивости информационной системы, разрабатываемой на предприятии ЗАО "Компания РОС"

  Разработка программного комплекса и описание алгоритма. Разработка пользовательского интерфейса. Анализ тестовых испытаний программного блока. Защита пользователей от воздействия на них опасных и вредных факторов. Режимы работы программного комплекса.
  
  дипломная работа [1,7 M], добавлен 14.03.2013
  

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

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