Устройство для исследования сетей Петри Советский патент 1988 года по МПК G06F15/173 

и

00

4ik

14)

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

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

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

Устройство содержит модели 1(1)- 1(Н) вершин, где Н - колшгество вершин в исследуемой сети Петри, модели 2(1)-2(М) переходов, гд М - количе- JCTBO переходов в исследуемой сети |11етри, вход 3 задания разметки гене|ратор А одиночных жшульсов, первый 1регистр 5 сдвига 5, разрядность которо |ГО должна соответствовать -количеству |Вершин исследуемой сети Петри, nepBjrio Irpynny элементов И 6, второй регистр 17 сдвига, первый триггер 8 первый bjieMeHT И 9, формирователь 10 и яIyль- сов, первый элемент ИЛИ 11,) триггер 12, первый элемент 13 задержки,, первый генератор 14 импульсов, элементы И 15 и 16,, элементы 17 и 18 за,цержки9 )второй генератор 19 импульсов, второй И первьШ элементы НЕ 20 и 21, четвер а-ый злемект И 22, второй счетчик 23, (зазрядность которого должна обеспечивать хранение удвоенного числа моделей переходов и моделей переходов с взсодами для ингибиторных дуг, третий триггер 245 третий регистр 25 |гдвига, разрядность которого должна соответствовать количеству моделей йереходов и моделей переходов с входами для ингибиторных дуг первый счетчшс 26 той же разрядности что н У счетчика 23, дешифратор 27 на М+Е выходов, где Е - колш1ество переходов с входами для ингибиторных дуг в исследуемой сети Петри, элементы И 28 и 29, элемент НЕ 30, второй и третий элементы ИЛИ 31 и 32 элементы И 33 и 34J вторую группу элементов И 35j количество которых определяется количеством моделей переходоз и моделей иереходов с входами ,цля ингибиторнык дуг, элемент ИЛИ 36 и модели 37(1)- 37(Е) переходов с входами агся инги- торных дуг 5 Каждая модель 1 вершины йодержит реверсивный сч&тч №. 38 и

элементы VJM 39-41. Каждая модель 2 перехода содержит элементы И 42 и 43, Каждая модель 37 перехода с входами

для ингибиторных дуг содержит элементы или 44, И 45 и 46, элемент НЕ 47.

Модели 1 вершины имеют вход 48 эа- дания начальной загрузки разметки, входы 49( 1)49(M-t-E) приема фишек,

вькод 50 признака наличии фишек, входы 51(1) (M-i-E) изъятия фишек и вход 52 признака записи начальной разметки .

Каждая модель 2 перехода и модели

37 перехода с входами для ингибиторных дуг имеют входы 53(l)-53(H) условий перехода выход 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 присутствует уровень логической еди

ницы, поскольку на его первом входе уровень логической единицы задан с выхода первого разряда сдвигового регистра 5, а на втором - сигналом разрешения записи с входа 59, По заднем фронту сигнала разрешения записи с входа 59 в регистре 5 происходит сдви единицы на один разряд, и уровень логической единицы появляется на перво входе второго элемента И 6. Таким образом, подготавливается к записи первоначальной разметки счетчик 38 модели 1(2), После, установки в регистре 7 начальной разметки для второго места и вьщачи с входа 59 сигнала разрешения записи начальная разметка записывается в счетчик 38 модели 1(2). Таким образом последовательно производят начальную разметку для всех моделей. При загрузке последней разметки на установочном входе триггера 8 появляется уровень логической единицы, а на тактовом входе - сигнал разрешения записи с входа 59, в результате чего триггер 8 устанавли- вается в единичное состояние.

На входах элемента И 9 появляются логической единицы, один с прямого выхода триггера 8, другой с проинвертированного элементом НЕ 20 выхода признака переполнения счетчика 23, который находится в нулевом состоянии (исходном), Уровень логической единицы с выхода элемента И 9 запускает формирователь 10 и разрешает с некоторой задержкой, обусловленной элементом 13 задержки, необходимой для компенсации времени распространения сигнала в блоках 11 и 12, генератору 14 вьщавать последовательность импульсов. Формирователь 10 вырабатывает импульс, которьй, проходя через элемент ИЛИ 11, поступает на вход установки в единицу триггера 12„ К этому моменту времени генератор 14 вырабатывает первый импульс, который, проходя через элемент И 16 при наличии единичного уровня на прямом выходе триггера 12 с задержкой на элементе 17, необходимой для формирования импульса на выходе, элемента И 16, сбрасывает триггер 12 в нулевое состояние.

Генератор 19 постоянно вьфабаты- вает последовательность импульсов с периодом, значительно меньшим периода импульсов генератора 14, К моменту появления импульса с выхода эле

10

t5

20

25

40

30

35

45

50

5

мента И 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 устанавливается уровень логической единицы, еели иа всех подключенных к модели 37 йходах 53(1)53(Н) присутствуют уров- ии логической единицы а на входах $8(1)-58(К) - уровни логического нуля (это необходимо для реализации функций ингибиторных дуг, что означает наличие нулевой разметки в подклк) Ценных к данным входам модели 3.7 мо- елей 1 верши, на выходе элемента Ш 47 устанавливается уровень логи- геской единицы, что приводит к уста- ювке уровня логической единицы на выходе элемента И 45, т.е на выходе 5 моделей 2 и 37 появляется сигнал г1ризнака возможности вьшолнения пере- . При совпадении сигналов на вы- одного из элементов И 35 появля- eJTCH уровень логической единицЫа ко- 1}орый поступает на соответствую1чую Данному элементу И 35 модель 2 или 37, на ее вход 56, подготавливая эле- цент И 43 для моделей 2 переходов nirtH элемент И 46 дпя мoдeJJeй 37 переходу модели 1, проходит через элемент ИЛИ 40 и поступает на вычитакщий вход реверсивного сче тчика 38, вычитая из него одну метку (фишку). Импульс, поступивший на вход 49 последующей модели 1, проходит через элемент ИЛИ 39, поступает на суммирующий вход счетчика 38, прибавляя в нем однуметку (фишку).

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

