Развитие методов анализа сетей Петри для распределенных систем тема диссертации и автореферата по ВАК РФ 05.13.16, кандидат физико-математических наук Нгуен Нгок Тхуан

• Нгуен Нгок Тхуан
• кандидат физико-математических наук
• 1997

Оглавление диссертации кандидат физико-математических наук Нгуен Нгок Тхуан

ВВЕДЕНИЕ

ГЛАВА 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 секунд поиск одной конфликтной или тупиковой ситуации.

Список литературы диссертационного исследования кандидат физико-математических наук Нгуен Нгок Тхуан, 1997 год

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.