Автоматика.
    Автоматизация.
        Электротехнические
            комплексы и системы.

УДК 004.652/.942

ИСПОЛЬЗОВАНИЕ АППАРАТА Е-СЕТЕЙ  ДЛЯ АНАЛИЗА РАСПРЕДЕЛЕННЫХ ПРОГРАММНЫХ СИСТЕМ

Дуравкин Е.В., Амер Таксин Каламех Абу Джаккар

Постановка задачи и актуальность. Анализ распределенных программных систем, как правило, сводится к выявлению состояний взаимоблокировок и тупиков [1]. Одним из средств, позволяющих проводить такой анализ, являются Е-сети. К основным  достоинствам данного аппарата можно отнести возможность описания параллельных взаимодействующих асинхронных процессов; возможность различной трактовки своих элементов по уровню абстракции (детализации), что позволяет строить иерархические модели, в которых переход может транслироваться в подсеть более низкого уровня детализации. Применение данного аппарата так же позволит оценить временные характеристики анализируемой системы (время реакции, пропускная способность). Одной из особенностей данного аппарата является способность анализа систем не только посредством имитационного моделирования (количественный анализ), но и аналитическими средствами (качественный анализ). Использование средств качественного анализа позволяет выявить последовательности разметок, приводящие к тупиковым и конфликтным, что и есть основным объектом исследования в данной предметной области. Имитационное моделирование, как правило, применяется для получения характеристик производительности системы.

Обзор литературы. В работах [2,3] рассматривались способы анализа сетей Петри методами качественного анализа. Однако Е-сети в своей топологии и логике работы имеют существенные отличия от сетей Петри (наличие переходов и мест нескольких типов, ненулевое время срабатывания переходов, взаимодействие со внешней средой и т.п.).  В [4] показано, что наличие у Е-сетей свойств безопасности, непротиворечи­вости (детерминированность) и живости позволит говорить о корректности работы анализируемой системы.

 Данная статья посвящена оценке возможности использования некоторых методов качественного анализа сетей Петри применительно к Е-сетям.

Основная часть. Формально Е-сеть задается как двудольный ориентированный граф, описываемый множеством:

,

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

Множества  удовлетворяют следующим условиям:

 (граф Е-сети должен содержать хотя бы один переход и одно место, причем вершина графа не может быть одновременно элементом множеств  и ).

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

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

Для обычной сети Петри такое уравнение имеет вид

,                                                                     (1)

где  – номер такта работы,  – разметка после  тактов работы,  – транспонированная матрица добавления меток в места

,                                                                                   (2)

при этом  – матрица обратных инцидентностей,  – транспонированная матрица прямых инцидентностей,  – управляющий вектор, компоненты которого равны 1, если условия возбужде­ния данного перехода выполняются в -м такте работы сети:

,                                                    (3)

где  – разметка места ,  – прямая функция инцидентности.

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

.                                                   (4)

Для получения возможности учета временных параметров срабатывания переходов в условие (3) необходимо ввести дополнительную переменную:

,                                      (5)

где  – функция срабатывания перехода инцидентного рассматриваемому месту.

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

.                                                                                       (6)

Из уравнений состояния можно получить соотношение

,                                                                              (7)

где  – любая достижимая разметка.

Отсюда вытекает смысл компонент вектора р-инварианта – это «весовые» коэффициенты меток в местах, характеризующие их распределение в сети. Доказано, что если все компоненты р-инварианта положительны, то Е-сеть ограничена. Такой р-инвариант называется р-цепью, а Е-сеть – инвариантной. Кроме того, можно определить t-инвариант  как решение матричного уравнения:

.                                                                                      (8)

Для t-инварианта верно соотношение

,                                                                        (9)

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

Одним из результатов рассмотрения уравнений состояния Е-сеть является возможность достижимости из начальной разметки , как решения системы матричных уравнений:

,                                                                    (10)

