Размеченный график

— Размеченный граф это сеть Петри , в которой в каждой позиции имеется ровно одна входящая и ровно одна исходящая дуга. Это значит, что не быть конфликта может , но может быть параллелизм . Математически: $\forall p\in P:|p\bullet |=|\bullet p|=1$ . Размеченные графики используются в основном для математического представления одновременно выполняемых операций, таких как состояние внутреннего процесса многопроцессорной машины. Этот класс сетей Петри получил свое название от популярного способа их представления: в виде графа, где каждое место является ребром, а каждый переход — узлом.

Использование

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

Пример

В этом примере представлен размеченный граф, в котором процесс разветвляется на переходе T1 и синхронизируется на этапе T4. Между ними выполняются две операции недетерминированным образом: T2 и T3. На самом деле сети Петри настолько недетерминированы, что могут вообще не иметь места. Но причина наличия этого недетерминированного свойства заключается не в этом, а в имитации реального опыта, который показывает, что параллельные вычисления всегда означают, что невозможно определить, какой процесс/поток завершится первым, т. е. какая операция(и) будет выполняться быстрее. . Это может быть связано с ожиданием ввода-вывода в реальном мире или просто с различными параметрами, заданными процессам/потокам.