Моделирование систем на основе сетей Петри
Моделирование систем на основе сетей Петри
Моделирование последовательных процессов
Рассмотрим, как сетью Петри может быть представлен отдельный процесс. Отдельный процесс описывается программой на одном из существующих языков программирования.
Пример 6.9. Текст программы на языке программирования Pascal, вычисляющей произведение всех чётных чисел из отрезка [1, Y] для Y Î N:
program mult;
var X, Y: integer;
begin
read(Y);
X:=1;
while Y>0 do
begin
if Y mod 2 = 0 then X:=X*Y;
Y:=Y-1;
end;
write(X);
end.
Программа представляет два различных аспекта процесса: вычисление и управление. Сети Петри удачно представляют структуру и управление программ. Они предназначены для моделирования упорядочения действий и потока информации, а не для действительного вычисления самих значений.
Стандартный способ представления структуры программы и потока управления в ней – схемы алгоритма, которые, в свою очередь, могут быть представлены сетями Петри. Схема алгоритма программы изображена на рисунке 6.7 а, где использованы следующие обозначения блоков:
a: read(Y); X:=1;
b: Y>0;
c: Y mod 2 =0;
d: X:=X*Y;
e: Y:=Y-1;
f: write(X).
В сети Петри (рисунок 6.7 б), моделирующей схему алгоритма, узлы схемы представляются переходами сети, а дуги - позициями сети Петри. Фишка в сети представляет счетчик команд схемы алгоритма.
а) схема алгоритма б) сеть Петри
Рисунок 6.7 – Структура программы
6.8.2 Моделирование взаимоисключения параллельных процессов
Сеть Петри на рисунке 6.8 моделирует механизм взаимного исключения для двух процессов P1 и P2. Она легко обобщается на произвольное число процессов.
Рисунок 6.8 – Моделирование взаимного исключения процессов P1 и P2
Позиция m представляет условие «критическая секция свободна», разрешающее вход в критическую секцию. Попытка процесса P1(P2) войти в критическую секцию осуществляется после помещения фишки в его позицию s1(s2). Такая попытка будет успешной, если в позиции m содержится фишка. Если оба процесса пытаются войти в критическую секцию одновременно, то переходы t1 и t2 вступят в конфликт, и только один из них сможет запуститься. Запуск t1 запретит запуск перехода t2, вынуждая процесс P2 ждать, пока процесс P1 выйдет из своей критической секции и возвратит фишку обратно в позицию m.
6.8.3 Моделирование взаимодействия типа «Производитель – Потребитель»
Разделяемым объектом в задаче является буфер, посредством которого реализуется взаимодействие через асинхронную передачу сообщений. Такое взаимодействие может быть промоделировано сетью Петри, изображенной на рисунке 6.9.
Рисунок 6.9 – Взаимодействие типа «Производитель – Потребитель»
Позиция B сети Петри представляет буфер, каждая фишка соответствует сообщению, которое произведено, но еще не использовано. Переходам сети соответствуют следующие события взаимодействующих процессов:
1) t1 – процесс «Производитель» генерирует сообщение;
2) t2 – процесс «Производитель» помещает сообщение в буфер обмена;
3) t3 – процесс «Потребитель» извлекает сообщение из буфера обмена;
4) t4 – процесс «Потребитель» использует считанное сообщение.