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

Изооретеннс с-тио;л; ся к :---iucj - тельной технике и .южет .rv i, ;r з®вано при решении ча;., и,- . : ::а;|ач 13 частности . лир1.1ч;1: (п nc v;-} Петри,

Цель изоорете спя - pjcuipeirnc: класса решаемых задач а t: гет i):;p::, ления гупикопых размй ;г) -- - ; еч-;;х Петри.

На чертеже показа- - :Ъу:1 :;:1 Ч5: р.ч- пая схама устрокстел.

Устройстве сг|дер;ки г С)& П-1 vep-;

КО, 1 (2) , .. . , UlO , тле П -:оЛ : Р;Г

во Sepiiuni I ис следусг:г)н сета 1птр::. модели переходо) 2 1 / , 2 { 2; , ,, . „ , 2(М), где i i - кп тлиес Г -; -тягтех-: дов в 1 сс:1ед;/1;:мой сс лечпм , вход 3 за;1апия -jaaMPT - f ::o:i:-pm4j; одиночпьух кмпу гьсоБ . рег ис/тп д:;; га, разрядность ггот.Н ) ; :;сг:ка; ;: ; ветствовать количестЕП й мл чг сс,:; дуемой сети Нетрк, Dvnrrv пемсм-- тов И б, peri;CT p 7,, TTi r r-ci; 3, меит И 9, фирмиролате; ъ i С. ,i;-- vv::i; . элемент Ш1И 11, тр - Т ср , пемрч 13 задержки, reiiCpaTop 1 t 5; млу;; -/::;: элемент И 15, элеме 1т П 1 и, jJiiMv-e-;- 1 задержки,, элемент 18 --iri: ; - ::ж:л: i ператор 19 кмпу,г,, :),.e;-jci; 11, Пл и 21 „ элекепт И /2. слртчи 13.. о л

рядность КОч ОрОГЛ) ГЧЛ С ; Л ;г -| ;-Л |;П :р,:

неиие удвосЕиюго чисг;а ллл ходов, триггер 24. р/:л.;-г(:лр гЗ с. разрядность ;.о орoj o с;л1 ; -л : |}л С количеству мсдё, л .и с . чик 26 той ;ке разидгдл;стт -; :; . - счетчика 23,, деглифлгЛ -ор 2 ;л;: ri:i- дов i эттементь: 28 л 29 : .л::1 .;,.лт ; 30„ элемент)) ИЛИ 3; л 3 --:- ,h - i-- 33 и 34, группу :.)Л Л-Ч Т тсл , ч-;.. чпс-гво которых опред :.:.::-2-.л- чл;-,:чл зом модйлсй ; (ирел л: :и „ 36, элемент 37 ;:пд лл.:|;л; З лл 2) , Каледая -юдель ; вЛ|Л:1МНЬ ;:}/ лЛ;-лч ; версивп.1и с четчдк л}, ло лл.л;:: ;л

39-41. Кажд.Л ХК)Д с,;,;:: ::ергл::л;;: :л

держит элемеить И л л - . -,ле.;-л и 2 () нлодЬ: i вход 4 иачалл1-л 1Л а-лл л:-;- рл:л.лл .ч входы 5 ( I) , ,. , ( -л; 11;лпл-;- 11пл:л:к Л6 мри .гнака iani тгл . vin;.

ДЫ А7( О 5 , „ ,ч7 ;;М) НТЛЯЧЧ ;: Л1т;::;-д

48 прчл1нака зашл;-: лгллтллчгП тлл .,

КН„ входы - ) З i. I ) „ , „ ЛЛ- дЛ ЛП1);Л

рехода,, зьгход ЬО .ллшакл i;-: :...: перехо;;а. 5 1ЛЛ1Ь;0 :

лести ВЫПЛЛ11(Л:пЧ П О ГКЛ-: О:.; ,:л ::Л;л. - Признака H spoj; e4M.- иллп --лл1л;1 г е-„

Лтпа, /-ход )3 пуска перехода, вход 54 ;разла;1а яни;;-и начальной разметки,

