Сети Петри презентация

является понятие дискретной динамической системы
Дискретной динамической системой называется система обладающая некоторым набором состояний, переход между которыми происходит в дискретные моменты времени
Примером дискретной динамической системы является автомат

последовательной алгоритмической системы
Поведение таких систем детерминировано: они последовательно переходят из одного состояния в другое в соответствии в определенной функцией перехода
Конечные автоматы не подходят для описания дискретных систем более общего вида – недетерминированных параллельных систем

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

событиями
Примеры событий:
выполнение оператора программы,
прерывание в операционной системе,
завершение технологической операции в производственном процессе и т.д.
Событие может произойти один раз или повторяться многократно; совокупность событий в динамической системе, образует процесс, порождаемый этой системой

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

связь заменяется причинно-следственной
Отказ от времени позволяет считать события или неделимыми («мгновенными»), или составными, состоящими из «подсобытий»

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

60-х годах прошлого века немецким математиком Карлом Адамом Петри

быть:
не выполнено – ёмкость 0,
выполнено – ёмкость 1,
Выполнено с n-кратным запасом – ёмкость n
В терминах сетей Петри события называются переходами, а условия – позициями
Предусловия реализации события – это входные позиции для перехода, а постусловия – выходные позиции

экземпляров одного и того же элемента
Сеть Петри S является четверкой
S = (P, T, I, O), где
P – конечное множество позиций;
T – конечное множество переходов;
I – входная функция, сопоставляющая переходу мультимножество его входных позиций;
O – входная функция, сопоставляющая переходу мультимножество его входных позиций

= {t1, t2, …, tm}, m ≥ 0;
Входная функция:
I: T → P*, где P*- мультимножество входных позиций;
Выходная функция:
O: T → P*, где P*- мультимножество выходных позиций;

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

{p1, p1, p2},
O(t1) = {p3},
I(t2) = {p1, p2, p2},
O(t2) = {p3}

виде двудольного, ориентированного мультиграфа
Граф сети Петри обладает двумя типами узлов:
круг , представляющий позицию сети Петри,
планка, представляющая переход сети Петри
Ориентированные дуги этого графа соединяют переход с его входными и выходными позициями
Дуги направлены от входных позиций к переходу и от перехода к выходным позициям
В графе сети Петри невозможны дуги между двумя позициями и между двумя переходами (двудольность)

путем размещения в ней числа фишек, соответствующего ёмкости этой позиции
Фишки изображаются на графе точками; количество фишек в позиции в процессе работы сети Петри может изменяться от 0 до бесконечности
Разметка μ сети Петри – это функция, отображающая множество позиций P во множество натуральных чисел N
μ: P → N

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

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

не может сработать

во время их параллельного выполнения
Существуют различные виды взаимодействия (синхронизации) процессов, в том числе: взаимодействие посредством общей памяти; посредством передачи сообщения различных видов
Необходимо уметь моделировать различные механизмы синхронизации процессов

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

он осуществляет доступ к разделяемому объекту данных
Прежде, чем выполнить свою критическую секцию, процесс ждёт, пока другой процесс не закончит выполнение собственной критической секции и лишь затем он входит в критическую секцию
При этом блокируется доступ для любого другого процесса к своей критической секции до выхода этого процесса из критической секции

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

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

философ возьмет вилку слева, а затем будет ждать, когда освободится вилка с правой стороны
Так они будут ждать, пока не умрут от голода
Тем самым, это состояние системы «обедающие философы» является тупиковым

следующей модификации ее правил поведения
Пусть философ при переходе из состояния размышления в состояние приема пищи берет одновременно обе вилки (слева и справа), если они свободны

k-ограниченной, если μ`(p) ≤ k для любой достижимой разметки μ`.
Позиция называется ограниченной, если она является -ограниченной для некоторого целого значения .
Сеть Петри ограниченна, если все ее позиции ограниченны.