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

Эта статья не цитировать любой источники. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удаленный. Найдите источники: «Маркированный график»  – Новости  · газеты  · книги  · ученый  · JSTOR (Декабрь 2009 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

Использует

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

Пример

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