diplom (664611), страница 5

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

Текст из файла (страница 5)

Рис. 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), состоящей из пяти узлов. Каждый узел изначально отличается от остальных только своим номером в таблице связности.

Характеристики

Список файлов реферата