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

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

НГУЕН НГОК ТХУАН

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

05.13.16 - применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

Автореферат

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

Тверъ-1997

Работа выполнена на кафедре высшей математики Московского государственного горного университета и Института информатики, Ханой, Вьетнам.

Научный руководитель

академик РАЕН, МАИ, доктор технических наук, профессор С.А.РЦЦКОЗУБОВ

доктор физико-математических наук, доктор технических наук, профессор

Ведущая организация:

Московский государственный институт электроники и математики (технический университет)

Защита состоится " г. в 14 часов на заседании

диссертационного совета Д.-63.97.01 при ТвГУ по адресу: 110013, Тверь, ул.Желябова, 33.

С диссертацией можно ознакомиться в научной библиотеке Тверского госуниверситета.

Автореферат разослан " " Ъс^&яЗм^л 1997 г.

Ученый секретарь диссертационного совета Д.063.97.01 Кандидат физ.-мат. наук, доцент к Л ХИЖНЯК

Официальные оппоненты:

В А ГОРБАТОВ

кандидат физико-математических наук, доцент Н.Д.СИМАЧЕВ

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

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

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

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

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

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

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

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

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

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

3. Разработать алгоритм сохранения глобальной информации в моделируемой распределительной системе вычислений.

4. Разработать алгоритмы анализа сетей Петри для распределенных систем.

Методы исследования. Исследования осуществлялись на основе: теории сетей Петри; теории алгоритмов; теории формальных грамматик и языков; формальной, предикатной логики; теории множеств.

На защиту выносятся результаты автора, имеющие мучную новизну.

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

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

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

4. Разработка алгоритма для сохранения глобальной информации в распределенных системах вычислений.

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

Класс распределенных систем включает в себя не только вычислительные системы, но и распределенные системы управления в различных предметных областях.

Внедрение результатов работы. Результаты диссертационной работы использованы при выполнении НИР "Разработка теории сетей Петри в распределенных системах информации" (Институт информатики,

Ханой, Вьетнам) и в учебном процессе курсов моделирования Московского государственного горного университета.

Апробация работы. Основные результаты работы докладывались на:

- Международном семинаре по информационным технологиям (Таиланд, 1990 г.);

- Международной конференции по моделированию распределенных вычислительных систем (Польша, 3992 г.);

- Международной конференции по логическому управлению с использованием ЭВМ (Россия, 1993 г.), на научных семинарах МГУ факультета БМК, кафедрах высшей математики и вычислительных машин МГГУ, института информатики (Ханой).

Публикации: Основное содержание работы отражено в 3 публикациях.

Объем и структура диссертации. Диссертация состоит из введения, 3 глав и заключения. Она содержит страниц машинописного

текста, включает рисунков и список литературы из 27 наименований.

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

Приводится обзор и критический анализ методов моделирования распределенных систем и процессов, а также место теории сетей Петри в моделировании и проектировании распределенных систем.

На основе исследований существующих методов анализа процессов сети Петри (Петри С), временные сети (Мерлин П.), числовые сети (Джонатан Б.), Е-сети (Лауэр П., Ной Дж.), стохастические сети (Ямоун М.), Т-сети (Крупа Т.) выявлены недостатки:

- существующие сети Петри имеют большую мощность носителя соответствующего графа процесса;

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

(потеря наблюдаемой информации), что делает их неэффективными при формализации технических систем;

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

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

Определение 1.

Определение 2.

Определение 3.

Сетью называется тройка <5,Т,Р>, где 8 - множество мест, Т - множество переходов, а Рс(8хТ)и(Тх5) -отношение достижимости. При этом мы полагаем 5пТ—0 Тс<Зот(Р)псос1о1л(Р). Для всякого элемента геБиТ положим г°={г'ДРг'}; «г={г |гТг}. Сеть К=<8,Т,Б> назовем сетью происшествий, если транзитивное замыкание Р4* отношения Б иррефлексивно, и для всякого места 8еБ имеет место Ы<1, |<1. Для удобства отношение Б будем представлять иногда в виде функции Р: (5хТ)и(Тх5)-> {0,1}.

