Ограниченность сетей Петри. Задача о производителе и потребителе

Ограниченность сетей Петри. Задача о производителе/потребителе.

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

Определение 4.2. Позиция р_i P  сети Петри С= (Р, Т, I, О) с начальной маркировкой μ является k-безопасной, если μ'(р_i)  к для всех μ'  R(C, μ).

1-безопасная позиция называется просто безопасной. Заметим, что граница k' по числу фишек, которые могут находиться в пози­ции, может быть функцией от позиции (например, позиция р₁ мо­жет быть 3-безопасной, тогда как позиция р₂ — 8-безопасной). Однако, если позиция p_i k-безопасна, то она также и k'-безопасна Для всех k'  k. Поскольку число позиций конечно, можно выбрать f_t, равное максимуму из границ каждой позиции, и определить сеть Петри k-безопасной, если каждая позиция сети k-безопасна.

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

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

Обратите внимание на лекцию "Рост и развитие детей и подростков".

Одни из вариантов этой задачи — это задача о нескольких про­изводителях/нескольких потребителях. В этом случае несколько производителей порождают элементы данных, помещаемые в общий буфер, для нескольких потребителей. На рис. 3.30 представлено решение этой задачи в виде сети Петри. Эта сеть совпадает с сетью на рис.3.29, за исключением того, что для представления s произ-

водителей и t потребителей мы начали выполнение сети с s фишка­ми в начальной позиции процесса-производителя и t фишками в начальной позиции процесса-потребителя. Таким образом мы представляем s производителей и t потребителей, реализуемых реентерабельными совместно используемыми программами. Аль­тернативой было бы дублирование программного кода для процес­сов производителя и потребителя, однако результатом этого при том же самом поведении была бы гораздо большая сеть.

В другом варианте задачи о производителе/потребителе исполь­зуется буфер ограниченного размера. При такой постановке задачи буфер между производителем и потребителем ограничен, т. е. имеет только n ячеек для элементов данных. Следовательно, производи­тель не может постоянно работать с той скоростью, которая ему нуж­на, а вынужден ждать, если потребитель работает медленно и бу­фер заполнен. На рис. 3.31 показано решение этой проблемы. Огра­ниченному буферу сопоставляются две позиции: В представляет количество элементов данных, которые произведены, но еще не ис­пользованы (число заполненных ячеек), В' — количество пустых ячеек в буфере. Первоначально В' имеет n фишек, а В фишек не имеет. Если буфер заполнен, то В' фишек не имеет, а В имеет n фишек. Если теперь производитель попытается поместить еще один элемент данных в буфер, то он будет остановлен, так как в В' нет фишки, делающей этот переход разрешенным.