Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984, страница 12

Эта сеть совпадает с сетью на рис. 3.29, за исключением того, что для представления з произ- ЛроилА йилаля Лотреоителе Ряс. 3.29. Задача о производителе!потребителе, моделируемая сетью Петрн. 3-оо2 Уолт теАаиилв Рис. З.ЗО, Задача о нескольких производителях/нескольких потребителях (з производителей и 1 потребителей лая Фиксированных а и Ф).

Потрибилтяхгь Произ бодитп ела Рис, З.З1. Задача о пронзводителерзотребятеле с ограняченныи буберозо Бубпр. представленный позяцнямн В и В', ограничен и ячейками. 67 Сети Петри для моделирования водителей и г потребителей мы начали выполнение сети с з фишками в начальной позиции процесса-производителя и 7 фишками в начальной позиции процесса-потребителя.

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

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

Если буфер заполнен, то В' фишек не имеет, а В имеет и ° фишек. Если теперь производитель попытается поместить еще один элемент данных в буфер, то он будет остановлен, так как в В' нет ' фишки, делающей этот переход разрешенным. 3.4.6. Задача об обедающих мудрецах Задача об обедающих мудрецах была предложена Дейкстрой в ,' Щ и связана с пятью мудрецами, которые попеременно то думали, то елн. Мудрецы сидят за большим круглым столом, иа котором много блюд китайской кухни. Между соседями лежит одна палочка для еды.

Однако для приема китайской пищи необходимо две палтяь и ки, следовательно, каждый мудрец должен взять палочку слева и палочку справа: проблема, конечно, заключается в том, что если , все мудрецы возьмут палочки слева и затем будут ждать, когда ' освободятся палочки с правой стороны, то они будут ждать вечно ' и умрут от голода (состояние тупика). На рнс. 3.32 показано решение этой задачи с помощью сети Петри. Позиции Си ..., С представляют палочки для еды, и так как каждая из них первоначально свободна, то в начальной маркировке в каждой из этих позиций имеется фишка. Каждый мудрец пРедставлен двумя позициями тт1; и Ет для состояний размышления И принятия пищи соответственно. Для того чтобы мудрец перешел из состояния размышления в состояние принятия пищи, обе палочки (слева и справа) должны быть свободны.

