Сеть Петри: позиции, переходы и маркировка

Сеть Петри - это математическая модель дискретных событий, которая показывает, какие условия выполнены и какие действия могут произойти. Её особенно удобно применять, когда несколько процессов идут независимо, делят ресурс или должны дождаться друг друга. Круги обозначают позиции, прямоугольники - переходы, а точки в кругах - маркеры. Их распределение называют маркировкой: оно описывает состояние модели в данный момент.
Попробуйте простой замкнутый процесс ниже: задайте количество маркеров и число шагов. Калькулятор последовательно проводит их через три позиции и показывает полученную маркировку. Затем разберём, как читать схему и что она позволяет доказать.
Из чего состоит сеть Петри
У обычной сети есть позиции, переходы и направленные дуги между ними. Дуга соединяет позицию с переходом или переход с позицией, но не две позиции непосредственно. Позиция может означать условие «заявка ожидает», наличие свободного ресурса или завершение работы. Переход выражает событие: начать обработку, закончить её, освободить ресурс.
Маркер - это не обязательно предмет, который физически путешествует по системе. Его смысл задаёт модель: он может представлять заявку, разрешение или единицу ресурса. В одной позиции допустимо несколько маркеров, а отсутствие маркера тоже несёт информацию. Вектор перечисляет их количества во всех позициях в выбранном порядке.
В отличие от автоматов Мура и Мили, где состояние обычно изображают одной вершиной, сеть Петри распределяет состояние по нескольким позициям. Это удобно для описания одновременной готовности разных частей системы. При этом рисунок - только начало: смысл позиции и правило изменения маркировки необходимо определить явно.
Как срабатывает переход
Для простоты сначала считаем, что вес каждой дуги равен единице. Переход разрешён, если в каждой его входной позиции есть хотя бы один маркер. При срабатывании он забирает по одному маркеру из каждой входной позиции и добавляет по одному в каждую выходную. Все эти изменения составляют одно событие. Если входных позиций несколько, переход ждёт выполнения всех условий, а не любого одного.
На видео показан учебный цикл с единичными дугами. Движение между кругами помогает проследить порядок событий; формально маркер не обязан проводить время на дуге. Обычная сеть Петри описывает само срабатывание, но не задаёт его длительность. Для времени нужны дополнительные соглашения или расширенная модель.
Разрешённый переход не обязан сработать немедленно. Если одновременно разрешены несколько переходов, модель может допускать разные дальнейшие последовательности. Поэтому один просмотренный сценарий не доказывает, что иных сценариев нет. Формальное правило и терминология подробно разобраны в учебных материалах Технического университета Мюнхена.
Пример: заявка проходит цикл
Пусть позиции , , означают соответственно «ожидает», «в работе» и «готово». Переход начинает работу, завершает её, а возвращает готовую заявку в ожидание для нового цикла. У каждого перехода одна входная и одна выходная позиция, веса дуг равны единице.
Начнём с . Сначала разрешён : он удаляет маркер из и помещает его в . Затем перемещает маркер в , а возвращает в . Так получается последовательность:

