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

со

4 1C 4 1C

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

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

На фиг, 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 управления режимом работы.

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

Сеть Петри задается четверкой, С (Р, I, Т, 0, Р {Р.„ Pi, ,,,, Р fi l - конечное множество позиций, пл 0. Т t,, tj, ,,,, конеч- нов множество периодов, га О, Множество позиций и множество периодов не пересекаются, РГ)Т 0.1 Т- Р является входной функцией - отображением их переходов в комплекты по- зиций, О - - выходная функция - отображение из переходов в комплекты позиций. Структура сети Петри представляет собой совокупность позиций и переходов. Сеть Петри может быть представлена в виде графа с двумя типами вершин - позиции и переходы. При описании сетью Петри 1 аких-либо процессов или систе позиций принимают знание состояния.: или условие события,.Для описания динамики вводится понятие маркировки f/ , т.е. присвоение фишек позициям сети Петри, которые используются для определения выполнения сети Петри. Маркированная сеть Петри М {С, это совокупность структуры сети Петри С fP, I, Т, маркировки и может быть записана в виде М , I, Т, О, /xj.

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

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

Определяем ,i (Р,,1(г:)), ,iJ (Р; ,0(tj)), где D - определяет входы в переходы

В определяет выходы {j 1, ,,,, m; ,.,,,п),

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

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

В исходном состоянии схемы в блоке 4 памяти находится матрица входов D, в блоке 25 памяти находятся вререшенный переход, остается записанным в регистре 2.

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

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

мена срабатывания переходов, имеющих-|Q реходов в порядке их срабатывания из ся в. матрице D

15

25

30

в последовательности срабатывания. На вход 50 блока 3 управления поступает сигнал установки, обнуляющий через элементы ИЛИ 12 и 13 счетчики 11 и 26 соответственно. На вход 28 устройства поступает сигнал, записывающий в регистр 1 значение нормальной маркировки. Работа устройства протекает в два этапа: выбор разрешенных переходов и запись 20 их в блок 9 памяти; расположение раз- решаемьк переходов в порядке срабатывания с учетом времени срабатывания и их последовательная запись в блок 16 памяти.

Первый этап начинается с подачи сигнала на вход 29 устройства. После , этого блок 3 управления начинает вы- .рабатьшать управляющие сигналы, под действием которых информация с блока 4 памяти построчно поступает на первый вход схемы 5 сравнения, где происходит ее сравнение со значением начальной маркировки, поступающей на второй вход схемы 5 сравнения с регистра 1. Если в результате сравнения значение строки блока 4 памяти и значение начальной маркировки совпадают по всем сравниваемым разрядам, вырабатывается управляющий сигнал, in поступающий на суммирующий вход счетчика 11 и разрешающий запись в блок 9 памяти информации выходов с выхода 44 блока 3 управления. Содержимое счетчика 11 на каждом т.акте записи номера очередного разращенного це- рехода поступает через дешифратор 7, в позиционном коде на блок 9 памяти, указьшая адрес записи. Первый этап работы устройства заканчивается после просмотра всех строк блока 4 памяти и перезаписи всех разрешенных переходов с блока 4 памяти в блок 9 памяти. По окончании первого этапа сигнал с выхода 47 блока 3 управления устанавливает О через элемент ИЛИ 12 счетчик 11. При этом номер последней позиции блока 9 памяти, по адресу которой бьш записан последний раз35

45

50

55

блока 25 памяти и подает их на схему 15 сравнения. Одновременно из блока 9 памяти на схему 15 сравнения подаются двоичные номера разрешенных переходов . Это осуществляется следующим образом. Тактовые импульсы с выхода 49 блока 3 управления поступают через элемент 20 задержки и элемент И 17 на вычитающий вход счетчика 11, а на второй вход элемента И 17 подается высокий потенциал с выхода нулевого разряда дешифратора 7. Кроме того, тактовые импульсы поступают на первый вход элемента И 19, который закрывается на данном этапе, так как на второй его вход через элемент НЕ 18, подается высокий потенциал с выхода нулевого разряда дешифратора 7. В каждом такте происходит перезапись двоичного номера перехода в схему 15 сравнения, где он сравнивается с двоичным кодом перехода, имеющим на данном этапе наименьшее время срабатывания.

После того, как содержимое счетчика 11 станет равным нулю, с выхода нулевого разряда дешифратора 7 низкий потенциал закроет элемент И 17 и через элемен-г 18 НЕ. откроет элемент И 19. Тактовые импульсы нач1 нут поступать на вход признака записи счетчика 11. При этом все разрешенные переходы выбраны и в блок 9 памяти возможна запись новых разрешенных переходов при смене матрицы D или при записи в регистр 1 новой маркировки . Если в результате сравнения двоичные номера переходов совпали, то схема 15 сравнения вырабатывает управляющий сигнал, поступающий через элемент 27 задержки на вход признака записи блока 16 памяти и на суммирующий вход счетчика 26, который формирует адрес записи разрешенного переход из блока 9 памяти. После сравнения всех двоичных номеров разрешенных переходов из блока 9 памяти с двоичными номерами переходов из блока 25 памяти в блоке

Q реходов в порядке их срабатывания из

5

5

0

0

n

5

5

0

5

блока 25 памяти и подает их на схему 15 сравнения. Одновременно из блока 9 памяти на схему 15 сравнения подаются двоичные номера разрешенных переходов . Это осуществляется следующим образом. Тактовые импульсы с выхода 49 блока 3 управления поступают через элемент 20 задержки и элемент И 17 на вычитающий вход счетчика 11, а на второй вход элемента И 17 подается высокий потенциал с выхода нулевого разряда дешифратора 7. Кроме того, тактовые импульсы поступают на первый вход элемента И 19, который закрывается на данном этапе, так как на второй его вход через элемент НЕ 18, подается высокий потенциал с выхода нулевого разряда дешифратора 7. В каждом такте происходит перезапись двоичного номера перехода в схему 15 сравнения, где он сравнивается с двоичным кодом перехода, имеющим на данном этапе наименьшее время срабатывания.

После того, как содержимое счетчика 11 станет равным нулю, с выхода нулевого разряда дешифратора 7 низкий потенциал закроет элемент И 17 и через элемен-г 18 НЕ. откроет элемент И 19. Тактовые импульсы нач1 нут поступать на вход признака записи счетчика 11. При этом все разрешенные переходы выбраны и в блок 9 памяти возможна запись новых разрешенных переходов при смене матрицы D или при записи в регистр 1 новой маркировки . Если в результате сравнения двоичные номера переходов совпали, то схема 15 сравнения вырабатывает управляющий сигнал, поступающий через элемент 27 задержки на вход признака записи блока 16 памяти и на суммирующий вход счетчика 26, который формирует адрес записи разрешенного переход из блока 9 памяти. После сравнения всех двоичных номеров разрешенных переходов из блока 9 памяти с двоичными номерами переходов из блока 25 памяти в блоке

16 памяти остаются записанными разг решенные переходы в порядке их. сра- батьшания.

Появление в старшем разряде кольцевого регистра. 23 сдвига единицы, поступающей на первый вход элемента И 21, означает, что просмотрены все номера переходов, расположенные в порядке срабатывания в блоке 25 памяти. При этом открывается элемент И 21, на второй вход которого через элемент 24 задержки поступает сигнал с выхода. 49 блока 3 управления и с выхода которого импульс через элементы ИЛИ 12 и 13 поступает на вход установки в О счетчиков 11 и 26 соответственно. Кроме того, импульс поступает на второй вход блока 3 управления.

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

Ф.о рмула изобретения

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

10

15

20

25

30

35

40

45

50

55

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

ду элемента НЕ,выход которого подклю- ,

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

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

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

фиг.г