Устройство для обнаружения тупиковых ситуаций Советский патент 1987 года по МПК G06F11/00 

113Изобретение о ли сится к г ычпплтг- тельной технике и может быть- iicnoni-- зовано в мультипрограм 5ных вычислительных сиетемах (ВС),

Це:аь изобретения - ювьпнение быстродействия устройства.

На фиг 1 и 2 представлена функциональная схема устройства,

Устройство содержит две Г руппь: блоков элементов И 1 и 2„ тригг ер j режима, триггер 4 тупика, грунпы 5 триггеров saHpocEj г руппы 6 триггеро распределения 5 две группы 7 и 8 Tpi-:i геров управления, триггер проверки запросов} триггер 10 проверки распт-е делений, генератор П импу.пьсов; чс:-- тыре группы элементов И 12-15, четыре элемента И 16-19, две группы управляющих элементов PUD/I 20 v. 21, группы 22 запросных элемерзтов ИЛИ, грулпы 23 распределительных элемеп . о ИЛИ, одиннадцать элементов ИЛИ 24- ; Устройство имеет вь ход 35 ГЕризнака тупиковой ситуации, вход ЗЬ , вход 37 кода запроса и BXOJI 38 кода распределения.

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

В исходном состоянии триггер 3 режима находится в нулевом состоянии. Единичный сигнал с инзерсн ого выхода триггера 3 разрешает пуривм кодов запроса и распределен11К,, Через блоки элементов И 1 и 2 в триггеры групл 5 и 6 поступает с 37 и 38 устройства но командам oiiepaifHOH- ной системы ВМ7 По сигналу Пуск (1 Начало анализа) , поступающему н;1 вход 36 устройства у устаназлизаютс: в нулевое состояние триг-ге эы уп|)ав - ления групп 7 и В, триггер -: тупик., а через элементы ИЛИ 29 и З --- - три - геры 9 и 10. По этому же сигпачу триггер 3 режима устанавли13.;1етг;и jj единичное состояние и блокирует крч- ем информации в триггеры групп 5 и 6, Сигналом с единичного выхода гера 3 релсима запускается г ечтератоо 11 импульсов,

По тактовому импульсу с выхода генератора 1 1 импульсов про -,е ряется наличие liyjiesbix стро к и сточб цов триггеров групп 5„ По слелуюи-.е-гу тактовому импульсу с зторог;) ); г генератора 1 1 импульсов проверяете. наличие нулевых строк и столбцо}-; триггеров групп Ь. ECJ;H -тая строка (i-й столбеп) триггеров rpy:ni 5 находится в пу.певом со стоя И ,- и , то по

