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

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

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

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

1. Диагностика системного уровня
2. Реконфигурация

Диагностика системного уровня включает (1) самодиагностику каждого узла и (2) диагностику соседей.

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

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

Структура ВС  описывается графом G (V,E), где V – множество узлов (процессоров),

 E – множество рёбер (дуг, каналов связи).

Мы рассматриваем системы распределённой обработки информации регулярной структуры [хорош.]

Такие структуры различаются по следующим параметрам (характеристикам):

1. Обмен сообщениями через шину или систему линий (каналов связи)
2. Видом структуры связи, её параметрами и ограничениями
3. Шириной – числом узлов на шину
4. Размерностью
5. Числом узлов
6. Числом линий или шин

 Некоторые структуры для систем большого масштаба представлены в таблице 1:

Наименование	Число узлов	Число линий(L) или шин(B)	Число портов на удл	Число непосредственных соседей
Cетка	N = WD	L = D * N	2D	2D
Двоичный n-куб	N = 2D	L = D * N/2	D	D
Тороидальный куб	N = D * 2D	L = 3 * D * 2D-1	3	3
Гиперкуб с шиной	N = WD	B = D * WD-1	D	D(n-1)
Гиперкуб с двойной шиной	N = WD	B = 2 * WD-1	2	2(W-1)

                                                                                                                                         Таблица 1

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

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

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

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

                                                                                                                             Рисунок 1

Идеальная структура G1 соответствует основным законам образования ВС.

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

Неповреждённая (безошибочная) структура  G3  описывается тем же законом, что и G1 и списком ошибочных компонентов за время  t_n.

Рабочая конфигурация GY определяет структур системы, требуемую для выполнения набора задач ‘T1.

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

                   G4      G3      G2     G1

Диагностика определяет ошибочные элементы в G3. На основе этого осуществляется реконфигурация в G4.

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

В общем случае каждый узел системы включает системное устройство, процессор(ы)

Обработки задач и некоторые общие ресурсы (ОП, ПЗУ, в/в).

Системное устройство (СУ) отвечает за приём и передачу сообщений и диагностику (собственного узла и вне узла - соседей).

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

Итогом самодиагностики будет специальный символ a_j  :

  a_j= 0, если V_j неисправен, узел V_j отключается от системы;

  a_j= 1, V_j исправен.

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

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

Диагностика соседей включает две составляющие :

1. Циклические тесты
2. Собственно диагностику

Идея первой фазы состоит в следующем. Каждый исправный узел V_i принимает результат теста S_j от неповреждённых непосредственных соседних узлов V_j и формирует контрольный вектор S(i, t_n) в момент времени t_n.

S_j = 1, если V_j исправен и объявляется как V_j.

S_j = 0, если V_j повреждён и обозначается как V_j по истечении некоторого проверочного интервала.

Это хорошо подходит для шинных структур ВС, использующих D*W тест-матрицу S(i, t_n).

Когда тествектор сформирован, или закончилось время испытания, то происходят сравнения полученного тествектора S(i, t_n) с предыдущим S(i, t_n-1). Если S(i, t_n)= S(i, t_n-1), то контрольная фаза заканчивается в узле V_i  за время t_n.

Если же эти векторы различны, то начинается второй этап – фаза диагностики, независимо от наличия неисправности в собственном узле или у соседей. Если же случайная (неустановленная) ошибка будет обработана, то для сравнения должен быть использован вектор  S(i, t_n-2).

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

Рассмотрим основные аспекты фазы диагностики.