Это легко моделиРуется сетью Петри. Глава 8 Рис. 3.32. Задача об обедающих мудрецах. Каждый мудрец предстазлея даумя позициями: размышленяе (Ме), принятие пнщн (Е,1. 3.4Х Задача о чтении/записи Существует несколько вариантов задачи о чтении/записи (58(, однако основная структура их остается неизменной. Имеются процессы двух типов: процессы чтения и процессы записи. Все процессы совместно используют общий файл или переменную или элемент данных. Процессы чтения не изменяют объект в отличие от процессов записи Таким образом, процессы записи должны взаимно исключать все другие процессы чтения и записи, в то время как несколько процессов чтения могут иметь доступ к разделяемым данным одновременно. Задача ссстоит в определении структуры управления, которая не приведет к тупику и ие допустит нарушения критерия взаимного исключения.

На рис. З.ЗЗ иллюстрируется решение задачи в том случае, когда количество процессов чтения ограничено величиной л. Если в системе количество процессов чтения ие ограничено, то только и процессов могут выполняться в одно и то же время. Проблема возникает в том случае, если количество процессов чтения не ограничено и мы хотим предоставить возможность не- Сети Легри для моделирования Лроиооеец оотецчл~ Пронесем еаоаеа Рис. 3.33. Задача о чтении(записи в случае, когда число процессов чтения ограничено величиной и. Первоначально ииекися а процессов чтения и Г процессов записи.

ограниченному количеству процессов читать одновременно. В',этом случае можно утверждать, что возникает необходимость храйения р количества читающих процессов. При инициализации каждого про", 'цесса чтения в счетчик добавляется единица, а по окончании про- ,~ цесса единица вычитается. Это легко моделируется позицией, в ~~ которой количество фишек равно количеству процессов чтения. ,' Однако, для того, чтобы предоставить процессу записи возможность приступить к записи, необходимо, чтобы счетчик был нулевым, т.

е. соответствующая позиция была бы пустой. В сетях Петри нет механизма, который бы осуществлял проверку на нуль неограниченной позициип. Таким образом, оказывается, что задача о чтении/записи с неограниченным числов процессов чтения не макет быть ,решена с помощью сетей Петри. Это первый случай, когда мы столк'"„,нулись с тем, что сети Петри не способны моделировать все системы.

~ Этот вопрос заслуживает дальнейшего изучения (гл. 7). 3.4.8. Р- и У-системы Большинство задач синхронизации не могут быть решены непосредственно сетями Петри, но разрешимы скорее на основе известных механизмов синхронизации. В частности, одним из самых популярных механизмов синхронизации являются Р- и Ъ'-операции над семафорами, впервые определенные Дейкстрой ~7ф Семафор— мто элемент данных, который может принимать только неотрицательцц цццц ю '.ц-цчцц ц~ ° ~ ° ~в„,1, р.

>цр, ц ° р, „„Й „,,цц,,, ц.— егрим, ред. Глава 8 70 операция уменьшает его на 1. Р-операцию можно применять только в том случае, когда значение семафора останется в результате неотрицательным; если же значение семафора равно О, то Р-операция должна ждать, пока какой-нибудь другой процесс не выполнит У-операцию Р- и Ч-операции определены как примитивные, т. е. никакая другая операция не может изменять значение семафора одновременно с ними. и(ю Рис. 3.34. Мохелироааиие Р- и У-операций пад семафором 8. Такие операции легко моделируются сетью Петри, как показано на рис.

3.34. Каждый семафор моделируется позицией, копичество фишек в позиции показывает значение семафора. Р-операция использует псвицию семафора в качестве входа, Ч-операция— в качестве выхода. Преимущество этого заключается в том, что многие системы проектируются и описываются с помощью Р - и Ч-операций. Например, в операционной системе Чепца 1179] Р- и и'-операции являются основным механизмом связи между процессами. Такие системы, следовательно, можно промоделировать сетями Петри.

3.$. Другнв системы Описанные до сих пор системы относятся к самому очевидному типу систем, моделируемых сетями Петри: аппаратному и программному обеспечению ЭВМ. Но в балыпей части эта «очевидность» является результатом того, что сети Петри были определены и разработаны главным образом для этой цели. Но они также применимы для моделирования большого числа других систем, совершенно отличных от вычислительных систем. В этом разделе мы бегло ознакомимся с некоторыми из инх. РЕЙТ-диаграмма давно используется для планирования больших проектов.

РЕЕТ-диаграмма является графическим представле- Сети Петри для моделирования вием взаимосвязей между различными этапами, составляющими проект. Проект представляет собой совокупность большого числа этапов, при этом некоторые этапы должны завершиться прежде, чем начнут выполняться другие. Кроме того, на выполнение каждого этапа требуется определенное количество времени (иногда каждому этапу соответствует три времени, соответствуицве худшему, сред- нему и лучшему случаям). Этапы графически представлены узла- ми; дуги используются для отображения причинно-следственных связей между ними.

РЕВТ-диаграмма и сеть Петри взаимосвязаны: РЕКТ-диаграм- ма легко преобразуется в сеть Петри. Каждый этап РЕКТ-диаграм- мы представляется позицией, причинно-следственные связи — пере- ходами. Диаграмма на рнс. 3.35 может быть преобразована в экви- валентную сеть Петри, изображенную на рис. 3.36. Сеть Петри является превосходным средством для представления параллелизма и причинно-следственных связей РЕКТ-диаграммы, но РЕЙТ-диаграмма предоставляет также информацию о времени, ~ используемую для определения минимального времени, необходи- мого для выполнения проекта, — «время позднего началаь и т.

д. Сеть Петри не содержит такой информации. Добавление информации о времени может придать сети новое мощное свойство, но зто несов- местимо с основными концепциями сетей Петри. Для такого рас- ширения сетей Петри требуются дополнительные исследования [277, 1171. Конвейерная обработка, описанная в равд. 3.3.2, является част- > ным случаем производственной системы [1071.