Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 33
Текст из файла (страница 33)
Было определено несколько подмножеств множества обычных сетей Петри: маркированные графы, бесконфликтные сети, простые сети, сети со свободным выбором (гл. 7). Каждый из этих классов сетей Петри, по-виднмому, имеет свой класс языков с присущими им отличительными ссобенностями, Некоторые исследования этих классов уже проведены. Известно [1Щ, что классы Е ЕР л л з б, б, Р и Р для простых сетей Петри (без петель и кратных дуг, все комплекты — множества, и для каждого 1л У(Е~) 11 0(У;) = а) идентичны соответствующим классам для обычных сетей Петри Нетрудно видеть также, что классы Х,л, бл и Р" не изменятся при ограничении сетей до сетей со свободным выбором (см.
разд. 7А.З). Остаются не изученными еще многие интересные случаи. В частности, языки, порождаемые маркированными графами или в общем случае бесконфликтнымн сетями, как оказалось, имеют структуру, напоминающую структуру детерминированных контекстно-свободных языков, их исследование многообещающе. Еще одна важная открытая задача касается отличия между т;- .
свободными языками (1., Р, ...) и неограниченными языками (Ь, Р, ...). Например, не известно, выполняется ли 7. = У.л или л л нет. 1. Выберите класс языков сетей Петри, отличный от языков Е;типа, и разработайте его теорию. 2. Определите все множество взаимосвязей между 12 классами языков сетей Петри, в частности для каждой пары классов языков сетей Петри, или покажите, что один класс содержится в другом, или найдите язык, находящийся в одном классе и не присутствующий в другом.
184 3. Рассмотрите возможность присвоения меток незнаниям сети Петри, а не переходам. Этот йодход использовался в 11041. Определите осуществимость такого подхода и, если ои возмсзкен, разработайте новую теорию языков позиций сетей Петри. 4. Разработайте теорию языков сетей Петри, в которой сети Петри рассматриваются не как порождающие язык, а как распознжщие его. ГЛАВА У РАСШИРЕННЫЕ И ОГРАНИЧЕННЫЕ МОДЕЛИ СЕТЕЙ ПЕТРИ В гл. 3 мы показали, что сети Петри могут быть использованы для моделирования самых различных систем: аппаратного и программного обеспечения вычислительных машин.
хнмкческих, социальных систем и т.д. Однако это разнообразие примеров лишь показывает, что сети Петри могут адекватно моделнронать некоторые системы, но могут существовать системы, которые нельзя должным образом моделировать сетями Петри, т. е. мощность моделирования сетей Петри имеет пределы. Кроме того, в гл. 5 показано, что не все вопросы анализа сетей Петри разрешимы. Так, неразрешимы задачи эквивалентности и включения для множеств достижимости сетей Петри н языков сетей Петри, хотя этн задачи могуг оказаться очень важными для получения оптимальных сетей Петри. Даже те вопросы анализа, которые разрешкмы, очень трудны, имеется в виду то, что они требуют большого обьема вычислений.
В этой главе мы исследуем предложения, которые были сделаны для преодоления двух ограничений сетей Петри: ограничений на мощносгпь моделирования сетей Петри и ограничений на мощность разрешения сечей Петри. Вопервых, рассмотрим некоторые предложения по расширению модели сети Петри. Расширение модели сети Петри должно увеличивать мощность моделирования сетей Петри, ио прн этом оно может уменьшать их мощность разрешения. Влияние любого расширения на мощность разрешения расширенной модели требует тщательного изучения.
Отметив, что расширение модели сети Петри может приводить к уменьшениюю мощности разрешения, мы рассмотрим также, как мопщость разрешения ьюжет быть увеличена пссредствгм ограничения модели сечи Петри. Уже предложены различные подклассы моделей сети Петри, которые обусловлены ограничениями на структуру сети Петри. Необходимо исследовать влияние этих ограничений квк иа мощность моделирования, так н иа мощность раэрешевня.
Такое исследование покажет, как взаимосвязаны мощность моделирования и мощность разрешения, а также укажет границы обеих для модели сети Петри. УЛ. Границы возмонаюстей моделирования с помощью сетей Петри Исследователи, использовавшие сети Петри для моделирования систем, обнаружили, что возможности моделирования сетями Петри реальных систем ограниченны. Этим объясняется появление тенденции к расширению модели. Имеется несколько типов расширений. Патил [23Ц предложил расширить сети Петри путем введения понятия области ограничения. Область ограничения — зто множество позиций.
Правило запуска модифицируется таким образом, что переход может быть запущен тогда и только тогда, когда в результирующей маркировке не все позиции, входящие в область Глава 7 1об ограничения, одновременно имеют фишки (не пусты). Например, если (ре, ра) есть область ограничения, то в любой момент времени либо р„либо ра должны быть пусты. Если п~ не пуста, то фишка не может быть помещена в радо тех пор, покавсе фишки из р,не будут удалены, и наоборот. Рис. 7.1.
Переход нсключаюшее ИЛИ. Переход 11 может быть запущен, если одна нз нозицнй р; к ра имеет фишку. Нос в своей моделя операционной системы СВС 0400 1214] ввел другое расширение: переход искличавн(ег ИЛИ (рис. 7.1). В обычных сетях Петри переход запускается, когда все его входы имеют фишки. Такое правило называется логикой И, поскольку мы должны иметь фишки и в первом входе, и во втором входе, и в третьем входе и т. д. Переход исключающее ИЛИ может запускаться тогда и только тогда, когда точно один из его входов имеет фишки, а все другие фишек не имеют. Следовательно, разрешающее правило состоит в том, чтобы имел фишку или первый, или второй вход (но не оба одновременно). Когда переход запускается, он удаляет фишку только из входа с фишками. Подобное расширение было использовано Баером в его модели компилятора 123). Баер ввел понятие лгрекляжатгля (рнс.
7.2). Переключатель — зтоспециальный переход со специальным входом, называемым переключающим, и точно двумя выходами (один помечен символом г для пустого переключающего входа, а другой помечен символом 1' — для непустого переключающего входа). Переключаемый переход запускается, когда он разрешен (независимо от состояния специального переключающего входа). Когда он запускается, фишка помещается в выход, помеченный символом е, если переключающий вход пуст, или в выход, помеченный символом 7", если переключающий вход не пуст. Таким образом, в зависимости от состояния переключателя запуск переключаемого перехода приведет к одной из двух возможных маркировок. Фишка удаляется из переключающего входа, если он имел ее, поэтому после того, как переключаемый переход запустится, переключающий вход будет пуст.
Рассмотренные расширения сетей Петри были предложены для решения определенных задач, с которыми встретились исследователи Расширенные и ограниченные модели сетей Петри Рис. 7.2. Эапуск перенлючателя. Позиция переключающего входа изображена в виде пятиугольника. и — пустой переключатель; б — полный переключатель. при попытках моделировать реальные системы. Однако акцент в этих работах сделан на моделирование, а не на теоретическую мощность сети Петри„поэтому в них не рассматривается, были ли эти расширения необходимыми или достаточными для решения общих проблем моделирования. Фактически во всех случаях рассматриваемые сети были безопасными и, следовательно, множество достижимости — конечным, т. е.
эти сети представляются конечными автоматами, которые в свою очередь (разд. 3.3.1) легко представляются ординарными сетями Петри. Очевидно, что в описанных случаях были введены не расширения, а некоторые удобства. В равд. 5.3 также показано, что многие расширения ограниченной модели сети Петри, например, допускающие кратные дуги и петли, в действительности являются не расширениями, а средствами, облегчающими моделирование.
Из сказанного выше не становится ясным, что является ограничением (если оно существует) сетей Петри. Ответ на этот вопрос был найден после получения ответа на подобный вопрос о Р- и уоперациях Дейкстры над семафорами. Дейкстра определил свои Р- и У-операции над семафорами для обеспечения синхронизации и связи в системах взаимодействующих процессов [731. Семафор может рассматриваться как целочисленная Глава 7 переменная, которая принимает только неотрицательные значения.
Ч-операция над семафором В увеличивает значение семафора на единицу: В = Б + 1. Р-операция, наоборот, уменьшает Я на единицу до тех пор, пока результат не становится равным нул'о; при 5 = О процесс, прежде чем продолжать свою работу, должен ждать момента, когда Б можно будет уменьшить. Связь между семафорами и сетями Петри была выявлена в равд.
3.4.8. Поскольку Р- и У-операции были предложены как механизм для решения всех задач синхрояизации программ, то естественно возникаег вопрос о полноте, т. е. об их способности к решению всех задач координации. Патнл в 1971 г. (233) предложил доказательство того, что Р- и У-операции недостаточно мощное средство для решения всех задач координации.
Его подход был весьма прост: он сформулировал задачу синхронизации, которая не может быть решена с помощью Р- н У-операций, — это задана о курильп1иках сигарсгп. Задача о курильщиках сигарет включает (по меньшей мере) четыре процесса, которые моделируют агента и трех курильщиков. Каждый курильщик непрерывно изготавливает сигарету и курит ее. Чтобы сделать сигарету, необходимы три составные части: табак, бумага и спички. Один нз курильщиков всегда имеет бумагу, другой — табак, а третий — спички. Агент обладает бесконечными запасами всех трех составных частей.
Агент кладет две составные части на стол. Курилыцик, имеющий третий недостающий инградиент, может сделать и закурить сигарету, сигнализируя об этом агенту. Тогда агент помещает другие два из трех инградиентов, и цикл повторяется. Если семафор поставить в соответствие каждой составной части, задача о курильщиках формулируется в терминах семафоров. Семафоры первоначально равны нулю. Агент увеличит два из трех семафоров с помощью У-операций, а затем ждег семафора «сделано».
Соответствующий процесс курильщика уменьшает два семафора (с помощью Р-операций), а затем, произведя действия «сделать сигарету» и «закурнть сигарету», увеличивает семафор, указывая «сделано». Задача заключается в том, чтобы разработать программу процессов курильщиков для того, чтобы определить, какой из трех процессов должен действовать в очередной момент. Действия агента фиксированны и не могут быть изменены.
Рис. 7.3 иллюстрирует очевидное «решение». Предположим, агент кладет табак и бумагу (17(1), Цр)). Тогда курильщик с бумагой может взять табак! Р(1)), а курильщик с табаком может взять бумагу (Р(р)), что в результате приводит к тупику. Патил доказал, что никакая последовательность Р- и Ч-операций не может коррекгно решить эту задачу.
Это было показано с помощью доказательства того, что все Р- и У-«решения» могут быть промоделиронаны сетями Петри определенного вида (каждый переход имеет не более двух входов), но что решением является сеть Пет- 189 Расширенные и ограниченные модели сетей Петри Рис. 7 3. Задача о курильщиках сигарет. ри другого вида, н нет способа преобразовать сеть одного вида в сеть другого вида, не допуская возможности возникновения тупика. Существовали некоторые сомнения, связанные с решением Патила, — особенно в том, что касается массивов семафоров (230), но тем не менее идея решения верна.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