Сетью Петри назовем четверку К=<8,Т,Р,М>, состоящую из сети <8,Т, Р> и разметки М: Б—>-(0,1,2,...), указывающей количество фишек, помещенных в каждое место сети.

Пусть М - произвольная разметка сети К. Переход 1е'Г назовем М-активным, если М(Б)>0 для любого .че0и В этом случае разметку М' такую, чш М'(5)=М(8)-Р(в,0+Р(1,5) для любого яеЭ назовем Ь преемником М.

Последовательностью срабатывания переходов (Р-

последовательностью) сети Петри 1Ч^<8,Т,Р,М> назовем конечную или бесконечную последовательность 10, I], г?, ..., для которой существует последовательность разметок М°, М1, М2,... такая, что М°=М, и для каждого 1, ¡>0 переход является М'-активным, а М'+1 является

приемником М1. Множество всевозможных Б-последовательностей сети Петри N обозначим ЦГ4). Это множество определяет функционирование сети Петри в семантике чередования.

Для заданной сети Петри №=<3,Т,Р,М>, сети происшествий

N=<S,T,F> и функции маркировки р: 8иТ-»8иТ пару л =< 1\т,р> назовем процессом, если выполнены следующие условия:

(1)р($) £ 8,р(Т) с Т; (И)У5 е 5,М(Б) =

p-1(s)/4SoL г fleSo = -js'e Sj°s' = 0К

(iii)Vt e T,Vs е S,F(s,p(t)) = |p~'(s)/\°t| и |F(p(t),s)| = |p-4s)nt°|.

Переходы T в процессе тг мы будем называть происшествиями. На множестве происшествий процесса Tt=<N,p> введем отношение строгого

частичного порядка «хл> полагая, ti t2 (tl;t2) е F+. Частично упорядоченное множество (Т, -<к) будем называть характеристикой процесса п. Два процесса 71 j = <S],T],F|,P]> и Щ—<В2,Т2'^2'Рг> сети Петри N назовем сильно-эквивалентными, если существует биекция f: Т!->Т2 такая, что

(i)VteTi:Pl(t)=p2(f(t)); (iOVtSfeT^tHpfofit')^ f(t").

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

Указанную выше функцию маркировки р мы будем обозначить пате, а множество всевозможных процессов сети Петри N будем обозначать n(N). Функционирование сети Петри в семантике частичного порядка определяется совокупностью характеристик процессов из n(N).

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

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

Для последовательности происшествий р = процесса

% =< Ы,р> будем полагать р(Р) =р01),р(12),... Тогда для заданных Р-последовательности а и процесса % сети Петри N обозначим: 1лп(д)={а |а=пате(р), где Р - линейное упорядочение множества Т отношением <к, РгосГч!(а)={тг !аеЬш(и)}. Справедлива следующая

Теорема 1. Для заданной сети Петри N и последовательности переходов а включение аеЦ1Ч) справедливо в том и только том случае, когда аеЬт(тг) для некоторого процесса 7сеП(]Ч).

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

Для заданного множества переходов А обозначим Л*(А°>) совокупность всех конечных (соответственно, бесконечных) последовательностей элементов А Положим Аю=А*иАт. Пустую последовательность обозначим £, а множество всех префиксов последовательности аеА00 обозначим Рге £"(«). Для аеА°° и яеА обозначим #д<х число вхождений элемента о в а и будем полагать 0(а)={(йД) |#да>0 и 0<К#аа+1}.

Причинной зависимостью на А будем называть всякое рефлексивное бинарное отношение БсАхА. Для заданной последовательности аеА00

причинная зависимость Б порождает частично упорядоченное множество О(сх), гДе ' рефлексивное и транзитивное замыкание

отношения «, определенного следующим образом: (а,п)«(Ь,т) тогда и только тогда, когда п-ое вхождение а в а предшествует т-ому вхождению Ь и при этом (а,Ь)еО. Далее, для заданной причинной зависимости Б введем на множестве А00 отношение частичного порядка -<0, полагая, что для любой пары а,РеА°° сравнимость а^р имеет место тогда и только тогда, когда 0(а)=0(Р) и

Пример 1. Пусть А = [а,Ъ}, В={(а,а), (Ь,Ь), Оз,а}, (а)=(ааЬЬ)ю -ааЬЪааЬЪ..., Р=(йЬ)®=дЪйЬ... Тогда <х-<0р.

