Пособие ТСиСА

O – вектор выходных функций: O :T P – выходная функция, отображающая переход O(tj) во множество позиций, называемых выходными позициями перехода.

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

Граничными являются позиции, которые еще не обработаны алгоритмом. После обработки граничные позиции будут определены как терминальные, либо дублирующие, либо внутренние.

Терминальные (пассивные) – это позиции, для которых нет разрешенных переходов.

Дублирующие – это позиции, ранее встречающиеся в дереве. Внутренняя – это вершина, которая не является ни граничной,

ни терминальной, ни дублирующей.

Таким образом, предполагается, что для решения задач моделирования достаточно представлять дискретные системы как структу-

моделирует процесс обучения в университете, может состоять из пяти состояний (позиций): P1 – обучение на первом курсе; P2 – обучение на первом курсе; P3 – обучение на третьем курсе; P4 – обучение на четвертом курсе; P5 – защита дипломной работы, а также четырех условий (переходов): t1 – успешное окончание первого курса; t2–успешное окончание второго курса; t3 – успешное окончание третьего курса; t4 – успешное окончание четвертого курса. Используя формализованное описание, рассматриваемую сеть Петри можно представить следующим образом: S=(P, T, I, O); P= (P1, P2, P3, P4, P5,); T= (t1, t2, t3, t4); I(t1)={P1}; I(t2)={P2}; I(t3)={P3}; I(t4)={P4}; O(t1)={P2}; O(t2)={P3}; O(t3)={P4}; O(t4)={P5}.

3.3. Графическое представление сетей Петри

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

80

Рис. 25. Графическое представление основных понятий теории сетей Петри: а – позиция, б – переход

Программы визуального моделирования (например, Microsoft Visio) позволяют пользователю вводить описание моделируемой системы преимущественно в графической форме, что упрощает понимание исследователем моделируемой системы (рис. 26).

г

Рис. 26. Графическое представление сети Петри

сдвумя позициями и двумя переходами, где а – позиция,

б– переход, в – входная дуга, г – выходная дуга

Заметим, что представленная на рис. 26 сеть Петри имеет сле-

дующую структуру: S=(P, T, I, O); P= (P1, P2); T= (t1, t2); I(t1)={P1}; I(t2)={P2}; O(t1)={P2}; O(t2)={P1}, а рассмотренное ранее формализованное (теоретико-множественный) представление модели процесса обучения в университете имеет графическое представление, изображенное на рис. 27.

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

81

Рис. 27. Графическое представление сети Петри процесса обучения в университете

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

г

Рис. 28. Графическое представление сети Петри с двумя позициями

идвумя переходами, где а – позиция, б – переход,

в– входная дуга, г – выходная дуга

При моделировании дискретных систем маркеры соответствуют объектам, передаваемым от компонента к компоненту системы или от одного системного состояния к другому. Формально маркер означает выполнение соответствующего условия, т.е. выполнение какоголибо условия связано с появлением одного или нескольких маркеров в соответствующей этому условию позиции. При этом каждое условие имеет емкость (целое неотрицательное число): емкость = 0 (условие не выполнено), емкость = 1 (условие выполнено), емкость = n, где n – целое положительное число (условие выполнено с n-кратным запасом). Выполнение условий изображается разметкой соответствующей позиции, а именно: помещением числа необходимого количества маркеров в соответствующую позицию или позиции (рис. 29).

82

4

Рис. 29. Графическое изображение сети Петри,

где P1 – условие не выполнено, P2 – условие выполнено, P3 - условие имеет емкость 3; P4 - условие имеет емкость 4

Процесс распределения маркеров по позициям называется маркировкой (M). Маркировка сети Петри есть вектор M, отображающий множество позиций P во множество неотрицательных целых чисел N: M : P N . Таким образом, вектором маркировки для сети Петри называется вектор, в котором число элементов равно числу позиций, а значением каждого элемента является количество маркеров в соответствующей позиции. Каждое изменение маркировки называют событием. Считается, что события происходят мгновенно и разновременно. Событие может произойти однократно, многократно повториться или не произойти ни разу. Каждое событие связано с определенным переходом – каждое срабатывание перехода (или комбинации переходов) порождает новую маркировку, т.е. порождает новое размещение маркеров в сети. Маркировку сети до срабатывания любого перехода называют начальной или стартовой. Например, начальная маркировка сети Петри, представленной на рис. 29, имеет вид: M (0; 1; 3; 4). Функционирование сети Петри останавливается, если ни один из переходов сети не может сработать. Завершение процесса функционирования приводит сеть к разметке, называемой конечной или завершающей. Например, для сети Петри, представленной на рис. 29, конечной (завершающей) маркировки не существует.

