Книжка по сетям Петри (547616), страница 24
Текст из файла (страница 24)
Алгоритм преобразования иерархичаской сати в ееть в приорнтетамн соатоит в погледоеательной замене составных переходов, начннея е таких, у которых все внутранние переходы яростью. на фрагменты сати с приоритетами. Расомотрим сначала чаетный алучай иерархичаской сети, которая пред. атавплет собой апинстванный составной переход, вса внутренннэ лерююды которого — проетые. Пуеть ); - множеотво внутренних парехолое перехода г, Р, — множество его внутренних мает, луч — начальная разметка еети. Преобразование будет состоять а "раскрытии" составного переходе.
Для поотроенип Х-эквивалентного фрагмента аети а прнорнтетамн копируетея "внутренняя сеть" перехода т и «го входные и выходные маета. К копни добавляютел следующие маета и Х«пераязды (ам. рис. 63) . И 1) Л.переход Ь, с двумя выходными местами гцп, н епд,. Этот переход в сети с приоритетами будет менять разметку входных мест перехода г и активировать внутреннюю сеть. 2) Множество Л-переходов С, (с„„„, ср,..., ср„), где р,,..., р„- места из Р,. Эти переходы начнут работать тогда, когда ни один из внутренних переходов составного перехода г не сможет сработать, и "очистят" внутренние места от фишек.
3) Множество Л-переходов О, Ыы с(т,..., с(м) с входными местами ды дт,..., д . Место д; получает фишки от перехода Ь„с ксторым оно связано дугой. Эти Л-переходы будут восстанавливать начальную разметку внутренних мест после завершения работы внутренней сети. 4) Л-переход е„входнымместомкоторогослужитместо епг(,. Этот переход будет менять разметку выходных мест перехода г и инициировать восстановление разметки во внутренней сети. Для введенных переходов и простых переходов в г вводятся приоритеты следующим образом: рг(г1) ''' рг(гь) > рг(стчч) ) рг(ср ) '' ~ рг(ср ) ) ) рг(д,! =...
рг(см! ) рг(е,) > рг(Ь,), где гы..., гэ ~Е Т<. Введенные Л-переходы и места связываются дугами с простыми переходами и местами иерархической сети следующим образом. (1) Каждое входное место из'с соединяется дугой с Л.переходом Ь,. (2) Место гоп, становится входным и одновременно выходным местом каждого внутреннего перехода из Т,. (3) Место гоп, и кюхдое внутреннее место р, из Р, становится вход. ным местом соответственно Л-перехода сгчь и Л-перехода ср .
Рг (4) Каждое внутреннее место Р~ из Р, становится выходным местом ! Л.переходов из О„где ( = Д(е (р, ) . (5) Каждое выходное место иэ г' становится вьгходным местом Л-перехода е,. На рнс. 6.8,е показан пример составного перехода, на рис. 6.8,б — построенная по описанному алгорятму сеть с приоритетами. Анализ функционирования исходной иерархической сети с единственным составным переходом и построенной сети с приоритетами непосред. ственно убеждает, что эти сети эквивалентны. Дайствительно, пока не сработает переход Ь,, ни один переход из Т, не может сработать, так Как с: (эи >ю) а) гнс в.е.
Рис. 6.9. место гоп~ не содержит фишек. Переход Ь, может сработать только при тех условиях, при которых активируется составной переход т. После срабатывания Ь, место тип, получает фишку, и может функционировать подсеть, соответствующая внутренней сети перехода т. Переход Ь, не может повторно сработать, пока не сработает переход в,, соответствующий завершению составного перехода т, так как рг(в,) >рг(Ь,) .
Поскольку приоритет внутренних переходов перехода т — наивысший, то внутренняя сеть будет функционировать до тех пор, пока ни один из этих пцзеходов не сможет сработать. Лишь после этого может сработать переход с,„„, который "выключит" внутреннюю сеть, убрав фишку из гип,. Затем могут сработать остальные переходы из С,, удаляющие все фишки из внутренних мест. Переходы из От могут сработать и передать начальную разметку, которая хранится в местах О„..., О„„в соответствующие внутренние места. Наконец, может сработать переход е,, после чего функционирование фрагмента сети с приоритетами, соответствующего составному переходу с, ааканчивается.
Ярефиксные и терминальные языки, порождаемые в обоих случаях, совпадают. В случае произвольной иерархической сети преобразование в сеть с приоритетами состоит в последовательной замене составных переходов на фрагменты сети с приоритетами. Сначала заменяются составные переходы с простыми внутренними переходами. Затем заменяются составные переходы второго уровня. При этом процедура замены составных переходов второго уровня повторяет описанную выше процедуру замены составных переходов первого уровня. Однако она не затрагивает те переходы и места, которые входят в уже построенные по переходам первого уровня фрагменты сети с приоритетами.
Исключение составляют А.переходы Ь,„которые соединяются входными и выходными дугами с новым местом гип. Приоритеты переходов для второго уровня ниже приоритетов переходов в фрагментах для первого уровня. Приоритет )(-переходов Ь,, вставляемых вместо составных переходов второго уровня, равен приоритету, назначаемому переходам, охватываемым этими составныын переходами. О Т а о р е мл 6.11. Класс иерархических сетей равномощвн клвссвм ингийитсрных сетей и сетей с приоритетами и строго мощнее классов (ордикерных) сотай Петри и рвзуллркых сетей.
Д о к а з а т в л ь с т в о. Справедливость утверждения теоремы немадленно следует из теорем В.9 и 6.6. На рис. 69 показаны примеры иерархических сетей, которые порождают языки, не принадтюжащие классам языков сетей Петри. Помеченная иерархическая сеть на рис. 69,в задается структурированной формулой 1 ° (и)(с) и: (ьтв; Ь), (1 ° а; т! 95 и помечающей функцией Х такой, что Е(а) ее, Х(Ь) Ь, Цс) вс, Е(г) Х, т.е.
переход г является Х-переходом. Эта сеть пораидавт яаык, кото. рый, как было установлено а докааательстае теоремы 3.6, не порождается никакой помеченной сетью Петри. Сеть на рис. 63,6 порождает свободный язык (а, аа, авЬ, Ь, Ьа, Ьаа), который не принадлежит кпессу сво. бодных языков сатей Петри (см. докааатапьство таоремы 32) . П % 6.%. Сети с ожцджвем я строго яерархячеакяе сети Опредвпенне правил функционирования иерархической сети, данное в % 6.3, прадпопагает, что локальные и внешние входнью места внутренних переходов а составных переходах равноправны при выяснении возмож.
ности срабатывания пареходоа, В результате составной Переход завершает. ся, вали ни один нз его внутренних переходов не может сработать, так как хотя бы одно из аго входных мает, безразпнчно — локальное илн внешнее, не имеет фишек. Рассмотрим, например, иерархическую сеть на рис.
6.10. Еспи составной переход и перешеп а активное состояние, а переход а еще не сработал, то переход Ь нв может сработать и тогда переход и завершается н становится пассивным. Здесь место р, внешнее место для перехода Ь истороннае место для составного перехода и, служит как бы "внешним выключатв. лем" для внутренней сети перехода и: есин Р содержит фишку, то анут. ранняя сеть функционирует (срабатывает переход Ь), а отсутствие фишек а Р немайпенно зааершаат и (переход Ь не срабатыааат прн ЭТОМ! ° Меж но изменить семантику функцнснироаання иерархической сати таким об. разом, чтобы сторонние места служили на выключателями.
а "внешнимн задержками": в скучав сети на рис. ВЛО и описанной выше ситуации (переход а не сработал) . хотя переход Ь не может сработать, переход и нв за. еершается, а ждет появления фишек а места д Условием завершения перехода и будет служить тот факт, что покальное входное место перехода Ь нв содержит фишек. Таким обрезом, можно ввести новый тип нербрхических сетей — сети с ожш)синем, синтаксис которых полностью совпадает с синтаксисом церер хических сетей из % 6.3, но семантика изменяется за счет изменения уеловил завершения составного перехода. В иерархической сети с ожиданием активный составной переход и может завершиться, если для пюбого его анутреннего перехода г зерно, что (в) переход г пассивен, (б) не выполняется локаяыюе усяоене активации перехода г: ЧР Е Р„;. ДУ(Р) — Р(Р. П > О, Гда Рч, — МНОжаетВО ЛОКаЛЬНЫХ ВХОДНЫХ МЕСТ ПараХОда С Сети с ожиданием болев адекватно, чем "простые" иерархические сети, описывают н моделируют, напримар, структуры опереционных систем.
для которых типичны паралпаяьные процессы с ожиданием: процасс ждет информацию, вырабатыцаемую другими процессами, или процесс ждет осво. бождения ресурса, захваченного другими процессамн. Обозначим чертя 8, кпасс иерархических сетей, введенных а % В.З. а через,8, — класс иерархических сетей с ожиданием. Пару иерархических сетай — одна сеть И, из класса 8, и вторая сеть И, из класса 8т -нжв. аем подобными, если онн задаются одной и той жа формулой свтн.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