Для заданного отношения причинности D на множестве переходов А определим систему переписывания слов (А,Р), где PD={ab->ba|(a,b)eD}.

Теорема 2. (i) Если офеА*, то а-<оР тогда и только тогда, когда

«Др.

(ii) Если ареАю, то a~<Dp тогда и только тогда, когда 0(ос)=Ю(р) и при этом Vp'sPref f(P)3a,ePref(a)3yeA*:(a,¿>P'Yl-

Ha множестве А00 с фиксированной причинной зависимостью D определим отношение эквивалентности полагая a=Dp тогда и только

тогда, когда -<a,D=4p,D- Из теоремы 2 следует * *

а=роос_*р_>а.

Мы будем рассматривать отношение причинно зависимости D^ между переходами, определяемое сетью Петри N=<S,T,F,M> следующим образом:

Dn = {(t,t)|t е Г}и ^t'^fe T,(t°A°t'# 0}

Теорема 3. Для всякой сети Петри №=<S,T,F,M>-последовательности aeL(N) и процесса 7t=<(S,0(a),F,p>eProcNa-отношение на множестве О(а) не превосходит отношения т.е.

"^S-^DN-

Из теоремы 3 следует, что для заданной F-последовательности а некоторая информация о структуре процессов тсеРгос^-(а) может быть извлечена на основе анализа отношения

Пример 2. Для сети Петри N, изображенной на рис. 1, причинная зависимость определяется множеством (b,b), (b,a)}. Рассмотрим

F-последовательность a=(üb)*. Тогда ProcN(a) содержит единственный процесс тс, изображенный на рис. 2, причем О(а), -<a,DN является его

характеристикой.

Теорема 4. Пусть a-<D^p для некоторой сети Петри N, и aeL(N). Тогда PeL(N) и ProcN(a)cProcN(P).

5

а

bГ

v.

Рис.1

Рис.2 -

и

В дальнейшем мы ограничимся рассмотрением специального класса сетей Петри - так называемых сетей без самоконкурирующих переходов. Будем говорить, что переход t в сети N является самоконкурирующим, если существует процесс леЩТЧ), в котором происшествия (t,i), (t.j) несравнимы по отношению ■<к, для некоторой пары различных натуральных чисел ij. В частности, так называемые 1-безопасные сети Петри, в которых каждое место может быть размечено не более чем одной фишкой, не содержат самоконкурирующих переходов. При этом класс сетей Петри без самоконкурирующих переходов охватывает также все сети, в которых для каждого перехода t существует место S такое, что s°=°s={t} и М(.ч)<1. Пример сети Петри такого вида изображен на рис. 1. Легко видеть, что данная сеть не является 1-безопасной. Теорема 5. Если сеть Петри N не содержит самоконкурирующих переходов и oceL(N), то

^ гм =

a-UN ягРгосц(а)

Можно отметить, что теорему 5 нельзя распространить на класс всей сети Петри.

