автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Причинно-следственные структуры и сети Петри: взаимосвязь и сравнительный анализ

ртв оа

2 * ИОЯ

На правах рукописи

Устименко Александр Петрович

ПРИЧИННО-СЛЕДСТВЕННЫЕ СТРУКТУРЫ И СЕТИ ПЕТРИ: ВЗАИМОСВЯЗЬ И СРАВНИТЕЛЬНЫЙ АНАЛИЗ

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

Автореферат диссертация на соискание ученой степени кандидата физико-математических наук

Новосибирск 1997

Работа выполнена и Институте систем информатики Сибирского отделения Российской академии наук.

Научный руководитель: кандидат физико-математических наук

Непомнящий В.А.

Официальные оппоненты: доктор технических наук,

Анисимов H.A.

кандидат физико-математических наук Викентьев A.A.

Ведущая организация: Институт программных систем РАН

(г.Переяславль-Залесский)

Защита состоится "11" ноября 1997 года в й час. ^Рмйн. на заседании диссертационного .совета К0003.93.01 в Институте систем информатики Сибирского отделения РАН по адресу:

630090, г.Новосибирск, пр. ак.Лаврентьева, 6'

С диссертацией можно ознакомиться в читальном зале библио- " теки ВЦ СО РАН (пр. ак.Лаврентьева, 6).

Автореферат разослан "Й" октября 1997 г.

Ученый секретарь

к.ф.-м.н.

М.А.Бульонков

ОБШАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность. Информационный прогресс сопременного индустри-1льного общества основывается на использовании параллельных и рас-тределенных систем. Чтобы успешно решать задачи анализа и верификации все более сложных систем, необходимо дальнейшее развитие \ совершенствование математических методов их исследования. Для решения этих проблем предлагались различные формальные модели и летоды, такие как автоматы и системы переходов, алгебры процессов, ЗСБ Р.Милнера, СЭР Ч.Хоара, структуры событий, истории срабатыва-шя А.Мазуркевича, деревья синхронизации и другие формализмы, а также многообразные их модификации.

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

Следует отметить, что п;>:т практическом применении сущестБую-[их методов и средств, разработанных на основе общепризнанных фор-альных моделей, обнаруживаются некоторые недостатки, связанные неадекватным представлением параллелизма или отсутствием нарядного графического представления. Стандартные сети Петри, со-

вмещал в себе наглядность и адекватное представление параллелизма не обладают удовлетворительными средствами композициональносп-и модульности.

В середине 80-х годов польский ученый Людвиг Чайл предложи/ новый формализм - причинно-следственные структуры (ПСС),- исполь зующий преимущества сетей Петри и дающий компактное алгебраи ческое представление для анализа поведения параллельных систем Эта модель, подобная в некотором смысле сетям Петри, имеет наглядное графическое представление, но в отличие от сетей граф причинно-следственной структуры имеет только один тип вершин - узлы. Взаимосвязи между узлами указаны в двух "индексах", приписанных каждому узлу и представляющих собой совокупность подмножеств узлов, обозначающих в верхнем "индексе" группы (альтернативные одна другой) предшественников данного узла, в нижнем "индексе" - 1'руппь: преемников данного узла. Эти индексы представляются двумя формальными полиномами с операциями сложения и умножения. Операция сложения моделирует альтернативный выбор вариантов передачу или получения активности данным узлом. Операция умножения моделирует синхронизацию передачи активности различными узлами е данный узел или из данного узла в группу независимых узлов.

В последнее время модель ПСС получила развитие в ряде зарубежных работ, которые посвящены анализу структурных, динамических и композициональных свойств ПСС. Была попытка обобщить операции + и *, определенные на множестве формальных полиномов, на множестве ПСС. Но, как отмечено, в частности, в работе Маджиолли-Щеттини и Маттеуси, в порожденной таким образом алгебре ПСС возникает ряд проблем: "непредсказуемость" операции +, порождение операцией * структурных дедлоков. Кроме того, в алгебре ПСС аксиома дистрибутивности операций сложения и умножения выполняется только при дополнительном условии. Поэтому открыта проблема построения "корректной" алгебры ПСС, что позволило бы из простейших базисных ПСС с помощью операций 4- и * конструировать произвольную ПСС.

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

>ткрыта проблема обратного отображении: выделение подкласса СП 1ли построение расширения класса Г1СС, равномощного класс}' CII в смысле строгой эквивалентности.

