Недостатки и достоинства матричного подхода

Матричный подход к анализу сетей очень перспективен, но имеет и ряд недостатков. Матрица D сама по себе не полностью отражает структуру сети, так как встречные дуги между переходом и позицией взаимно уничтожаются в матрице. Кроме того, в векторе запуска переходов f(σ) отсутствует информация о последовательности запуска переходов. Это приводит к тому, что одному и тому же решению уравнения можно поставить в соответствие несколько последовательностей запуска переходов.

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

Задачи, решаемые сетями Петри

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

Задача о взаимном исключении

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

З адача о производителе/потребителе

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

Задача об обедающих философах

Задача была предложена Дейкстрой. За едой философы сидят за круглым столом, в центре которого стоит большая миска спагетти. На столе лежит пять вилок, по одной между соседними местами. Каждый философ должен сначала взять вилку слева и справа, а затем приступать к еде. Возможна ситуация, в которой каждый философ возьмет вилку слева, а затем будет ждать, когда освободится вилка с правой стороны. Так они будут ждать, пока не умрут от голода. Тем самым, это состояние системы «обедающие философы» является тупиковым.

Асинхронный процесс, как модель дискретной динамической системы. Виды асинхронных процессов.

Дискретная динамическая система – система, рассматривающая последовательность событий в реальном времени.

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

Асинхронный процесс – это модель ДДС, состоящая из множеств {S, F, I, R}, в которой

S – непустое множество ситуаций (состояний),

F – отношение между ситуациями, F S×S, т.е. в процессе могут быть события, не являющиеся ни инициаторами, ни результантами.

IS – множество инициаторов (входных сигналов), подмн-во ситуаций, активизирующих процесс:

– для любого iI существует sS такое, что iFs;

– для любого iI существует sS\I такое, что sFi,

– для любого iI, если iFs_k и s_kS\I, то для s_p, s_kFs_p→S_pI.

RS – множество результантов (выходных сигналов):

– для любого rR, если rFs, то sR;

– для любого rR не существует sS/R такого, что rFs (т.е. результант не м/б инициатором).

Допустимая последовательность ситуаций. Траектория АП.

Рассмотрим последовательность ситуаций s₁,s₂,…,s_k,s_k+1,…, где s_k элемент стоит на k-м месте. Для АП можно составить множество последовательностей ситуаций, где для любого kN справедливо s_kFs_k+1, таких, что ни одна из последовательностей не является частью другой. Это и есть допустимые последовательности ситуаций. Каждая допустимая послед-ть ситуаций описывает траекторию АП.

Автономный процесс – процесс, в котором не существует инициаторов и результантов.

Классы эквивалентности

Е – отношение эквивалентности такое, что:

– для s_i, s_jS, s_iEs_j, если s_iМs_j и s_jМs_i, где M – какое-то отношение;

– для любой sS sEs,

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

Очевидно, что

1. Если некоторая ситуация s является инициатором и sS(j), где S(j) – класс эквивалентности, стоящий на j-ом месте в некоторой допустимой последовательности, то все ситуации классов S(1), …S(j) в этой последовательности являются инициаторами

2. Если некоторая ситуация s является результантом и sS(j), где S(j) – класс эквивалентности, стоящий на j-ом месте в некоторой допустимой последовательности, то все ситуации классов S(j),S(j+1),…S(q), где S(q) – заключительный класс, являются результантами.

3. Начальный класс эквивалентных ситуаций эффективного АП состоит только из инициаторов, а заключительный класс только из результантов.

4. Каждый класс эквивалентности ситуаций эффективного АП, не принадлежащий к результантам, состоит из одной ситуации.