Теорема 6. Если сеть Петри N не содержит самоконкурирующих переходов и a,f3eL(N), то Ргосм(а)=ProcN((3), тогда и только тогда, когда шф.

Теорема 7. Если сеть Петри N не содержит самоконкурирующих переходов, то для любой F-последовагельности aeL(N) все процессы в Ргос^(а) сильно-эквивалентны тогда и только тогда 0(а), -^dn является

их характеристикой.

Таким образом, семантики чередования и частичного порядка совпадают для ограниченного класса сетей, включающего 1-безопасные сети.

В распределенной вычислительной сети рассмотрим состояние системы в момент действия процесса вычисления. Состояние системы в какой-то момент времени состоит из состояния локальных процессов в этот момент и состояния в каналах связи сети.

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

событий, когда два события имеют причинно-следственные отношения друг к другу и когда они конкурентны между собой. Таким образом, кооперирование, сравнение и синхронизация между процессами в асинхронном сообщении крайне затруднено, если в системе нет понятия общего основного времени системы • L. Lamport ввел это понятие, названное им логическими часами. Хотя логические часы Lamporta описывают причинно-следственный характер между событиями, однако они оказались достаточно неэффективны для решения некоторых задач: задачи исключения параллельных сообщений или оценки глобального состояния системы.

Пусть {pj, P2, Рп) есть распределительный способ вычисления, обладающий п процессами. Структура векторных часов для распределенной системы такова: время ставится в соответствие с событиями и регистрируется векторными часами, принадлежащими Nn такие часы называют векторными часами порядка п.

Пусть, каждый процесс pj, имеет часы 9j, их значения принадлежат Nn. Начальное значение Qj, есть (О, О, ...О) и после свершения каждого события pj, i-тая компонента 0j повышается на 1 до появления любого события на Pj.

Как в схеме Lamporta, каждое сообщение m из pj имеет временную метку точно соответствующую значению 9j, когда сообщение m послано.

Получение сообщения, обозначенного временной меткой через t, процесс воспринимает его время как: 0i=max(0i.t). Наконец, для любого события а, мы приписываем векторное время 0(a)=0j(fl), если событие а появляется в pj.

Показано, что для любого события a, 0(a)[i] - есть именно число событий от pj, появившихся до события a: 0(a)[i]= |Cjn(!a) I.

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

Теорема 8. Если 6: C->Rm есть векторные часы, характеризующие конкуренцию, то m > п, где п - число процессов в распределительной системе.

Рассмотрим конкретную модель распределенной системы как сеть процессов, соединенных канатами связи, по которым могут быть посланы сообщения. В такой системе имеются 3 типа событий: 1) IX О С ылхи сообщения, 2) получения сообщения; 3) внутренние события в процессе.

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

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

выбранного, то в новом глобальном состоянии готовое к выполнению (активное) действие т снова будет активно и может быть выбрано в

качестве очередного действия системы.

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

Для определения глобального состояния распределенной системы предлагается понятие временного сечения. Его основная идея заключается в том, что временное сечение рассматривается как разделение событий на два множества: первое множество содержит события, появляющиеся до временного сечения, а второе множество содержит события, появляющиеся после временного сечения. Частичный порядок описывает временное упорядочение событий(_^_).

Определение 4: Конечное множество В событий называется временным сечением, если выполняется следующее: если ееЪ и то ГеВ.

Предложен алгоритм определения временного сечения.

Разработана модель распределенной вычислительной системы в виде временной алгебры, где для удобства описания поведения системы введено понятие размеченной переходной системы.

Определение 5: Размеченной переходной системой называется тройка Р=(<5,—>,А), где 6 - множество конфигураций, А - множество меток, и->сС)хАхС? - переходное отношение.

Распределенная вычислительная система в данном рассмотрении состоит из атомарных процессов, не имеющих общей памяти и

работающих совместно с посылкой сообщений в каналах связи, где сеть связи предполагается связанной.

Определение 6: Распределенной вычислительной системой с N процессами называется набор

0=(РьР2,...,Рк, С,->& М), где

1) Р{=(ОЬ->1,АО - размеченная переходная система, называемая 1-ым процессом системы, О; - множество локальных состояний 1-го процесса, А - множество его локальных вычислительных действий;

2) С - множество коммуникаций действий систем, причем Гц есть получение сообщения ¡-го процесса от .]-го процесса, есть послание сообщения ¡-го процесса .¡-ому процессу;

3) М - есть матрица, у которой элемент Мц, находящийся на ¡-ой строке и .¡-том столбце, есть множество возможных сообщений от ¡-го процесса к 3-му процессу.

4) ->с есть размеченное переходное отношение на С:

^ ->с с О] х (Му х <20,

гщ->с £ х Мд) х Оь .¡=1,2,..„К

Определение 7: £д=А1 и {гу, эу, X,! j=l,2,...,N} называется множеством действий, выполненных процессом ¡, где X - пустое действие.

Множество А = £1 х £2 х... х называется множеством возможных действий системы. Поведение системы можно представить как множество последовательностей действий этой системы, т.е. это представляет вектор последовательности действия системы.

Определение8: Пространством состояний распределенной вычислительной системы Б является множество Б = х СЬ х--х С^ х Г, где Г - есть множество матриц у порядка ТЫЧ, у которых элемент ууеМу

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

Каждый элемент пространства Б называется полным состоянием этой системы, а первые компоненты называются состоянием системы.

