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

МО И ПО

РФ

Курсовой проект по ВКСС

Выполнил: Бобров Д.В.

Факультет: АВТ

Группа: АМ - 89

Новосибирск

2002

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

Отказоустойчивость является одной из главных целей разработки распределенных вычислительных систем – ВС РОИ. ЭВМ ВС РОИ взаимодейтсвуют друг с другом, через программно - управляемую сеть связи – сеть коммутации. Для того, чтобы ВС РОИ стали отказоустойчивыми, они снабжаются дополнительными линиямии связи.    Когда активная компонента системы выходит из строя, её задачи динамически передаются избыточной компоненте, таким образомпозволяя продолжать выполнение системных функций, возможно, в несколько урезанном виде. Такой тип динамической избыточности включает    три базовые процесса : диагностика (обнаружение отказа), системная реконфигурация и операторное восстановление.

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

          В целом, система представлена графом [1-5] , чьи вершины обозначают процессоры, а ребра -  линии связи.

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

1.1  Модель распределенного восстановления.

Рассматриваются системы, представленные ненаправленными графами, вершины которых обозначают процессоры, а ребра – линии связи. Назовем размеченный n – вершинный граф Gb  базисным. Он представляет в значительно упрощенной форме структуру системы, необходимой для выполнения заданного набора задач (программ).   Метки в Gb соответсвуют задачам, предписаных его вершинам.

Избыточный граф Gr  по отношению к Gb , который обозначается как Gr(Gb), имеет подграф, изоморфный Gb.

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

отказ в системе эквивалентен удалению из графа GR вершины x и всех ребер

инцедентных к x.каждая вершина в Gr имеет n + 2 возможных состояний: n ситуативных состояний или состояний задачи , обозначаемых метками 1,2,…n, неактивное или запасное состояние, обозначаемое «0» и состояние сбоя, обозначаемое как “-1”. Состояние S (GR) m – вершиной системы GR является m- ка S = (x1,…,xi,…xm) = (S(x1),…,S(xi),…,S(xm)), где S(xi) – состояние вершины xi.

          Конфигурация Gr графа Gr(Gb) есть помеченный граф, изоморфный GR, в котором каждая вершина x помечена в соответствии с ее состоянием.

          Конфигурация GR является правильной, если она содержит подграф GR изоморфный Gb, так что существует взаимооднозначное соответствие между меткой Gs и аналогичной Gb.

          В этом случае говорят, что Gs (Gb) являются М – изоморфными, что обозначается в виде Gs = mGb. Если конфигурация Gc является правильной, то подграф Gs соответствует активной  безотказной системе, выполняющей задачи, представленные разметкой ее состояний.

          Тогда можно сказать, что восстановление   -  это процесс, с помощью которого неправильная конфигурация преобразуется в правильную конфигурацию с помощью замены состояний вершин в Gr. Говорят, что GR будет К- отказоустойчивым (к - ОУ) с восстановлением t вершин (t  вв) по отношению к стратегии восстановления R, если с помощью стратегии восстановления систему можно восстановить после К или меньше отказавших вершин,заменой состояний на более t исправных вершин.   Таким образом, К является мером отказоустойчивости системы, а t  грубой оценкой времени ее восстановления.Если стратегия R позволяет восстановить  Gr  после сбоев, влияющих не более чем на К вершин графа Gr за Р шагов, то будем говорить G является Р – шаговой, к отказоустойчивой структурой по отношению к алгоритму   восстановления R.

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

         На рис.1.1 показана шестимашинная отказоустойчивая ВС (ОУВС).На рис. 1.2 а приведен избыточный граф Gr(Gb), с соответствующим ЭВМ системы, а ребра – непосредственным связям между ЭВМ. Базовый граф Gb – пятивершинный граф    Gs (рис.1.2 б).

          Пусть начальное состояние системы Gr  S(a,b,c,d,e,f) = = (1,2,3,4,5,0). Вершина f является резервной (избыточной).

          Граф Gc (рис.1,2 с) является начальной конфигурацией . Gc содержит подграф М – изоморфный Gb (на рис. 1.2 с выделена жирными линиями). Следовательно, конфигурация Gc является правильной.

Рис.1.1

Рис 1.2

Сбой F  в вершине G приводит к замене S на Sf = (-1,2,3,4,5,0) и дает конфигурацию Gc (Рис 1.2 д). Gc является неправильной конфигурацией, так как не содержит вершины, помеченой “I” и потому она не может содержать подграф М – изоморфный Gb.