Отмеченный график - Marked graph

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

А отмеченный график это Сеть Петри в котором каждое место имеет ровно одну входящую дугу и ровно одну выходящую дугу. Это означает, что может нет быть конфликт, но может быть параллелизм. Математически: ${displaystyle forall pin P:|pullet |=|ullet p|=1}$. Отмеченные графы используются в основном для математического представления одновременно выполняющихся операций, таких как внутреннее состояние процесса многопроцессорной машины. Этот класс сетей Петри получил свое название от популярного способа их представления: в виде графа, где каждое место является ребром, а каждый переход - узлом.

Использует

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

Пример

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