Для распределенной вычислительной системы Б вводится понятие размеченной переходной системы для Б: Размеченной переходной системой для В называется система А), где —> определяется

следующим образом: Пусть

АЬ = (А! и {Х})х(А2 и {Л})х...х(Ац и {X}) АБ. = (Е^ и {Х})х(112 и М)х...х(Ык и (М)

АБ = (Б! и {>.})х(3, и {Х})х...х(8ы и М), Б^и^Ь 3 = 10,...,К

Определекие 9: Пусть поведение и "протяженные" состояния распределенной системы определяется как: Пусть

В = е УАБ(А)^ - ч для ц е 8} Я = й е 8|я0 - W 5 для W е УАБ(А)},

где Чо = есть фиксированное состояние, которое

называется начальным состоянием системы Б; (0 обозначает матрицу, имеющую пустую очередь в качестве его элементов).

Множества В, Я называются соответственно поведением, "протяженным" состоянием системы Б с начальным состоянием Ч о. Аналогично, множества

Вн = -¡^ 6 УА^А^ - W е Б} И

- £ е ^ ^ е )}

называются синхронным поведением и "протяженным" синхронным состоянием системы Б. _

Из определения системы Т следует, что если Чо ~~ ^ Ч > то W может быть представлена в виде а1а2---ак так, чтобы Чо _ а1 _а2 ->...■-ак -> як = q', причем а^" < ^ является элементом

множества А, имеющим только один компонент, который отличается от X.

Пусть

^ = (<1Г,Ч?,.",ч£,Ут)> П1 < к,

W = (WI,W2,...,WN).

Для того, чтобы связывать модель поведения с теорией сети, построим сеть появления для каждого элемента We В.

Пусть D - распределенная система вычислений, T=(S, ->, Л) размеченная переходная система системы D, есть начальное состояние системы и_В есть множество ее поведений как определено выше.

Для WeB, мы обозначим:

Init(W) = -р е B|W = Wb для ü е VAS(A)}

И называем это множеством всех начальных частей от W. На Init(W), мы определим следующие операции:

Й5Я _ _

W = W" = {%,%,..: ,W¿) е Init(W),

max(W',W") = (m ax( W,', W,"),..., m ax( WN, WN))

miníW, W) = (min(W,, Wj"),..., min(WN, WN)).

Причем для слов u, v на алфавите

и, если V есть префикс от и т&\'(и,\') = V, если и есть префикс от V

0, в противном случае

и если и есть префикс от V шт(и,у) = V если V есть префикс от и

0, в противном случае.

Следствие: множество Init(W) с определенными выше операциями

шах, min является совершенной конечной решеткой. _

Наша цель состоит в том, чтобы использовать множество Init(W) в представлении _всех возможных "прошлых" частей реализации (W) системы. Для WeInit(W), если мы называем каждое появление буквы в Wj,' событием, то структура этих событий выражает действие, выполненные локальными процессами и случайное отношение между ними. _

Рассмотрим W=(Wb...,Wi,...,WN)eB, где Wj=vfl, означает, что событие а выполнено процессом i (событие а появляется в Wj).

Обозначим через К.](уя) минимальную начальную часть поведения АУ, содержащую а.

Для простоты, мы будем записывать К^(д) вместо К[(уй), если а есть фиксированное буквенное появление в

Получим следующую теорему. Теорема 9. Пусть а'ач, где \¥рхЬу, где а - получение в \\>1 и Ь -соответственная посылка_получения а в Wj, значит #урс = тогда

Причем обозначает элемент множества А, все компоненты

которого есть X кроме того, что ьая компонента есть а. Теорема 9 является основанием алгоритма сохранения количества глобальной информации системы в процессах. Для проектирования алгоритма для общего случая, мы представим некоторые следующие определения.

Пусть Р - частичная упорядоченная решетка и функция Г:1пк(\у)-»Р; которая представляет знания глобальных свойств, полученных от К;(д), и удовлетворяющая условиям:

где - заданная функция из (1ш1:(\у)хА|) в Р, 1 = 1,2....,Ы.

Алгоритм сохранения глобальной информации ^ОДа)) в локальном состоянии 1-го процесса после того как этот процесс выполнил событие й, представлен как распределенная система О', по своему поведению эквивалентная системе Б. Глобальная информация ДК^а)) в интерпретации системы В' рассмотрена как один компонент состояния локального 1-того процесса после того, как он выполнил событие а. Теорема 10. Системы й и О' являются эквивалентными по поведению, т.е. В=В'. Далее, если (ч.ф^еСН, с1еЦУА8(А)) - локальное состояние процесса 1 системы О' после того как он выполнил событие а в исполнении имеющим результат \У, то <1=Г(К}(а)).

