Устройство для исследования сетей петри

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 14 1) 4 С 06 Г 15/20 СЭ Фя 1 уИ;те,;, ,13ВЮ 44 д-;.,ПИСАНИЕ ИЗОБРЕТЕНА ВТОРСНОМУ СВИДЕТЕЛЬСТВУ У 39(54) УСТРОЙСТВОТЕЙ ПЕТРИ ЕДОВАНИЯ СЕ(57) Изобретение осится к жет быть ния сете ерсными) асширени ычисл споль Петри угами тельнои технике иэовано для исследос ингибиторными (иЦель изобретения -унк ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И.ОТКРЫТИЙ(56) Авторское свР 1345208, кл. С циональных возможностей за счет определения тупиковых разметок в сетяхПетри с ингибиторными дугами - достигается тем, что в устройство дополнительно введена группа моделей переходов 37 с входами для ингибиторныхдуг, содержащих элемент ИЛИ 44, первый 45 и второй 46 элементы И и элементы НЕ 47. В устройстве случайнымобразом осуществляется выбор перехода из всех существующих разрешенныхпереходов и определяется наличие тупиковой разметки исследуемой сетиПетри в зависимости от устанавливаемой начальной разметки. По достижении тупиковой ситуации в сети Петрив счетчиках 38 моделей 1(1)-1(Н) будет храниться разметка тупиковой ситуации. 1 ил.Изобретение относится к вычислительной технике, может быть применено для исследования сетей Петри с ингибиторными (инверсиыми) дугами иявляется усовершенствованием устройства по авт, св. Р 1345208.Целью изобретения является расширение Функциональных возможностейустройства за счет определения тупиковых разметок в сетях Петри с инги,биторными дугами,На чертеже представлена Функциональная схема предлагаемого устройства для исследования сетей Петри. 15Устройство содержит модели 1(1)1(Н) вершин, где Яколичество вершин в исследуемой сети Петри, модели:Петри, вход 3 задания разметки, гене -ратор 4 одиночных иггпульсов, первыйрегистр 5 сдвига, разрядность которо"го должна соответствовать количествувершин исследуемой сети Петри, первую 25,группу элементов И 6, второй регистр7 сдвига, первый триггер 8,. первыйэггемент И 9, Формирователь 10 импульсов, первый элемент ИЛИ 11 триггер12, первый элемент 13 задержки первый генератор 14 импульсов, элементыИ 15 и 16, элементы 17 и 18 задержки,рторой генератор 19 импульсов, второйй первый элементы НЕ 20 и 21, четвертый элемент И 22, второй счетчик 23,разрядность которого должна обеспечивать хранечие удвоенного числа мо"делей переходов и моделей переходовс входами для ингибиторных дуг, третий триггер 24, третий регистр 25сдвига, разрядность которого должнасоответствоцать количеству моделейПереходов и моделей переходов с входами для ингибиторных дуг, первыйсчетчик 26 той же разрядности, что иу счетчика 23, дешифратор 27 на М+Е45выходов, где Е - количество переходовс входами для ингибиторных дуг в исследуемой сети Петри, элементы И 28и 29, элемент НЕ 30, второй и третийэлементы ИЛИ 31 и 32, элементы И 33и 34, вторую группу элементов И 35,количество которых определяется количеством моделей переходов и моделейпереходов с входами для ингибиторныхдуг, элемент ИЛИ 36 и модели 37(1)37(Е) переходов с входами для ингиторных дуг. Каждая модель 1 вершинысодержит реверсивный счетчик 38 и элементы Рг 1 И 39-41. Каждая модель 2 перехода содержит элементы И 42 и 43. Каждая модель 37 перехода с входами для ингибиторных дуг содержит элементы ИЛИ 44, И 45 и 46, элемент НЕ 47,Модели 1 вершины имеют вход 48 задания начальной загрузки разметки входы 49(1) -49(М+Е) приема Фишек, выход 50 признака наличи 1 Фишек, входы 51(1) -51(М+Е) изъятия Фишек и вход 52 признака записи начальной разметки еКаждая модель 2 перехода и модели 37 перехода с входами для ингибиторных дуг имеют входы 53(1)-53(Н) условий перехода выход 54 признака выполнения перехода, выход 55 признака возможности выполнения перехода, вход 56 признака разрешения выполнения перехода и вход 57 пуска перехода. Каждая модель 37 перехода с входами для ингибиторных дуг дополнительно содержит входы 58(1)-58(К) условий ингибиторных дуг, где К " необходимое количестве ингибиторных дуг, поступающих на переход с входами для ингибиторных дуг.Устройство также содержит вход 59 разрешения записи начальной разметки и выход 60 признака тупиковой ситуацииаУстройство работает следующим образом.Коммутацией входов 49( 1)-49(М+Е) и 51(1)-51(М+Е), выходов 50 моделей 1(1)-1(Н) и входов 53(1)-53(Н), вы. ходов 54 моделей 2(1)-2(М) и 37(1)- 37(Е), входов 58(1)-58(К) моделей 37(1)-37(Е) между собой согласно топологии исследуемой сети Петри осуществляется подготовка устройства к работе. В исходном состоянии триггеры 8 и 12, а также регистры 5 и 25 и счетчики 23 и 26 находятся в нулевом состоянии. При включении устройства генератор 4 одиночного импульса вырабатывает импульс, который устанавливает первый разряд регистра 5 в единичное состояние. В регистре 7 устанавливается в двоичном коде значение начальной разметки для первого места (модели вершины), а с входа 59 выдается сигнал разрешения записи начальной разметки, по которому начальная разметка иэ регистра 7 записыва, ется в счетчик 38 модели 1(1), так как на выходе первого элемента И 6 присутствует уровень логической еди 3 1432ницы, поскольку на его первом входеуровень логической единицы задан свыхода первого разряда сдвигового регистра 5, а на втором - сигналом разрешения записи с входа 59. По заднемуфронту сигнала разрешения записи свхода 59 в регистре 5 происходит сдвигединицы на один разряд, и уровень логической единицы появляется на первомвходе второго элемента И 6. Такимобразом, подготавливается к записипервоначальной разметки счетчик 38модели 1(2). После установки в регистре 7 начальной разметки для второго места и выдачи с входа 59 сигналаразрешения записи начальная разметказаписывается в счетчик 38 модели1(2) . Таким образом последовательнопроизводят начальную разметку длявсех моделей. При загрузке последнейразметки на установочном входе триггера 8 появляется уровень логическойединицы, а на тактовом входе - сигнал разрешения записи с входа 59, врезультате чего триггер 8 устанавливается в единичное состояние.На входах элемента И 9 появляютсяуровни логической единицы, один спрямого выхода триггера 8, другой спроинвертированного элементом НЕ 2выхода признака переполнения счетчика23, который находится в нулевом состоянии (исходном). Уровень логическойединицы с выхода элемента И 9 запускает формирователь 1 и разрешает с 35некоторой задержкой, обусловленнойэлементом 13 задержки, необходимойдля компенсации времени распространения сигнала в блоках 11 и 12, генератору 14 выдавать последовательность 4импульсов. Формирователь 1 вырабатывает импульс, который, проходячерезэлемент ИЛИ 11, поступает на входустановки в единицу триггера 12. Кэтому моменту времени генератор 14вырабатывает первый импульс, который,проходя через элемент И 16 при наличии единичного уровня на прямом выходе триггера 12 с задержкой на элементе 17, необходимой для формирования импульса на выходе элемента И 16,сбрасывает триггер 12 в нулевое состояние,Генератор 19 постоянно вырабатывает последовательность импульсов 55с периодом, значительно меньшим периода импульсов генератора 14. К моменту появления импульса с выхода эле 547 4мента И 16 счетчик 26 работает в счетном режиме, так как на первом входе элемента И 22 установлен уровень логической единицы с выхода элемента НЕ 21, а на втором действуют импульсы с генератора 19, которые, проходя через элемент И 22, поступают на суммирующий вход счетчика 26Импульс единичного уровня с выхода элемента И 16 инвертируется элементом НЕ 21 и в виде импульса нулевого уровня запрещает прохождение импульсов с ге", нератора 19 на счетчик 26. Счет останавливается, и в счетчике 26 хранится какое-то псевдослучайное число, которое за исключением младшего разряда, поступаез на вход дешифратора 27, на выходе которого появляется единица в одно из М+Е разрядов, К этому моменту времени на выходе элемента 18 задержки появляется импульс с выхода элемента И 16, задержанный на время распространения сигнала в блоках 21, 22 и 26. Данный импульс разрешает занесение случайного значе" ния младшего разряда счетчика 26 в триггер 24, кода с выхода дешифратора 27 - в регистр 25 и обнуляет счетчик 23.Таким образом, в одном из разрядов регистра 25 находится единица, означающая, что переходу с номером, соответствующем разряду, в котором находится единица, разрешение сработать при условии, что данный переход разрешен. Данное условие проверяется группой элементов И 35, на первые входы которых поступает код из регистра 25, а на вторые - сигнад о готовности переходов к срабатыванию. Выходы группы элементов И 35 объединяются на элементе ИЛИ 36. Наличие сигнала единичного уровня на выходе данного элемента означает, что выбранный переход сработает.Сигналы о готовности к срабатыванию переходов поступают на вторые входы элементов И 35 с выходов 55 моделей 2 и 37, Если на всех подключенных к модели 2 входах 53(1)-53(Н) присутствуют уровни логической единицы, что означает наличие ненулевой разметки, которая обнаруживается элементом ИЛИ 41, объединяющим все разряды выхода счетчика 38 модели 1, на выходе элемента И 42 устанавливается уровень логической единицы, ес5 1432547 б ли на всех подключенных к модели 37 ходу модели 1, проходит через элемент входах 53(1)-53(Н) присутствуют уров- ИЛИ 40 и поступает на вычитающий вход ни логической единицы, а на входахреверсивного счетчика 38, вычитая 8(1)-58(К) - уровни логического ну- из него одну метку (фишку). Импульс, Бн ЖФ ля (это необходимо для реализации поступивппй на вход 49 последующеи функций ингибиторных дуг, что означа- модели 1, проходит через элемент ИЛИ ет наличие нулевой разметки в подклю, поступает на суммирующий вход Ченных к данным входам модели 37 мо- счетчика 38, прибавляя в нем однуметделей 1 вершин), на выходе элемента 10 ку (фишку). ЙЕ 47 устанавливается уровень логи- В случае, если на выходе элемента еской единицы, что приводит к уста- ИЛИ 36 установится уровень логическоовке уровня логической единицы на го нуля, подготавливается к открытию ыходе элемента И 45, т.е. на выходе элемент И 29, на первый вход которого 5 моделей 2 и 37 появляется сигнал 15 поступает проинвертированный элеменфизнака возможности выполнения пере- том НЕ 30 сигнал с выхода элемента хода. При совпадении сигналов на вы- ИЛИ Зб. В этом случае импульсы с геоде одного из элементов И 35 появля- нератора 14 проходят через элементы тся уровень логической единицы, ко- И 15 и 29, поступают на суммирующий торый поступает на соответствующую вход счетчика 23, а через элементы анному элементу И 35 модель 2 или И 33 или 34на управляющие входы 37, на ее вход 56, подготавливая эле- сдвига влево или вправо регистра 25. мент И 43 для моделей 2 переходов Направление сдвига определяется совпи элемент И 46 для моделей 37 пере- держанием триггера 24. В результате одов к открыванюо. На выходе элемен в регистре 25 осуществляется случай" а ИЛИ Зб появляется уровень логичес" ный сдвиг влево или вправо. В счетчиой единицы, который подготавливает ке 23 осуществляется подсчет количек открыванию элемент И 28 и запреща- ства сдвигов в регистре 25. Элементы е 1 через элемент НЕ ЗО работу элемен- ИЛИ 31 и 32 служат для организации та И 29. З 0 циклического сдвига в регистре 25.Генератор 14 вырабатывает следую- Сдвиги продолжаются до тех пор, щей по счету импульс, который уже не пока в группе элементов И 35 не про" сможет пройти через элемент И 16, так изойдет очередное совпадение единиц, как триггер 12 установлен в нулевое а если совпадение не происходит, это состояние, а проходит через элемент свидетельствует об отсутствии разре- И 15, так как на его втором входе ЗБ шения переходов, т.е. о наличии тупиуСтаовлен уровень логической едини- ковой ситуации в сети Петри. После ф с инверсного выхода триггера 12. завершения цикла сдвига единицы по Импульс с выхода элемента И 15 посту- всему регистру 25 в счетчике 23 пропрет на входы элементов И 28 и 29 40 исходит переполнение и проинвертироЭ нЬ пройти сможет только через элемент ванное элементом НЕ 20 значение приз- И 28 и далее на второй вход элемента нака переполнения счетчика 23 посту" ИЛИ 11, и с его выхода на вход уста- пает на элемент И 9, запрещая работу новки в единицу триггера 12, устанав- генератора 14, и на выход 60 призналнвая его по заднему фронту в единич" ка тупиковой разметки устройства. ное состояние и подготавливая устрой" . Таким образом, в устройстве слуство к выработке нового псевдослучай- чайным образом осуществляется выбор ного числа, и поступает на вход 57 перехода из всех существующих разревсех моделей 2 переходов и моделей шенных переходов и определяется на переходов с входами для ингибитор- личие тупиковой разметки исследуемой ных. дуг. Ло этому импульсу открывает О сети Петри в зависимости от устанав ся элемент И 43 одной из моделей 2 ливаемой начальной разметки. По доили элемент И 46 одной из моделей 37, стижении тупиковой ситуации в сети и на ее выходе 54 появляется импульс, Петри в счетчиках 38 моделей 1(1)- который поступает на входы 51 пред(Н) хранится разметка тупиковой шествующих данной модели 2 или 37 55 ситуации, моделей 1 и на входы 49 последующих Формула изобретения моделей 1. Импульс, поступивший на Устройство для.исследования сетей вход 51 предшествующей данному пере- Петри по авт. св. Ф 1345208, о т -Составтель О,ГречухинаТехред А. Кравчук Корректор И.Муска Редактор О.Юрковецкая Заказ 5443/43 Тираж 704ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д. 4/5 Подписное Производственно-полиграфическое предприятие, г. Ужгород, ул, Проектная, 4 л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет определения тупиковыхразметок в сетях Петри с ингибитврными дугами, в него введена дополнительная группа моделей переходов,входы подключения простых и ингибиторных дуг которых соединены с выходами подключения моделей переходовустройства, входы признаков возможности и разрешения выполнения йерехода соединены соответственно с выходами признаков возможности и разрешения выполнения перехода устройства, а выходы признака выполнения перехода моделей переходов дополнительной группы соединены с входами признака выполнения переходов устройства,каждая модель перехода дополнительнойгруппы содержит элемент ИЛИ, первыйи второй элементы И, элемент НЕ, вы 32547 8ход которого соединен с первым входомпервого элемента И, а вход соединенс выходом элемента ИЛИ, входы которого являются входами ингибиторных дуг 5модели перехода дополнительной группы, с второго по К-й выходы первогоэлемента И (где К " число дуг, подходящих к переходу) являются входамипростых дуг модели перехода дополнительной группы, выход первого элемента И соединен с первым входом второго элемента И, второй и третий выходы которого являются соответственновходами признака возможности выполнения перехода и признака разрешениявыполнения перехода модели переходадополнительной группы, выход второго элемента И является выходомпризнака выполнения перехода модели перехода дополнительной группы.