Развитие методов анализа сетей Петри для распределенных систем

• Автор: Нгуен Нгок Тхуан
• Шифр специальности: 05.13.16
• Научная степень: Кандидатская
• Год защиты: 1997
• Место защиты: Москва
• Количество страниц: 133 с.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ

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

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

1.2. Сеть

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

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

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

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

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

II.I.2. Сеть Петри и ее поведение

1.2.1. Сеть Петри
1.2.2. Композиция сети и ее процесс
1.2.3. Разложение системы и поведения атомарной сети
1.2.4. Поведение сети
II.II. Последовательности срабатываний переходов в сетях Петри и параллелизм внутри них .II.1. Причинная зависимость
П.П.2. Информация реальной конкуренции в последовательности срабатываний переходов сети Петри
ГЛАВА III. РАСПРЕДЕЛЕННАЯ СИСТЕМА ВЫЧИСЛЕНИЙ.
Введение
.. Некоторые определения и понятия
1.1. Вычисление распределенных систем
1.2. Временные часы и их некоторые свойства
1.2.1. Логические часы
1.2.2. Векторные часы и их свойства
А. Описание
Б. Свойство векторных часов
1.3. Методы описания распределенных систем
1.3.1. Взгляд пространствовремя
1.3.2. Вид интерливинга
1.4. Глобальное состояние распределенной системы.
1.4.1. Временная логика
. Модель
Б. Семантика
. Некоторые временные операторы
Г. Некоторые временные свойства программы
1.4.2. Глобальное состояние распределенных систем
1.4.2.1. Временное сечение
1.4.2.2. Глобальное состояние
1.4.3. Алгоритм БпарэБоз
1.4.3.1. Описание
1.4.3.2. Некоторые применения
1 Распределенная система вычисления
П.1. Распределенная система вычисления и ее размеченная переходная система
.1.1. Определения и свойства П. 1.2. Пример
.2, Глобальная информация распределенных систем вычислений
.2.1. Глобальная информация в процессах системы
.2.2. Алгоритм сохранения глобальной информации системы в локальном состоянии процесса
II.3. Моделирование горных технологических процессов
.3.1. Технологический процесс обмена вагонеток в надшахтных зданиях
.3.2. Модель сети Петри процесса обмена вагонеток
ВВЕДЕНИЕ
Актуальность


Распределенные системы, вычислительные или технологические, представляют собой пространственный параллелизм - это одновременное выполнение различных частей процесса (подпроцесса) на вычислительной технике или технологическом оборудовании. Параллельные подпроцессы всегда одновременно допускаются, а по завершении ждут окончания друг друга. Дальнейшее продолжение процесса возможно только после завершения всех параллельных процессов. Повторяемый (циклический) процесс с пространственным параллелизмом может запускаться повторно либо после своего завершения, т. В последнем случае имеет место конвейерное выполнение повторяемого дискретного процесса (конвейерный параллелизм), когда одновременно выполняются несколько “волнообразных” следующих друг за другом последовательностей операций. При их выполнении должен выполняться ряд требований -условий корректности процесса (отметим, что не модели процесса, а самого процесса). Во-первых, из свойства повторяемости (цикличности) процесса следует, что при его выполнении не должно возникать “тупиковых” операций, не имеющих продолжения и не позволяющих вернуться в исходное состояние. Во-вторых, хотя в конвейерных процессах и предусмотрены повторные запуски процесса во времени его выполнения, для некоторых операций это может быть недопустимо. Иначе операции могут повторно инициироваться лишь после своего завершения. В-третьих, параллельные процессы могут частично быть реализованы на одном и том же оборудовании, либо обращаются к общему ресурсу. Необходимо, чтобы при этом не возникали конфликты, когда, например, одновременно один из параллельных подпроцессов должен включать, а другой выключить оборудование, либо несколько процессов одновременно обращаются к общему ресурсу. При построении логических моделей надо стараться получить наиболее детальное отображение реального объекта, используя всю имеющуюся априорную информацию. Если при этом состав входной информации модели не позволяет достичь целей моделирования, следует пополнить объем сведений об объекте моделирования или пересмотреть цели моделирования. Анализ существующих подходов к моделированию. При проектировании и усовершенствовании больших и сложных систем, а также при поиске путей их наиболее рационального использования существенную роль играют методы сетевого анализа. Для моделирования и анализа систем логического управления на абстрактном уровне используются сети Петри и их развитие, например, трансформационные сети Крупа. Методы анализа систем можно разделить на две группы: исследование качественного поведения систем и количественная оценка их характеристик. Проблема установления формальных свойств моделирующей сети, таких как ограниченность, живость, справедливость, устойчивость, достижимость, относится к группе проблем динамического анализа. Существующие методы динамического анализа можно разделить на три группы: структурные методы; методы инвариантов и матричных уравнений; алгоритмы, использующие граф достижимых разметок. Методы анализа структурных подклассов СП высокоэффективны с вычислительной точки зрения, однако, в силу своей неуниверсальности требуют весьма жестких ограничений на графовую структуру сети. В практике требование адекватности модели зачастую расходится с пожеланиями к топологии сети. В последнее время сильно продвинулись вперед структурные методы упрощения СП для анализа: редукции, декомпозиции, абстракции и трансформации. В ряде случаев их применение позволяет свести анализ сети к тривиальной сети. Видимо, оправдано их применение перед произвольной процедурой анализа с целью сокращения размерности задачи. Однако, во-первых, большинство этих методов ориентировано на преобразования последовательных процессов, родственные методам теории автоматов, и поэтому при применении могут нарушить параллельную семантику исходной модели, во-вторых, сети зачастую не удовлетворяют структурным ограничениям этих методов и подбор нужного преобразования становится нетривиальной и не всегда разрешимой задачей. Методы инвариантов и теории матричных уравнений СП состоят в нахождении целочисленных решений систем линейных уравнений или неравенств с матрицей инцидентности сети.