На основе разработанных методов и алгоритмов создан пакет прикладных программ.

К1 (а) = шахСК^),

Пакет прикладных программ состоит из диспетчера и операционной части. Операционная часть состоит из двух основных программных модулей, которые реализуют "Анализ" и "Симуляция". Кроме этих основных программ операционной части, имеются десять подпрограмм. Структура ППП изображена на рис. 3. "С ++" и реализована на ПЭВМ.

Разработанный пакет может работать как в автоматическом, так и в диалоговом режиме.

В работе разрабатывается распределенная модель технологического процесса обмена вагонеток в надшахтных зданиях по тупиковой схеме рис. 4.

Вытолкнутая из клети 1 толкателем 16 вагонетка с грузом через открытые стволовые предохранительные двери 2 откатывается по самокатным рельсовым путям к буферному отбойнику 5, минуя стрелки 3 и 4. Ударившись об отбойник, вагонетка движется в обратную сторону и, направленная стрелкой 3, устремляется к путевому тормозу 6, разгружается в опрокидывателе 7, перемещается к задерживающему стопору 8, компенсирует потерянную высоту на компенсаторе 9 и самокатом движется к отбойнику 10, минуя стрелку 11. Снова переменив направление от отбойника 10, через стрелки И и 12 вагонетка движется к путевому тормозу 13, а затем к стрелочному переводу 14. Оператор, находясь у пульта 18, направляет вагонетку к правой либо к левой клети. При этом вагонетка, проходя через путевой тормоз 15, останавливается на задерживающем стопоре 17, расположенном у ствола.

Вагонетка с материалами (оборудованием и т.п.), поднятая на поверхность и вытолкнутая из клети, после изменения направления движения при ударе об отбойник 5 направляется стрелкой 4 на обратный самокатный путь, по которому, минуя опрокидыватель, попадает на задерживающий стопор 8 и па компенсатор высоты 9. Затем, перемещаясь дальше, ударяется об отбойник 10, достигает стрелки 12, которая направляет ее к путевому тормозу 20 и после него в клеть подъемника 19. Подъемник опускает вагонетку на нулевую площадку.

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

Сеть Петри, соответствующая модели этого процесса, будет выглядеть, как на рис. 5.

. ■ ; /toy V«** ç^fcù*ujo /?/7/"»/4>j¿#»ft-ft

- Jüme

— tote

po'ih ■ ¿{<?{LOjh

-г : vos/ detpoih t

: гсЫ .1 koñtr

-P- ■i ¿crsf>y

« /г 'fe"

P«c. 4

Pue. S

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

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

Результат моделирования передается на этап алгоритмического проектирования систем логического управления с целью получения на этом этапе корректного закона управления.

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

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

4. Разработан алгоритм сохранения глобальной информации в моделируемой распределенной системе вычислений без буферизации на

основе предложенной процедуры временного сечения и векторного логического времени.

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

Основные результаты диссертации опубликованы в работах

1. Thuan N.N., Ban D.V., Hung D.V., How much information of concurrency

can be got from fïring Sequences in Pétri nets. Journal of Informatics and Cybernetics vol, №4, 1993, 34-46.

2. ВАЗахаров, H.H.Txyan, Д.В.Бан, Д.В.Хынг. О восстановлении сети процесса по последовательности срабатываний переходов сети Петри "Вестник Московского Университета, Серия "Вычислительная математика и кибернетика" № 2, 1997, 18-29.

3. Н.Н.Тхуан, Д.В.Бан, Д.В.Хынг, Ван З.Ч. Сохранение количества глобальной информации в локальных состояниях процессов распределенной системы. "Вестник Московского Университета, Серия "Вычислительная математика и кибернетика", № 2 1997, 38-44.

