Устройство для обнаружения тупиковых ситуаций

Устройство для обнаружения тупиковых ситуаций

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано в мультипрограммных вычислительных системах. Изобретение позйоляет повысить быстродействие устройства за счет сокращения числа рабочих тактов и расширить его функциональные возможности путем индикации номеров процессов, приведших к тупику. С этой целью устройство содержит две матрицы триггеров - триггеры запроса и триггеры распределения , управляющие ими группы элементов И и HJIIi. Номера запросов и ресурсов фиксируются на триггерах управления. Одновременная обработка запросов и их распределений на триггерах , запроса и распределения сокращает число рабочих тактов устройства , а фиксация номера процесса на. первой группе триггеров управления позволяеФ обнаруживать процесс, приведший к тупику. 2 ил. i сл CXD о 00

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

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

РЕСПУБЛИК (511 4 G 06 F 11/00

h !

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) .4037965/24-24 (22) 19.03.86 (46) 30,06.87, Бюл. № 24 (72) В.В.Акмурзин, В.В,Герасименко, В,А.Фильштинский и И.А.Юртов (53) 681.325(088,8) (56) International Journal of System Science, 1979, ч. 10, № 5, р. 482, fig. 3.

Авторское свидетельство СССР № 1015385, кл, G 06 F 11/00, 1981, (54) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ ТУПИКОВЫХ СИТУАЦИЙ (57) Изобретение относится к вычислительной технике и может быть использовано в мультипрограммных вычислительных системах. Изобретение позволяет повысить быстродействие устSU» 1320810 А1, ройства за счет сокращения числа рабочих тактов и расширить его функциональные возможности путем индикации номеров процессов, приведших к тупику, С этой целью устройство содержит две матрицы триггеров — триггеры запроса. и триггеры распределения, управляющие ими группы элементов И и ИЛИ. Номера запросов и ресурсов фиксируются на триггерах управления. Одновременная обработка запросов и их распределений на триггерах, запроса и распределения сокращает число рабочих тактов устройства, а фиксация номера процесса на, первой-группе триггеров управления позволяет обнаруживать процесс, приведший к тупику. 2 ил, 13 0810

4 -n2 (n-k) 1

L 2 (III+n) (2) 50 длительность тактового имгде пульса; суммарное каличество процессов, вла,leþùèõ ресурсами, запросы на которые отсут55

c7 Вуют, временные потери на обнаупикавай ситуации известОценим ружение т менты И второй и третьей групп (пер— вой и четвертой групп) запираются.

При этом триггер 10 проверки распределений с помощью элементов !7, 30, 31, 32, 33 устанавливается в единичное состояние.

Если были нулевые строки либо столбцы триггеров распределения 6 групп, то па сигналу, сформировавшемуся с помощью элементов 30 и 31 íà 1О выходе элемента 32, триггер 9 через элемент 29 устанавливается в нулевое состояние. Если триггеры 9 и 10 находятся одновременно в единичном состоянии и не все триггеры управления 15 первой 7 группы находятся в единичном состоянии, та па единичному сигналу с инверсного выхода первого элемента И 16 открывается четвертый элемент И 19 и устанавливает триггер 20

4 тупика в единичное состояние, С выхода 35 устройства выдается сигнал признака тупиковой ситуации, Через элемент И !И 24 триггер 3 режима устанавливается в нулевое состоя- 25 ние, прекращая работу устройства.

Номера процессов и ресурсов, вовлеченных в тупик, — это номера триггеров управления первой 7 и второй

8 групп сйответственно, оставшихся в нулевом состоянии.

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

ВС с п ресурсами и III одновременна функционирующими процессами известным и предлагаемым устройствами оп— ределяются выражениями (1) и (2) соответственно ным и предла аемь.м устройствами для случая, когда в ВС все ресурсы заняты и ее состояние описывается, например, следующими матрицами запросов и распределений

0 1 0 0 0!

1 0 0 0 0

0 О О О!

i 0000, 00010

00010

Относительное повышение быстродействия с учетом формул (1) и (2) может быть оценено по формуле т1 -7. 75-4

К = - - —" 1007.= — -- 1002=1775X (3)

<и

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

Устройство для обнаружения тупиковь|х ситуаций, содержащее две группы блоков элементов И, триггер режима и триг -ер тупика, прямой выход которого являе гся выходом признака

Tóïêêoâîé ситуации устройства, вход пуска устройства соединен с входом установки в ну: ь триггера тупика и с входом установки в единицу триггера режима, инвереный выход которого соединен с первыми входами элементов

