Введение к работе
Актуальность проблемы. Развитие теории сетей Петри проводилось по двум направлениям. Прикладная теория сетей Петри связана главным образом с применением сетей Петри к моделированию систем, их анализу и получающимся п результате этого глубоким проникновением в моделируемые системы. Это требует хорошего знания предметной области применения, сетей Петри и методов теории сетей Петри. Чистая теория сетей Петри занимается разработкой основных средств, методов и понятий, необходимых для применения сетей Петри, для чего необходим прочный теоретический фундамент.
Теория сетей Петри широко применяется для моделирования и анализа поведения распределительных, вычислительных систем. В терминах сетей Петри достаточно адекватно выражаются многие важные явления параллельных вычислений, такие как взаимное блокирование процессов, состязательное распределение ресурсов, взаимное исключение доступа к ресурсам и другие.
Такие системы параллельной обработки информации, как многопроцессорные вычислительные машины, параллельные программы, моделирующие параллельные дискретные системы и их функционирование, мультипрограммные операционные системы, асинхронные электронные схемы и другие моделируются при помощи сетей Петри.
Помимо этого аппарат сетей Петри обладает большой гибкостью, позволяющей осуществлять моделирование параллельных вычислений в различных семантиках. В теории параллельных вычислений наиболее употребительными являются семантики чередования и частичного порядка. В семантике чередования параллельное вычисление представляется последовательностью действий, в которой параллельное выполнение нескольких действий подменяется недетерминированным выбором порядка их выполнения. В семантике частичного порядка на множестве действий устанавливается отношение частичного порядка, отражающее причинно-следственные и временные зависимости между событиями. Параллельно выполняемые действия при этом оказываются несравнимыми. Семантика чередования находит отражение в последовательностях срабатывания переходов сети, семантика частичного
порядка приводит к рассмотрению специального класса так называемых сетей происшествий, отражающих упорядоченность событий. Каждая из упомянутых, семантик обладает своими особенностями її достоинствами, и поэтому в целях наиболее полного анализа поведения распределенных систем необходимо иметь разработанную технику перехода от одной семантики моделирования параллельных вычислений к другой.
В моделировании и исследовании поведения сложной распределенной системы большую трудность представляет задача синтезирования всей глобальной информации о системе по времени, когда известна информация о каждом подпроцессе и нет буферной памяти для ее запоминания. Поэтому разработка необходимого формализма в сетях Петри для распределенных систем для определенного класса является актуальной.
Целью работы является разработка методов анализа сетей Петри для моделирования параллельных и распределенных систем на основе предложенного формализма сетей Петри, обеспечивающих эффективное поведение многовариантного анализа систем на этапе их алгоритмического проектирования. Для достижения поставленной цели необходимо решить следующие задачи:
-
Разработать формализм сети Петри для распределенной системы, функционирование которой может быть описано либо в семантике чередования последовательности срабатываний переходов, либо в семантике частичного порядка на множестве происшествий процесса. Установить соответствие между классами эквивалентности процессов и классами эквивалентности последовательностей срабатывания переходов в распределенной системе.
-
Создать размеченную переходную систему для распределенной системы для определения глобального состояния распределенной системы с использованием логических часов между событиями.
3. Разработать алгоритм сохранения глобальной информации в
моделируемой распределительной системе вычислений.
4. Разработать алгоритмы анализа сетей Петри для распределенных
систем.
Методы исследования. Исследования осуществлялись на основе: теории сетей Пстрн; теории алгоритмов; теории формальных грамматик и языков; формальной, предикатной логики; теории множеств.
На защиту выносятся результаты автора, имеющие научную новизну.
-
Исследована взаимосвязь в конкуренции (параллелизме) событий между двумя основными подходами при моделировании и анализе поведения распределенных систем в теории сетей Петри: первый подход привлекает понятие последовательности срабатываний переходов и соответствует семантике чередования параллельных вычислений, второй подход отражает понятие сети-процесса, соответствующее семантике частичного порядка.
-
Для класса сетей (без самоконкурирующих процессов) получены необходимые и достаточные условия, при которых сеть-процесс однозначно восстанавливается по заданной последовательности срабатываний переходов.
3. Введено описание формализма распределенной системы
вычисления в виде временной алгебры взаимодействующих процессов
сети Петри на основе предложенной размеченной переходной системы
без буферизации информации.
4. Разработка алгоритма для сохранения глобальной информации в
распределенных системах вычислений.
Научная и практическая ценность работы состоит в создании математических моделей и формализма анализа распределенных систем, создающих основу разработки программных комплексов в задачах спецификации и верификации дискретных параллельных. и распределенных систем.
Класс распределенных систем включает в себя не только вычислительные системы, но и распределенные системы управления в различных предметных областях.
Внедрение результатов работы. Результаты диссертационной работы использованы при выполнении НИР "Разработка теории сетей Петри в распределенных системах информации" (Институт информатики,
Ханой, Вьетнам) и в учебном процессе курсов моделирования Московского государственного горного университета.
Апробация работы. Основные результаты работы докладывались на:
- Международном семинаре по информационным технологиям
(Таиланд, 1990 г.);
- Международной конференции по моделированию распределенных
вычислительных систем (Польша, 1992 г.);
- Международной конференции по логическому управлению с
использованием ЭВМ (Россия, 1993 г.), на научных семинарах МГУ
факультета БМК, кафедрах высшей математики и вычислительных машин
МГГУ, института информатики (Ханой).
Публикации: Основное содержание работы отражено в 3 публикациях.
Объем и структура диссертации. Диссертация состоит из введения,
3 глав и заключения. Она содержит страниц машинописного
текста, включает рисунков и список литературы из 27
наименований.
