Иркутск

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

Безопасность — это частный случай более общего свойства ограниченности. Некоторые соображения относительно реального ограничения на аппаратную реализацию позиций позволяют прий­ти к заключению, что безопасность — необязательное требование. Безопасность позволяет реализовать позицию триггером, но в бо­лее общем случае можно использовать счетчик. Однако любой аппаратно-реализованный счетчик ограничен по максимальному числу, которое он может представить. Позиция является 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 фишек. Если теперь производитель попытается поместить еще один элемент данных в буфер, то он будет остановлен, так как в В' нет фишки, делающей этот переход разрешенным.

Лучников В.А. Программирование на языке Си. Учебное пособие – Иркутск: ИрГУПС, 2012.-157 с.

Учебное пособие предназначено для студентов специальностей “Информационные системы и технологии”, “Программная инженерия” и “Информационная безопасность”. Оно может быть также полезно для студентов других специальностей, изучающих программирование и использующих его в прикладных задачах при выполнении расчетно-графических и курсовых работ по специальным дисциплинам.

Учебное пособие содержит последовательное изложение основ программирования на примере алгоритмического языка Си, необходимую для практической работы справочную информацию. Пособие снабжено большим количеством примеров, иллюстрирующих основные приемы программирования. Рассматривается структурная и объектно-ориентированная технологии программирования, методы проектирования, отладки и тестирования программ, использование основных структур данных для решения конкретных практических задач. В конце каждой темы приводятся часто встречающиеся ошибки программирования, относящиеся к этой теме. Изложение материала опирается на учебник автора “Программирование на языке Паскаль”.

Данное учебное пособие является вторым в серии учебных пособий по программированию на алгоритмических языках высокого уровня, написанных автором. Следующими будут выпущены учебники по программированию на языках PHPиJava,необходимые студентам специальностей Института информационных технологий и моделирования.