где  – транспонированная матрица обратных инцидентностей,  – единичный вектор,  – матрица инвариантов, получающаяся объединением векторов-строк фундаментальной системы решений уравнений (7). Решениями системы (10) являются тупиковые разметки. Рассмотренный метод целесообразно использовать с целью анализа на ограниченность (7) и на наличие тупиковых разметок (8). Преимуществами метода являются универсальность, то есть применимость к обычным Е-сетям без топологических ограничений, а также удобная, компактная математическая формулировка, облегчающая практическую реализацию. Однако возможности данного метода ограничиваются тем, что в нем сформулированы лишь достаточные условия, например, не для всякой ограниченной Е-сети существует полная р-цепь и т. д. Таким образом, данный метод предлагается использовать как проверочный на наличие свойства ограниченности и тупиковых разметок.

Другим методом, позволяющим проводить качественный анализ сетей Петри, является метод разложения на инвариантные и состоятельные подсети.

При использовании Е-сетей данный метод предполагает следующие ограничения:

1.                  Сеть должна относиться к подклассу ординарных, то есть:

.               (11)

В данной сети нет дуг с кратностью больше 1, и переход не может иметь цикличных дуг.

2.                  Сеть имеет цикличную структуру – каждый элемент входит в некоторый цикл.

Разметка в терминах данного метода называется переменной заряда сети:

,                                                                            (12)

где  – разметка -го места в момент времени , а  – число мест в сети.

В методе рассматривается так называемый вектор тока сети:

,                                                                       (13)

где  – вектор срабатываний переходов, компоненты которого равны числу срабатываний -го перехода к моменту времени . Элементы вектора соответствуют средним частотам срабатываний переходов за интервал времени , ,  – число переходов в сети.

Задержки задаются матрицей задержек:

.                                                                (14)

Отношения инцидентности задаются матрицей инцидентности :

,                                                                                  (15)

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

,                                                                            (16)

 ,                                                             (17)

где – множество векторов  таких, что t – инвариант сети  может быть представлен как линейная комбинация  с неотрицательными коэффициентами:

.                                                                 (18)

Такое множество векторов получило название генератора сети. Для нахождения решения уравнений (16) и (17) предложено разбиение сети на элементарные состоятельные и элементарные инвариантные подсети, покрывающие анализируемую Е-сеть. В качестве состоятельных удобно выбирать синхронизационные (маркированные) графы, а в качестве инвариантных – автоматные сети Петри. Такой выбор обусловлен простотой нахождения вектора , например, при указанных ограничениях, в случае автоматных инвариантных подсетей решением системы  является вектор . Каждая выделенная подсеть замкнута и циклична, что определяется условием равенства нулю суммы векторов – строк матрицы инцидентностей , соответствующих местам, вошедшим в подсеть. Число подсетей должно быть минимально. Разбиение на инвариантные подсети определяет генератор. Тогда решение уравнения (17) при известных задержках даст требования к начальной разметке, под которой обычно подразумевают ресурсы, или позволит определить максимальные токи, под которыми обычно понимают интенсивности заявок и т.д., в зависимости от постановки задачи. Аналитические зависимости, связывающие интенсивности потоков заявок, ресурсы, конфигурацию обслуживающего устройства и алгоритмы его работы, безусловно, наиболее желаемый результат сетевого моделирования. Возможность получения таких зависимостей – главное достоинство рассматриваемого метода. Однако применение его для исследования сложных распределенных систем затруднено по следующим причинам. Реализация метода для сложных Е-сетей большой размерности, особенно на этапах выделения минимального множества покрывающих инвариантных (состоятельных) подсетей и решения уравнения (17), трудоемка, требует перебора и анализа большого числа вариантов. Однако данный метод может использоваться для анализа некоторых частных алгоритмов.

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

1.                  Э. Таненбаум, М ван Стеен Распределенные системы. Принципы и парадигмы. – СПб.: Питер, 2003. – 877с.

2.                  Питерсон Дж. Теория сетей Петри и моделирование систем. – М. Мир, 1984. – 264 с.

3.                  Применение микропроцессорных средств в системах передачи информации: Учеб. пособ. для вузов по сп-ти АСУ/ Я. Советов, О.И. Кутузов и др. – М.:Высш. шк., 1987. –256 с.

4.                  Лосев Ю.И., Шматков С.И., Дуравкин Е.В. Применение методов анализа Е-сетей к моделям СОД // Радиотехника. – Х.: ХНУРЭ, 2003. - Вып. 132.– С. 64 – 69.