У /тл:.л и :тпо работает следующим об- , л пм .,ийл входов 4 5 (1) . . . 45 (М) , И ) . ; . 4 / (М,| ,, выходов 46 моделей (О.,.:(Н) и выходов 49(1) . . .49(Н) , -,-).-, 2(М) между собой согласно то.:;.,:г;ГИ1 : ИС СТГВДУ ОМОЙ сетИ ПетрИ ОСуЩв: лл .яе - ся подготовка устройства к ра- :л)лс, I: нсходлом состоянии триггеры 8 . л-:. 3 также 5 и 25 и счет- :лк11 2-- н 26 находятся в нулевом- л::)Стоя :л1Г1 „ При включении устройства -л ератч:-р одиночного импульса выра- лд ьрзает и:.тпу: ьс„ который устанавли- - . первый рлзряд регистра 5 в еди- - 4-iiOf состояляе В регистре 7 уста- :мрли1:1ается н двошзном коде значение .4Лзль1Д)й рагл гетки ,цля первого места ; oepK;;-i {b ,) , С входа 54 вь;цается сиг- л;,:: рлзрси е;-:-ля записи начальной разК этому моменту 4 вырабатывает пер л,1й лмпулт-С; хоторый, проходя через 1лемен - Л 16, при наличии единичного /рорпя иа прль-ioM выходе триггера 12 л расынаел глзследний в нулевое сос- тояпие

Гсл Л ЛГор :9 постоянно вырабатыва- л : г:ос: едо1эа:л;льность импульсов с пе- лоцом, з ачлтельно превЕ га ающим пери- -ЛI имлульсов ленератора 14. К момен- ;io;r 4-:efUiR- импул1--са с выхода эле- и;..; г-а И it) слатчь-пч 26 работает л ;л:с /лсм редслме так как на первом : -.лле :;лемен-: г И 22 установлен уро- г- л;Л илеслч длниды с выхода эле- л- ллл Г , I , ;; иа втором действуют л /уЛпГ с геле1:;атора 19, которые, лчл - -ij ;;: четез элемент Н 22, посту- .( н, у ллнлующий: вход счетчика 26 ад ---;ил;1ого уровня с выхода :;. 4; -iGH-; ;i /1 1 i инвертируется элеменл 2: н в йкде импульса нулевого лл)Л;л -ляпрсчцает прохождение импуль- ЛЛ.1 Ч; енер чгора 19 на счетчик 26. 01лга ;авливаетс:я и в счетчике 26 ;-::кл 1Лг Л-, каиос-то лсевдослучайное мл;л,о., : -О оро1-, за исключением млад- р,;л::р дл, гюстз пает на вход деши- л:л гор;: /:, н,л выходе которого появ- ::Л ;;я ..;динлда в одном из М разрядов. . ;л1пм}- ьлок,.-;Г:у ла выходе элемента 18 л,,д л::л-: г пиглляетс импульс с выхода л-. М 16, задержанный на время ;.-;1Л1 /ос: гране1- ия сиг нала в элементах ; 22 . 2k, jlaHhb - импульс разрешает занесение случайного значения младшего разряда счетчика 26 в триггер 24, кода с выхода дешифратора 27 в регистр 25 и обнуляет счетчик 23, в счетчик 38 модели 1(1), так как на выходе первого элемента И 6 - уровен логической единицы, поскольку на его первом входе уровень логической единицы задан с выхода первого разряда сдвигового регистра 5, а на втором - сигналом разрешения записи с входа 54

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

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

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

11и 12, генератору 14 выдавать последовательность импульсов. Формирователь 10 вырабатывает импульс, который, проходя через элемент ИЛИ 11, поступает на вход установки в единицу триггера.

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

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

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

