ГЛАВА 7. РАСШИРЕННЫЕ И ОГРАНИЧЕННЫЕ МОДЕЛИ СЕТЕЙ ПЕТРИ

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

Кроме того, в гл. 5 показано, что не все вопросы анализа сетей Петри разрешимы. Так, неразрешимы задачи эквивалентности и включения для множеств достижимости сетей Петри и языков сетей Петри, хотя эти задачи могут оказаться очень важными для получения оптимальных сетей Петри. Даже те вопросы анализа, которые разрешимы, очень трудны, имеется в виду то, что они требуют большого объема вычислений.

В этой главе мы исследуем предложения, которые были сделаны для преодоления двух ограничений сетей Петри: ограничений на мощность моделирования сетей Петри и ограничений на мощность разрешения сетей Петри. Во-первых, рассмотрим некоторые предложения по расширению модели сети Петри. Расширение модели сети Петри должно увеличивать мощность моделирования сетей Петри, но при этом оно может уменьшать их мощность разрешения. Влияние любого расширения на мощность разрешения расширенной модели требует тщательного изучения.

Отметив, что расширение модели сети Петри может приводить к уменьшению мощности разрешения, мы рассмотрим также, как мощность разрешения может быть увеличена посредством ограничения модели сети Петри. Уже предложены различные подклассы моделей сети Петри, которые обусловлены ограничениями на структуру сети Петри. Необходимо исследовать влияние этих ограничений как на мощность моделирования, так и на мощность разрешения.

Такое исследование покажет, как взаимосвязаны мощность моделирования и мощность разрешения, а также укажет границы обеих для модели сети Петри.

7.1. Границы возможностей моделирования с помощью сетей Петри

Исследователи, использовавшие сети Петри для моделирования систем, обнаружили, что возможности моделирования сетями Петри реальных систем ограниченны. Этим объясняется появление тенденции к расширению модели. Имеется несколько типов расширений.

Патил [231] предложил расширить сети Петри путем введения понятия области ограничения. Область ограничения — это множество позиций. Правило запуска модифицируется таким образом, что переход может быть запущен тогда и только тогда, когда в результирующей маркировке не все позиции, входящие в область

ограничения, одновременно имеют фишки (не пусты). Например, если есть область ограничения, то в любой момент времени либо либо должны быть пусты. Если не пуста, то фишка не может быть помещена в до тех пор, пока все фишки из не будут удалены, и наоборот.

Рис. 7.1. Переход исключающее ИЛИ. Переход может быть запущен, если одна из позиций имеет фишку.

Ное в своей модели операционной системы [214] ввел другое расширение: переход исключающее ИЛИ (рис. 7.1). В обычных сетях Петри переход запускается, когда все его входы имеют фишки. Такое правило называется логикой поскольку мы должны иметь фишки и в первом входе, и во втором входе, и в третьем входе и т. д. Переход исключающее ИЛИ может запускаться тогда и только тогда, когда точно один из его входов имеет фишки, а все другие фишек не имеют. Следовательно, разрешающее правило состоит в том, чтобы имел фишку или первый, или второй вход (но не оба одновременно). Когда переход запускается, он удаляет фишку только из входа с фишками.

Подобное расширение было использовано Баером в его модели компилятора [23]. Баер ввел понятие переклюнателя (рис. 7.2). Переключатель — это специальный переход со специальным входом, называемым переключающим, и точно двумя выходами (один помечен символом для пустого переключающего входа, а другой помечен символом для непустого переключающего входа). Переключаемый переход запускается, когда он разрешен (независимо от состояния специального переключающего входа). Когда он запускается, фишка помещается в выход, помеченный символом если переключающий вход пуст, или в выход, помеченный символом если переключающий вход не пуст. Таким образом, в зависимости от состояния переключателя запуск переключаемого перехода приведет к одной из двух возможных маркировок. Фишка удаляется из переключающего входа, если он имел ее, поэтому после того, как переключаемый переход запустится, переключающий вход будет пуст.

Рассмотренные расширения сетей Петри были предложены для решения определенных задач, с которыми встретились исследователи

Рис. 7.2. Запуск переключателя. Позиция переключающего входа изображена в виде пятиугольника. а — пустой переключатель; б - полный переключатель.

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

Из сказанного выше не становится ясным, что является ограничением (если оно существует) сетей Петри. Ответ на этот вопрос был найден после получения ответа на подобный вопрос и V-операциях Дейкстры над семафорами.