/игиалу с выхода ге: ератора 1 1 ИМПУЛЬСОВ открыв;1.ётся j й элемент И первой 12 ( 13) грунпы и через :..1ле.меты Ш1И rirynn 23 обнуляются все т ;Л:ггеры групп 6 од,1 юименного столбц (; роки) , Через управ.пяюший элемент ИЛИ групп 20 (21) - триггер управле- групп 7(8 устанавт ивается в ед :Н1Чпое состояние, запрещая дальней- ПИЙ анализ j-и строт .и триггеров за- чрпса ГО столбца триггеров рас- :1ределег-:ия (i-го столбца триггеров запроса и i-й строки триггеров рас- Ч1л: ;;елепия) , так как соответствующие элементы И первой и четвертой групп 12 и IS запираются При этом триггер 5 пгюве.рки запросов с помощью элементов П,, 25, 26. : 7,. 28 устанав- .::и,:ется Б едиу ичпос состояние.

;сл1 в рупгтах Т 1иггеров 5 запро- ;.; ;-|улевь;е стрсжи либо столбцы триг- )B J то по си1Л{ал;/5 сформировавше- - :уся с помощью э. тем(-:нтов 25 и 26 МП ыходе эле1-1ента 2.7, триггер 10 ; ::рез элемент ИЛИ Зч устанавливает- (.;; : - улсБос состоя;}ие. Если триггер .пепия первой г;2уппы 7 - в единичном СОСТОЯНИИ; то па прямом выхо- .ци riepHOi o элемента И 16 формируется ;то:1Ол{ гге;иэаый си.чгал. Через эле- R lH 24 триггер 3 режима уста- .и-(15ается в ьгу-гевое состояние, ос- гп .я работу устройства и опре- лет,чя отсу д ствие тучиковой ситуации

г; i5x..

Eejn-i не вс:е триг; еры управления )вой группы 7 )дятся в единич- iiO M состоянии J, то по следующему так- i ;П:С)му импултзСу С 3 гсрог о выхода i L; ме-ратора 11 импульсов проверяется ; ;м:1:чие нуле1-зъ|х с;трэк и столбцов )- .геров расп;;еде ; иия групп 6..,Ес- .;1и L-тая строк,:- (j-i CTOji6en) триг- 1 :г:ч.;и раснрt;ne;ieinu гоупп ;шходится ; ip;j;eaoM сосгсннии, тс открывается .i--;j ;)лемепт И ре-;ч.,2й i pynnbi (j-й :5.чсмепт И четвертой г руппы) . Через злг; зос1-- Ь(; элемеп : ы 1ЛИ i-ro столбца (1 CTpoKi-O обпуля отся все триггеры запроса 3 .:i;;HOi--c- ieHHoro столбца (ст).-КгО t 1ерез управляю- элемепт IJTOOOH группы (пер- гругнты) о:;:-: у с-т ппалливаются в с :а иич;;ое ее;стсиние, запрещая даль- Н1ЧП.1Л1Й анализ -п с ri)Oi;i-i триггеров -; распределении и i -го столбца триггеров :) запрос;;, (i-i n r-: c;i6u.a триг- : еров 6 раен pe; ej;eH H и -и строки riHMrepoji 5 за.:ф(:киО, так как элементы И второй и третьей групп (первой и четвертой групп) запираются. При этом триггер 10 проверки распределений с помощью элементов 17, 30, 31, 32, 33 устанавливается в единич- ное состояние.

Если были нулевые строки либо столбцы триггеров распределения 6 групп, то по сигналу, сформировавшемуся с помощью элементов 30 и 31 на выходе элемента 32, триггер 9 через элемент 29 устанавливается в нулевое состояние. Если триггеры 9 и 10 находятся одновременно в единичном состоянии и не все триггеры управления первой 7 группы находятся в единичном состоянии, то по единичному сигналу с инверсного выхода первого элемента И 16 открывается четвертый элемент И 19 и.устанавливает тригге 4 тупика в единичное состояние, С выхода 35 устройства выдается сигнал признака тупиковой ситуации. Через элемент ИЛИ 24 триггер 3 режима устанавливается в нулевое состоя ние, прекращая работу устройства.

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

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

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

t,n (n-k)C , , (т+п)% ,

(1) (2)

где С,, - длительность тактового импульса

k - суммарное количество процессов, владеющих ресурсами, запросы на которые отсутствуют ,

Оценим временные потери на обна- ру7кение тупиковой ситуации известным и пред.лат яемым устройствами для случая, когда в ВС все ресурсы заняты и ее состояние описывается, например, следующими матрицами запросов и распределений

01000 10000 о О о 1 о 00000 00010

10000 00100 00010 01000 00001

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

ч - -Г- - 100% 100% 1775% (3)

l он

Из выражения (3) следует, что предлагаемое устройство примерно на 1775% превосходит известное по быстродействию. При этом расщиряются функциональные возможности устройства по выяс}1еь:ию процессов и ресурсов, вовлеченных в тупиковую ситуацию. При обнаружении тупика номера этих процессов и ресурсов определяются по номерам триггеров первой и второй групп управления соответственно, оставшихся в нулевом состоянии. Указание виновников тупиковой ситуации позволяет использовать различные методы выхода из тупика.

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

Устройство для обнаружения тупиковых ситуаций, содержащее две группы блоков элементов И, триггер режима и триггер тупика, прямой выход которого являегея выходом признака тупиковой ситуации устройства, вход пуска устройства соединен с входом установки в нуль триггера тупика и с входом установки в единицу триггера режима, инверсный выход которого соединен с первыми входами элементов И всех блоков обеих групп, разряды входов кода запроса и кода распределения устройства соед инены с вторыми вxoдa :и соответствую щих элементов И всех блоков первой и второй групп ссответст)енно, о т л и ч а- ю щ е е с я тем, что, с целью повышения быстро;;с1 ;ст1Ч1я устройства, оно со;;е 1жит М по N триггеров запроса, N групп по М триггеров рас 1ре;;елсн1.ч (где X - число параллельных npoucccoi, К - число ресурсов в системе), цве гг упиь; триггере управления 5 тригте р проверки 3;uipo- сов, триггер проверки распре/хелеп.ий генератор-импульсов , четыре rpyrribi элементов И, четыре элемента И; две группы управляющих эле-ментов ИЛИ, М групп по N запроспых элементов ИЛИ „ N групп по М распределитель: ;ых элементов РШИ и одиннадцать эле-ментон ИЛИ, причем прямой выход 1-го триггера запроса j-ft i pyrnibi (где , ,M) подключен к i-му входу j-rc элемента И первой группы и к входу i-ro элемента. И второй группы, прямой выход j-ro тригт ера распределения i-й группы подключен к j-му входу i-ro элеме 1та И третьег группы и к i-му входу j-ro элемеи 1а И четвертой группы„ прямые выходы триггеров управления т-;ервок группь; подключены к соотве гствую1:1им входг-к первого элемента И, и к N+i-м нхо-- дам сО Ответствуюиц-тх элементов К первой и четвертой групп, прямые пы- ходы триггеров управления второй группы подключены к i -м входам соответствуюп1тих элементов Р; второй и третьей групп; N+2-рые входы элементов И первой Г эупнь подключены к М+2-М входам элементов И второй группы, к первому выходу генерато-- ра импульсов и к первому входу втс - рого элемента И, М+2-рые входы злс;- ментов И третьей группы по;1кл1очень1 к входам элеменч ов И четпер-- той группы, к второму выходу reHejia- тора импульсов и к первому входу третьего элемента И, выход j-ro элемента И i-ro блока первой груты подключен к входу устаноБК -: в единицу i-ro трип ера ::5а)оса j--й груи-- пы, вход установки и нуль которого подключен к выходу i-j-o заг росного элемента ШШ j-й груггиы, выход i-i o элемента И б.иока второй :группь1 подключен к входу установки в сдиии- цу j-ro триггера распределения группы, вход установки в которого подключен к выходу распределительного элемента ИЛИ .-й группы, первые входы j-й распреде.читель ных элементов ИЛИ всех групп под1слю- чены к врлходу j-T o элемента И вой группы, к первому входу - го уиравляющего элеме гсс . НИИ г:ер1 ой I pyr;- пы и к j-му I pCTber O элеме;г: а ИЛИ, выход KOTCj-.-oro подклют-;еп к первому входу чет1(Сртогс элемента ИЛИ и второму в т-оэого элемен j a I,

0

О6

треч ий вход которог -) подключен к вто- )ому входу четвертого элемента ИЛИ Л к выходу второго э: емента ИЛИ, i-й 15ХОД KOTOporcj пэдключе) к ьыходу i-io элеме1гта И второй группы, к первому входу i-ro управляющего эл емен- )-а И ГИ второй групггз и к вторыг--; вхо-- 1гам распределительн х элементов ИЛИ i.-и группы ; вь.ход i-ro элемента И | ретьей подключен к второму входу i-ro управляющего элемента ИЛИ второй группы, к первым входам i-x яапросных элементов ИЛИ всех групп и к i-му вхопу 1лэсьм(5го элемента ИЛИ, вторые входь: запросных эле1чгентов ИПИ группы подкл сченл)1 к второму входу -го управ; ЯЮ111,ег о элемента первой I pynnbij к входу седьмого эле- мси га VJlll и к выходу j-ro элемента И четвертой груггпы, выходы управляю- элементов ИЛИ гер1юй и второй v pynn подключе:ны к входам установки и единицу соот зетствующих тригн еров унравления сосггветс 1 зен: о первой и Г1ТО))ой групп., зходь установки в нуль коч орЬ Х подключены к входу пуэка ус/гройства и к перкыь: входам шесто- j o и одиннадцатого э, 1емен1-ов ИЛИ, первый и ;зто|-)ой первого элемента ИЛИ подключены соответственно к TpHi гера тупика и к нрнммому выхо;: у nepijoro элеме 1та И, ин)5ерсный выход которого подключен к первому входу четвертого элемента И., второй BXOJ1 которого подключен к HpJiMOMy триггера проверки запросов, входы yci aKOBKH в единицу и и нул1 которого подк;;ючень к выходах соответст)зенпо пятого и шестого элементов ИЛИ, вход пятого ;)лсмента ИЛИ ;:одкл1 нен к выходу вто- р(я у элемента Л. а уг) орой пход пя- Т01 о элемента ИЛИ -- к выходу четвер- то; о ojiCNresrra ЛИИ и ic В1 орому }зходу ;ни:1ПК1Д11ато1 О элемсн га ИЛИ, вь;ход ,гд,мо t o aj :,-: .i j:n a ИЛИ 1;одключ,ен к игсрому входу трс 1 эламе 1та Инк ервому 13X0;.;;/ ;iei3 r-oi o элемснт-а ИЛИ,

)ОГО НОНКЛЮЧе;: к

