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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к области вычислительной техники, может быть использовало при моделировании сетей и позволяет определять тупиковые разметки в сетях Петри. Для этого в состав устройства введены модели вершин (мест), модели переходов, соединенные согласно топологии сети, и блок управления. После загрузки начальной разметки блок управления выбирает случайным образом переход из всех существующих разрешенных переходов и пускает модель сети. При наличии тупиковой разметки устройство вырабатывает сигнал - наличия тупиковой разметки и запоминает ее на счетчиках моделей вершин (мест). 2 з.п. ф-лы, 1 ил. со 4 сл ю о 00

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

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

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

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

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

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

По ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4058752/24-24 (22) 24.04,86 (46) 15.10,87. Бюл. В 38 (72) В,Н,Чуркин, И.И.Ласточкин и Б,Б.Борисов (53) 681.333(088.8) (56) Авторское свидетельство СССР

У 1171803, кл. G 06 F 15/20, 1983, Авторское свидетельство СССР

Ф 1134946, кл. G 06 F 15/20, 1983. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

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

„„SU„„1345208 А1 и позволяет определять тупиковые разметки в сетях Петри, Для этого в состав устройства введены модели вершин (мест), модели переходов, соединенные согласно топологии сети, и блок управления. После загрузки начальной разметки блок управления выбирает случайным образом переход из всех существующих разрешенных переходов и пускает модель сети. При наличии тупиковой разметки устройство вырабатывает сигнал наличия тупиковой разметки и запоминает ее на счетчиках моделей вершин (мест), 2 3 и. ф-лы, 1 ил.