Актуальной является задача развития математического аппарата "еории причинно-следственных структур , в частности, важным пред-тавляется решение таких открытых проблем, как построение "коррект-юй" алгебры ПСС, различные расширения класса ПСС для лучшей [римепимости в прикладных областях. Актуальной так же являет-я задача установления взаимосвязей и сравнительный анализ раз-[ичных формализмов. В частности, важными открытыми проблемами вляются установление взаимоотношений между классами I1CC и СП, ключая такие известные раширения класса СП, как цветные, иерархи-[еские и временные СП; построение обратного отображения из класса /П в класс ПСС.

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

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

Научная новизна работы.

Проведен анализ алгебры ПСС и предложено обобщение класса СС - двухуровневые причинно-следственные структуры (ДПСС), что озволило разрешить две главные трудности, возникшие на данном гапе разработки теории ПСС, а именно:

- Построена алгебра ДПСС, замкнутая относительно операций слоения и умножения и свободная от ограничений алгебры ПСС: по-зждения дедлоков, непредсказуемости альтернативной композиции вух ПСС, ограниченности аксиомы дистрибутивности. Это позволяет взбить процесс анализа, конструирования и преобразования структур i. несколько более простых этапов.

- Показано, что для ДПСС обратное отображение из класса СП

в класс ДПСС является взаимно-однозначным и сохраняет строгугс эквивалентность. С другой стороны, класс ПСС строго эквивалентен подклассу так называемых максимальных ДПСС.

Кроме того, класс ДПСС, сохраняя компактность и композициональ-ность аналитического представления ПСС, имеет более наглядное графическое представление.

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

- Исследовано соотношение классов временных ПСС (ВПСС) и временных СГ1 (ВСП). Установлено, что каждая ВПСС имеет строго эквивалентную ВСП, заданную в согласованной с предложенной Чайя для ВПСС семантике времени.

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

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

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

- Введение семантики иерархически вложенных подструктур (ИПСС) существенно повышает компактность представления и свойство композициональности класса ПСС. Рассматривается расширение ПСС до иерархических структур по типу, предложенному для СП Кото-вым. В иерархических сетях Котова составными объектами являются переходы, но в ПСС соответствующие им компоненты срабатывания явно не заданы. В ПСС есть только один тип вершин - узлы, поэтому они и представляются как составные объекты. Это значит, что вводится два типа, узлов: локальные - моделирующие выполнение опре-

хеленного условия или наличие определенного ресурса, и глобальные ■ моделирующие некоторый выделенный процесс и содержащие в се->е некоторую иерархическую ПСС. Для того чтобы класс ИПСС мог >ыть сравним, в некотором смысле, с классом иерархических СП, глобальные узлы выделяются в некий особый подкласс узлов со своими ьксиомами для операций + и *.

Показана эквивалентность данных расширений ПСС известным рас-иирениям СП - раскрашенным СП в смысле Иенсона и иерархическим Ш в смысле Котова.

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

