Методика обнаружения и предотвращения блокировок процессов информационного обмена с использованием маркированных потоковых графов

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

Методика обнаружения и предотвращения блокировок процессов информационного обмена с использованием маркированных потоковых графов

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

The developed methods of detection and prevention of blocking of information exchange processes based on marked streamed graphs, allow to estimate steadiness and marking of network and to analyze not determined information exchange processes.

Основные трудности взаимодействия процессов информационного обмена (ПИО) связаны со взаимными блокировками (отсутствием сообщений во входных буферах, либо переполнением выходных буферов). В результате возникают ситуации «столкновения» процессов и состояние их «неопределенности» («голодания»), при приходе взаимоисключающих сигналов. Отдельные аспекты определения возможности и предотвращения блокировок рассматриваются в книгах [1,2]. Как в них показано, для решения данных задач целесообразно использовать различные модели, наиболее удобными из которых представляются потоковые [3].

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

Маркированным потоковым графом будем называть шестерку G = (V, X, Y, А, с, у), где V -- множество вершин (операторов программы); X и Y -- множества входных и выходных позиций вершин; А ? Y ? X -- множество информационных дуг; с: (X U Y)? V -- функция распределения позиций по вершинам; у: А?Lout ? Lin -- функция маркировки позиций. Здесь Lin и Lout -- множества меток соответственно входных и выходных позиций вершин, в том числе и фиктивных, инцидентных входам и выходам графа. При этом множество X включает подмножество ординарных позиций, каждой из которых инцидентна одна дуга, и подмножество позиций для альтернативного выбора входящих потоков данных (select, или slt). В множество Y включаются подмножество ординарных выходных позиций, а также подмножество позиций, соответствующих альтернативным переключениям (switch, или swh) и ветвлениям (fork, или frk) исходящих потоков данных. В общем случае входная позиция любой вершины v? V может быть ординарной или slt-позицией. Выходная позиция вершины v является ординарной, frk-позицией либо единственной выходной swh-позицией, которой инцидентно не менее двух информационных дуг. Этот случай соответствует условному ветвлению. Точкой входа в цикл является slt-позиция.

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

Рисунок 1 - Информационно-логический граф (а) и соответствующая М-сеть (б)

Данный аппарат позволяет представить ПИО в виде эквивалентных схем. Рассмотрим информационно-логический граф ПИО и соответствующий ему маркированный граф, называемый метаоператорной сетью (М-сетью) [7], изображенный на рисунке (информационные связи представлены сплошными дугами, логические -- штриховыми). Префикс «мета» означает, что здесь мы отвлекаемся от содержательного смысла операторов программы, перенося акцент на взаимодействие процессов, реализующих эти операторы.

В информационно-логическом графе (см. рис. а) вершины v1 -- v5 соответствуют операторам, которые связаны по данным и управлению (для организации условных ветвлений). Вершина М-сети -- метаоператор m, если ее выходные позиции являются ординарными или frk-позициями (на рис. б -- метаоператоры m1 -- m4). Вершина -- это тест t, или логическое условие, если она имеет единственную выходную swh-позицию (на рис. б -- тест t5). В М-сети метки из Lin, Lout -- натуральные числа. Метки выходных и входных позиций обозначают число производимых и потребляемых токенов в компонентах соответствующих сообщений. Для описания недетерминированных распределенных ПИО с каждым процессом ассоциируются входные и выходные буферы типа FIFO. Тогда метка позиции обозначает ширину буфера -- число токенов в компоненте сообщения. Набору операндов, связанных с определенным буфером процесса, соответствует одна позиция вершины и одна дуга М-сети.

Таким образом, представленная М-сеть охватывает и случай обмена сообщениями между процессами через каналы или очереди, подобно сетям процессов Кана [5]. Длина очереди, или глубина буфера, равна числу входных сообщений. Ширина буфера совпадает с числом токенов в компоненте сообщения. Число очередей (буферов) равно числу компонентов входного сообщения для соответствующего процесса. Токены от процесса-производителя пересылаются сразу же по мере формирования в соответствующие каналы процессов-потребителей. Процесс-потребитель инициируется лишь тогда, когда переданы все необходимые компоненты сообщения от процессов-производителей. Однако при этом в отличие от детерминированной модели Кана допускаются различные последовательности формирования токенов в компонентах и самих компонентов входных и выходных сообщений.

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

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

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

Бесконтурный маркированный потоковый граф G' = (V, X', Y, Е, с', у'), где Е ? Y ? X' - множество дуг, |E| = |A|, А -- множество дуг равносильного G' потокового графа G, X ? X', с': (X' U Y) ? V, у': Е ? Lout ? Lin, с заданной посредством порядковой функции нумерацией уровней l = 1,...,L называется L-уровневой сетью. Такой подход позволяет свести разметку любой М-сети к разметке равносильной безконтурной L-уровневой сети и, как следствие, задача анализа реализуемости потоковой модели распределенных ПИО, заданных М-сетью G, сводится к установлению существования стационарной и нахождению неизбыточной разметки L уровневой сети G', равносильной G [8].

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

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

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

ЛИТЕРАТУРА

1. Корнеев В.В. Параллельные вычислительные системы. -- М.: Нолидж, 1999. - 320 с.

2. Таненбаум Э. Архитектура компьютера. -- СПб.: Питер, 2002. -- 704 с.

3. Lee E.A., Sangiovanni- Vincentelli A. A framework for comparing models of computations // IEEE Trans, on CAD of Integrated Circuits and Systems. -- 1998. - V. 17, № 12. -- P. 1217-1229.

4. Топорков В.В. Структурно-динамические модели вычислений на метаоператорных сетях // Вестник МЭИ. -- 1994. -- № 2. -- С. 68-73.

5. Kahn G. The semantics of a simple language for parallel programming // Information Processing 74. N.-H. Publishing Company. -- 1974. -- P. 471-475.

6. Топорков В.В. Проблема разрешимости задачи анализа потоковых моделей программ // Программирование. -- 2003. -- № 3. -- С. 3-14.

7. Топорков В.В. Разрешение коллизий параллельных процессов в масштабируемых вычислительных системах // Автоматика и телемеханика. -- 2003. -- № 5. -- С. 180-189.

8. Najjar W.A., Lee E.A., Gao G.R. Advances in the dataflow computational model // Parallel Computing. -- 1999. - V. 25. -- P. 1907-1929.

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