Конечные разметки сети

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

Суть проблемы состоит в ответе на вопрос для данной конкретной сети - существует ли такая последовательность срабатывания переходов, которая приводит сеть к тупиковой разметке (т.е. разметке, при которой ни один переход не может сработать)?

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

Более того, анализ сети позволяет утверждать, что эта сеть всегда приходит к тупиковой разметке. Это математическое утверждение (теорема!) может быть строго доказано.

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

Например, утверждение: “ сеть на рис.3 всегда останавливается, когда все фишки собраны в позиции V2” - справедливо.

А похожее утверждение: “ сеть на рис.3 всегда останавливается, причем все фишки собраны в позиции V2” - не верно.

Свойство достижения конечной разметки присуще далеко не всем сетям. Например, на рис.4 приведен пример сети всегда приходящей к тупиковой разметке, на рис.5 - сеть никогда не “попадает в тупик”, на рис. 6 - сеть, которая может остановиться, а может и нет.

 

Ограниченность сети Петри

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

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

Если ни в одной позиции сети при любой последовательности срабатываний переходов количество фишек не превышает некоторого K, то такую сеть называют K-ограниченной.

Например, сеть на рис.7 является ограниченной - при любом срабатывании сети количество фишек в любой позиции не превысит 1. Заметим, что само функционирование этой сети - бесконечно. Т.е. у данной сети отсутствует тупиковая разметка.

Так же не достигается тупиковая разметка сети на рис.8. Однако эта сеть не является ограниченной - количество фишек в любой позиции может увеличиваться бесконечно.

 

Вопрос №12

 

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

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

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

Сеть Петри С = (Р, Т, I, О) с начальной маркировкой m называется строго сохраняющей, если для всех m'принадлежащих R(C, m):

Строгое сохранение требует, чтобы число входов в каждый переход должно равняться числу выходов |I(t_j)| = |O(t_j)|. Если это условие не будет выполняться, то запуск перехода изменил бы число фишек в сети.

Рассмотрим график сети Петри (рисунок 1), которая не является строго сохраняющей.

Рис.1. Сеть Петри, не являющаяся строго сохраняющей

В этой сети запуск перехода t₁ или t₂ уменьшает число фишек на 1, а запуск переходов t₃ или t₄ добавит фишку к маркировке. Эту сеть можно преобразовать в сеть строго сохраняющую (рисунок 2).

Рис.2. Строго сохраняющая сеть Петри

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

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

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

Вектор взвешивания w = (w₁, w₂, ..., w_n) определяет вес w_i для каждой позиции p_i, принадлежащей Р.

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

Сеть Петри С = (P, T, I, O) с начальной маркировкой m называется сохраняющей по отношению к вектору взвешивания w, где w = (w₁, w₂, ..., w_n), при n = | P |, w_i > 0, если для всех m', принадлежащих R(C, m):

Строго сохраняющая сеть Петри является сохраняющей по отношению к вектору взвешивания (1, 1, ..., 1). Все сети Петри являются сохраняющими по отношению к вектору взвешивания (0, 0, ..., 0).

 

Вопрос №13

На этом шаге мы введем понятия тупика и активного перехода.

Рассмотрим систему, включающую два различных ресурса q и r и два процесса а и b. Если оба процесса нуждаются в обоих ресурсах им необходимо будет совместно использовать ресурсы. Для выполнения этого требуется, чтобы каждый процесс запрашивал ресурс, а затем освобождал его. Предположим, что процесс а сначала запрашивает ресурсq, затем ресурс r и, наконец, освобождает и q, и r. Процесс b работает аналогично, но сначала запрашивает r, а затем q(рисунок 1).

Рис.1. Распределение ресурсов для случая двух процессов (a и b) и двух ресурсов (q и r)

Начальная маркировка помечает ресурсы q (Р4) и r (Р5) доступными и указывает на готовность процессов a и b. Одним выполнением этой сети является t₁ t₂ t₃ t₄ t₅ t₆; другим t₄ t₅ t₆ t₁ t₂ t₃. Ни одно из этих выполнений не приводит к тупику. Однако рассмотрим последовательность, которая начинается переходами t₁, t₄, а процесс а обладает ресурсомq, чтобы получить r; процесс b обладает ресурсом r, чтобы получить q.