И всех блоков обеих групп, разряды входов када запроса и кода распределения устройства соc-;.;èíåíû с вторыми входами соответствующих элементов Ii все блоков г,ергай и второй групп сса,I!c7cII еннс, о т л и ч аю ш е е с я тем, чта, с целью павыIJeIiия быетрадейст.:II!7 устройства, ана c0Ä,ержит М гру: « Iin N триггеров запроса, груIII Iii гр:1ггеров раси!7еделен,» (где 3 — числа параллельных прспеессн, М вЂ” число ресурИз выражения (3) следует, что предлагаемое устройство примерно на

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

1 7" Д

) г) сов в систeме), цг)е )руппь; г->и гс,.:св управления, триггер про))ерки .)спро— соВ, триггер проверки p<1(t

в, )етыре вру(.пь. элементов И, четыре элек(е((та И, цве групг(ы управляюцих эл !QHтов И11И);"1 групп по 1. ) запрос)гьх ")J)eìåíтов ИЛИ „

N групп по >1 распределител():-.Ых элс— ментов ИЛИ и оди)п адцать зле«ентов

ИЛИ, причем прямой выход .: — го тр?и— гера запроса j-и гру)п)ы (! де ) -1, j=1 N) подключен к i-му входу;-гс элемента И первой гру)гпы и к (--му входу i-го элемеп ..1(И второй группь), прямой выход (- го три(гера ра(— пределения i-й груг:пы попключен к

j му входу 1. го злеlf(! )а И трс (!)Ql группы и к i — му входу j — t о эпеменз а

И четвеРтой гРУП)(ыу ПРЯмыс ВЫХОДЫ триггеров управ)?е)3?- я )ервсй группы подключены к соо; )!eт с Tвую> !им )!Ходам первого элемента И, и к 0+1-м «ходам ссответствуюцих ).(емевтов И п(рвой и четвертой .-, рупп, пр (>ые )3ы— хОДы твиг Г еР О В У!7Р Р) 1)л 2 1lи Я ?)то)зОЙ группы подключены к И+1 bf I!Xoi!<?м сООтВетствуюЩих э)lем(3:)To)> 1 : Втог>01 и третьей групп,. 4+2-рые входы .)J);— ментов И первой гругп,1 п(одкгво"((-ны к 11+2-м Bxîäàì элемен TQB И второй группы, к первому выходу гснератсра имг!ульсов и к первому 1:ходу вт(—

Рого элемен l cl И, 11+2 — Рые Бхоцы .)Jl(.— ментов И третьей ..-руппы подклю (сны к 1>(+2-м входам элемен гов И»F г )Ортой группы, к второму выходу г(с) а " тора импульсов и к первому Bxo)(y третьего элемента И, ()ыход j-f о э):-;-мента И i-го блока ((Q()Bo t By;f»bl подключен к входу уст:11! QBKI 13: дики-цу i — го триггера >)апрос;< i- -.i груп-У С Т и 0 )3 К:.! подклк)»ен к I)bfxoду 1.- о bàl(;ðoñëoiэлемента ИЛИ j-й (руп!(ы, Bfbxo;l —, o элемента И j — го блока Втор сй гoól-.i lb!

ПОДКЛК)ЧeH К ВХОДУ ) CТ T IIIÎÁÊ И D г ЦИ!:=iцу 7 -го триггера распр(".,7e?fpпия группы, вход уст IIH>BI(! c3 )л JIB от(—

;Зt ь((>!ty ) — го ->а(преДелите)льпого 0»<?b.(ct. l а !1 1И ). и i>y! f— пы) пеpBbip Вхо ь! 1 ")и (>сlспреде l?(те! »" ных эгементов И.1 .1 всpx гр )IH г(>ц;()иочены к вь!ходу ) — I О )Jlel tetfT(f " i(iрВой ГPyППЫ К 1 () г)!)ОМУ 13ХО ((У "" О равляюЩРГО .)Лe )21!т? j) I(И 1:(г:13ой 1 () . пы и к 1 !)У вхо, ) тР(I 1)(!1 О 31! !Q)f!Га

ИЛИ, выход кот;f;o <> п,:)к;пь»Q!i к

Вому РхОДу»(I !3(.> 1 >. (, >((е,"1(l I а ИЛ1( и второму в:;о,) у 3 гo;>o: о О.-ь(r:c,: га,"< i ИИ 1)ХО;1 1< > 7 Г > (! Г))))? .".!)>» (!11 К БТО (> ОМ )г BXO??y»С Т i) < !) ТО -C) ЭЛ СМЕН Тя ?11И

,! K 13ЫХОду BТО;)С) O 3(fel IЕНTа ff)fft

