Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 39
Текст из файла (страница 39)
Беед Ед, Еед. Услзюдюмдд ддайа АМ КесеЬе ЕЗ; Мдеаппыден А2; Бег Пчел." А2: Бе| ЕОЕ. АЗ: БепдЕ2; О гоА1; Еед. Устрейатдо дыак7а *Ы Кесепе ЕБ. Соде А$; Еед: Рпс. 6.9. Система пропессов, описанных на яаыке моделирования программ- ных процессов. Моделе параллельнмх вычисления 217 ные процессы множествами позиций (по одной на каждый тип сообщений), мы можем представить предложение зеЫ переходом„который помещает фишку в швицию, представлягощую соответствующие канальный процесс и тип сообщений. Предложение гесе)ое просто удаляет фишку из любой позиции канального процесса.
Конкретная позиция, которая поставляет фишку, определяет тип получаемого сообщения. Эта информация может использоваться в любом последующем предложении ип)езз. Единственным символом в выражении передачи сообгцений является тип сообщений для тех сообщений, которые посылаются к , или принимаются от канального процесса. Поскольку каждый переход в сети Петри приводит к появлению символа в языке сети Петри для этой сети Петри, то только предложения юЫ и гесе)ое в системе с ЯМПП могут быть промоделированы. Таким образом, существуют два вида позиций в сети Петри. Один вид позиций, помо кхгных рй,н, действует кек счегчик числа сообщений типа ьл3у тл в канальйом процессе 1,. Другой вид позиций представляет предложения яло' и гасе)ое программы ЯМПП.
Пусть зти предложения однозначно помечены з,, ..., з,. Мы пгееетим позицию, представляющую предложение з; с сообщением типа и; в буфере сообщений, символом рв,„. Фишка в позиции, ассоциированной с вот г предложением еь означает, что предложение е~ уже выполнено. Рис. 8.10 иллюстрирует, как предложения зь. вега и зь. гесе)ое должны моделироваться сетью Петри. На рис. 8.10 позиция рв, представляет позицию, ассоциированную с каким-либо предложением„которое предшесгвует предложению зн. Теперь осталось показать, что существует возможность определения предложения, предшествующего другим предложениям в программе на ЯМПП.
Отметим, что каждое предложение можно рассматривать как пару, состоящую из типа сообщения и номера предложения, поскольку одно и то же предложение с различными типами сообщений в буфере сообщений будет моделироваться сетью Петри различным образом. Наиболее очевидный способ определения предшественников предложения состоит в запуске в начале каждой программы на ЯМПП специального стартового предложения (которое становится стартовой позицией) н в порождении согласно описанию программ всех возможных последующих предложений еепа и гесеие с соответствующим им содержимым буфера сообщений.
Этот процесс повторяется для всех появляющихся предложений до тех пор, пока все предложения мел( и геев)ее не будут порсвкдены, а их последователи не будут идентифицированы. Поскольку число предложений в описании на ЯМПП и число типов сообщений конечно,то порождается только конечное число пар предложение/ !тип, сообп)ение. Эта процедура подобна характеристическим уравнениям, используемым Риддлом [258) для построения выражения передачи сообщений. На рис.
8.11 перечисляются предложения 218 Глава В лвс,5елее ~у ' гл Рнс. 8.10. Преобразование предложений левс1 и геелсое в переходы сети Петри еееллл — попель пренложенн» лала»о' с сообнсеннеы евна ле в бувара оообнсавне. Напальные процесс — 1, ляпав — мопель преп»ожени» лл гссвсе нл напального процесса Е и Воамомпые ляпы сообсцеяпп в Š— гп, еле, еэ и их возможные последователи для системы с ЯМПП, изображенной на рис.
В.9. После того как последователи предложения определены, мы можем, используя эту информацию, идентифицировать возможные предшественники предложения и, следовательно, построить сеть Петри, эквивалентную системе с ЯМПП, используя переходы, подобные приведенным на рис. 8.10. Специальная стартовая позиция является предшественником первого предложения каждого процесса системы. На рис. 8.12 система с ЯМПП, изображенная на рис. 8.9, преобразована в эквивалентную сеть Петри.
Краткое описание преобразования систем передачи сообщений в сети Петри показывает, что эта модель включается по мощности моделирования в сети Петри. Оно показывает также, что множество выражений передачи сообщений, рассматриваемое как класс языков, является подмножеством класса языков сети Петри. Поскольку Р/Ч-системы можно моделировать системами переда чи сообщений с сообщениями только одного типа, то РЛ~-системы Модели параллельных вычислений р, (Кесеые 1 1, -1 рз . (Бепй 1.3, КЕАР1 (Бепй 1 3. КИАР) (Кесеже $.2,! НР()Т) (Кесеже Е?, ЕОГ) (Бепп' Е5, О()ТР((Т) (Бепп' 1.4.
ЕОГ) (Бепй $З, КЕАР) ( ) р ' (Кесеые 1.2 1йРЬТ) р4 (Кесеже й? ЕОГ) р (Бепй 15 ОСТР()Т) р (Бепп' (.4, ЕОГ) Уппройоюйо ооой е рв . '(Косе~ее (-3. КЕАР) (Бепй 1„2, (МР()Т) (Беп(( Е?, ЕОГ) (Йесеже ЕЗ, КЕАР) (Кесепе (З, КЕАР) р ." (Бепй Ь?, 1ИР()Т) рд (Бепй с?, ЕОГ) Уооройотдо Фохйойо рж . -(Кесепе (.5 О()ТР()Т) — о- (Кесеже 1.5, О()ТРОТ) Рнс.
8.11. Предложении и последователи длн системы с Я)1(ПП, изображен ной на рис. 8.9. включаются в системы передачи сообщений. Легко построить систему с сообщениями для решения задачи о курильщикзх сигарет, поэтому включение Р/Ч-систем в системы с сообщениями является собственным, С другой стороны, системы с сообщениями не способны воспринимать входные сооб(пения от нескольких источников одновременно и поэтому не эквивалентны сетям Петри. При попытке моделирования перехода с несколькими входами может возникнуть один из следующих двух случаев: 1.
Процесс будет пытаться получить фишки (сообщения) из всех своих входов, но будет недопустимым, и поэтшиу будет блокирован, задерживая при этом фишки, которые нужны для того, чтобы позволить продолжать работу другим переходам. Это приведет к тупикам в системе с сообщениями, которые не соответствуют тупикам в сети Петри, что нарушает третье ограничение. 2. Процесс будет уклоняться от создания лишних тупиков, определяя, что оставшиеся нужные фишки отсутствуют, и возвращая Глава 8 Ю м Ф Ф о В о ы Р б л1одели параллельных еиеисленад 221 фишки в позиции (кзнальные процессы), из которых они были получены. Такие действия могут выполняться произвольно часто, а это означает, что не существует ограничения на длину последовательности действий в системе с сообщениями, соответствующей ограниченной последовательности запусков переходов в сети Петри. Таким образом, при этом нарушается наше второе ограничение.
сети йетри Ристеиы е ееюситиииаис Р/~Г-системах /рина с Ретислеиий - л"иве те иртетиемс Иарсиредиииасе .еииесы Рис. алз. добавление систем с сообщениями и иерархии моделей. Риддл 1259) представил преобразование, которое подпадаег под случай 1 и приводит к лишним тупикам. В любом случае мы видим, что системы с сообщениями не могут моделировать произвольные сети Петри (прв сформулированных нами ограничениях). Поэтому в результате мы получаем иерархию, приведенную на рис. 8ДЗ. е.й. гр ф искл Сеть Петри является графовой моделью параллельных вычислений. Другая графовая модель разработана в Калифорнийском университете в Лес-Анджелесе под руководством профессора Эстрина.
Эта модель является сложной билогичгской графоеой моделью вмчисеенпй (или графовой моделью $3С(.А) (19, 23, 302, 105, 491. В этой модели системы представляются графом со сложными ориентированными дугами. Сложная дуга — это дуга с (потенциально) многими источниками и назначениямип. Комбинационная логика управляет последовательностью операций в вершинах. Если входной логикой вершины является ло- И Формальное определение дается ниже. — Прим. Ред. Глана В Рис. 8.~4. Сложный билогическнй граф (граф $3С/ А). Модели иараллельиых выеиелеиий 223 гика И (»), то для того, чтобы разрешить действия, фишки должны присутствовать на каждой входной дуге.
При логике ИЛИ (+), фишки необходимы только на какой-либо одной входной дуге. Выполнение вершины удаляет разрешающие фишки на входных дугах и помещает фишки на выходные дуги в соответствии с выходной логикой. При выходной логике И фишки помещаются на все выходные дуги, тогда как при логике ИЛИ фишки помещаются на МульлуаРуга Юарагиьи Рис. 8Л5. Представление основных элементов графа ПС?.А в сети Петри. какую-либо одну выходную дугу. Число фишек, задействованных в данной паре вершина-дуга, называется слгепенью (или кратностью) этой пары и может быть любым целым неотрицательным числом.
??а рис. 8.14 приведен пример графа ?.?С?.А. Заметим, что некоторые дуги имеют несколько источников (окончаний) и назначений (начал). Кроме того, отметим, что логика каждой пары дуга- вершина помечена в графе либо » для логики И, либо+ для логики ИЛИ. Степень дуги указывается числом там, где дуга соединяется с вершиной. Степень опускается, если она равна единице, так же, как и обозначение логики, когда только одна дуга является входом в вершину. В приведенном примере вершина а может быть запущена, как только дуга 8 имеет фишки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