ВВЕДЕНИЕ

ГЛАВА I. НЕКОТОРЫЕ АСПЕКТЫ ТЕОРИИ СЕТЕЙ И ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

1.1. Состояние и переход

1.2. Сеть

1.3. Система условия/события (С/Е System) и процессы

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

II.I. Предикатное выражение и поведение сетей Петри II.I.1. Основные определения

1.1.1. Предикатное выражение и язык

1.1.2. Расширение проекции и синхронизация предикатов ILI.2. Сеть Петри и ее поведение

1.2.1. Сеть Петри

1.2.2. Композиция сети и ее процесс

1.2.3. Разложение системы и поведения атомарной сети

1.2.4. Поведение сети

ILII. Последовательности срабатываний переходов в сетях Петри и параллелизм внутри них II.II. 1. Причинная зависимость

II.II.2. Информация реальной конкуренции в последовательности срабатываний переходов сети Петри

ГЛАВА III. РАСПРЕДЕЛЕННАЯ СИСТЕМА ВЫЧИСЛЕНИЙ.

Введение

IILI. Некоторые определения и понятия

1.1. Вычисление распределенных систем

1.2. Временные часы и их некоторые свойства

1.2.1. Логические часы

1.2.2. Векторные часы и их свойства

А. Описание

Б. Свойство векторных часов

1.3. Методы описания распределенных систем 1.3.1. Взгляд пространство-время

L3.2. Вид интерливинга

1.4. Глобальное состояние распределенной системы.

1.4.1. Временная логика

A. Модель

Б. Семантика

B. Некоторые временные операторы

Г. Некоторые временные свойства программы

1.4.2. Глобальное состояние распределенных систем 1.4,2Л. Временное сечение

1.4.2.2. Глобальное состояние 1.4.3. Алгоритм Snapshos 1.4.3.1. Описание L4.3.2. Некоторые применения 1П.Н. Распределенная система вычисления

ПЛ. Распределенная система вычисления и ее размеченная переходная система IIЛ Л. Определения и свойства IIЛ.2. Пример

П.2. Глобальная информация распределенных систем вычислений

11.2.1. Глобальная информация в процессах системы

11.2.2. Алгоритм сохранения глобальной информации системы в локальном состоянии процесса

II.3. Моделирование горных технологических процессов

11.3.1, Технологический процесс обмена вагонеток в надшахтных зданиях

11.3.2. Модель сети Петри процесса обмена вагонеток

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

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

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

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

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

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

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

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

3. Разработать алгоритм сохранения глобальной информации в моделируемой распределенной системе вычислений.

4. Разработать алгоритмы анализа сетей Петри для распределенных систем.

Методы исследования. Исследования осуществлялись на основе: теории сетей Петри; теории алгоритмов; теории формальных грамматик и языков; формальной, предикатной логики; теории множеств.

На защиту выносятся результаты автора, имеющие научную новизну.

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

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

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

4. Разработка алгоритма для сохранения глобальной информации в распределенных системах вычислений.

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

Класс распределенных систем включает в себя не только вычислительные системы, но и распределенные системы управления в различных предметных областях.

Внедрение результатов работы. Результаты диссертационной работы использованы при выполнении НИР "Разработка теории сетей Петри в распределенных системах информации (Институт информатики, Ханой, Вьетнам) и в учебном процессе курсов моделирования Московского государственного горного университета.

Апробация работы. Основные результаты работы докладывались на:

- Международном семинаре по информационным технологиям (Таиланд, 1990 г.);

- Международной конференции по моделированию распределенных вычислительных систем (Польша, 1992 г.);

- Международной конференции по логическому управлению с использованием ЭВМ (Россия, 1993 г.), на научных семинарах МГУ факультета ВМК, кафедрах высшей математики и вычислительных машин МГГУ, института информатики (Ханой).

Публикации: Основное содержание работы отражено в 3 публикациях.

Объем и структура диссертации. Диссертация состоит из введения, 3 глав и заключения. Она содержит страниц машинописного текста, включает рисунков и список литературы из наименований.

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

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

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

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

1. Albersberg 1.J., Rozenberg G., Theory of Traces,

2. Theoret.Comput.Sci. 60 (1988), 1-82.

