Теоретическая часть

Цель работы

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

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

Описание (спецификация) системы - это идентификация ее определяющих элементов и подсистем, их взаимосвязей, целей, функций и ресурсов, т.е. описание допустимых состояний системы.

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

Структура является связной, если возможен обмен ресурсами между любыми двумя подсистемами системы (предполагается, что если есть обмен i-й подсистемы с j-й подсистемой, то есть и обмен j-й подсистемы с i-й).

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

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

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

Модель системы представляется графом H=<G,H> с множеством переменных Х=x₁,...., x_n, N - общее множество вершин, множеством дуг G - упорядоченных пар номеров смежных вершин (i,j), G=(i,j)1,... (i,j)n. Общее количество таких пар обозначено как Q. Несмотря на всю компактность и удобство такой записи, на практике чаще используют матрицу смежности R = r_ij, показывающую наличие дуги между i-ой и j-ой вершинами.

Рис. 1. Модель системы в форме графа

Для приведенного на рис. 1 графа матрица смежности имеет вид:

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

Дата добавления: 2014-01-15