Система заблокирована, то есть никакой процесс продолжаться не может. Тупик в сети Петри - это переход (или множество переходов), которые не могут быть запущены. В сети Петри (рисунок 1) тупик возникает, если нельзя запустить переходы t₂, t₅. Переход называется активным, если он не заблокирован (нетупиковый).

 

Вопрос №17

На этом шаге мы кратко опишем некоторые модификации сетей Петри.

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

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

Рис.1. Виды расширенных сетей Петри

Рассмотрим подробнее некоторые типы сетей Петри.

Ингибиторная сеть представляет собой сеть Петри, дополненную специальной функцией инцидентности I_IN: Р х Т -> {0, 1}, которая вводит ингибиторные (запрещающие) дуги для тех пар (p, t), для которых I_IN(Р, Т) = 1. Ингибиторные дуги связывают только позиции с переходами, на рисунках их изображают заканчивающимися не стрелками, а маленькими кружочками.

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

Например, используя ингибиторную дугу, можно промоделировать оператор условного вычитания (если x_i <>0, то x_i = x_i- 1) и получить фрагмент ингибиторной сети (рисунок 2).

Рис.2. Фрагмент ингибиторной дуги

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

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

В структурированных сетях некоторые из переходов являются сложными. При их срабатывании запускается сеть другого уровня иерархии (рисунок 3).

Рис.3. Структурированная сеть Петри

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

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

В цветных сетях вводится понятие цвета для фишек. В общем случае может быть n цветов. В вычислительной технике используются трехцветные сети (n = 3). Такие сети используются для моделирования аппаратных средств.

В сетях с изменяемой структурой кратность ребер не является постоянной.

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

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

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

Во временных сетях переходам ставится в соответствие их времена срабатывания, либо позициям ставится в соответствие времена нахождения фишек в позициях.

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

Предикатные сети - это сети с логическим описанием состояния системы.

Со следующего шага мы начнем рассматривать созданное приложение "Редактор сетей Петри" для моделирования систем.

 

Вопрос №20

Язык программирования СИМУЛА

 

Cимула (от SIMUIation LAnguage, т.е. язык моделирования специальный язык программирования, облегчающий доведение модели реальной системы до готовой компьютерной программы) семейство языков программирования, разработанных в Норвегии. Широкую известность и распространение получили языки Симула-1 и Симула-67. Они базируются на Алголе-60 и содержат его в качестве своего подмножества.

Язык Симула-1, появившийся в 1964 году, создан У.Далом и К.Нюгордом. Предназначен для моделирования систем с так называемыми дискретными событиями (например, систем массового обслуживания). Термин моделирование У.Дал определил в 1966 году как "процесс представления динамической системы моделью для получения информации об этой системе путем проведения экспериментов над моделью".

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

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

В 1967-1968 годах авторы Симулы-1 и присоединившийся к ним Б.Мюрхауг создали Симулу-67. Как утверждает Е.Киндлер, данный язык по своей "универсальности" ближе к таким языкам, как Алгол-68 и Ада, чем к языкам моделирования. Однако следует отметить, что все средства Симулы-1 являются частью языка Симула-67 и их можно использовать при помощи так называемого стандартного класса SIMULATION (моделирование).

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

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

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

В 1968 году У.Дал охарактеризовал язык так: "С помощью языка Симула-67 и вместе с ним языки моделирования влияют на основы математики. Язык Симула-67 выходит за традиционные рамки языков программирования и может служить основой, на которой строятся различные математические и естественно-научные теории от геометрии и алгебры до химической технологии и сельского хозяйства, даже в тех случаях, когда речь идет не об имитации и программировании, а лишь о получении количественной информации".

У нас язык Симула-1 был реализован на машинах "Урал-14" и БЭСМ-6, а Симула-67 — на БЭСМ-6, в моделях ЕС ЭВМ, в системах "Эльбрус-1" и "Эльбрус-2".