Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 38
Текст из файла (страница 38)
Графы вычислений не могут моделировать принятие решений или условное выполнение — это ограничение справедливо и для маркированных графов. Таким образом, наша иерархия моделей принимает вид, покшанный на рис. 84. Карп и Миллер Н471 подробно исследовали графы вычислений, особенно проблемы активности и безопасности. В действительности Модели пареллельныа вычислений их интересовало обеспечение и определение условий завершенности графа вычислений (т. е.
условия неактивности). Так как дуги (позиции) представляют очереди данных, то исследования ограниченности, проводимые Карпом и Миллером, были направлены на определение максимальной длины очереди. Эти различия в обозначениях и целях, а также отличия в определении моделей между графами вычислений и маркированными графами послужили причинои того, что никто не попытался соотнести результаты и алгоритмы Карпа и Миллера (1471 по графам вычиснений с работой (541 по маркированным графам. Пети Петри /рарлл елтиеееией аенееные айтеыаты Иирниребанные грар и Рне.
8А. Лобавленве графов вычвсленнй к нера рхнн моделей. ЗА. Р/У-системы Р- и Ъ'-операции над семафорами впервые введены Дейкстрой (791 для решения проблем синхронизации в системах параллельных процессов. Как таковые они могут использоваться для моделирования синхронизации и связи таким же образом, как и сети Петри. Патил использовал этот подход, когда определи,п задачу о курильшиках сигарет„чтобы показать ограниченность систем, которые могут использовать только Р- и Ъ'-операции между процессами. РИ-системы тем не менее популярны, н поэтому имеется много литературы по вычислительной технике, в которой обсуждаются или применяются зти операции, например, (44, 1791. В разд. 3.4.8 показано, что Р- и Ъ'-операции можно промоделировать с помощью сетей Петри Доказательство Патила (2331 свидетельствует о том, что это включение собственное: существуют задачи (например, задача о курилыциках сигарет), которые можно решить в сетях Петри, но нельзя с использованием только Р- и Ъ'- операций.
Однако Р7Ъ'-системы являются достаточно мощным средством, чтобы включать модели графов вычислений (1771 и модели конечных автоматов. Чтобы преобразовать конечный автомат в РФ-систему, мы ис- пользуем для моделирования каждого состояния автомата отдель- Глава Я 2!2 ный процесс. Каждому состоянию сопоставим семафор. Пусть (~ = = ф~ь дм ..., д„) — множество состояний, а б: Я х Х -~- Я вЂ” функция переходов с множеством действий Х. Сопоставим состоянию д; семафор 5; и процесс. В начале процесс выполняет Р(Б;).
В общем случае он будет ждать до тех пор, пока автомат не перейдет в состояние д;. После выполнения Р(3;) процесс выбирает произвольное а С Е, для которого определена функция Ь(д;, о), и выполняет У(5;), где д~ = 8(д;, и). После чего этот процесс возвращается по Рис. З.5. Конечный автомат. петле к своему Р (Ю;). Рис. 8.6 иллюстрирует преобразование конечного автомата, изображенного на рис. 8.5. Семафоры первоначально равны нулю, кроме семафора начального состояния, который инициализируется единицей. Для преобразования графа вычислений в РМ-систему каждой дуге (О ь ои) графа ставим в соответствие семафор ЗР е.
Значениемсемафора будет число элементов данных, ожидающих в очереди для этой дуги. Таким образом, первоначально значением семафора Я; и будет 7;,е. Для каждого узла в графе вычислений создается процесс. Процесс узла ив сначала выполняет Т, е Р-операций над семафорами Лье для всех дуг (о;, ои), направленных в ов. Этим обеспечивается то, что каждая очередь будет содержать не менее Т~.е элементов данных. Затем, поскольку каждая Р-операция уменьшает семафор, а правильным результатом является только уменьшение 5;,е на М7;,л, то мы выполняем Т;л — )р;л у-операций над Б~д, чтобы восстановить правильное значение Я~,е.
Мы завершаем процесс узла и„, выполняя р'е,, Ч-операций над семафором Зе,, для каждой дуги (ою о„), направленной из узла ии. Это преобразование проиллюстрировано на рис. 8.7 для узлов пв н о4 графа вычислений, приведенного на рис. 8.2. Отметим, что граф вычислений может проверять и осуществлять ввод из нескольких источников за один шаг, тогда как РФ-системы 213 Модели паеаллельнмх емаиолений Процесс Рт Процесс Ре Процесс Ре Процесс Рл Рис. 8.6.
Р/Ч-система дая конечного автомата на рис. 8.5. могут проверять и осуществлять ввод из нескольких источников только с помощью последовательности проверок и вводов из отдельных источников. Неспособность к проверке и вводу из нескольких источников одновременно является ключевым моментом доказательства Патила ограниченности Р/Ч-систем. Проблема состоит в том, что пока вы захватываете один ресурс, другой процесс может захватить второй ресурс, что приводит к тупику. Такой проблемы для графов вычислений не существует, так как источники не используются совместно процессами — не может быть двух узлов, разделяющих входные дуги. Это замечание существенно для построения Р/т/-системы, которая не попадала бы в тупик (завершалась) до тех пор, пока соответствующий граф вычислений не завершится.
Добавление Р/Ч-систем к нашей иерархии моделей приводит ее к виду, изображенному на рис. 8.8. 8.$. Системы передачи сообщений Использование Р- и У-операций для организации взаимодействий процессов в системе может осуществляться до тех пор, пока цет лучшего механизма связи.
Одним из предложений по улучшению 2!4 ! Глава 8 Рис. 8.7. Р7ч'-систем» процессов для двух у»лов графа вычислений ва рис. 8.2. Сели Пен ди 1 Р/7е-оиооююи Грп~ры Юичиаоений Конечныв идеоыаеаее Рис. 8.8. Добавление Р7ч'-сис- тем в иерархию моделей. Маркированные ера4ое~ этого механизма является предложение использовать пюбщенил Система с сообщениями — это набор процессов, которые взаимодействую1 с помощью пюбщений. Над сообщениями возможны две операции: послагпь н получить.
Передача сообщения подобна У-операции, а прием сообщения подобен Р-операции. Если при выполнении операции получить нет ни одного сообщения, то получатель ждет до тех пор, пока сообщение не будет послано. На этом механизме основана схема моделирования, предложенная Риддлом (2581. Эта модель кажется наиболее подходящей для моделирования протоколов в сетях ЗВМ. Риддл рассматривает (конечное) множество процессов, которые взаимодействуют с помощью аюби4ений.
Сообщения посылаются и запрашиваютея специальными процессами, называемыми кинильными процессами (почтовые ящики). Канальные процессы предоставляют, что существенно, комплект сообщений, которые посланы, но еще не приняты, или комплект запросов на сообщения от приемников, которые выданы, но еще не удовлетворены. Другие процессы системы называются программными процессами и описываются на языке моделирования программных процессов (ЯИПП). Модели параллельних зачислений 215 Пример системы из трех процессов приведен на рис.
8.9, Как видно из примера, описание процессов на ЯМПП является, по существу, схемой. Интерес представляет только деятельность по передаче сообщений в системе. Сообщения являются абстрактными элементами, единственной характеристикой которых является тип. Число типов сообщений в системе может быть только конечным. Сообщения посылаются из или принимаются в буфер сообщений в каждом из процессов. Существует только по одному буферу на процесс Предложениями ЯМПП являются: ее1 й Поместить сообщение типа г в буфер сообщений.
зепй и Послать сообщение в буфер сообщений канального процесса д тесное й Запросить сообщение из канального процесса Г. )Кдать (если необходимо) до тех пор, пока не будет получено сообщение. Сообщение помещается в буфер сообщений. илйэз 1 з: Проверить тип сообщения в буфере сообщений и перейти к предложению з, если сообщение имеет тип, отличный от 1.
Ц-ЕпеегпаИез! к Моделировать внутреннюю, зависящую от данных, проверку. Либо продолжать обработку, выполняя следующее предложение, либо перейти к предложению с меткой з. йо-го к Передать управление предложению з. епа: Завершить процесс. Система с ЯМПП моделирует множество параллельных процессов. Каждый процесс стартует в начале своей программы и выполняет свою программу до тех пор, пока ему не встретится предложение епй.
Риддл показывает, как построить выражение передами сообщений, которое представляет возможные потоки сообщений в системе и использует это выражение для исследования структуры системы и организации правильного функционирования. Это выражение передачи сообщений используется для тех же целей, что и язык сети Петри. Поэтому мы показываем, как описание системы процессов на ЯМПП может быть преобразовано в такую сеть Петри, что ее язык совпадает с выражением передачи сообщений из анализа Риддла. Это преобразование игнорирует выполнение отдельных предложений описания на ЯМПП, хотя с помощью незначительной модификации и они могли бы быть представлены в языке сети Петри. Для моделирования процесса сетью Петри используем по одной фишке на процесс и качестве программногосчетчика. Присутствие сообщения в канальном процессе также представляется фишкой.
Поскольку сообщения идентифицируются типом, то необходимо моделировать каждый тип сообщений в канальном процессе отдельной позицией. Очень важным свойством систем с ЯМПП является то, что число сообщений конечно. Каждый программный процесс также конечен. Только очередь сообщений занимает потенциально неограниченный объем памяти. Таким образом, способность моделировать канальные процессы и правильно представлять предложения еепй и гегеле являются наиболее важными аспектами преобразования описания на ЯМПП в сеть Петри. Моделируя каналь- прюеуююы Кесепе 1М АЕ жКЕАЬ, Бепд $.3, К сене Е2. ип1 ыааЧЛА2, Б С ООГЕОт Бенд Е5. Она АЦ А2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
