Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984, страница 8

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

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

Непримитивное событие может быть представлено в виде двух примитивных событий: <начало непримитивного события», «конец непримитивного события» и условия «иепримитивное событие происходит». Эта ситуация может быть промоделирована с помощью сети, показанной на рпс. 3.4 Рес. Ззп Вред«тая»ение иеоримитиниы о события В»твид»т нряиоутсиннииом, ВгиЪ| Петри и другие предложили представля ~ь непри мити нные события в сети Петри в виде прямоугольника ~244~, как показано на рис.

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

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

Другая ситуация, в которой одновременное выполнение затруднено и которая характеризуется невозможностью одновременного Сети Петри длл моделирования слагая Рнс. 3.6 Моделирование выннслитс льной слктемы с пспользованнем непримн- тнвного перехода. р ЛиЪияь' едрхгйггпь дапегря .%%буне олгиулл ег Юьяуалуя 4 Ряс. 3.7. Одаовреяенность. Этп двн перехода люгут Г>ыть запущены в ля>бом порядке. Ряс. 3.8.

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

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

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

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

3З.1. Конечные автоматы На низком уровне вычислительные системы могут быть описаны автоматами. Автомат — это пятерка (9, Х, Л, Ь, Г), где (~ — конечное множество состояний (д„д„..., дь); Х вЂ” конечный входной алфавит; А — конечный выходной алфавит; 6: 9 х Х вЂ” ~-9 — функция следующего состояния, отображающая текущее состояние и текущий вход н следующее состояние; Г: () х х Х -~ Л вЂ” функции выхода, отображающая текущее состояние и текущий вход в выходной символ. Автоматы часто представляют в виде графов переходов, как, например, на рис. 3.9.

В графе переходов состояния представляются кружками, являкхцимися вершинами. Дуга из состояния д~ в д~, помеченная а/Ь, означает, что, находясь в состоянии дь автомат при входе а перейдет в состояние дп выдавая при этом символ Ь. Формально следовало бы записать б(дь а) = д~ и Г (дь а) = Ь. Сети Петри для моделирования Входной алфавит определяет входы автомата из внешнего мира, а выходной алфавит — выходы автомата во внешний мир. В качестве примера рассмотрим автомат, изображенный на рис. 3.9.

Этот автомат преобразует двоичное число, представленное последовательностью бит, начиная с младшего, в дополнение до двух. В данном случае входной и выходной алфавит состоит из трех символов: О, 1 и 1с. Автомат начинает работать в состоянии дь Символ сброса (Я) означает конец (или начало) числа и возвращает автомат в исходное состояние. Выход автомата для символа сброса является просто его повторением. о1о оп о1о по Ю Рис. 3ХК Граф переходов для конеч- ного автоиата, вычисляющего допол- нение до двух двоичного числа.

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

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

Общая схема проиллюстрирована на рис. 3.11. Заметим, что здесь не исключена возможность путаницы в поНятиях, таК КаК ПОЗиЦин„сООтввтетвуЮЩИе ВХОДНЫМИ ВЫходнЫМ символам, могут быть обоснованно названы входными и выходными позициями сети. Однако их не следует путать с входными или вы- Глава Л Рис. 3.11. Общий подход л модедирояаиию сяязи меасду сетью Петри и ииещиим миром. ходными позициями переходов. Несмотря на возможную путаницу, эти термины наиболее естественны для обоих понятий. В качестве альтернативного подхода к моделированию входов н выходов сети могут быть использованы переходы.

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

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

аласубт Рис. 3.12. Альтериатиииый подход иредсзаядеиия связи между сетью Петри и яиешиим миром, где вместо позиций используются переходы. Сигм Петра для лодеааросония Рис. 3.13. Сеть Петри, эквивалентная автомату иа рпе. 3.9. Для конечного автомата (ф Х, Ь, 8, Г) мы определили сеть Петри (Р, Т, 1, 0) таким образом: Р =Я() Хцб, Т =-(~е,. ~ дсЯ и оЕХ), ~ (гд, з) (дя ~ф 0(1„,,) =-- (3(4, о), Г(п, и)).