книги / Теория графов и её приложения.-1
.pdfMOV R0,A |
; Х0(i+1) вR0 |
JNZ Next |
; Переходпонулю |
MOV A,R2 |
; ВыходвR2 |
ANL A,#0C0H |
; Выделяемy2(t+1)y1(t+1) |
MOV R3,A |
; РезультатвR3 |
MOV P2, R2 |
; ВыходнаР2 |
M1: JNB 0B0H,M1 |
; организуемпетлюпонулевомубиту |
Р3 для
M2: JB 0B0H,M2 ; имитации«синхронизации» автомата jmp Begin
TABL:db 0C0H,00H,50H, db 0C0H,40H,0C8H, db 0C1H,0C0H,84H,
db 0C1H,0C1H,0C8H, db 0C2H,80H,02H,
db 0C2H,82H,01H,00H
END
Рекомендуется создать проект в системе схемотехническо-
го моделирования Proteus 7.2 SP6 [20, 21] (рис. 12.48).
Рис. 12.48. Проект в системе схемотехнического моделирования Proteus 7.2 SP6 – микроконтроллер 80С51
131
ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 13. МОДЕЛИРОВАНИЕ СЕТИ ПЕТРИ
1.Опрос по теоретическому материалу – особенности сетей Петри.
2.Коллективное решение задач по теме занятия у доски – «вручную».
3.Самостоятельная работа по вариантам – на ПЭВМ в программе GRIN.
Пример решения задачи представления схемы алгоритма сетью Петри
Задание алгоритмов работы систем, в том числе, например, систем защиты информации, может осуществляться с помощью схем алгоритмов. Пример такой схемы приведен на рис. 13.1.
Рис. 13.1. Схема алгоритма (СА) оборудования защиты информации
132
Здесь используются микрооперации zi, которые принимают только булевы значения. В зависимости от значений логических условий х схема алгоритма реализуется по трём вариантам:
1) Если х1 = 1, то z1,z2,z2z2… 2) Если х1 = 0, х2 = 0, то z1,z2,z3,z4, z1,z2,z3,z4… 3) Если х1 = 0, х2 = 1, то z1,z2,z3,z5, z1,z2,z3,z5…
Позиции выбора значения логического условия обозначим Х, а дополнительные вершины, необходимые для возврата меток в них, обозначают Р. Для каждого значения логического условия необходима отдельная вершина, например Х1–1, для условия Х1, равного 1, Х1-0 для условия Х1, равного нулю. Дополнительные вершины, обозначаемые Р, предназначены для обеспечения возврата метки. Таким образом, по схеме алгоритма (см. рис. 13.1) можно получить в свободно распространяемой программе GRaph INterface (GRIN) сеть Петри (рис. 13.2).
Рис. 13.2. Сеть Петри, созданная в свободно распространяемой программе GRaph INterface, соответствующая схеме алгоритма на рис. 13.1
На рис. 13.2 позиция Р1 предназначена для реализации «петли» при Х1, равном 1, когда в цикле выдаётся Z2 (см. рис. 13.1). В этом случае Х1–1 содержит метку, Х1–0 не содержит метки (в эту вершину метку не ставят перед моделированием), поэтому при активации позиции Z2 срабатывает («сгорает») пе-
133
реход t0, передавая метку в вершину Р1, которая затем посредством срабатывания перехода х1 возвращается в Z2. Причём при срабатывании t0 метка возвращается и в Х1–1 (на рис. 13.2 дуга в Х1–1 двунаправленная). Остальные пути реализуются проще – активируются вершины Х2–1 либо Х2–0, причём и у них двунаправленные дуги. Таким образом, в зависимости от значений логических условий реализуется одна из трёх последовательностей выдачи Z.
Для моделирования сети Петри в свободно распространяемой программе GRaph INterface (GRIN) необходимо выбрать закладки: Свойства, Моделирование, Моделирование сети Петри, автоматический режим. Тонкость такая – надо проверять, чтобы при моделировании шаг был = 1, тогда возможно пошаговое выполнение схемы алгоритма. Заносим в вершины Z1, X1–0, X2–0 метки (рис. 13.3).
Рис. 13.3. Исходное состояние: Z1=1, X1–0=1, X2–0=1,
метки исходные синие
Делаем шаг, нажимая соответствующую кнопку на
«Плеере» (рис. 11.4).
Производится перенос метки из Z1 в Z2. Далее делаем второй шаг (рис. 13.5).
134
Рис. 13.4. Первый шаг: перенос метки из Z1 в Z2
Рис. 13.5. Второй шаг: перенос метки из Z2 в Z3
Выполнен перенос метки из Z2 в Z3. Третий шаг на рис. 11.6. Выполнен перенос метки из Z3 в Z4. Четвёртый шаг – воз-
врат в исходное состояние показан на рис. 13.7.
Если логические условия не изменяются, далее последовательность остаётся прежней. Аналогично моделируются оставшиеся две ситуации значений логических условий: X1–0 = 0,
X2–0 = 1; X1–0 = 1.
Если Х1 = 1 – постоянно, выдаётся Z2 (рис. 13.8–13.9).
135
Рис. 13.6. Третий шаг: перенос метки из Z3 в Z4
Рис. 13.7. Возврат в исходное состояние
Рис. 13.8. Исходное состояние при Х1=1
136
Рис. 13.9. Выдача Z2 при Х1 = 1
Далее активируется позиция Р1 (рис. 13.10).
Рис. 13.10. Активация Р1 при Х1 = 1 – метка в Р1
Метка из вспомогательной вершины удаляется и переносится опять в Z2 (рис. 13.11).
Далее опять активируется Р1, обеспечивая очередную выдачу Z2 при Х1 = 1.
Теперь пусть х1 = 0, х2 = 1. Исходное состояние дано на рис. 13.13.
Далее выдаётся Z2 (рис. 11.14).
Далее выдаётся Z3 (рис. 13.15). После чего выдаётся Z5 (рис. 13.16).
137
Рис. 13.11. Повторная выдача Z2 при Х1 = 1
Рис. 13.12. Повторная активация Р1 (второе срабатывание перехода t0) при Х1 = 1 – метка в Р1
Рис. 13.13. Исходное состояние при х1 = 0, х2 = 1
138
Рис. 13.14. Выдача Z2 при х1 = 0, х2 = 1
Рис. 13.15. Выдача Z3 при х1 = 0, х2 = 1
Рис. 13.16. Выдача Z5 при х1 = 0, х2 = 1
139
И сеть возвращается в исходное состояние (рис. 13.17).
Рис. 13.17. Возврат в исходное состояние при х1 = 0, х2 = 1
Если нет необходимости формировать «импульсы» Z2, то можно поступить так (рис. 13.18).
Рис. 13.18. Сеть с фиксацией Z2 при Х1 – 0 = 0
Тогда в позиции Z2 метка будет сохраняться до Х1 – 0 = 1. Задание. Выполнить моделирование сети Петри по вариан-
там (приложение 7).
140