Генератор 14 вырабатывает следующий по счету иг шульс, который },тке не может пройти через элемент И 16, так как триггер 12 установлен в нулевое состояние, а проходит через элемент И 15, так как на его втором входе установлен уровень логической единицы с инверсного выхода триггера 12. Импульс с выхода элемента И 15 поступает на входы элементов И 28 и 29, но пройти может только через элемент И 28 и далее - на второй вход элемента ИГМ 11 и с его выхода - на вход установки в единицу триггера 12, устанавливая его по заднему фронту в единичное состояние и подготавливая устройство к выработке нового псевдослучайного числа. Затем он поступает на вход 52 всех моделей 2 переходов. По этому импульсу открывается элемент И 43 одной из моделей 2 и на ее выходе 50 появляется и шyльc, который поступает на 47 предщестBjnouj.i-ix данной мо.пели I моле: ей и входы Д5 ггоследу|0пд х моде.. Импульс, 11ос гупнвв1ик на вход 1 прс шествующей модели 1 -.. Г роход т чп: элемент ИЛИ 40 v пгкггугтает :э тающий иход реверс -:пиог о счгггчпк,; вычитая из него едепипу ра;- мет1С1 (фишку), Иыпульс, ; ос Г}ш;Ш;|; - м ка вход 49 последую;1:ей модели i , пр; дит через элемент kLTIH ЗЭ, лссту ;; на суммирующий вход счгггч гк;. ЗВ. бавляя 13 нем единицу ряз -гр гч;р1 В случае, ecaii ;;п вмхги ; - 3jrc 4( ИЛИ 36 устанаклИБас:тс5 : уро ;-:-яь л ческого нуля., будет ;к)()Ягте i крытию элемент Ic 29 5 на пориыл г-; которого посч упает ттрот ив л ирсл;; ный эJIeмeнтo НЕ ЗС с: Mhi,( 4

ЭЛемеНТа /UUl Jb, Г; ::-;T(J -- : . М7;;аС :пульсь с геиерат(5ра П);) элемеить И 15 и 29, , ути1кл и; суьпчирующий Бхо,г 3, г рез элеь::енть И 33 и 3 i - ii- 1цие входы с;дпи: а .изево ; в п:рапо гистра 25, I 1 пзультатб n i oro ч гистре 25 осущес :-лляется с/1Ун(й: сдвиг Блечо или imptiiir; 3 :: :« происходит подсчет :олн.чс;1; г.а гов 3 регистре 25 , Эл;.;: -:;г ;-- 3 слу);;ат для орга;иг ;г::;л( д;:кл т сдвига в рЕ1 И1. 25 :

Сдвиги продолжают сг до го пока в rpynvjc; sxeMPiiToii li 55 исходит очерегпк е с jnn ,;л: ггг:: ; а если сояпадеаис 1Т|}оь;-;..:чО/ это сзи)тетельстйу п о- г-тсу ., :)азрешси Г;1х пет ехоцоь- : ; , мии тупиконс и г;-ггуа л-а : й : . завер 1е1п-1л иик.т:а сд ;;а-а :j(

rSCSMV D 6 ТТ-Г с D . 25 Ъ .| Ma.tr

)фоисход - г ibD aua: а атаг/ - :: iipoHnBep ) 4poBafu;o T .ja; ;- a,v-,: i

значение ПТСа О рЯ;ИЗяГл ;- (;:

: Лемевт 37 ин/дпспаа.; к--гп ам пизирует о /,сс а: у а; г ации в сети Па аза, - г -га ia-;f:a аапрещак работу ;аа;ератгр,-) - . Таким о5гчг:-о-.а в м-е,д1:л: а;а-. ройстве случай}а,: ;ajpft a-- атся выбор г ерг хода -а jnayv с )утащи}с рГ;Зрс 1 е: аьа; леро иаго/а деляется наличие /а/лк а -о ; :ai; исследуе:Г-1ОЙ сэти Пе лр;и .v; аалаа ,с)Т ycTaKanJii-nsfiKcii аг.ча- ьиоа I M, По дострййеааи туп гкс;;ой р: 13 счетчпишх 38 модел -; : - : i, - хранится larfjjiixoi a;:; ; ua. ,

обретения

Уг

1. Устройство для исследования сетей Петри, содержащее модели вер- три триггера, шесть элементов И дяа элеьгента ИЛИ, пэрвые счетчик и jaaiepaTop импульсов, отличаю- т, 2 р. с я тем, ЧТО ; с целью расши- аа ия leiacca peinaeMjiix задач за счет агределения тупиков1 Х разметок в се- : я х , в него В1зедены М моделей Д реходов, два регистра сдвига, вто- o:-.ii счет шк, регист 5 три элемента Н г;)и ojiBMCHTa задержкиS второй генератор ьтмпульсов, dicpNMpoBaTenb импуль- ау га, две группы элементов Hj третий к чет;зерт1)К элементы ШБ-i,, седьмой 11 яоськой элементы И и дешифратор, . пгу -али вершин и переходов соединены ; -амтяс;и тспслогии сети Петри, вход а;дания начальной разметки устройст- : подключен к информационному входу :ма ;стра,. вьгход которого подключен ; аходам ьтчальной загрузки разметки 1ЧСГ--Х моделей перпшн, вход признака :-п1 иси -- ачальной разметки устройства :1Г);п;лючр}Г к первым входам всех эле- ь саагов If первой группы к входу син- «Гаатизацик первого триггера и входу аа узнака сдвига первого регистра ..а,, выход К--го разряда которого а - ,,,,. :,, где И - количество моделе :а;а;:;кн сати Петой) подключен к втсг- входу элемента И первой ) : ,i которого подключен к аа ;ау паигикака на.чальной разметки 5 и аодели вершины выход Н-го раз- гау:тл те Э|;ого регистра сдвига додклю : ииформадионном :/ входу первого туапа ерд., вьгхо,:т которого подключен . С -7К}: Я входу первого элемента И, --а; когорого подключен к входу а-.: а-; iio гжирозателя импульсов и вхо- ;-ч- аекечтя задеркки,, выход которого г:а; у-атючея к входу нуска первого гене а-::-аара и; ;тульсов, выход которого a j;i04eM к перзык входам второго и ггагьего эленегггов И, выход которого : aixjuoaen к входам второго элемента i ::,ь-:а ..жки., первого элемента НЕ и : тутас-го элймеята за гержки, выход ко а -:а-с подключен X установки i; i) второго pHrre;ja, прямой выход ai - opcro подключен к второму входу ;-;аа,его элсмен -а И, выход формирова чч:. импульсов подключен к первому 1 :а ду т ерБого элемента ИЛИ, выход aaiарого подключен к входу установки

