3.2. Одновременность и конфликт

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

Другая важная особенность сетей Петри — это их асинхронная природа. В сети Петри отсутствует измерение времени или течение времени. Это отражает философский подход к понятию времени, утверждающий, что одно из важнейших свойств времейи, с логической точки зрения, — это определение частичного упорядочения событий. В реальной жизни различные события укладываются в различные интервалы времени, и это отражено в модели сети Петри независимостью от времени управления последовательностью событий. Структура сети Петри такова, что содержит в себе всю необходимую информацию для определения возможных последовательностей событий. Таким образом, на рис. 3.3 событие «завершение выполнения задания» должно следовать за соответствующим событием «начало выполнения задания». Однако нет и не требуется никакой информации, связанной с количеством времени, необходимым на выполнение задания.

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

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

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

Обратимся к теории относительности. Одним из ее основных положений является утверждение, что передача чего-либо не может быть мгновенной. Даже информация о возникновении события распространяется в пространстве со скоростью, ограниченной скоростью света с.

Рис. 3.4. Моделирование непримитнвного события.

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

Такое представление, хотя и является необходимым для полноты рассмотрения происходящего, однако влечет за собой значительные трудности при описании и анализе динамического поведения сети Петри, когда определяется последовательность запусков переходов. Для простоты обычно вводят следующее ограничение. Запуск перехода (и соответствующего события) рассматривается как мгновенное событие, занимающее нулевое время, и возникновение двух событий одновременно невозможно. Моделируемое таким образом событие называется примитивным; примитивные события мгновенны и неодновременны. (Иногда это обосновывается тем, что время — это непрерывная действительная переменная. Следовательно, если мы присвоим каждому событию время возникновения, то вероятность того, что любые две произвольно выбранные непрерывные действительные переменные совпадают, равна нулю, и, следовательно, события неодновременны.)

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

Рис. 3.5. Представление непримитивного события прямоугольником.

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

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

Другая ситуация, в которой одновременное выполнение затруднено и которая характеризуется невозможностью одновременного

(кликните для просмотра скана)

возникновения событий, показана на рис. 3.8. Здесь два разрешенных перехода находятся в конфликте. Может быть запущен только один переход, так как при запуске он удаляет фишку из общего входа и запрещает другой переход.

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