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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике, может быть использовано для исследования сетей Петри и позволяет расположить разрешенные в сети перехс ды в порядке их срабатывания во времени. Так как сети Петри обладают свойством параллелизма , возможно появление критических ситуаций, т.е. возможности срабатывания перехода от двух маркированных позиций или двух разрешенных переходов от одной маркированной позиции. Если от двух ипи более маркированных позиций есть входные дуги в переход, то очередность срабатывания перехода должна определяться каким-Либо критерием . В данном устройстве в качестве критерия срабатывания перехода выбрано время срабатывания. С этой целью в устройстве задаются матрица входов сети Петри, матрица времен срабатывания переходов и значение начальной маркировки. Путем сравнения начальной маркировки со строками матрицы входов отыскиваются разрешенные для срабатывания переходы. После этого указанные переходы упорядочиваются в соответствии с их временем срабатывания и записываются в один из блоков памяти. 2 ил. (Л

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

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

РЕСПУБЛИК

А1

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4131309/24-24 (22) 23,07,86 (46) 15.02.88. Бюл. и 6 (72) Б.М.Герасимов, С.Ю.Переваров, В.В.Архаров и Е.В.Черньппев (53) 681.333(088.8) (56) Авторское свидетельство СССР

Ф 995094, кл. G 06 F 15/20, 1983 °

Авторское свидетельство СССР

9 684550, кл. С 06 F 15/347, 1979. (54),УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

СЕТЕЙ ПЕТРИ (57) Изобретение относится к вычислительной технике, может быть использовано для исследования сетей Петри и позволяет расположить разрешенные в сети переходы в порядке их срабатывания во времени, Так как сети

Петри обладают свойством параллелизма, возможно появление критических

„„SU„„1 74242 (5g 4 G 06 F 15/20 ситуаций, т.е ° возможности срабатывания перехода от двух маркированных позиций или двух разрешенных переходов от одной маркированной позиции.

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

После этого указанные переходы упорядочиваются в соответствии с их временем срабатывания и записываются в один из блоков памяти. 2 ил.

1374242

Изобретение относится к вычислительной технике и может быть использовано для исследований сетей Петри.

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

На фиг. 1 изображена структурная схема устройства для исследования сетей Петри; на фиг. 2 — функциональная схема блока управления.

Устройство содержит два регистра

1 и 2, блок 3 управления, первый блок 4 памяти, первую схему 5 сравнения, три дешифратора 6-8, второй блок 9 памяти, второй элемент 10 задержки, первый счетчик 11, второй элемент .ИЛИ 12, первый элемент ИЛИ

13, первый элемент 14 задержки, вторую схему 15 сравнения, третий блок

16 памяти, первый элемент И 17, элемент НЕ 18, второй элемент И 19, пятый элемент 20 задержки, третий элемент И 21, четвертый элемент 22 задержки, кольцевой регистр 23 сдвига, третий элемент 24 задержки, четвертый блок 25 памяти, второй счетчик

26, шестой элемент 27 задержки, информационный вход 28, вход 29,пуска.

Блок 3 управления содержит счетчик 30, схему 31 сравнения, триггер

32, элементы И 33-35, генератор 36 тактовых импульсов, регистр 37, элемент ИЛИ 38, триггер 39, элемент 40 задержки, элемент ИЛИ 41, элемент 42

ИЛИ, элемент 43 задержки, выход 44 номера перехода, первый 45, второй

46, третий 47 выходы синхронизации, вход 48 признака начала работы, тактовый.выход 49, вход 50 начальной установки, вход 51 управления режимом работы.

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

Сеть Петри задается четверкой, С = (P, I, T, О, P = Р.„, Р,, Р— конечное множество позиций, и О. Т = (с,, с,, ..., с 3- конечное множество периодов, m > О. Множество позиций и множество периодов не пересекаются, PDT = ф . I = Т Р является входной функцией — отображением их переходов в комплекты позиций. О = Т «Р — выходная фуйкция — отображение из переходов в комплекты позиций. Структура сети

Петри представляет собой совокуп5

55 ность позиций и переходов. Сеть Петри может быть представлена в виде графа с двумя типами вершин — позиции и переходы. При описании сетью

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

Маркированная сеть Петри M = С, р это совокупность структуры сети Петри С = Р, I Т, 01и маркировки и может быть записана в виде М =. Р, Т, Т, О,р1.

Выполнением сети, Петри управляют количество и распределение фишек в сети. Фишки находятся в позициях и управляют выполнением переходов сети.

Сеть Петри выполняется посредством запусков переходов. Переход запускается управлением фишек из его входных позиций и образованием новых фишек, помещаемых в его выходные позиции.

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

Один из переходов к анализу Петри основан на матричном представлении сетей Петри, Альтернативным по отношению к анализу сети Петри в виде (Р, Т, I, О) является определение двух матриц D и D, представляющих входную и выходную функции. Каждая матрица имеет m строк, по одной на переход, и и столбцов, по одному на позицию.

Определяем D Ц,ij = (Р;,Т(с )), И д,Ц = (Р;,О(г. )), где D — определяет входы в переходы, D+ определяет выходы () = 1, ш, — 1, ..., и).

Сети Петри обладают свойством параллелизма, в связи с чем возможно

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

Если от двух или более позиций есть входные дуги в переход и они маркированы, то очередность срабатывания перехода должна определяться какимлибо критерием, значение которого

3 1374 назначено для каждой позиции. В предлагаемом устройстве, предназначенном для разрешения критических ситуаций, в качестве критерия срабатывания перехода выбрано время.

В исходном состоянии схемы в блоке 4 памяти находится матрица входов

D" в блоке 25 памяти находятся времена срабатывания переходов, имеющих- 0 ся в. матриц D, в последовательности срабатывания. На вход 50 блока 3 управления поступает сигнал установки, обнуляющий через элементы ИЛИ 12 н

13 счетчики 11 и 26 соответственно.

На вход 28 устройства поступает сигнал, записывающий в регистр 1 значение нормальной маркировки. Работа устройства протекает в два этапа: выбор разрешенных переходов и запись их в блок 9 памяти; расположение разрешаемых переходов в порядке срабатывания с учетом времени срабатывания и их последовательная запись в блок

16 памяти. 25

Первый этап начинается с подачи сигнала на вход 29 устройства. После, этого блок 3 управления начинает вы- .рабатывать управляющие сигналы, под действием которых информация с блока 3р

4 памяти построчно поступает на первый вход схемы 5 сравнения, где происходит ее сравнение со значением начальной маркировки, поступающей на второй вход схемы 5 сравнения с

35 регистра 1. Если в результате сравнения значение строки блока 4 памяти и значение начальной маркировки совпадают по всем сравниваемым разрядам, вырабатывается управляющий сигнал, 40 поступающий на суммирующий вход счетчика 11 и разрешающий запись в блок

9 памяти информации выходов с выхода

44 блока 3 управления. Содержимое счетчика 11 на каждом такте записи 45 номера очередного разрешенного перехода поступает через дешифратор 7, в позиционном коде на блок 9 памяти, указывая адрес записи. Первый этап работы устройства заканчивается после просмотра всех строк блока 4 памяти и перезаписи всех разрешенных переходов с блока 4 памяти в блок 9 памяти, По окончании первого этапа сигнал с выхода 47 блока 3 управления устанавливает 0 через элемент ИЛИ

11 I t

12 счетчик 11. При этом номер последней позиции блока 9 памяти, по адресу которой был записан последний раз242 4 решенный переход, остается записанным в регистре 2.

Работа устройства на втором этапе заключается в следующем. С выхода блока 3 управления подаются тактовые импульсы через элемент 22 задержки на вход сдвига кольцевого регистра 23, который .выбирает двоичные номера переходов в порядке их срабатывания из блока 25 памяти и подает их на схему

15 сравнения. Одновременно из блока

9 памяти на схему 15 сравнения подаются двоичные номера разрешенных переходов. Это осуществляется следующим образом. Тактовые импульсы с выхода 49 блока 3 управления поступают через элемент 20 задержки и элемент

И 17 на вычитающий вход счетчика 11, а на второй вход элемента И 17 подается высокий потенциал с выхода нулевого разряда дешифратора 7. Кроме того, тактовые импульсы поступают на первый вход элемента И 19, который закрывается на данном этапе, так как на второй его вход через элемент

НЕ 18. подается высокий потенциал с выхода нулевого разряда дешифратора

7. В каждом такте происходит перезапись двоичного номера перехода в схему 15 сравнения, где он сравнивается с двоичным кодом перехода, имеющим на данном этапе наименьшее время срабатывания.

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

И 17 и через элемент 18 НЕ, откроет элемент И 19. Тактовые импульсы нач нут поступать на вход признака .записи счетчика 11. При этом все разрешенные переходы выбраны и в блок

9 памяти возможна запись новых pasрешенных переходов при смене матрицы

D . .или при записи в регистр 1 новой маркировки . Если в результате сравнения двоичные номера переходов совпали, то схема 15 сравнения вырабатывает управляющий сигнал, поступающий через элемент 27 задержки на вход признака записи блока 16 памяти и на суммирующий вход счетчика

26, который формирует адрес записи разрешенного переход из блока 9 памяти. После сравнения всех двоичных номеров разрешенных переходов из блока 9 памяти с двоичными номерами переходов из блока 25 памяти в блоке

1374242 решенные переходы в порядке их, срабатывания.

Появление в старшем разряде коль- °

5 цевого регистра 23 сдвига единицы, поступающей на первый вход элемента

И 21, означает, что просмотрены все номера переходов, расположенные в порядке срабатывания в блоке 25 па- 10 мяти, При этом открывается элемент

И 21, на второй вход которого через

45 второго блока памяти и входу первого дешифратора, выходы которого под50 ключены к адресным входам первого блока памяти, выход которого подключен к второму информационному входу первой схемы. сравнения, выход признака равенства которой подключен к вхо-55 ду первого элемента задержки, суммирующему входу первого счетчика и входу управления режимом блока управле16 памяти остаются записанными разэлемент 24 задержки поступает сигнал с выхода, 49 блока 3 управления и с выхода которого импульс через элементы ИЛИ 12 и 13 поступает на вход установки в "0" счетчиков 1.1 и 26 соответственно. Кроме того, импульс поступает на второй вход блока 3 управления.

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

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

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

40 ния, первый выход синхронизации : торого подключен к входу второго элемента задержки, выход которого подключен к входу опроса первой схемы сравнения, информационный вход устройства подключен к информационному входу первого регистра, вход признака записи которого подключен к второму выходу синхронизации блока управления, третий выход синхронизации которого подключен к первому входу первого элемента ИЛИ и первому входу второго элемента ИЛИ, выход которого подключен к входу установки в "О" первого счетчика, выход которого подключен к входу второго дешифратора и информационному входу второго регистра, выход которого подключен к информационному входу первого счетчика, выходы второго дешифратора, исключая выход нулевого разряда, подключены к адресным входам втброго блока памяти, выход нулевого разряда второго дешифратора подключен к первому входу первого элемента И и вхоI ду элемента НЕ,выход которого подключен к первому входу второго элемента И, выход которого подключен к входу признака записи первого счетчика, выход первого элемента задержки подключен к входу признака записи первого блока регистров, выход которого подключен к первому информационному входу второй схемы сравнения и к информационному входу третьего блока памяти, тактовый выход блока управления подключен к входу третьего элемента задержки, выход которого подключен к входу опроса второй схемы сравнения, входу четвертого элемента задержки, первому входу третьего элемента И и входу пятого элемента задержки, выход которого подключен к второму входу второго элемента И и второму входу первого элемента И, вы. ход которого подключен к вычитающему входу первого счетчика, выход четвертого элемента задержки.подключен к входу признака сдвига кольцевого регистра сдвига, выходы разрядов которого подключены к адресным входам четвертого блока памяти, выход старшего разряда кольцевого регистра сдвига подключен к второму входу третьего элемента И, выход которого под-. ключен к входу признака записи второго регистра, второму входу второго

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

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

1374242

Составитель А.Мишин

Техред Л.Сердюкова Корректор. М.Щароши

Редактор Е.Копча

Тираж 704 Подписное

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

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

Заказ 604/46

Производственно-полиграфическое предприятие, г.ужгород, ул. Проектная, 4