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

Переход t1 пассивен (уровень 0), так как маркеры не могут одновременно находиться в позициях Р2 и Р3.

Переход t2 активен только в тех состояниях, которые характеризуются наличием объекта в позиций Р2 и Р4. Данный переход может сработать только один раз, удалив объект из позиций P2 и Р4 , и породив объект в Р3. Следовательно. t2 имеет уровень 1.

Переход t4 может срабатывать n раз (по числу маркеров, находящихся в позиции P4, которые были добавлены после срабатывания перехода t3), при условии предварительного срабатывания t2. Активность t4соответствует уровню 2.

Переход t3 может сработать неограниченное число раз, но только до срабатывания t2. Поэтому t3 имеет уровень активности 3.

Для срабатывания перехода t5 необходимо наличие, по крайней мере, двух маркеров в позиции и Р3 и Р4, но в процессе функционирования системы количество маркеров во входных позициях перехода t5 – Р3 и Р4 будет всегда меньше числа дуг из позиций в переход. В этой связи переход t5 является пассивным и может означать избыточность аппаратуры или наличие неисполняемых функций в программе. Переходы t1, t2 , t3, и t4 в рассматриваемой сети имеют уровень 4, т.е. являются активными.

Проиллюстрируем свойство живости на модели процесса сдачи сессии студентом (рис. 52).

P3

P2

. . .

Рис. 52. Сеть является неограниченной и живой, так как маркеры могут накапливаться в завершающей позиции, срабатывают

все переходы, тупики отсутствуют

120

Содержательный смысл позиций и переходов: P1 – студент, который сдает сессию; P2 – наличие допуска к сессии; P3 – установленные сроки сессии для студента; P4 – сдача студентом первого экзамена; Pn–1 – сдача студентом i–го экзамена; Pn – обработка результатов сдачи экзаменов; t1– получение допуска к сессии; t2– проверка результатов сдачи первого экзамена; t n–1 – проверка результатов сдачи i–го экзамена; t n – установка сессии.

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

Устойчивость – сеть Петри называется устойчивой, если для любого ее перехода выполняется следующее условие: состояние возбуждения этого перехода не может быть снято срабатыванием другого какого-либо перехода. Таким образом, если в сети имеются альтернативные переходы, то она является неустойчивой. На рис. 53 представлены две сети Петри, описывающие выбор специальностей для поступления на бюджетную (рис. 53, а) и коммерческую (рис. 53, б) основы. Содержательный смысл позиций и переходов (рис. 53, а): P1 – комплекты документов для подачи заявления на выбранную специальность на бюджетную основу; P2 – первая специальность для поступления; P3 – вторая специальность для поступления; P4 – третья специальность для поступления; P5 – справка о принятии документов на бюджетную основу; t1 – выбор специальностей для поступления на бюджетные места. Содержательный смысл позиций и переходов (рис. 53, б): P1 – комплекты документов для подачи заявления на выбранную специальность на коммерческую основу; P2 – первая специальность для поступления; P3 – вторая специальность для поступления; P4 – третья специальность для поступления; P5 – справка о принятии документов на коммерческую основу; t1 – выбор первой специальности для поступления с оплатой стоимости обучения по договору; t2 – выбор второй специальности для поступления с оплатой стоимости обучения по договору; t3 – выбор третьей специальности с оплатой стоимости обучения по договору .

121

а

б