Неформально работу сети можно представить как совокупность локальных действий, называемых «срабатываниями переходов» и приводящих к изменению маркировки, т.е. локальному изменению условий в системе. Срабатывание перехода представляется как неделимое действие, изменяющее разметку входных и выходных позиций. Таким образом, срабатывание перехода состоит в изъятии маркеров

83

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

сданной конкретной позицией.

3.4.Правила срабатывания переходов

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

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

снего снимается срабатыванием другого перехода.

3.Переход запускается удалением всех разрешающих маркеров из его входных позиций (рис. 31, а, рис. 32, а) и последующим помещением в каждую из его выходных позиций (рис. 31, б, рис. 32, б), по одному маркеру для каждой дуги. В этой связи в сети Петри есть понятие кратности дуг. Кратность дуги означает количество маркеров, которые могут перейти по данной дуге за одно срабатывание перехода. На рассмотренном ранее примере (рис. 30, а-в) при срабатывании перехода по каждой дуге переходил один маркер, т.е. все выходные дуги имеют кратность 1. Если все входные и выходные дуги сети Петри имеют кратность, которая равна одному, то такая сеть называется ординарной (рис. 30, а-в). Если необходимо переместить сразу два (или более) маркера, то отображают две (или более) дуги (рис. 30, г) или одну дугу с пометкой кратности над ней.

84

Рис. 30. Правила срабатывания переходов: а – переход t1 разрешен

(каждая из его входных позиций Р1 и Р2 содержит ненулевое количество маркеров и их число равно числу дуг из каждой позиции в переход t1); б– переход t2 разрешен (дополнительные маркеры во входных позициях Р1и Р2 перехода t2 не влияют на его запуск); в – переход t3 неразрешен (входная позиция Р2 содержит нулевое количество маркеров); г – переход t4

не разрешен (количество маркеров из входной позиции Р2 в переход t4 меньше числа дуг из позиции в переход)

Рис. 31. Правила срабатывания переходов:

а – ситуация до срабатывания перехода t1; б – ситуация после срабатывания перехода t1

85

t1

P2 4

а

P1 P3

P2 3

б

Рис. 32. Правила срабатывания переходов:

а– ситуация до срабатывания перехода t1;

б– ситуация после срабатывания перехода t1

4.Если имеется несколько попарно независимо-разрешенных переходов, которые не имеют общих входных позиций, то их сраба-

тывание является независимыми действиями и может произойти

влюбой последовательности (рис. 33, а) или параллельно (рис. 33, б).

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

сунках (рис. 34, а-в, и рис. 35, а-в) два разрешенных перехода (t1 и t2) находятся в конфликте. При этом может быть запущен только один переход, так как при запуске он удаляет маркер из общей входной позиции и запрещает срабатывание второго перехода.

86

t2 P3

а

t2 P3

б

Рис. 33. Правила срабатывания переходов:

а– срабатывание одного из переходов (например, t2) приводит

кснятию условий разрешения для другого перехода (например, t3);

б– после срабатывания перехода (t1) емкость позиции P2 будет равна двум

(см. правило срабатывания переходов 3), в этой связи срабатывание одного из переходов (например, t2) не приведет к снятию условий разрешения для другого перехода и переходы t2 и t3 могут сработать в любой последовательности или параллельно

87

Рис. 34. Пример простой сети Петри: а – ситуация до срабатывания

переходов t1 и t2; б – ситуация после срабатывания перехода t1

(после запуска перехода t1 маркер из общей входной позиции P2 удаляется, запрещая срабатывание перехода t2); в – ситуация после срабатывания

перехода t2 (после запуска перехода t2 маркер из общей входной позиции P2 удаляется, запрещая срабатывание перехода t1)

Рис. 35. Пример простой сети Петри: а – ситуация до срабатывания

переходов t1 и t2; б – ситуация после срабатывания перехода t1

(после запуска перехода t1 маркер из общей входной позиции P3 удаляется, запрещая срабатывание перехода t2); в – ситуация после срабатывания перехода t2 (после запуска перехода t2 маркер из общей входной позиции

P3 удаляется, запрещая срабатывание перехода t1)

88

3.5. Достоинства и недостатки cетей Петри

Достоинства сетей Петри заключаются в следующем.

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

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

тижения в процессе функционирования определенных состояний

ицелей.

3.Сети Петри являются наглядным, удобным и мощным средст-

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

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

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

6.Математически строгое описание модели и наличие известных аналитических методов ее исследования, позволяет проводить анализ моделей с помощью современной вычислительной техники.

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

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

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

89