:- -ъкго элемента И (; -inei-ieHTa I-U1IL немента И тюдключе} н, элемента ИЛИ; второй п;;о1; КО : (н:ого по,г,к:тючеп к ныходу деяягото элемента ИЛИ и к г; :;рому аходу шестого элемента ИЛИ, 1-1ходы дес;г1ого н одиннаднатог С эле- г-; Н: ;он ИЛИ ггэдкнгн.см ы гг-ответстзен- но к };ходам ус-т, н e, :i,HHHnv и в

торои вход к I lic т ьему ВХО.Н

и : ВЫХОДУ но

выход третьек HCHHiOMV

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

третьему входу четвертого элеме}1та И,

выход которого подключен к входу

установки в единицу триггера тупика.

И,

.

13208108

выход nepBoj o ч/к мента ИЛИ подключен к входу уста} орки в пуль триггера режима, выход ксторо -о подключен к входу запуска генератора импулт,- сов .

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

Coci aBtiren : I; . Замггреиич Редактор И, КасгрдаТехред 11. (епко

Заказ 2660/52

Тираж 672Г о;:;|1исное

ВНИИИИ Г осулпрст:км ; г1 о хомктета С;СС;р

по де1:ам ;-13О();к csriiii и и открытий 113035. Москва ; -35 , Рпукская наб.; д. 4/5

11роизводствелио-- 1Олн1 рафичоск(:. е . :р .. и;р :я 1 :1/ , г. Ужг ороДэ ул, Проектная. 4

tf //p 7

I -- ,- , ,.