Рис. 53. Свойство устойчивости: а – пример устойчивой сеть Петри; б – пример неустойчивой сеть Петри (срабатывание одного из переходов (например, t2) приводит к снятию условий разрешения для другого перехода (например, t1 и t3)

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

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

122

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

Множество достижимых маркировок описывается графом достижимости, у которого каждой вершине соответствует определенная маркировка, а каждой дуге – переход, который срабатывает при данной маркировке: GD = {V, E}, где V – массив вершин (маркировок, соответствующих вершинам): V= {M1, M2, M3, … Mi}, где Mi – i-я

ность E= {A1, A2, Tj} , где A1 и A2 – номера начальной и конечной вершин графа; T= {T1, T2, T3, … Tk} – массив переходов, соответствующий дуге; k – количество одновременно срабатывающих переходов при переходе от одной маркировки к другой.

Алгоритм построения графа достижимости для сети Петри начинается с определения начальной разметки.

1.За исходную берется маркировка M0 и ей присваивается метка «новая».

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

3.Для каждого разрешенного перехода или комбинации перехо-

дов определяется маркировка Mn, которая образуется при срабатывании данного перехода (или комбинации переходов). В массив E= {A1, A2, Tj} записывается дуга с соответствующими A1, A2, и Tj.

4.Просматриваются все маркировки на пути от Mn к начальной M0. Если на пути находится маркировка Mn-1, элементы которой больше либо равны соответствующим элементам рассматриваемой

маркировки и которая не равна Mn, то вместо элементов, которые больше, чем элементы, маркировки Mn, записывается символ « » (бесконечность). Ввиду того, что число маркеров в позиции может

быть либо неотрицательным целым, либо бесконечно большим, то бесконечное число меток обозначим символом « ». Символ « » означает потерю информации о емкости состояния, конкретное количе-

123

ство маркеров отбрасывается и учитывается только существование их большего числа.

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

вершина графа, в которую записывается новая маркировка, в массив E записывается дуга, у которой A1 равна номеру исходной маркировки, A2 – номеру новой маркировки, Tj – набор переходов, срабатывание которых привело к переходу от одной маркировки к другой. Далее определяется массив всех разрешенных переходов и расчет продолжается, начиная с п. 1[12].

На рис. 54 представлена сеть Петри, описывающая процесс защиты курсовой работы, где: P1 – обсуждение результатов выполнения курсовой работы; P2 – положительная оценка в зачетной ведомости и зачетной книжке; P3 – полученные замечания и вопросы; t1– проверка результатов выполнения курсовой работы и формулирование замечаний преподавателем; t2 – проверка результатов выполнения курсовой работы преподавателем и выставление положительной оценки преподавателем.

Рис. 54. Сеть Петри, описывающая процесс защиты курсовой работы

Для рассматриваемой сети Петри начальная разметка M0 задается следующем образом: M0 (P1) = 1, M0 (P2) = 0, M0 (P3) = 0 или в векторной форме: M0 (1, 0, 0).

При разметке M0 могут сработать следующие переходы t1 и t2. При запуске перехода t1 в выходную позицию P3 приходит один маркер. При запуске перехода t2 из входной его позиции P1 уходит один маркер, а в выходную позицию P2 приходит одни маркер. Таким об-

124

разом, из начальной маркировки M0 (1, 0, 0) непосредственно достижимыми являются две маркировки: M1 (0, 1, 0) и М2 (1, 0, 1).

Причем из маркировки M1 (0, 1, 0) невозможно достичь ни одной маркировки, так как ни один переход не является разрешенным (разметка является тупиковой). Из маркировки M2 (1, 0, 1) можно получить маркировки M3 (0, 1, 1) (при срабатывании перехода t1) и M4 (1, 0, 2) (при срабатывании перехода t2). При этом маркировка M3 (0, 1, 1) является тупиковой (или завершающей), а из маркировки M4 (1, 0, 2) достижимы маркировки M5 (0, 1, 1) и M6 (1, 0, 3).

Видно, что емкость позиций P3 для каждой из маркировок M1, M2, M3 и т.д. больше предыдущих на единицу. При циклическом срабатывании перехода t3 количество маркеров в позиции P3 может увеличиваться бесконечно – число циркулирующих маркеров внутри сети Петри не является постоянным. В этой связи при построении графа и матрицы достижимости конкретное количество маркеров в позиции P3 отбрасывается и учитывается только существование их большего числа – символ « ». Построение дерева достижимости сети Петри закончено.

Граф и матрица достижимости изображены на рис. 55 (а - б). Проведем анализ сети Петри изображенной на рис. 30. Данная

сеть Петри является:

–не ограниченной – при циклическом запуске перехода t1, количество маркеров в позиции P3 может увеличиваться бесконечно;

–не безопасной – число маркеров внутри позиции P3 может превышать одного;

–живой – отсутствуют зацикливания, тупики и блокировки;

–не сохраняемой – число циркулирующих маркеров внутри сети Петри не является постоянным, а учитывается только существование их большего числа;

–достижимой – заданные маркировки являются достижимыми.

–не устойчивой (конфликтной) – срабатывание одного из пере-

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

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

втерминальной (конечной) позиции (P2).

125

t3 – проверка результатов сдачи зачета преподавателем (удовлетворительный ответ студента).

t2

P3

25

t4

Рис. 56. Сеть Петри, описывающая процесс сдачи зачета студентами

В результате анализа пространства состояний модели были получены следующие результаты: тупиковые маркировки – отсутствуют; недостижимые переходы – отсутствуют; активные переходы – все.

Проведем анализ сети Петри изображенной на рис. 56. Данная сеть Петри является:

–ограниченной – максимальное количество маркеров соответствует 25 (количеству студентов в группе).

–не безопасной – число маркеров внутри позиций P1, P2 и P4 более одного;

–живой – отсутствуют зацикливания, тупики и блокировки;

–сохраняемой – число циркулирующих маркеров внутри сети Петри является постоянным;

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

(рис. 33 а - б).

127

– не устойчивой (конфликтной) – срабатывание одного из переходов (например, t1) приводит к снятию условий разрешения для другого перехода (например, t2);

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

Рис. 57. Пример построения матрицы и графа достижимости для модели процесса организации сдачи зачета студентами университета:

а – матрица достижимости; б – граф достижимости (где, 25≥k, m≥0)

128

4.3.Задачи для самостоятельного решения студентами

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

P4 t4

а

t1

P1 P3 t4

t5 P4

б

Рис. 58. Пример сети Петри

129