поступает проинвертированньй элементом НЕ 30 сигнал с выхода элемента ИЛИ 36. В этом случае импульсы с генератора 14 проходят через элементы И 15 и 29, поступают на суммирующий вход счетчика 23, а череэ элементы И 33 или 34 - на управляницие входы сдвига влево или вправо регистра 25, Направление сдвига определяется содержанием триггера 24. В результате

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

з |одов к открыванию. На выходе злемен- 25 в регистре 25 осуществляется случай30

35

40

ИЛИ 36 появляется уровень логичес- к|ой единицы, который подготавливает 1 открыванию элемент И 28 и запреща- eJT через элемент НЕ 30 работу элемен- TJa И 29.

Генератор 14 вырабатывает следующий по счету импульс, который уже не сможет пройти через элемент И 16, так к&к триггер 12 установлен в нуле вое сЬстояние, а проходит через элемент И: 15, так как на его втором входе у|ста 1овлен уровень логической едини- цМ с инверсного выхода триггера 12. иЦтульс с выхода элемента И 15 посту- на входы элементов И 28 и 29, н|э пройти сможет только через элемент Hi 28 и далее на второй вход элемента ИЛИ 11, и с его выхода на вход установки в единицу триггера 12, устанавливая его по заднему фронту в единичное состояние и подгота вливая устрой- ство к выработке нового псевдослучайного числа, и поступает на вход 57 всех моделей 2 переходов и моделей 37 переходов с входами для ингибитор- нлк.дуг. По этому импульсу открьгоает- ся элемент И 43 одной из моделей 2 или элемент И 46 одной из моделей 37, и на ее выходе 54 появляется импульс, который поступает на входы 51 предшествующих данной модели 2 или 37 моделей 1 и на входы 49 последующих моделей 1. Импульс, поступивший на вход 51 предшествующей данному пере50

55

ный сдвиг влево или вправо. В счетчике 23 осуществляется подсчет количества сдвигов в регистре 25. Элементы ИЛИ 31 и 32 служат для организации циклического сдвига в регистре 25.

Сдвиги продолжаются до тех пор, пока в группе элементов И 35 не произойдет очередное совпадение единиц, а если совпадение не происходит, это свидетельствует об отсутствии разрешения переходов, т.е. о наличии тупиковой ситуации в сети Петри. После завершения цикла сдвига единицы по всему регистру 25 в счетчике 23 происходит переполнение, и проинвертиро- ванное элементом НЕ 20 значение признака переполнения счетчика 23 поступает на элемент И 9, запрещая работу генератора 14, и на выход 60 признака тупиковой разметки устройства.

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

Устройство для.исследования сетей Петри по авт. св. № 1345208, о т 5 в регистре 25 осуществляется случай0

5

0

0

5

ный сдвиг влево или вправо. В счетчике 23 осуществляется подсчет количества сдвигов в регистре 25. Элементы ИЛИ 31 и 32 служат для организации циклического сдвига в регистре 25.

Сдвиги продолжаются до тех пор, пока в группе элементов И 35 не произойдет очередное совпадение единиц, . а если совпадение не происходит, это свидетельствует об отсутствии разрешения переходов, т.е. о наличии тупиковой ситуации в сети Петри. После завершения цикла сдвига единицы по всему регистру 25 в счетчике 23 происходит переполнение, и проинвертиро- ванное элементом НЕ 20 значение признака переполнения счетчика 23 поступает на элемент И 9, запрещая работу генератора 14, и на выход 60 признака тупиковой разметки устройства.

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

Устройство для.исследования сетей Петри по авт. св. № 1345208, о т личающееся тем, что, с целью расширения функциональных возможностей за счет определения тупиковых разметок в сетях Петри с ингибитер- ными дугами, в него введена дополнительная группа моделей переходов, входы подключения простых и ингиби- торных дуг которых соединены с выходами подключения моделей переходов устройства, входы признаков возможности и разрешения вьшолнания rtepe- хода соединены соответственно с выходами признаков возможности и разрешения выполнения перехода устройст- 5 входами признака возможности вьтолне- ва, а выходы признака выполнения перехода моделей переходов дополнительной группы соединены с входами признака вьтолнения переходов устройства, каж,цая модель перехода дополнительной группы содержит элемент ИЛИ, первьш и второй элементы И, элемент НЕ, вы20

ния перехода и признака разрешения выполнения перехода модели перехода

дополнительной группь, выход второго элемента И является выходом признака выполнения перехода модели перехода дополнительной группы.

ход которого соединен с первым входом первого элемента И, а вход соединен с выходом элемента ИЛИ, входы которого являются входами ингибиторных дуг модели перехода дополнительной группы, с второго по К-й выходы первого элемента И (где К - число-дуг, подходящих к переходу) являются входами простых дуг модели перехода дополнительной группы, выход первого элемента И соединен с первым входом второго элемента И, второй и третий выходы которого являются соответственно

входами признака возможности вьтолне-

ния перехода и признака разрешения выполнения перехода модели перехода

дополнительной группь, выход второго элемента И является выходом признака выполнения перехода модели перехода дополнительной группы.