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

 

Изобретение относится к вычислительной технике и может быть использовано для исследования сетей Петри с ингибиторными (инверсными) дугами. Цель изобретения - расширение функциональных возможностей за счет определения тупиковых разметок в сетях Петри с ингибиторными дугами - достигается тем, что в устройство дополнительно введена группа моделей переходов 37 с входами для ингибиторных дуг, содержащих элемент ИЛИ 44, первьш 45 и второй 46 элементы И и элементы НЕ 47. В устройстве случайным образом осуществляется выбор перехода из всех существзпощих разрешенных переходов и определяется наличие тупиковой разметки исследуемой сети Петри в зависимости от устанавливаемой начальной разметки. По достижении тупиковой ситуации в сети Петри в счетчиках 38 моделей 1(1)-1(Н) будет храниться разметка тупиковой ситуации . 1 ил. с «в (Л

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51) 4 G 06 Е 15/20

ОПИСАНИЕ ИЗОБРЕП=НИЯ 13 „-.,:...., ., g.

Н А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И.ОТКРЫТИЙ (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ СЕТЕЙ ПЕТРИ (61) 1345208 (21) 4204221/24-24 (22) 27,02,87 (46) 23. 10.88, Бюл. У 39 (72) В.Н. Чуркин, И.И.Ласточкин, Б.Б.Борисов, А.Н.Федотенкбв и А.И.Сысоев (53) 68 1.325 (088.8) (56) Авторское свидетельство СССР

Р 1345208, кл. G 06 F 15/20, 1986. (57) Изобретение относится к вычислительной технике и может быть использовано для исследования сетей Петри с ингибиторными (инверсными) дугами.

Цель изобретения — расширение функ„„Я0„„14З2547 А2 циональнык возможностей за счет определения тупиковых разметок в сетях

Петри с ингибиторными дугами — достигается тем, что в устройство дополнительно введена группа моделей переходов 37 с входами для ингибиторных дуг, содержащих элемент ИЛИ 44, первый 45 и второй 46 элементы И и элементы НЕ 47. В устройстве случайным образом осуществляется выбор перехода из всех существующих разрешенных переходов и определяется наличие тупиковой разметки исследуемой сети

Петри в зависимости от устанавливаемой начальной разметки. По достижении тупиковой ситуации в сети Петри в счетчиках 38 моделей 1(1)-1(Н) бу- @ дет храниться разметка тупиковой ситуации. 1 ил.

1432547

Изобретение относится к вычисли-: тельной технике, может быть применено для исследования сетей Петри с ингибнторными (инверсными) дугами и

5 является усовершенствованием устройства по авт. св. Р 1345208.

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

Иа чертеже представлена функциональная схема предлагаемого устройства для исследования сетей Петри. 15

Устройство содержит модели 1(1)-- 1{Н} вершин, где H - количество вершин в исследуемой сети Петри, модели ,2 (1) -2 (М) переходов, где М - количе,, ство переходов в исследуемой сети ,Петри, вход 3 задания разметки, ген-..— ратор 4 одиночных импульсов, первый регистр 5 сдвига, разрядность которо« го должна соответствовать количеству вершин исследуемой сети Петри, первую 25 группу элементов И 6, второй регистр . 7 сдвига, первый триггер 8,. первый элемент И 9, формирователь 10 импульсов, первый элемент ИЛИ 1 1„ триггер *

12, первый элемент 13 задержки„ пер- 30 вый генератор 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 и элементы PJIH 39-41. Каждая модель 2 перехода содержит элементы И 42 и 43.

Каждая модель 37 перехода с входами для ингибиторных дуг содержит элементы ИЛИ 44, И 45 и 46, элемент HE 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(K) условий ингибиторных дуг, где К - необходимое количестве ингибиторных дуг, поступающих на переход с входами для ингибиторных дуг.

Устройство также содержит вход 59 разрешения записи начальной разметки и выход 60 признака тупиковой ситуацииа

Устройство работает следующим образом.

Коммутацией входов 49(1)-49(M+E) и 51(1)-51(М+Е), выходов 50 моделей

1(1)-1(Н) и входов 53(1)-53(Н), аегходов 54 моделей 2(1)-2(М} и 37{1}-

37(E}, входов 58(1)-58(K) моделей

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 начальной разметки для второrо места и выдачи с входа 59 сигнала разрешения записи начальная разметка записывается в счетчик 38 модели t(2) . Таким образом последовательно производят начальную разметку для всех моделей. При загрузке последней разметки на установочном входе триггера 8 появляется уровень логической единицы, а на тактовом входе — сигнал разрешения записи с входа 59, в результате чего триггер 8 устанавли вается в единичное состояние.

На входах элемента И 9 появляются уровни логической единицы, один с прямого выхода триггера 8, другой с проинвертированного элементом НЕ 20 выхода признака переполнения счетчика

23, который находится в нулевом состоянии (исходном). Уровень логической единицы с выхода элемента И 9 запускает формирователь 10 и разрешает с 35 некоторой задержкой, обусловленной элементом 13 задержки, необходимой для компенсации времени распространения сигнала в блоках 11 и 12, генератору 14 выдавать последовательность 4О импульсов. Формирователь 10 вырабатывает импульс, который, проходя через элемент ИЛИ 11, поступает на вход установки в единицу триггера 12. К этому моменту времени генератор 14 вырабатывает первый импульс, который, проходя через элемент И 16 при наличии единичного уровня на прямом выходе триггера 12 с задержкой на элементе 17, необходимой для формирова- 5Q ния импульса на выходе элемента И 16, сбрасывает триггер 12 в нулевое состояние, Генератор 19 постоянно вырабатывает последовательность импульсов с периодом, значительно меньшим периода импульсов генератора 14. К моменту появления импульса с выхода эле547 4 мента И 16 счетчик 26 работает в счетном режиме, так как на первом входе элемента И 22 установлен уровень логической единицы с выхода элемента

HE 21, а на втором действуют импульсы с генератора 19, которые, проходя через элемент И 22, поступают на суммирующий вход счетчика 26 ° Импульс единичного уровня с выхода элемента

И 16 инвертируется элементом НЕ 21 и в виде импульса нулевого уровня запрещает прохождение импульсов с re", нератора 19 на счетчик 26. Счет останавливается, и в счетчике 26 хранится какое-то псевдослучайное число, которое за исключением младшего разряда, поступаеа на вход дешифратора

27, на выходе которого появляется единица в одно из М+Е разрядов. K этому моменту времени на выходе элемента 18 задержки появляется импульс с выхода элемента И t6 задержанный на время распространения сигнала в блоках 21, 22 и 26. Данный импульс разрешает занесение случайного значения младшего разряда счетчика 26 в триггер 24, кода с выхода дешифратора 27 — в регистр 25 и обнуляет счетчик 23.

Таким образом, в одном из разрядов регистра 25 находится единица, означающая, что переходу с номером, соответствующем разряду, в котором находится единица, разрешение сработать при условии, что данный переход разрешен. Данное условие проверяется группой элементов И 35, на первые входы которых поступает код из регистра 25, а на вторые — сигнад о готовности переходов к срабатыванию.

Выходы группы элементов И 35 объединяются на элементе ИЛИ 36. Наличие сигнала единичного уровня на выходе данного элемента означает, что выбранный переход сработает.

Сигналы о готовности к срабатыванию переходов поступают на вторые входы элементов И 35 с выходов 55 моделей ? и 37. Если на всех подключенных к модели 2 входах 53(1)-53(Н) присутствуют уровни логической единицы, что означает наличие ненулевой разметки, которая обнаруживается элементом ИЛИ 41, объединяющим все разряды выхода счетчика 38 модели 1, на выходе элемента И 42 устанавливается уровень логической единицы, ес5 1432547 б ли на всех подключенных к модели 37 ходу модели 1, проходит через элемент входах 53{1)-53(H) присутствуют уров- KIN 40 и поступает на вычитающий вход ни логической единицы, а на входах реверсивного счетчика 38, вычитая

58(1)-58(К) — уровни логического ну- из него одну метку (фишку). Импульс, 5 ля (это необходимо для реализации поступивппп на вход 49 последующеи функций ингибиторных дуг, что означа- модели 1, проходит через элемент ИЛИ ет наличие нулевой разметки в подклю- 39, поступает на суммирующий вход бренных к данным входам модели 3.7 мо- счетчика 38, прибавляя в нем однумет елей 1 вершин), на выходе элемента 10 ку (фишку).

ЙЕ 47 устанавливается уровень логи- В случае, если на выходе элемента еской единицы, что приводит к уста- ИЛИ 36 установится уровень логическоовке уровня логической единицы на го нуля, подготавливается к открытию

ыходе элемента И 45, т.е. на выходе элемент И 29, на первый вход которого

5 моделей 2 и 37 появляется сигнал 15 поступает проинвертированный элеменфизнака возможности выполнения пере- том НЕ 30 сигнал с выхода элемента хода. При совпадении сигналов на вы- ИЛИ Зб. В этом случае импульсы с ге оде одного из элементов И 35 появля- нератора 14 проходят через элементы тся уровень логической единицы, ко- И 15 и 29, поступают на суммирующий торый поступает на соответствующую вход счетчика 23, а через элементы р анному элементу И 35 модель 2 или И 33 или 34 « «на управляющие входы

37, на ее вход 56, подготавливая эле- сдвига влево или вправо регистра 25.

° 1 мент И 43 для моделей 2 переходов Направление сдвига определяется сотфти элемент И 46 для моделей 37 пере- держанием триггера 24. В результате

1 одов к открыванию. На выходе элемен- 2б в регистре 25 осуществляется случай а ИЛИ Зб появляется уровень логичес" ный сдвиг влево или вправо. В счетчиой единицы, который подготавливает ке 23 осуществляется подсчет количеЙ открыванию элемент И 28 и запреща- ства сдвигов в регистре 25. Элементы е1 через элемент НЕ ЗО работу элемен- ИЛИ 31 и 32 служат для организации та И 29. З циклического сдвига в регистре 25.

Генератор 14 вырабатывает следую- Сдвиги продолжаются до тех пор, щей по счету импульс, который уже не пока в группе элементов И 35 не просможет пройти через элемент И 16, так изойдет очередное совпадение единиц, как триггер 12 установлен в нулевое а если совпадение не происходит, это состояние, а проходит через элемент свидетельствует об отсутствии разреИ 15 так как на его втором входе З5 шения переходов, т.е. о наличии тупиу та1 овлен уровень логической едини- ковой ситуации в сети Петри. После ц ю с инверсного выхода триггера 12. завершения цикла сдвига единицы по

И пульс с выхода элемента И 15 посту- всему регистру 25 в счетчике 23 пропрет на входы элементов И 28 и 29

40 исходит переполнение и проинвертироЭ нЬ пройти сможет только через элемент ванное элементом НЕ 20 значение призИ 28 и далее на второй вход элемента нака переполнения счетчика 23 посту"

ИЛИ t 1, и с его выхода на вход уста- пает на элемент И 9, запрещая работу новки в единицу триггера 12, устанав- генератора 14, и на выход 60 призналнвая его по заднему фронту в единич" ка тупиковой разметки устройства. ное состояние и подготавливая устрой- - Таким образом, в устройстве слуство к выработке нового псевдослучай- чайным образом осуществляется выбор ного числа, и поступает на вход 57 перехода из всех существующих paspeвсех моделей 2 переходов и моделей шенных переходов и определяется на37 переходов с входами для ингибитор- личие тупиковой разметки исследуемой ных. дуг. Ло этому импульсу открывает- сети Петри в зависимости от устанав ся элемент И 43 одной из моделей 2 ливаемой начальной разметки. По доили элемент И 46 одной из моделей 37, стижении тупиковой ситуации в сети и на ее выходе 54 появляется импульс, Петри в счетчиках 38 моделей 1(1)который поступает на входы 51 пред- 1(Н) хранится разметка тупиковой шествующих данной модели 2 или 37 55 ситуации. моделей 1 и на входы 49 последующих Формула изобретения моделей 1. Импульс, поступивший на Устройство для.исследования сетей вход 51 предшествующей данному пере- Петри по авт. св. Ф 1345208, о т—

Составтель О.Гречухина

Техред А. Кравчук

Корректор И.Муска

Редактор О. Юрковецкая

Заказ 5443/43 Тираж 704

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д, 4/5

Подписное

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет определения тупиковых разметок в сетях Петри с ингибитврными дугами, в него введена дополнительная группа моделей переходов, входы подключения простых и ингибиторных дуг которых соединены с выходами подключения моделей переходов устройства, входы признаков возможности и разрешения выполнения йерехода соединены соответственно с выходами признаков возможности и разрешения выполнения перехода устройства, а выходы признака выполнения перехода моделей переходов доп лнительной группы соединены с входами признака выполнения переходов устройства, .каждая модель перехода дополнительной группы содержит элемент ИЛИ, первый и второй элементы И, элемент HE вы32547 8 ход которого соединен с первым входом первого элемента И, а вход соединен с выходом элемента ИЛИ, входы которого являются входами ингибиторных дуг

5 модели перехода дополнительной группы, с второго по K-й выходы первого элемента И (где К " число дуг, подходящих к переходу) являются входами простых дуг модели перехода дополнительной группы, выход первого элемента И соединен с первым входом второго элемента И, второй и третий выходы которого являются соответственно входами признака возможности выполнения перехода и признака разрешения выполнения перехода модели перехода дополнительной группы, выход второго элемента И является выходом. признака выполнения перехода модели перехода дополнительной группы.