3. Bal H.E., Steiner J.G., Tanebaun A.S., Programming1.nguages for Distributed Computing Systems, ACM Computing Survey, Vol.21, No.3, September, 1989, 261-322 .

4. Best E., Concurrent behavior); Sequences, processes andaxioms, LNCS 197, 221-245.

5. Chandy K.M. and Lamport L., Distributed Snapshot:1. S-Ue

6. Determining the Global of Distributed Systems, Ann. Rev. Сотр. Sci. , Vol.2, 1987"", 37-68.

7. Charron-Bost В., Combinatories and Geometry of Consistent

8. Cuts, LNCS , Springer Verlag, 1989, 48-61.

9. Degano P., Gorriem, R. And Marchetti S., An Exercise in

10. Concurrency: A CSP Process as a Condition/Event System, LNCS , 1989, 85-105.

11. Fidge J. } Timestamps in message passing Systems thatpreserve the partial ordering, In Proc.11-th. Australian Computer Science Conference, 1988, 55-66.

12. Fridge C., Logical time in Distributed Computing Systems,

13. Computer, Vol. 24, No.8, August 1991, 28-33.

14. Goltz U. And Reisi^g W., The non-sequential behavior of

15. Petri Nets, Information and Control 57 (1983), 125-147.

16. Hoare C.A.R., Communicating Sequential processes, CACM21, 1978, 666-677.

17. Huhg D.V., Knuth E., Semi-Commutations and Petri Nets,

18. Theoret.Comp.Sci. 64 (1989), 67-81.

19. Hung D.V., A model for analyzing Distributed Systems,

20. Journal of Informatics and Cybernetics, Vol.1, N0.2,1^5^ 15-23.

21. HUNG D.V., BAN D.V., THUAN N.N., DUNG T.V., Maintainingthe Amount of Global Information in Local States of

22. Processes of Distributed Systems. Journal of Inaormatics and Cybernetics, Vol. 3, № 3, 1993, 34-42

23. Jojczyk K., Konieczny J., Kuzak Т., On Interleavingbehavior of PT-nets, Theoret"Comp.Sci. 64 (1989),25.38.

24. Keller R., Formal Verification of Parallel programs,1. CACM, 19, 1976, 561-572.

25. Lamport L. , Time, clocks and ordering of events in

26. Distributed Systems, Comm. Of ACM, 21,7, 558-564, 1978.

27. Mazurkiewicz A., Concurrent program schemes and their1.terpretation, DIAMI Report PB-78, Aarhus University, 1977.

28. Mazurkiewicz A., Semantics of Concurrent Systems: Amodular fixed point trace approach, LNCS 188, 353-357.

29. Mazurkiewicz A., Trace Theory, LNCS 255, 279-324.

30. Nielsen M., Plotkin G., Winskel G., Petri Nets, Event

31. Structures and domains. Theoret.Comp.Sci. 13 (1981), 85-108.

32. Pneuli A., The Temporal Logic of Programs, In 18-th Symp. On Foundation of computer Science 1977.

33. Shield M.W., Nonsequential behavior, Part I, Tech.Rept.

34. CSR-120-8 0 Dept.of Comput.Sci., University of1. Edinburgh, 1982.

35. Thiagarajan P.S., Some Aspects of Net Theory, LNCS 207,26.53 .

36. THUAN N.N., BAN D.V., HUHG D.V., How much information ofconcurrency can be got from firing Sequences in Petrinets .Journal of Inaormatics and Cybernetics, Vol. 3, № 4, 1993, 34-46

37. Winskel Q. , Event Structures, Petri Nets, LNCS 255, 325392, 1987.

38. В.А.Захаров, Н.Н.Тхуан, Д.В.Бан, Д.В.Хынг О восстановлении сети процесса по последовательности срабатываний переходов сети Петри. "Вестник Московского Университета, Серия "Вычислительная математика и кибернетика" № 2, 1997, 18-29

39. Н.Н.Тхуан, Д.В.Бан, Д.В.Хынг, Ван З.Ч. Созранение количества глобальной информации в локальных состояниях процессов распределенной системы. "Вестник Московского Университета, Серия "Вычислительная математика и кибернетика" № 12 1997, 38-54.