7 . в 1 второго триггера, инверсный выход которого подключен к второму входу второго элемента И, выход котрого подключен к первым входам четвертого и пятого элементов И, выход пятого элемента И подключен к второму входу первого элемента ИЛИ и к входам пуска переходов всех моделей переходов, выход второго элемента задержки подключен к входам синхронизации третьего триггера и второго регистра сдвига и входу установки в О первого счетчика, выход признка переполнения которого подключен к входу второго элемента НЕ, выход которого подключен к второму входу первого элемента И и является выход признака тупиковой разметки устройсва, выход первого элемента НЕ подключен к первому входу шестого элемента И, второй вход которого подключен к выходу второго генератора импульсов, а выход - к суммирующему входу второго счетчика, разряды выхода которого, исключая младший разряд, подключены к входу дешифратора выход Р-го разряда которого (,.. М-1) подключен к Р-му разряду информационного входа второго регистра сдвига, выход младшего разряда второго счетчика подключен к информационному входу третьего триггера, прямой выход которого подключен к первому входу седьмого элемента И, а инверсный выход - к первому входу восьмого элемента И, выход которого подключен к входу признака сдвига вправо второго регистра сдвига, вых признака сдвига влево которого под- ключей к выходу седьмого элемента И выход первого разряда дешифратора подключен к первому входу второго элемента ИЛИ, выход которого подключен к первому разряду информационного входа второго регистра сдвига, выход М-го разряда дешифратора подключен к первому входу третьего элементу ИЛИ, выход которого подключен к М-му разряду информационного входа второго регистра сдвига, Т-й разряд выхода которого (,..., М) подключен к первому входу Т-го элемента И второй группы, выход которого подключен к Т-му входу четвертого элемента ИЛИ и пходу признака разрешения выполнения перехода Т-й модели пере

0

5

208 5 0

8

хода, nepebrii разряд выхода второго регистра сдвига подключен к второму входу третьего элемента И, а М-й разряд - к второму входу второго элемента ИЛИ, выход признака возможности выполнения перехода Р-й модели перехода под ключен к втором входу Т-го элемента И второй группы, выход четвертого элемента ИЛИ подключен к второму входу пятого элемента И и входу третьего элемента НЕ, выход которого подключен к второму входу четвертого элемента И, выход которого подключен к суммирз ющему входу первого счетчика и вторым входам седьмого и восьмого элементов И,

2. Устройство по п, 1, отличающееся тем, что каждая модель вершины содержит три элемента ИЛИ, реверсивный счетчик, причем Р-й вход приема фишки модели вершины подключ ен к Т-му входу первого элемента ИЛИ, выход которого подключен к суммирующему входу реверсивного счетчика, Т-й вход изъятия фишки модели вершины подключен к Т-му входу второго элеме11та ИЛИ, выход которого подключен к вычитаюш;ему входу реверсивного счетчика, вход признака на7 чальной разметки модели вершины подключен к входу признака записи реверсивного счетчика, вход нача тьной загрузки разметки подключен к информационному входу реверсивного счетчика, разряды выхода которого подключены к входам третьего элемента ИЛИ, выход которого является выходом признака наличия фишек модели вершины.

0

5

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

.1 truj i 1 Р 1

., LbU .,

r--bj|:::; .

--T |-rf.

H--31. rl

XL...1..L2 ;.Jr----, (1

;:J.,..„..„„. ;I

,,. -111

I 7i: i5; i

j|:::; .

T |-rf.

H--31. rl

Jr----, (1

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

iliVU

I loppeKTOp Г Л ешетник

чятие. г.Ужгород, ул.Проектная, 4