Изобрете:-(ис с гн >; и: !! г --, <и< .! тельно>! тox,Hê «)>(:с:т

3 ФНЛН О (pH р Сl!Bill<(! .ijf() > r fl:: ., Л:<;(В ЧаСТ НОСТИ и(и М(11 .,li> !) r))<;"r f! < (. Е . *,*!1

Петрк.

Цель пзобр» гв с!<;! 0,3<: и )< !. 1( класса .)е(пас ?ff>f -;r< 1:1><::; "-т

ЛЕНИЯ 1 (/ПИ1(01!<:!?()и i>) :.: <)"

Петри.

НЛ ЧЕРтожс ПС,(СЛС(Л>г:. ">,. Оl!(!

НеН cxeì < 1/ . ; poi . <>л . г, стройствс . 1();i(f- );:с..::. >(.":.!

1(i), 1(2),,...1 !: 9 ";;(. !. ..с,.!! в0 вер;.I!ill н Hr c, с .),—. ";й .-"->: I<=. р

1,!ОДЕЛ(1 Пг> Р eX 0-!O

2 > (М!

9 дов в !<сспе;<(/с:.

Однночп

Га> pD )H;)l С i ; i.:(., (.> . ° ., . (ВЕтСт !ОВЛтЬ КР I <Ч<.-С г-„-. дуемои сеги I.:e! pH, - .:;( тов И 6 ()егкстi!,, r"(.-. ° " ме:1т И 9 форс!«)<)!>ят";;"эле>«ент ИПИ 11 p< "! .p, I; =-;.;г

13,àäåðæ;(H. г е<:.Сратор 1 элемент И ; 5,;1 e „"; ! 7 задер:/кг:! <, З)1<:. )с перс< "гop (.i. ..11(/i! r. < и 7I> эпei«e: т И .. :., с: вг:,"

>РЯДНС)СтЬ 1/i) > (Pul > ... <(>г . > ) !

<ение: ЯB.>е!«- .гс !<1- -: .:;r>

ХОДОГ 9 1"РЛI ГС <) . -! ...< .: ) .: >!;!

Раз!)Я/(!(Рс ь !< 0 f ()!; > (>

1С()ЛИЦ eC т1;," (/-.r С 1, е П чик 26 той !(e рлз!р! —... с -1ет<11.1кл 23 )e;r:.-с!; )и .;;;, .9 9 )

3а.; ." ;: ".",- <>;;, 33 и " - „. p""//пг:-

ЦОГ ГBO т,- -:.i r)ol

ВОМ !Oi(01- (< . H - . т/, .„, (с!)1()<ЛЯ I П), г(1Л "- Я -, .Г(-!!!

BepcHB":!i!.."i (ч e " <39-41. К,-;- (.;,«, .;() 1; держит э)!< менть> >, " . " „-с, и 2 км< >р-; .-I< г у<»(.(<"

/ / вход ч4 и:.>ч:.1;1- 11(>.

/ г / /

ВХОДЫ * )/ > .. /!-...;;;->,1; >(.-, чыхол -io >»)! .(;л-- > ,/ Г

Кt=, >ВXOГ, 41; ",!

/> реходл „-,<ыхсд », -.((

Hocт и пып;, . <и < i:! > «,с,>с:- <;::, :,, > )

П,>l!З1!В..!(<1 ??.i 1 .)> "П!< ° ",: ) > l !», /

>:оп 53 у; ка;-ерехода, вход 54 лпп: и нл <альной разметкИ.

:;:1:стпо работает следующим об, т-.lгlf"" )-.ход"в 5(- 45(M)

,, ((. ) ., выходов 4-6 моделей (Н/ i, т:)вка устройства к ра:<> ", . :Исxofy <о: сс>с= оянии триггеры 8 г;цс?х» реги<.-,ðû 5 и 25 и счет2 : и 26 лходятся в нулевом

„"т<)я! !li,, Пр-:. вклю=(енин устройства

"pH oð - ::)дкночного импульса выра-г< ст и IHу. E c> которьй устанавли<:.-рв и,),.зряд регистра 5 в едисл :ос);C>«."<.e,„ .Б регистре 7 уста,:. /;ир;- - .". Ся я пвои,но1-. код= значение зл<,> (), ре(-мет ;к для и =pBo;o места ,.<з;>!..,!1:. :.,), (. входа 54 выдается сигрлз-.<-. це:-"я злписк г!ача.чьной раз...:.-ки i)i(:i eр-: : К этому моменту спи i нс:ритор вырабатывает пер,<й . !!.у(1(.< 9 который„проходя через, 10. .е!. i 16, при нал1!чии единичнОгО

i:o=-.пя пл пр:-и <ом нь:: оде тригге" а 2 ,:.:i>ii:;:,е г::) -,,.— едник B нулевое сосо I)H

Г/".(,З)ор "= постоянно вырабатываг;-j .,-:...;. =: 1.?1(>(ГЬ ИМПУЛЬСОВ С ПЕ: !<) по:- . !1!eч.ггел.:>и 0 превышающкм пери..— .ль-»в; я=ритора 1- ". Х момен.Ег .И»:: ..".:Л1 СЛ С. ВЫХСДа ЗЛЕс»;=: "- ик 26 работает с . 0,.) -ie;i«.-..e "ак как на первом

:;-!. /i t". 22 установлен уро..-. <в-; ." д:;«кцы с выхода эле: я чторсм действуют

",и„: (. е Ррлт(>рл: 9 котОрые

9 9

>г(>.)ез =>-л „"-H И 22 постуГ г, " -.(И-у!<)!((К!. НХОд СЧЕтЧИКа 26.

"<" (1:. и 0 (»/p овня с выхода ! H!! зер-.ируется зпеменн -:: <,„е 1 мпульса нулевого .: ьпг ".", „.:-в г прохождение кмпуль:. l .п= .. гл 1- на счетчик 26. . ;- ".:.--:..i Bàe гся H в с.-;етчике 26

: я(-: /. !.л> (— то -!ceBä<)cëóи,-я, л > 1 оступает на вход дешиглр:,, )1,:- вых»де которогo появВ с)дllol. из M 1)аз рядов °

I /?! ..;: ;:, i л гыходе элемента 18 ...; !.,яп <с; импульс с выхода

:. "(:, з; держанный На время (1! (>с т<)/i H <- <и я с инала в зл(меHTBx

2 "" .. 1лп!<ь импу Ibc разреша1345208

55 о ет занесение случайного значения младшего разряда счетчика 26 н триггер 24, кода с выхода дешифратора 27 в регистр 25 и обнуляет счетчик 23, в счетчик 38 модели 1(i), так как на выходе первого элемента И 6 — уровень логической единицы, поскольку на его первом входе уровень логической единицы задан с выхода первого разряда 1О сдвигового регистра 5, а на втором— сигналом разрешения записи с входа 54.

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

Таким образом, подготавливается к записи первоначальной разметки счетчик

38 модели 1(2), После установки н ре- 20 гистре 7 начальной разметки для второго места и выдачи с входа 54 сигнала разрешения записи начальная разметка записывается в счетчик 38 моцели 1(2). Таким образом,.последовательно производят начальную разметку для всех моделей 1(К), где К=1,...Н.

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

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

Уровень логической единицы с выхода элемента И 9 запускает формирователь

10 и разрешает с некоторой задержкой, обусловленной элементом 13 задержки, необходимой для компенсации времени 45 распространения сигнала в элементах

11 и 12, генератору 14 выдавать последовательность импульсов. Формирователь 10 вырабатывает импульс, который, проходя через элемент ИЛИ 11, поступает на вход установки в единицу триггера, Таким образом, в одном из разрядов регистра 25 находится единица, означающая, что переходу с номером, соответствующим разряду, в котором находится единица, разрешено сработать при условии, что данный переход возможен °, 1анное условие проверяется груггой элементов И 35, иа первые входы которых поступает код из регистра 25, а иа вторые — сигналы о готовности переходов к срабатыванию.

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

Сигналы о возможности Н срабатываний пареходон поступают иа вторые входы элементов П 35 с выходов 51 моделей 2,, Если на всех подключенных к модели 2 входах 59(1)...59(Н) уровни логической единицы, что, в свою очередь,. означает наличие ненулевой разметки, которая обнаруживается элементом ИЛИ 4 1, объединяющим все разряды выхода счетчика 38 модели то на выходе элемента И 42 устанавливается уровень логической единицы, т.е. иа выходе 51 модели 2 появляется сигнал признака нозможиости выполнения перехода. При совпадении сигналов, на ныходе одиого из элем- 35 появляется уровень логической ециницы, поступающий »а соответствующую данному элементу И 35 модель 2 перехода, на ее вход 52, подготавливая эле— мент И 43 к открыванию. На выходе элемента ИЛИ 36 появляется уровень логической единицы, который подготавливает к открыванию элемент И 28 и запре— щает через элемент НЕ 30 работу элемента И 29.

Генератор 14 вырабатывает следующий по счету импульс, который уже не может пройти через элемент И 16, так как триггер 12 установлен н нулевое состояние, а прокодит через элемент

И 15, так как на его втором входе установлен уровень логической единицы с инверсного выхода триггера 12. Импульс с выхода элемента И 15 поступает на входы элементов П 28 и 29, но пройти может только через элемент

И 28 и далее — на второй нход элемента И31И 11 и с его выхода — иа вход установки в единицу триггера 12, устанавливая его по заднему фронту в единичное состояние и подготавливая устройство к выработке ноного псевдослучайного числа. Затем ои поступает на вход 52 всех моделей 2 переходов. По этому импульсу открывается элемент И 43 одной из моделей 2 и на ее выходе 50 появляется импульс, который поступает на входы 47 предшест)С(р с -.-,, >РО ((ХOi r,-.

ilpoHi>нер -.>ров,:).;1;oН >30Ц(1(Х Даl(пой МО (i» (t. ?;„>O it (- >Ей > > .

) г входЫ» по(.леду<вщь(х >.н „,:,,—.-,;...-! - „(11,,;пульс,, поступивший 1>а 1-х<1 7 ???????????????????? ???????????? i .,;:>ро:::од(>т (<" с; элемент ИЛИ />О i !!et< т !>В(т !:! н. ;Г:->:—

Т! H0L7Z(Z(. -)ХОД ЛОВP .0- :: il!О > ») .". 1 (>

ВЫЧИТЛЯ ИЗ !!ЕГО )- (>,.: (II!(>i О ;,1,> Т«1> (,фи tJI(> ) . И.>пу)(ь(" > ()" ° ->и>::T. !t."- .:

ВХОД -) .. ilOC OJIÚ (Oj!;= - i!О ><3;lt j 1!;

> дит чс . »с 3 .) J Ði!>7:;" -ll! > 3 „ i!< c t t,, (C y "I!,3HP "IO1jl бан-(яя н >!< (,;„;;,t! j;t р/!з>jð - >; i (.?;--,,ЕЛ<> Ч»!Е . Е(.: it -" Н!.t . О-(>ППИ ЗГО устана!3/!и „=!. т< 1 (><» < н>, <).

>(ЕСКС1>С, НС/Г(,т (> <->) З » >1,!:t«О.. > 1 крытию злемеп..- " )>О. 1(/.;-Г.:(:). ; которого ио(.т»/и(1(7 1.,"ii ный эпеменз (>(,i 3(Г 3 ;!r:,i.- » .,> элеме((та I I> .!(>, : .: пуп(с((с т е1((р; то > > /(, »1>1 элемен7ы !3 15,(2 .—:, Н,с,",,-„,:,>< т

C j "Iti(H17 tt«t >(Ий В .»»> tt 1 > » . »,, — т!» рез э ic! енть.: . 1 и )/1 —. >, .!(рцие нхo!>n! (.днига !i 1ен(. t н j! 17<

Гистра ?5, . ре= ">/371,7ит-:: з : гo гистре ?з о<.ущес. -г.- нет<.и (. у (: .:.. >i(i

CIiiii1i" БЛ Е )О HJi;:! !3(IP;, ii,, > Р "» .. . Е

I!POZ(CÄ". ОДИГ !-, < -.: =::Е, сд131(Г t н ре! j!. >1

>.,-) t(H >В Г Р /И : .:-:-М.

>(i °, O iиИ O>>c l <->>"!

1; а 3 р с л! с и! ),>;з х 17 е 1" "—,. õ i О >

>ИИ ТУ((()«О!),;, -, ане3)>1!е() i t !3>1 —, .; — —.;, с1 ji jt(t > >- t " >

ЛЕ> (Е1) .. / иизирует; ),(:.; .;.:-..:, и ((1!Иl> Н C -: .Т ) л З

)апреща»- па<>от-; с:;е; ат, -,-.

t)Oй< ) I3P (I! ) >i, и -, . ; <. :. з

:..тся ныхас.н 1(е ::сх ., а.)у(0щи)(03Г зи< >Гс .;.—,,-,; .- О(-.

ДЕЛЯЕ ГСН Н,)37-,.; .,.:;

1 (с < л еДу (!. t < - й! с -1 — — 1, И . -, <>1 Уста(:Н Н)н.>);. Р Сй .- т:-;.:t:, jib I

3(e IIQ / (I(it-, "< t у> i i ) >:, >>, ; >(I3 C (<7 t>!It><(0 » >." O!i ° .-.-,, > . >, (;,3

"-.ранитс.—. ".;.:-;:;;<»=„--:г -.;з; с:,- . о i>!ió>!,=:Изобретения

1. тройстно для исследования у,, тей Петри „СО/7()ржа(((ЕЕ МОДЕЛИ ВЕрTp i Tpzi: ãcpH., .7(ест(. элементов И,,>)а эпе>":ента ИПИ„ п=рные счетчик и е(>ат<)p 1:((пуп! сон) о т л H ч а юе с:: ем,.;; с целью расшис ия «ласса решае(:.ых задач за счет .1:7ецелеп 3я тупиконых разметок в сеГ

:<етри) н него введены М моделей

:з;)ехо.(о!3, два регистра сдвига, втосчет<(ик„ р- гистр, три элемента НЕ

>!i зле.;Опта задержки, второй генерат.:p имп -t!.ñoâ) ()Ор>миронатель импульдне груг; 71:! =.;ëåìåíòîâ И, третий (етнерт(Ж =-J(=-менты ИЛИ седьмой

«>..ь:!)t э".cj«t--.нт!.1 И и дешифратор, ..."(7!(ВЕРШИН И ПЕРЕХО IOI3 СОЕДИНЕНЫ

»и с (О то(!с/!Огни сети Петри, вход д/31!ия 1(ачал: ной разметки устройстОд <:>юче! к H)(it)op".(àö((oêíoìó входу иc рн, гыхо;! котс. рого подключен

"ходам > н-а;и ной загрузки разметки

«с(. (O,-елей нерпин, вход признака

:.i!Ic!! ачаль:OA разметки устройства

1, 1.:оч(-")1 к первым входам всех элеt . 1; <>н 1 е рной Г вуппы 1< вхОду сНН

;. -:а:,;,, пеи.:огс> триггера и входу .:1:знака сдвига псрного регистра ! га, 3(в:î". I»"-го разряда которого где П .- количество моделей

",,>(13 с.=ги Пет oH) подключен к вто)хо.>: К-Гс элемента И первой !! .!XD, «ОТОРО О ПОДКЛЮЧЕН К

Г;;.>Н па«е j(à ?H:tüíoé разметки

О ел>". н=-p:Uèíû, ьыход l!-го разиепи:>го регистра сдвига подклю- и> 7»>р!(анно(!НО! :.у входу первого

:Г.-; Н:ХО > КОТО!>ОГО Г ОДКЛ(0ЧРН

: . >Чс )> -. ó первого элемента И, «О »:р(го иодклю- .ei к нхо""ó оп >мигo:iате -я 1(мпупьсон и нхо;.-е !т-:. за!,ержки,, выход которого

:. Гпоие;-1 к -ходу пуска первого гене(н 3Н ..-(п.(7в, выход которого ,.:..e!- к первым входам н-.орого и г: > 1,:.- Го -..лементон И, ныход которого

;. «>(: «Входа-I второго элемента ,, с«и, перв.).-=, элемента ИЕ и с с ",J><.j->0 г-а задержки выход ко9

1>(дкс>2 .(.н . »»i joä)/ установки п T<»зого " 3>иггера, прямой выход

; ii-ГО Ио, t«;!iO>(ЕН К IJTOPGM>!" ВХОДУ

0! t-ie (c::. 1a И, ныход формирона- "и i -.(ов подкл«чен к первому ,Г:ого злемен(a ИПИ, выход

:;.,-О :;ОДК.Н0ЧЕН K ВХОДУ >/ CТаНОВКИ

3. Устройство,по п. 1, о т л и ч а ю щ е е с я тем, что каждая модель перехода содержит два элемента И, причем К-й вход условия перехода модели перехода подключен к К-му входу первого элемента И, вьгход которого подключен к первому входу второго элемента И и является вью:одом признака возможности выполнения перехода модели перехода, вход признака разрешения выполнения перехода которой подключен к второму входу второго элемента И, выход которого является выходом признака выполнения перехода модели перехода, вход пуска перехода которой подключен к третьему входу второго элемента И.

7 13452 в 1 второго триггера, инверсный выход которого подключен к второму входу второго элемента И, выход которого подключен к первым входам чет5 вертого и пятого элементов И, выход пятого элемента И подключен к второму входу первого элемента ИЛИ и к входам пуска переходов всех моделей переходов, выход второго элемента задержки подключен к входам синхронизации третьего триггера и второго регистра сдвига и входу установки в "0" первого счетчика, выход признака переполнения которого подключен 15 к входу второго элемента НЕ, выход которого подключен к второму входу первого элемента И и является выходом признака тупиковой разметки устройства, выход первого элемента HF, под- 1О ключен к первому входу шестого элемента И, второй вход которого подключен к выходу второго генератора импульсов, а выход — к суммирующему входу второго счетчика, разряды выхода которого, исключая младший разряд, подключены к входу дешифратора, выход P-ro разряда которого (Р=2,..., M-1) подключен к Р-му разряду информационного входа второго регистра 30 сдвига, выход младшего разряда второго счетчика подключен к информационному входу третьего триггера, прямой выход которого подключен к первому входу седьмого элемента И, а инверсный выход — к первому входу восьмого элемента И, выход которого подключен к входу признака сдвига вправо второго регистра сдвига, выход признака сдвига влево которого под- 4п ключен к выходу седьмого элемента И, выход первого разряда дешифратора подключен к первому входу второго элемента ИЛИ, выход которог о подключен к первому разряду информацион- 45 ного входа второго регистра сдвига, выход М-ro разряда дешифратора подключен к первому входу третьего элемента ИЛИ, выход которого подключен к M-му разряду информационного входа второго регистра сдвига, Т-й разряд выхода которого (Т=1,..., М) подключен к первому входу Т-го элемента И второй группы, выход которого подключен к Т-му входу четвертого элемен55 та ИЛИ и входу признака разрешения выполнения перехода Т-й модели перехода, первый разряд выхода второго регистра сдвига подключен к второму входу третьего элемента И, а М-й разряд — к второму входу второго элемента ИЛИ, выход признака возможности выполнения перехода P и модели перехода подключен к второму входу Т-го элемента И второй группы, выход .етвертого элемента И1П1 подключен к второму входу пятого элемента И и входу третьего элемента НЕ, выход которого подключен к второму входу четвертого элемента И, выход которого подключен к суммирующему входу первого счетчика и вторым входам седьмого и восьмого элементов И, 2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что каждая модель вершины содержит три элемента

ИЛИ, реверсивный счетчик, причем

Р-й вход приема фишки модели вершины подключен к Т-му входу первого элемента ИЛИ, выход которого подключен к суммирующему входу реверсивного счетчика, Т-й вход изъятия фишки »одели вершины подключен к Т-»у входу второго элемента ИЛИ, выход которого подключен к вычитающему входу реверсивного счетчика, вход признака на-, чальной разметки модели вершины подключен к входу признака записи реверсивного счетчика, вход начальной загрузки разметки подключен к информа— ционному входу реверсивного счетчика, разряды выхода которого подключены к входам третьего элемента ИЛИ, выход которого является выходом признака наличия фишек модели вершины. ре {:гор l,. !{ецж п{и {

;яти"-:, г,Ужгород, ул.Гроектная, 4