Участие и проектах. Представленные в диссертации исследования [роводились в рамках бюджетной темы "Исследование формальных юделей и методов описания семантики, спецификации и верифика-;ии параллельных и распределенных систем", номер гос. регистрации 1.9.60 002068; проектов Российского фонда фундаментальных исследова-ий, грант 93-01-00986; Международного научного фонда и Российского [равительства, грант JCP100; Фонда INTAS, грант 1010-СТ93-0048.

Апробация работы. Основные научные и практические результаты аботы подробно обсуждались на объединенных семинарах Институ-а систем информатики СО РАН и Новосибирского государственного ниверситета с 1993 по 1996 гг., докладывались на семинаре Институ-а программных систем (г. Переяславль-Залесский, апрель 1997) и на [еждународной конференции "Параллелизм, спецификации и програм-:ирование" (Варшава, Польша, 1995).

Публикация результатов работы. По теме диссертации опубликова-о 7 научных работ.

Структура и объем работы. Диссертация состоит из введения, че-ырех глав, заключения и списка литературы из 42 наименований. Основное содержание составляет 92 страницы. Работа включает 14 ри-унков.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

В первой главе дано краткое напоминание основных понятий теории гтей Петри и причинно-следственных структур, предложенных Чайя.

В разделе 1.1 даются определения стандартных сетей Петри и

предложенных В.Е.Котовым регулярных и иерархических сетей Петри

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

Графическим представлением сети служит двудольный ориентиро ванный граф.

Сеть Петри - это набор (Р, Г, Р, 1У, Мо), где (Р, Т, Р) - конечная сеть а И^ : Р —> Л'\{0} и Мо : Р —> N - две функции, называемые соответствен но кратностью дуг и начальной разметкой. Если кратность дуг рав на единице, то сеть называется ординарной. Функционирование сей Петри описывается формально с помощью множества последователь ностей срабатывания, или свободного языка сети Ь(Л'), и множеств; достижь.мых в сети разметок. Эти понятия определяются через пра вила срабатывания переходов в сети.

Алгебра регулярных сетей строится с помощью операций над сетя ми и класса элементарных сетей. Элементарная сеть - это сеть, со стоящая из перехода, помеченного символом из некоторого алфавита его головного и его хвостового мест. В формульном представлена элементарная сеть обозначается символом перехода а. Над регуляр ными сетями определяется несколько операций: операция наложения "," (параллелизм), операция разметки "п(/У)", вспомогательная опера ция слияния мест в сети, операция итерации "*", операция присоеди пения ";" (последовательная композиция), операция исключения "V (недетерми- нированный выбор).

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

Иерархическая сеть - это сеть, задаваемая структурной формулой которая строится из терминальных и нетерминальных символов с помощью операций алгебры регулярных сетей и упорядоченного множества определений нетерминальных символов. Каждое определени< имеет вид « : А, где 5 - нетерминальный символ, А - формула внутрен ней сети, обозначаемой данным нетерминальным символом.

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

1ершения составного перехода служит тот факт, что все его внутренние [ереходы пассивны и ни один из них не может быть активирован.

С разделе 1.2 напоминается семантика времени, предложенная Си-)акисом; приводится полуформальное определение одного из наиболее 1звестных расширений класса сетей Петри - сетей с цветными фишка-га (ЦСП).

При моделировании асинхронных систем с помощью сетей Петри гикак не учитывается длительность действий и то, насколько начало гействия отстоит от его завершения. Исходя из этого было предложено несколько расширений класса СП введением временного параме--ра. Сифакис предложил рассматривать дискретное, со значениями 13 вполне упорядоченного множества Тт, и независимое от работы се-■и время, связанное с разметкой мест сети. Длительность действий гри этом моделируется следующим образом: срабатывание перехода 1Гновенно, но поступившие в его выходные места фишки остаются не-юступными для последующих переходов в течении определенного, за-1анее заданного для каждого места времени.

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

В разделе 1.3 рассматриваются задачи анализа сетей Петри. Мы 1Ыделяем, прежде всего, те свойства сетей, которые остаются актуаль-1ыми для задач анализа причинно-следственных структур. Приводит-л алгоритм построения покрывающего дерева сети - важного инстру-1ента для анализа основных свойств сетей Петри.

В раделе 1.4 напоминаются определения предложенного Чайя фор-1ализма - причинно-следственных структур (ПСС).

Причинно-следственная структура - это ориентированный граф с юполнительной конструкцией на множестве его узлов. Она предста-1ляет собой полукольцо с операциями + и соответствующими неде-■ерминированному выбору и паралеллизму.

Каждому узлу графа приписаны два "индекса". Верхний - формаль-

ный полином, построенный (с помощью операций + и *) из имен предшественников данного узла; нижний - формальный полином, построенный из имен преемников данного узла. Каждый узел может находиться либо в активном, либо в пассивном состоянии. Если узел активен,тс он пытается передать активность одновременно всем своим преемникам, составляющим произведение в его нижнем полиноме, при условии их пассивности. Симметрично, если узел пассивен, то он пытается забрать активность одновременно у всех своих предшественников, составляющих произведение в его верхнем полиноме, при условии их активности. Таким образом, группы узлов должны "согласовывать" друг с другом возможность изменения их состояния. Если у какого-либо узла нет предшественников или преемников, то этот факт обозначается полиномом 0 в верхнем или нижнем индексе

Пусть X - множество узлов и (^{Х], +, *, 0) - почти-полукольцо формальных полиномов над X: алгебраическая система с заданными на ней аксиомами рефлексивности, симметричности и ассоциативности для операций сложения и умножения, условной дистрибутивности умножения относительно сложения (при условии, что оба слагаемых в левой части либо одновременно равны 0, либо ни одно из них не равно 0), и двух аксиом для 0, являющейся нулем для сложения и единицей для умножения. Тогда причинно-следственная структура над X - это пара (С, Е) функций:

С : X —► (причинная функция), Е : X —» ^[.Х] (следственная функция), таких, что х входит в полином С{у), если и только если у входит в полином Е(х). ПСС полностью представляется множеством индексированных узлов : 1 € -20-

Операции + и *, определенные над формальными полиномами, естественным образом переносятся на множество ПСС. На основе этого определяется понятие подструктуры на множестве ПСС: V - подструктура (/, если и только если V + V — V. Этот факт обозначается как V < [/; БиВ[и] — {V : V < £/}• Легко проверить, что < - частичный порядок.

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

Функции разметки в СП соответствует состояние 5 С X ПСС. Узел

активен при состоянии 5, если и только если г 6 5, и пассивен в ротивном случае.

Пусть для <5 Е РС[и] [СЗ] обозначает бинарное отношение на множе-тве всех состояний 6 [(?] <=>■ *<2 С я; <3* Пя = 0, < = («-'<Э) и ф*. Семантика [[/] ПСС {/ - это объединение отношений [У] = и [<2].

<Зегс[У]

Заметим, что условиеф'Пв = 0 есть требование безопасности в ПСС, .е. любой узел ПСС по определению не может содержать более одной ишки.

В разделе 1.5 напоминаются определения двух моделей времени, веденных Чайя для ПСС:

- время измеряется тактами;

- один такт времени соответствует одному срабатыванию в струк-уре, между двумя последовательными срабатываниями время "замо-ожено";

- каждому узлу приписано натуральное число, обозначающее:

) в случае семантики с минимальным временем задержки - наимень-[ее время, в течение которого фишка обязана оставаться в данном узле,

0 того как она может быть перемещена в следующий узел;

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

Все структурные определения остаются неизменными в модели со ременем, изменяются только семантические понятия. Как отмечает айя, ПСС с семантикой времени минимальной задержки не расши-«от выразительной мощности системы моделирования, но служат ишь для более компактной и удобной формы записи. Семантика с максимальным временем активности" существенно увеличивает вы-1зительную мощность ПСС, так как позволяет производить проверку

1 наличие фишки в узле ( т.е. проверку на 0).

Во второй главе ставится проблема обратного отображения из сетей етри в причинно-следственные структуры, приводятся определения вух типов эквивалентностей между сетями и структурами - сильной слабой; конструируется алгоритм построения множества компонент ¡абатывания по заданной причинно-следственной структуре и отобра-ения ПСС в СП; проводится анализ проблем, возникающих в алгебре СС, и формулируется задача, построения "корректной" алгебры ПСС.

В разделе 2.1 исследуются понятия строгой и слабой эквивалентности. Рашунас исследовал вопрос взаимоотображений ПСС с СП и пришел к следующим результатам: всякая ПСС имеет строго эквивалентную ей СП, но обратное утверждение не верно.

В сетях Петри строгая эквивалентность означает существование двух биекций: одна между множествами переходов в обеих сетях и другая - между множествами их мест. Более того, биекции должны сохранять входные и выходные множества каждого перехода и каждого места. Подобным же образом понимается строгая эквивалентность между СП и ПСС. Во избежание возникшей проблемы Рашунас. предлагает более слабую эквивалентность между СП и ПСС. Она получается заменой требования биективного соответствия между местами и узлами требованием биективного соответствия между классами эквивалентности, заданной на множествах мест и узлов. Таким образом, остается открытым вопрос - как выделить подкласс СП или построить расширение ПСС, чтобы между СП и ПСС сохранялась строгая эквивалентность.

В разделе 2.2 строится алгоритм I, отображающий ПСС в СП. Важной с практической точки зрения частью алгоритма является построение множества компонент срабатывания, которые явным образом в ПСС не задаются. На этом шаге алгоритма осуществляется итерация последовательно для каждого

На предварительном этапе строим для данного х £ X множество "предкомпонент" срабатывания ( "предкомпонент" потому, что они не полны, т.е. не замкнуты относительно всех причинно-следственных связей данной группы узлов, но по ним конструируются настоящие компоненты срабатывания) по числу слагаемых в следственном полиноме х, где каждая "предкомпонента" имеет х (с его г-тым следственным мономом-индексом) в качестве своего входного узла и множество выходных узлов (2'х = {у : у 6 ¿-¡(я)} (с их причинными полиномами, содержащими х), и расширяем его за счет альтернативных вхождений х в причинный полином членов из Я'х Для каждой из полученных "предкомпонент" производим итерацию из четырех этапов и двух проверок, в ходе которой строятся новые "предкомпоненты" и удаляются неудовлетворяющие признакам компонент срабатывания. Итерация продолжается до тех пор, пока из рассмотрения не будут удалены все "предкомпоненты".

На втором шаге алгоритм строит СП, заданную прямым отображением множества узлов ПСС на множество мест, множества компонент срабатывания на множество переходов с сохранением структурных свя-

зей в отношении инцидентности и начального состояния в начальной разметке.

Теорема 1. Алгоритм I строит для каждой ПСС строго эквивалентную ей СП.

В разделе 2.3 исследуются задачи анализа свойств ПСС.

Специфической особенностью ПСС является их "принудительная" безопасность, т.е. семантика не допускает акта срабатывания в ПСС, если в одном из выходных узлов данной компоненты срабатывания уже содержится фишка. Тем самым свойства безопасности и ограниченности выполняются автоматически. Свойство достижимости конкретного состояния ПСС, проблемы Д-включения и /¿-эквивалентности для ПСС разрешимы с помощью алгоритма простого перебора: покрывающее дерево ПСС конечно, следовательно, алгоритм перебора будет эффективен.

Алгебра ПСС, порождаемая определенными в разделе 1.4 операциями + и *, имеет ряд специфичных свойств. Операция + является "непредсказуемой" в том смысле, что она может порождать новые, непред-полагавшиеся компоненты срабатывания, т.е. существуют ПСС V и V такие, что V + V = но РС[!7] ф РС[\У]. А это значит, что опе-

рация недетерминированного выбора вариантов поведения двух ПСС порождает совершенно новые варианты поведения в результирующей ПСС. Потеря информации происходит при преобразованиях в полиномах, в частности при применении аксиом К + 9 = в + К = К и К + К = К. Для более тонкого различения ПСС предлагается сохранить полную форму записи, т.е. не применять в преобразованиях полиномов вышеуказанные аксиомы.

Операция * порождает структурные тупики, т.е. ПСС, не имеющие ни одной компоненты срабатывания и следовательно, не способные изменить ни одно своё начальное состояние. Почему возникает структурный тупик? Когда мы имеем дело с операцией Н— из-за потери информации в записи ПСС. Кроме того, причина., порождающая тупики, вызывает невыполнение аксиомы дистрибутивности в алгебре ПСС.

В главе 3 предлагается расширение класса ПСС до двухуровневых ПСС (ДПСС) введением второго синтаксического уровня.

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

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

Операция ф действует как объединение множеств верхнего уровня. В отличие от операции + над ПСС, она не сливает элементарные ПСС в одно множество индексированных узлов. На множестве ДПСС также есть операция которая действует как декартово произведение множеств верхнего уровня. На множестве элементарных ПСС операция ® имеет ту же семантику что и операция * на множестве ПСС.

Из-за своей двухуровневой специфики ДПСС не могут быть графически представлены в виде, подобном ПСС. Граф ДПСС будет иметь два типа вершин - непомеченные точки ветвления, соответствующие переходам в СП, и кружочки, помеченные именами узлов, но без причинно-следственных индексов. Взаимосвязи между узлами полностью задаются системой дуг, проходящих (кроме случая элементарных компонент срабатывания типа {а^х"}) через точки ветвления.

В разделе 3.1 понятие ДПСС вводится более формально.

В отличие от определения ПСС, нэ первом этапе вводится понятие множества мономов М[Х] над множеством узлов X, т.е. полиномов без операции +. Тогда безальтернативная причинно-следственная структура (БПСС) над X - это пара (С, Е) функций:

С : X —► (причинная функция),

Е : X —► М[Х] (следственная функция), таких, что i входит в моном С(у), тогда и только тогда, когда у входит в моном Е(х).

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

ВПСС есть частный случай ПСС при отсутствии операции +, поэтому для них сохраняется определение подструктуры,для ПСС. Тогда определение подструктуры на множестве ДПСС будет следующим: ДПСС U является подструктурой ДПСС V, если и только если каждая ВПСС из U является подструктурой какой-либо БПСС из V.

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

состояния й ЛПСС II и ее семантики [У] остаются неизменными по сравнению с аналогичными определениями для ПСС.

В разделе 3.2 вводится понятие алгебры ДПСС.

Базисными будем называть ДПСС, имеющие вид {ах,ха}.

Над множеством ДПСС определены две операции: операция недетерминированного выбора ф и операция Я результате получаем алгебраическую систему < ТС£[Х],ф,®,0 > (где ТСЕ[Х] - множество ДПСС), которая является коммутативным кольцом двухуровневых ПСС (с 0 в качестве 1).

Каноническая форма ДПСС - это сумма её минимальных подструктур. Построенная таким образом алгебра ДПСС является полной.

Теорема 2. Множество ДПСС замкнуто относительно операций ф и

Теорема 3. Всякая ДПСС может быть получена из базисных ЛПСС с помощью операций фи®.

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

Утверждение. Всякая ДПСС имеет строго эквивалентную ей СП.

Теорема 4. Всякая СП имеет строго эквивалентную ей ДПСС.

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

Очевидно, что всякая ПСС имеет строго эквивалентную ей ДПСС, представленную суммой ее компонент срабатывания. Но обратное не верно. Всякая ЛПСС может быть преобразована в ПСС согласно следующему определению (но при этом несколько ДПСС могут отобразиться в одну ПСС): Рассмотрим отображение Я из класса ДПСС в класс ПСС, которое оставляет неизменными все БПСС, а операции © и ® заменяет соответственно на операции 4- и ».Тогда ПСС I! — ЩУ) называется сверткой ДПСС V.

Две ДПСС называются структурно эквивалентными, если при свертке они отображаются в одну и ту же ПСС. На множестве структурно эквивалентных ДПСС задан естественный частичный порядок - отношение "быть подструктурой" и есть наибольший элемент - их сумма. Таким образом, в классе ДПСС можно выделить подкласс максимальных ДПСС.

Теорема 5. ДПСС имеет строго эквивалентную ей ПСС тогда и только тогда, когда она максимальна.

В четвертой главе конструируется алгоритм отображения класса

временных ПСС (предложенных Чайя) во временные СП и приводится пример его работы на модели однобитового протокола; строятся расширения класса ПСС - цветные ПСС и иерархические ПСС; конструируются алгоритмы их отображения в цветные СП и иерархические СП соответственно.

В разделе 4.1 конструируется алгоритм III отображения заданной временной ПСС (ВПСС) в строго эквивалентную ей временную СП (ВСП). При этом множества мест, переходов и отношение инцидентности задаются также, как во второй части алгоритма I. Временная начальная разметка сети тождественно равна начальному состоянию ВПСС. Временная функция Т»те[Я], тождественно равна временной функции Г[Л] в ВПСС.

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

Утверждение. Алгоритм III строит для каждой ВПСС строго эквивалентную ей временную СП.

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

Пусть мы имеем конечный набор цветов С/ = [1-"], и пусть -X, как обычно, есть множество узлов. ПСС с цветными фишками ( сокращенно ИПСС ) есть структура, в узлах которой одновременно может находиться несколько фишек, но разных цветов из набора С1. Однако такое представление ЦПСС потребовало бы разработки нового математического аппарата, в частности для алгоритма построения множества компонент срабатывания. Но мы можем задать расширенное множество раскрашенных узлов = {< г,! > /г е Л,» 6 [1. «]}. Тогда введение семантики цвета в ПСС будет представляться копированием каждого узла со всеми его связями в п экземплярах - по числу различных цветов, т.е. ПСС с раскрашенными узлами (сокращенно РПСС) есть обычные структуры, удовлетворяющие всем определениям ПСС, но их множество формальных полиномов Я[Лс;] задается над расширенным множеством раскрашенных узлов -Ус

Определяемые таким образом РПСС служат лишь удобной математической абстракцией для представления !ШСС. Формы представления семантики цвета в виде ЦПСС и РПСС легко преобразуются одна в другую.

Схема определений ППСС совпадает со схемой определений ПСС, исключая следующие отличия.

Множество полиномов и коммутативное полу-кольцо полиномов определяются над расширенным множеством раскрашенных узлов. Вводится вспомогательная операция умножения множеств С1 и Е[Л'с] ~ для явного представления цветных фишек в аналитической форме записи ППСС. Тогда причинно-следственная структура с цветными фишками (ЦПСС) над X - это пара (С, Е) функций:

С \ X С1 у. Р[Хс] (причинная функция),

Е : X —* С1 х Г[Хс] (следственная функция), таких, что < х,г > входит в полином ]С'{у) из С(у) = (у), если

и только если < у,; > входит в полином гЕ*(х) из Е(х). При этом индексу перед причинным полиномом С1 (у) означает, что узел у должен получить из групп узлов, заданных в С', фишку цвета у, соответственно индекс г перед следственным полиномом Е'(х) означает, что узел х, имеющий фишку цвета г, должен передать активность в одну из заданных в Е' групп узлов.

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

Компоненты срабатывания ППСС представляют собой множества не узлов, но пар - < узел, цвет >. В множестве РС[£/] (компонент срабатывания ППСС и) могут быть группы компонент срабатывания, имеющие совпадающие множества входных и выходных узлов, но содержащих фишки различных цветов. В ПСП каждая такая группа соответствует одному переходу с заданными на нем вариантами связывания (зависимости цветов фишек выходных мест от цветов фишек входных мест ). Назовем компоненты срабатывания из таких групп эквивалентными.

Состояние ЦПСС, в отличие от состояния ПСС, представляет собой множество пар < узел, цвет >, причем один и тот же узел может входить в него несколько раз, но с разными цветами. Такал запись позволяет сохранить неизменным для ППСС определение семантики ПСС.

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

ное отличие касается специфики определения операции ® на ДПСС.

В качестве примера строится ИПСС, моделирующая задачу п обедающих философов.

В разделе 4.3 строится алгоритм IV отображения цветных причинно-следственных структур в цветные сети Петри. Этот алгоритм представляет собой прямое отображение множества узлов ЦПСС на множество мест ЦСП, множества групп эквивалентных компонент срабатывания на множество переходов с сохранением всех структурных связей ЦПСС в отношении инцидентности ЦСП. При этом число вариантов связывания перехода равно числу эквивалентных компонент срабатывания в группе <3;, а каждый вариант связывания определяется соотношением цветов входных и выходных узлов одной из эквивалентных компонент срабатывания.

Теорема 6. Алгоритм IV для данной ЦПСС строит строго эквивалентную ей ЦСП.

Теорема 7. Каждая ЦСП имеет строго эквивалентную ЦЛПСС.

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

В разделе 4.4 представлена полицветная семантика операции *. Введенная в разделе 4.2 операция * исключает возможность одновременной передачи из одного узла (так же, как получения в один узел) двух и более разноцветных фишек. Кроме того, возможно порождение структурного дедлока. Это ограничение может быть снято, но за счет введения на множестве индексированных цветами полиномов С1 х F[Xc] дополнительной операции V - "не исключающего или", которая действует либо как операция + , либо как * - в зависимости от контекста. Это позволяет, за счет усложнения математического аппарата, добиться более компактного алгебраического представления. В повой семантике пример с обедающими философами можно упростить, сократив один узел и слив в одну две компоненты срабатывания: поевший философ возвращает в набор одновременно обе свои вилки.

В разделе 4.5 вводится понятие иерархических причинно-следственных структур (ИПСС). Мы рассматриваем расширение ПСС до иерархических структур по типу, предложенному для СП Котовым. В иерархических сетях Котова составными объектами являются переходы, но в ПСС соответствующие им компоненты срабатывания явно не заданы. В ПСС есть только один тип вершин - узлы, поэтому они и будут представляться как составные объекты. Это значит, что мы имеем два типа узлов: локальные узлы, моделирующие выполнение определенного условия или наличие определенного ресурса, и глобальные узлы, мо-

16

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

Глобальные узлы обозначаются прописными буквами А, В,С,., и имеют определение внутренней сети А : U, где U - ПСС, возможно содержащая глобальные узлы и полностью не зависимая от ПСС, содержащей А. Соответственно, множество полиномов F[X U Kg] определяется над объединением множеств обычных (локальных) и глобальных узлов X U Л'а-

В алгебраической системе А = (F^YUA'g], +, *, 0) есть две выделенные аксиомы K*D=B*K=B+K и К *{L* М) — (К * L) * М при условии, что ни один из полиномов K,L,M не содержит глобальных узлов. Они выражают собой тот факт, что активация или завершение работы внутренней структуры глобального узла есть неделимый акт, т.е. не может происходить одновременно, например, с передачей активности какому-либо локальному узлу. И ПСС над X U Ха - это четверка (С, Са, Е, Еа) функций: С : X —► F[X U A<j] (причинная функция), Е : X —► F[A'UA'g] (следственная функция), Са ■ Ха М\Х) (глобальная причинная функция), Еа ■ Ха М[Х] (глобальная следственная функция), таких, что х £ X входит в полином С(у), либо в моном Cq{A) тогда и только тогда, когда у, либо А входит в полином Е(х)-, и аналогично для А 6 Ха- А входит в полином С(г) тогда и только тогда, когда х входит в моном Еа(А).

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

{СЬ, Eh) + (Cg, El) = {Ch.Eh) U(Cl El).

V - подструктура U, если и только если V 4- U = U, либо существует U' - внутренняя ИПСС какого-нибудь глобального узла U, такая, что

V + U' = U'.

В отличие от ПСС, состояние ИПСС распадается на два подмножества- множество активных узлов s0 и множество внутренне активных глобальных узлов s,. Так, когда фишка попадает в глобальный узел, он становится внутренне активным и множество головных узлов его внутренней ПСС включается в подмножество активных узлов; когда же его внутренняя ПСС завершает свою работу, то он переходит в под-

множество активных узлов, а все активные узлы его внутренней ПСС становятся пассивными.

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

Показано, что семантика иерархических ПСС естественным образом переносится на класс ДПСС.

Теорема 8. Каждая ИПСС имеет поведенчески эквивалентную ей строго иерархическую СП при условии равенства начальных состояний систем.

Алгоритм V этого отображения строится в два этапа.

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

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

Основные выводы и результаты, полученные.в диссертации: 1. Исследована взаимосвязь нового формализма для моделирования параллельных дискретных систем и процессов - причинно-следственных структур - с сетями Петри. Формализован алгоритм, предложенный Л.Чайя, отображающий класс ПСС в класс СП в смысле строгой эквивалентности. Важной практической частью алгоритма является этап построения по аналитическому представлению ПСС множества ее компонент срабатывания, являющихся аналогом переходов в СП.

2. Проведен анализ возникающих в алгебре ПСС проблем: порождение структурных дедлоков; генерация "лишних", не соответствующих логике функционирования объединяемых операцией + подструктур вариантов поведения; невыполнение аксиомы дистрибутивности операции * относительно операции +.

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

алгебре ДПСС не возникают проблемы, характерные для алгебры ] 1С С. Это позволяет, в частности, решить проблему обратного отображения: каждая сеть Петри имеет строго эквивалентную ДПСС, т.е. класс ДПСС, в отличие от класса ПСС, равномощен классу СП. Доказаны теоремы о полноте и композициональности алгебры ДПСС.

Доказана теорема о равномощности, в смысле строгой эквивалентности, подкласса максимальных ДПСС классу ПСС.

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

Публикации по теме диссертации

1. Уетименко А.П. Моделирование причинно-следственных структур Чайя в терминах регулярных сетей Петри// Проблемы теоретического и экспериментального программирования- Новосибирск,1993.-

2. Ustimcnko А.P. Mapping of time cause-effect. structures into time Petri nets// Specification,verification and net models of concurrent systems.- Novosibirsk, 1994,- P.99-115.

3. Уетименко А.П. Алгебра причинно-следственных структур// Проблемы спецификации и верификации параллельных систем- Новосибирск, 1995,- С.50-64.

4. Ustimenko А.P. Algebra of Two-level Cause-Effect Structures// Proceedings of the Concurrency Specification and Progranmiing'95 Workshop.- Warsaw,1995.-

5. Ustimenko A.P. Algebra of Two-level Cause-Effect Structures// Inform.Proc. Lett..- 1996,- Vol.59.- P.325-330.

6. Уетименко А.П. Отображение временных причинно-следственных структур во временные сети Петри// Кибернетика и системный анализ,-

Киев, 1997,- N2,- С.44-54.

7. Уетименко А.П. Причинно-следственные структуры с цветными фишками,- Новосибирск, 1997,- 22 С.- (Препр. ИСИ СО РАН: N39).

С.60-72.

Р.176-189.

Подписано и печать 06.06.97г. Формат бумаги 00 х 84 1/16 Объем 1.1 уч.-изд.л. Тираж 100 акз._Заказ 71

Ротаиушнч НИ СО РАН, Новосибирск-97