Дейкстра определил свои Р- и V-операции над семафорами для обеспечения синхронизации и связи в системах взаимодействующих процессов [781. Семафор может рассматриваться как целочисленная

переменная, которая принимает только неотрицательные значения. V-операция над семафором увеличивает значение семафора на единицу: наоборот, уменьшает на единицу до тех пор, пока результат не становится равным нулю; при процесс, прежде чем продолжать свою работу, должен ждать момента, когда можно будет уменьшить. Связь между семафорами и сетями Петри была выявлена в разд. 3.4.8.

Поскольку Р- и V-операции были предложены как механизм для решения всех задач синхронизации программ, то естественно возникает вопрос о полноте, т. е. об их способности к решению всех задач координации. Патил в 1971 г. [233] предложил доказательство того, что Р- и V-операции недостаточно мощное средство для решения всех задач координации. Его подход был весьма прост: он сформулировал задачу синхронизации, которая не может быть решена с помощью Р- и V-операций, — это задача о курильщиках сигарет.

Задача о курильщиках сигарет включает (по меньшей мере) четыре процесса, которые моделируют агента и трех курильщиков. Каждый курильщик непрерывно изготавливает сигарету и курит ее. Чтобы сделать сигарету, необходимы три составные части: табак, бумага и спички. Один из курильщиков всегда имеет бумагу, другой — табак, а третий — спички. Агент обладает бесконечными запасами всех трех составных частей. Агент кладет две составные части на стол. Курильщик, имеющий третий недостающий инградиент, может сделать и закурить сигарету, сигнализируя об этом агенту. Тогда агент помещает другие два из трех инградиентов, и цикл повторяется.

Если семафор поставить в соответствие каждой составной части, задача о курильщиках формулируется в терминах семафоров. Семафоры первоначально равны нулю. Агент увеличит два из трех семафоров с помощью V-операций, а затем ждет семафора «сделано». Соответствующий процесс курильщика уменьшает два семафора (с помощью -операций), а затем, произведя действия «сделать сигарету» и «закурить сигарету», увеличивает семафор, указывая «сделано». Задача заключается в том, чтобы разработать программу процессов курильщиков для того, чтобы определить, какой из трех процессов должен действовать в очередной момент. Действия агента фиксированны и не могут быть изменены.

Рис. 7.3 иллюстрирует очевидное «решение». Предположим, агент кладет табак и бумагу Тогда курильщик с бумагой может взять табак а курильщик с табаком может взять бумагу что в результате приводит к тупику.

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

Рис. 7.3. Задача о курильщиках сигарет.

Петри другого вида, и нет способа преобразовать сеть одного вида в сеть другого вида, не допуская возможности возникновения тупика.

Существовали некоторые сомнения, связанные с решением Патила, — особенно в том, что касается массивов семафоров [230], но тем не менее идея решения верна. следуя работе Патила, получена задача, которая не может быть решена Р- и V-операциями или сетями Петри. То же ограничение мощности моделирования было ранее определено Келлером [150].

Задача, сформулированная в [159, 7], вполне реальна. Предположим, что мы имеем два процесса производителя и два процесса потребителя. Первый процесс: производитель создает элементы данных для первого процесса потребителя а другой производитель для второго потребителя Элементы данных, которые произведены, но еще не использованы, помещаются в буфер: буфер для пары для Передача данных из буферов к потребителям происходит через общий канал. Канал может передавать только по одному элементу за сеанс, причем из любого буфера любому потребителю. Производители просто помещают данные в буфера. Потребители должны координировать свои действия по использованию канала. Управляющий потребитель приказывает каналу передать данные из соответствующего буфера. Все это схематично изображено на рис. 7.4.

Рис. 7.4. Процессы производителя/потребителя с буферизацией и совместно используемым каналом.

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

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

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

Более конкретно ограничение на моделирование с помощью сетей Петри состоит в неспособности проверить на наличие точно определенной маркировки в некоторой неограниченной позиции и осуществить действие в зависимости от результатов проверки. Это ограничение общеизвестно как неспособность к проверке на нулевую маркировку в некоторой позиции, и поэтому это свойство известно как проверка на нуль [150]. Сети Петри не могут проверить неограниченную позицию на нуль. [Если позиция ограниченна, то нуль может быть выявлен. Для ограниченной позиции с границей мы можем создать дополнительную позицию такую, что сумма является константой, равной для всех достижимых маркировок. Это позволяет нам проверить, равняется ли нулю, проверяя, равно ли (см. разд. 5.6).]

Упражнения

(см. скан)