1 и 13ход xo Topo 1 o 1 (î! (ê ((in»pH с:-:ых оду (> элемента И 1!торой гру!Гпы) к пер—

)<ому входу i--го управляющего э.;Смен-! а (Р И второй гр)уп.,. H к B)горь! вхо)!7м >3(!(прсд<3 iH 1 2)lьн !х э Ier!pHTÎB И 1И ..-и группы, гьхо:1 i — го элемента И трстьей гpyii!(ь: п<зцк.-(ючен к Б горому

Бхoду 1 го управ »B!<)U(,(! Bo элемен а ИЛИ

l! I 0 () Ой ГpyППЬ! ) к I! 2pBbt .(B X0„1HI(1 Х

Запрос)гых эзгс>ментов 11:1171 >)с-"х груггц

i3 к i ".«ty 3xo l!, 13 0 сьмо Гo OJ)ем 2 :(т а K(H у

l< f O()bI(3 BX0J:,f):c1HpO(ных э.зем(-н- (>B ИЛИ ("ii ГP y tl?lbl ПО(КЛ!С -I Сн,l К В Г ÎPÎ!- ВХО

1 1 0 ъпPББ) Яю!Кеl О э !сr!QH) B l((= РБОй

l !> c f(ПЬ(К ) r!У BXО 7 c ()P b «!ОГО OJ! Е .к ("! а И(1И и к Bt)» о;)у I- . о элемента

:! Е Т)32 3 Г ОИ T> i!-f, 7)(.f. 0 7 > У((!Зс ЛЯ!<) . )из: OJtpMQII TQI: (!.1:." (:2(з)30:. и вторсй ! > У IIП Г!ОДКЛЮ<, ЕНЫ К Рх ода "! у С 1 c) . ОБ К !!

l! (.Ц> IПИЦУ CÎО) )327 () . БУЮЩИХ ТОИ 1 С )3013

;:;;>ав:)QHø>3 состветствен:о псрвок и

:-:г"рой групп):эходь yстанэвки 1! нуль !. О )ЭРЬ Х I!O>7K)if)>»ЕI)Ы К ВХОД" .(у "Ка ч (.ТРОЙ СТ I! <- И ? H(! PI- b!l" Входам Ilt(! СTO

)" (> и с;(и)(!)27. а)(зго э. (Бменэ î ) И IH, )(Е. ЭЫй и ВтОРСй I!XC )1!el . ЕРВОГС> Э?IQMQH

)7! ffffi! по,,клю--.-.)3ы с О. 7ветстБе11но к !р я г;О: (у 1! I)txc< lу y1 )H) 1 )1)а тупик . >I x

:i";-Iмо"-су i3f)ixc;fy ilc pi QI 0 31(p (2нта И, . (П)ер с ный вь>хо l 1(о тo pol 1!Одключен к )li ði)oìy вхо, у -(еп) p Tогo э))е:-сента (1. )3To poli 13xo! (ко ОрОГО подключен к

:! ))i (О tу выхс;() т 1>и l Гeр а llрoв2 г)ки за

) Гр(.СО? „13ХО>,ы > .. cl ОБКИ В ЕДИ.«(иу «i нуль которо 0 пс,(кл:очень: к ВыхоÑ C> O T 13 Q Г С Т) . 2-i HO Il Я ТО Г G И fn(Q C T О ГС

>!1c !clf îâ И!(!1, )I(?pl,ый Вход пя гого

И11 0 (»; i f >)) ) .- к Бык о)) "у в гQ—

O (2)(())7 3 .(() c >H ) Оц <я

i;):, о э:(емс)нга (.! 1 -- к -:-:ыходу ч - вев(! ) (..(рс; (;! И(И !< >: 1)! Ор«-)му --.Jlем=: — l . 1 . и К

13 o! ty Bx(J;; т .!c: f

::., СРОК -":--.О,, :(> (;>О) С I! !)КЛ)Б- ";. :К

)7>С Гb(! fy (3! »; -. -,-.; -„" г.O) OJ..() :QH. а

Быхо>), ;0:.: Q) (> ;, с:,.! а !(1., .-)ыход Tp(:-в(> — ...2)я и а, 1 —. -,;f .l!î÷eí

f; (:> 13 С . « ".;::, ;; () ". >. (О 0 Э ?1 С ., -! Е "1 т а

1. l. -, -, 137 0!)(>1.: !3 Хо г. )((. (! (. О >,С:(ПСЧ< )3 ,ь>хо)(у лкс!!, 1. 01 0 >:.2:f(: т;- 1 "11 и к ...,) -.tei!el Ta ИЛИ)

>!l: (>,!!,! l д)2 с>! f Оt o !! . (!. H.. l.! ) (), ) (()Ц-) нуль триггера проверки распределений, првмоЙ третьему входу четвертого элемента И, 1 выход которого подключен к входу усТановки в единипу триггера тупика, 5 вь.хоп перво! 0 - 1(. епта ИЗП подключен к входу устà»îвк» в нуль триггера рейма, выход которо о подключен к вхог-.у запуска еперятора пмпуль— сов 11 ! (.....1

IJ а 1

2 ( аа

1 а 1 (E3 g

1 -1 — " - -а а аа

0 а а. 1"а,, r

С00; аВИатСЛ:, ;(:.а(:(11Иа(Т а..а-„а; Е il 11 1 „ аа т (. I I к 0 1;Ороси;Ор Т. Ходьб

Редактор И.Еас;-.рда

Заказ 2660/52 )

TH; > а. к . I C > .. i I I " Н 0 е

Б1111И1111 00 ((ар(:; а:. (1:... 0;0:1итета (.(., Р

I (0 а(О(аМ (3 0 (а Ра 0 I I I I! (а(И ОТК .:а(а(тИЙ

1 1 30 33, . 1СС(<11». а .—.;, - 11 аа(1(СЕаи Баб.,;(, а ) Производствеш(о-:10 «! раариа(еск .«::I:. .и(;,:, ти,, I, Уж(::ро;(, у-i. 11роектная. 4! а

; l а а

11; (=