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

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

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

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

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

Основные трудности взаимодействия процессов информационного обмена (ПИО) связаны со взаимными блокировками (отсутствием сообщений во входных буферах, либо переполнением выходных буферов). В результате возникают ситуации «столкновения» процессов и состояние их «неопределенности» («голодания»), при приходе взаимоисключающих сигналов. Отдельные аспекты определения возможности и предотвращения блокировок рассматриваются в книгах [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.

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

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

В информационно-логическом графе (см. рис. а) вершины 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