Сумма маркеров здесь на каждом шаге равна единице: каждый переход забирает один и добавляет один. Это свойство конкретной схемы, а не правило для всех сетей Петри. Например, переход с одной входной и двумя выходными дугами может породить два маркера из одного. Если в калькуляторе выбрать ноль начальных маркеров, первый переход не разрешён и число выполненных шагов останется нулевым.
Вес дуги и формула маркировки
Вес дуги показывает, сколько маркеров требуется забрать или добавить. Обозначим вес дуги из позиции в переход через , а обратной дуги - через . Отсутствующей дуге соответствует вес ноль. Переход разрешён, когда для каждой позиции выполняется .
После срабатывания разрешённого перехода новая маркировка равна
Проверка разрешения предшествует вычислению. Если во входной позиции один маркер, а вес входной дуги равен двум, переход не сработает, даже если его выходная дуга тоже возвращает маркеры в ту же позицию. Формула изменения без проверки могла бы дать неотрицательный результат и тем самым скрыть ошибку.
Для учебного цикла все соответствующие веса равны единице. При переход разрешён, а и - нет. Если увеличить начальное количество до двух, могут одновременно разрешиться разные переходы. Калькулятор всё равно использует заранее заданный порядок и не перебирает все варианты.
Параллельность, выбор и синхронизация
Сеть может представить параллельность: после одного события два маркера появляются в разных позициях и разрешают два независимых действия. Если действия не конкурируют за входные маркеры, их можно выполнить в любом порядке; оба порядка приводят к одной маркировке. Это не означает, что обычная модель измеряет, сколько времени действия шли одновременно.
Для выбора два перехода могут иметь общую входную позицию с одним маркером. Каждый по отдельности разрешён, но срабатывание одного забирает общий маркер и может запретить другой. Это конфликт за ресурс, а не параллельное выполнение двух действий с одним и тем же маркером.
Для синхронизации переходу дают две входные позиции: он разрешён, только когда обе содержат требуемые маркеры. Например, отправка заказа ждёт и упаковки товара, и подтверждения оплаты. Если одно условие выполнено раньше, его маркер остаётся ждать другого. Такие правила явно показывают зависимости, которые трудно заметить в длинном текстовом описании процесса.
Достижимость, ограниченность и тупики
Маркировка достижима, если из начальной к ней ведёт допустимая конечная последовательность срабатываний. Для конечного набора достижимых маркировок можно построить граф: вершины - маркировки, направленные рёбра - срабатывания. Его удобно исследовать обходом графа в ширину, запоминая уже встреченные состояния. В примере с одним маркером граф содержит три вершины и замыкается в цикл.
Сеть ограничена при заданной начальной маркировке, если существует конечная общая граница числа маркеров в каждой позиции во всех достижимых маркировках. Частный случай - безопасность: в каждой позиции всегда не больше одного маркера. Наш цикл с одним маркером безопасен; с двумя в первой позиции он уже не безопасен, хотя число маркеров остаётся ограниченным двумя.
Тупиковая маркировка - состояние, в котором ни один переход не разрешён. Нулевой вектор в нашем примере является тупиком. Важно различать тупик и завершение: модель одноразового процесса может намеренно останавливаться после успеха. Чтобы решить, является ли остановка ошибкой, нужно знать цель процесса. Обзор этих свойств и способов анализа есть в работе Тадао Мураты о сетях Петри.
Где применяют модель и где её границы
Сети Петри используют для анализа рабочих процессов, протоколов, распределённых программ и систем с общими ресурсами. Например, позиция со свободными разрешениями может ограничивать число одновременных обращений к ресурсу. Построив модель, проверяют, можно ли достичь нежелательного состояния и не блокируют ли процессы друг друга.
Полезно сначала определить границы системы: что считается событием, какие ресурсы учитываются и какая маркировка считается успешной. Затем стоит вручную пройти обычный и пограничный сценарии. Как и при построении сетевого графика работ, смысл зависимостей важнее внешнего вида стрелок; однако сеть Петри дополнительно описывает состояние с помощью маркеров.
Модель отражает только включённые в неё условия. Если забыть позицию ресурса или переход отказа, анализ не обнаружит связанную с ними проблему. Кроме того, число маркировок может быстро расти, а в неограниченной сети граф достижимости бывает бесконечным. Время, вероятности и данные заявок требуют отдельного моделирования; обычные маркеры сами по себе этих сведений не содержат.
Частые ошибки
- Путают позицию и переход. Позиция описывает условие или наличие ресурса, переход - событие, меняющее маркировку.
- Проверяют только один вход. Для срабатывания нужны маркеры во всех входных позициях с учётом весов дуг.
- Считают разрешение обязательным срабатыванием. При нескольких разрешённых переходах возможны разные сценарии.
- Обобщают сохранение маркеров. Оно выполняется в нашем цикле, но не во всякой сети.
- Делают вывод по одному пути. Для свойства всей модели нужно учитывать все достижимые маркировки, а не только удобную последовательность.
FAQ
Чем сеть Петри отличается от блок-схемы?
Блок-схема обычно показывает порядок шагов алгоритма. Сеть Петри явно хранит распределённое состояние в маркерах и позволяет описывать конкуренцию, независимые действия и синхронизацию. Формализм срабатывания делает возможной проверку свойств модели.
Сколько маркеров может быть в позиции?
В обычной модели - любое неотрицательное целое число, если ограничение не вытекает из конкретной сети и начальной маркировки. В безопасной сети во всех достижимых маркировках их не более одного на позицию.
Означает ли тупик ошибку?
Не всегда. Тупик может быть корректным финалом одноразового процесса. Он становится проблемой, когда система должна продолжать работу или когда достигнуто состояние без желаемого результата.
Коротко
Сеть Петри описывает систему позициями, переходами, дугами и маркировкой. Разрешённый переход потребляет маркеры входов и создаёт маркеры выходов с учётом весов. Исследуя допустимые последовательности, можно проверить достижимость, ограниченность и наличие тупиков, не забывая, что вывод относится к построенной модели и выбранной начальной маркировке.
Читайте также

Forum shopping: стратегия выбора суда в споре
Forum shopping в международном споре: почему истец выбирает суд, как оценить процессуальные выгоды, параллельные иски, оговорку о суде и правила АПК РФ.

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

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

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

Аддитивная и мультипликативная погрешность
Аддитивная и мультипликативная погрешность прибора: формулы сдвига нуля и ошибки масштаба, пример расчёта показания и поправки, калибровка прибора и пределы линейной модели.

Адиабатический процесс: уравнение Пуассона и расчёт
Уравнение Пуассона для адиабатического процесса: вывод через первое начало термодинамики, связь давления, объёма и температуры, пример и границы применения.