Моделирование процессов информационного обмена в АСУП на основе маркированных потоковых графов

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Моделирование процессов информационного обмена в АСУП на основе маркированных потоковых графов

Савенков А.Н.

Для распознавания и исследования свойств моделей протоколов информационного обмена широко используются различные графы. Метки, присваиваемые дугам или вершинам графа, представляют интересующие семантические свойства, а разметка графа - процедура сопоставления дугам и вершинам меток по заданным правилам. Разметка, определяемая иногда, как анализ информационных потоков (data flow analysis), является процессом сбора информации о свойствах графа, кодируемых элементами (метками) некоторого множества L. В контексте анализа под информационными потоками понимается не только передача операндов (данных), но и управления, синхронизация параллельных процессов и т. д.

Стандартное окружение для анализа представляет собой следующий набор: структурный граф G -- (V, А) информационного обмена с множеством V вершин и множеством А дуг.

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

Следующий компонент окружения -- алгебраическая структура в виде решетки (L, , ), нижней (L, ) или верхней (L, ) полуструктуры семантических свойств, где , _ операции пересечения и объединения на множестве меток (свойств) из L. Третья составляющая -- множество F монотонных функций : L>L, которые называют потоковыми функциями ли преобразователями свойств. Четвертой составляющей окружения для анализа -- это частичное отображение 2V 2A>F, сопоставляющее подмножествам вершин и дуг графа некоторую монотонную функцию .

Потоковая функция u может ассоциироваться с определенной вершиной uV графа G и представлять собой отображение входной информации (меток входящих дуг) в выходную информацию (метки исходящих дуг) вершины u. Пусть Iu, Ou L являются метками входа и выхода вершины u. Они связаны посредством потоковой функции Ou=u(Iu). Часто эту связь представляют так называемым потоковым уравнением вида

Ou=u(Iu) = Iu Pu Gu, или Ou=u(Iu) = Iu Pu + Gu,

где Pu, Gu L.

Таким образом, с графом связывается система из |V| потоковых уравнений вида:

или ,

где Pred(u) - вершина-предшественник u.

Разметка графа является стационарной, если свойства его дуг и вершин, не изменяются никаким применением правил разметки. Правило определяет характер замены меток на отдельных этапах анализа [5].

Рис. 1

Известны различные постановки и методы решения задач анализа размеченных графов [6]. При этом многие методы анализа основываются на исключении переменных, однозначно соответствующих меткам.

Пусть имеют место два потоковых уравнения:

,

.

Исключая переменную Ov из правой части уравнения Ни, получаем

.

Это равносильно тому, что в графе исключается дуга (v, u), а вместо нее вводится дуга (w, u).

Рассмотрим один из основных подхода к анализу графов на основе исключения переменных [6]. Пусть модель информационного обмена представлена потоковым графом на рис. 1, а.

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

Рассмотрим прямую задачу анализа, когда входная информация любой вершины определяется через объединение свойств выходов вершин-предшественников. Метод так называемого исчерпывающего (exhaustive) анализа позволяет получить такое решение, что метка выхода вершины г; графа полностью определяется параметрами Рu, Gu вершин, непосредственно доминирующих вершину v.

Отношение доминирования является рефлексивным и транзитивным. Оно может быть представлено деревом доминирования, или D-деревом. На рис. 1,б показано D-дерево, соответствующее исходному потоковому графу на рис. 1,а. Формой, занимающей промежуточное положение между потоковым графом и D-деревом, является DJ-граф (рис. 1,в). По сути это D-дерево, дополненное J-дугами, которые вводятся между парой вершин D-дерева, если ни одна из них непосредственно не доминирует другую. Так, на рис. 1,в J_дугами являются дуги (2, Е), (2, 4), (8, Е) и т.д.

В результате основные этапы исчерпывающего анализа состоят в следующем:

преобразование по определенным правилам DJ-графа в D-дерево;

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

3) «распространение» решений потоковых уравнений от корня D-дерева к остальным вершинам.

Рис. 2

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

Однако, дуги потокового графа не всегда являются однотипными и представляют либо передачу управления, либо передачу операндов и т. п. В так называемом k-кратном окружении для анализа потоковый граф процесса информационного обмена может содержать k типов дуг. На рис. 2 приведен пример такого графа.

Этот граф представляет процесс информационного обмена, образованный двумя потоками (линейными участками, состоящими из операторов 1,..., 4 и 5,. . ., 8), которые могут выполняться параллельно. Дуги управления упорядочивают выполнение операторов каждого потока. Частичный порядок выполнения операторов в процессе информационного обмена устанавливается с помощью дуг синхронизации, которые вводятся между вершинами, соответствующими Р- и V-операциям над бинарными семафорами s1 и s2 (на рис. 2 -- вершины 2, 5 и 8, 3). Семафоры позволяют синхронизировать действия параллельных процессов, управляющих потоками.

Так, при информационном обмене, граф которой показан на рис. 2, благодаря синхронизации оператор 2 всегда начинает выполняться раньше оператора 6, а оператор 8 - раньше оператора 4. Кроме того, в графе на рис. 2 показаны транзитивные дуги между вершинами, обозначающими операторы 2, 6 и 8, 4. С помощью этих дуг обеспечивается завершение выполнения тех операторов, которым предшествуют Р- и V-операции над семафорами. Оператор 2 устанавливает семафор s1, но не может непосредственно обусловить завершение выполнения оператора 6. Поэтому вводится специальная дуга (2, 6). По аналогии дуга (8, 4) символизирует завершение выполнения оператора 4 после изменения V-операцией (оператором 8) значения семафора s2. Таким образом, граф на рис. 2 содержит дуги трех типов. Следовательно, для каждой его вершины могут существовать три типа источников входной информации, являющейся передачей управления, синхронизацией или завершением обмена данными. Это приводит к необходимости введения k-кратного окружения для анализа (в данном случае k = 3). В таком окружении можно ставить и решать ряд задач анализа графов параллельных ветвей реализаций протоколов, когда результат выполнения какого-либо оператора зависит от типа входной информации. В окружение для анализа вводится множество L семантических свойств, состоящее из k-наборов элементов множества L. Решение задачи анализа, как правило, является неподвижной точкой k-кратного окружения.

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

Как правило, стационарность разметки обеспечивается структурой (полуструктурой) семантических свойств дуг и вершин графа, которые не увеличиваются в процессе разметки, либо свойствами самой модели, как в случае исследования достижимости и продуктивности вершин графа переходов схем Янова [2].

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

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

Литература

информационный поток маркированный граф

1. Гэри М.Р., Джонсон Д.С. Вычислительные машины и труднорешаемые задачи. - М.: Мир, 1982.- 416 с.

2. Ершов А.П. Об операторных схемах Янова // Проблемы кибернетики. Вып. 2-. - М.: Наука, 1967. - С. 181-200.

3. Еременко В.Т., Костин С.В. Алгоритмическое обеспечение отказоустойчивости информационно-управляющих систем // Наука и практика № 5 - 2004 г. - Орел: Орловский ЮИ. - С. 92 - 94.

4. Игнатущенко В.В., Подшивалова И.Ю. Динамическое управление надежным выполнением параллельных вычислительных процессов для систем реального времени // Автоматика и телемеханика. - 1999. - №6. - С. 142-157.

5. Капитонова Ю.В., Летичевский А.А. Математическая теория проектирования вычислительных систем. - М.:Наука, 1988. - 296 с.

6. Оре О. Теория графов. - М.: Наука, 1980. - 336 с.

Размещено на Allbest.ru