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

(50 4 С Об Е 11/00 ОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) 1 псегпаехопа 1 Зоцгпа 1 оЕ Буаеш 8 сепсе, 1979, ч. 10, М 5, р, 482, 118. 3.Авторское свидетельство СССР Р 1015385, кл, С 06 Е 11/00, 1981, (54) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ ТУПИКОВЫХ СИТУАЦИЙ(57) Изобретение относится к вычислительной технике и может быть использовано в мультипрограммных вычислительных системах. Изобретение позволяет повысить быстродействие уст 801320810 А 1, ройства за счет сокращения числа рабочих тактов и расширить его функциональные возможности путем индикации номеров процессов, приведших ктупику, С этой целью устройство содержит две матрицы триггеров - триггеры запроса. и триггеры распределения; управляющие ими группы элементов И и ИЛИ. Номера запросов и ресурсов фиксируются на триггерахуправления. Одновременная обработказапросов и их распределений на триггерах, запроса и распределения сокращает число рабочих тактов устройства, а фиксация номера процесса на,первой-группе триггеров управленияпозволяет обнаруживать процесс, приведший к тупику. 2 ил, 13:.08.ИзобрСТСИЕ 0 1(доит(5 К в "1 1;П.тельной технике и мдкет бытг испдл; -зовано в мультигрдграм 1 ых вь Ис:о- тельных си темах (БС).Цель изобретения - .двышсние бьстродействия устройств; .На фиг. 1 и 2 представлена. функциональная схема устройства.Устройство содержит две группь блоков элементов И 1 и 2. триггер режима триггер .5 туг.ика. группы 5 триггеров запроса, группы 6 тригерог; распределения, две группь " и 8 тр: 1- герон управления, триггер 9 проверки запросов, триггер О проверки ряспт с-делений, генератор 1 импуг:асов чстыре группы элемен гон И 1 2- 1 5,. -Отг-. ре элемента И 16- 19, де г 1:,уппы управляющих элементов ИГ 1 20 и 21, группы 22 запросных элементов ИЛИ, группы 23 распределительных элеме.01: ИЛИ, одиннадцать элсментов ИЛИ 1 -.,с . Устройство Рмееч вьход 35 признака тупиковой СРТуяцлР вход 36 пус;са., вход 37 кода эяпро, а и гхс 1( 38 кд,1;( распределения.Устройство работает следуозР:. Образом.В и(ходРдм со ст 05 нии трь гер 3 режима находится в нулевом (ос д 1- нии. ЕДиничньЙ с:1 Г нал . Ил 1 р с д гд выхода триггера 3 разрешает прРСм кодов запроса и распределен.я, (1 дс.з блоки элементов И 1 и 2 в "риггеры групп 5 и 6 поступает с вхо,св 37 38 устройства по комадам О(ерацид- ной системы ВМ 7. Пд сигналу "Пуск (сачало анализа ) пдс гула(цехгу н. вход 36 устройства ус. гяняв.ив,тктс с в нулевое состояние тряс геры,-прав ления групп 7 и 8., триггертупк. а через элементы И:П 29 и 3 - тр( геры 9 и 10. По этому же си:;1(а:у триггер 3 режима устанявлив;с . в единичное состоя ие и блоклрует .р в ем информации в триггеры рупп 5 6, Сигналом с. единичного выход;. тр:,. гера 3 режима зспускает я гнератд о 11 импульсов,ПО тактовому импульсу с 1.етвОгд .э.О( выхода генератора 11 мпул сон рд - ряется наличи пу.евых строк и стдб. цов триггеров групп 5, По, се,уо 1:с у тактовому импульсу с 1 срдгд в.Хд генератора 1 Имул сов прд;(ретсналичие нулевых : трдк и стд.:бп 01 триггеров груп 6, Есл; 1-Тая с.рока (1. - Й сто:1 бец) гри 1 Г рс я гру:и : и; - ходится в У:е вдх сос: дяп:. л тд пд. ра дра 1и".И 5 гИ .-: Нт:СЬХ С:ГО еры управления дятся в единичследующему так.Срд.о выхода.-ТЯЯ СТРОКд .(.п т (е иУ.;01 ДМ ОС ГС Я Пни11, Сз; ", ,0 ЭУ 111 ПЯХОДИТСЯ с открывается группы ,3 - ирупгЫ), Черезэ110 сКь е э л с .,С; О(К с Ди 1- зсп:рдся го. и 1ВД 1 Уи ) тся всс триггеК ПОС ЕННО Г О С.(1 д зПГОЯВ 1 ЯЮ 1 свт РАППЫ (ПЕР:-:вливаются в апреяя дяль 101:. ГДИГ 1 СРДВ в : 0 толбца триг 11 1 РИГР; - й строки тяк как эле 1: Г .15 И ЯН (11 И З.пялу с выходя гс. ерятдря 11 иму:г,сов дткрьгется 3-й элемент Ипсрпой 2 (второй 1) группь и черезоссвиты И(1 И групп . 3 дбну:яются всет иггеры групг 6 дд оиме ного столбцаг роки) , .Через упрсвпяюпвлй элемент1 цИрупп 20 ,2) - триггер уг:равлегрупп 7 (8устанавливается в еди; п 11 0 Р состояив зяпре 1 гяя дальнейпии анпиз 1-й строки триггеров заи"дгя и 1 гд стдлбцс тригеЗдв рясноеленин (1 го стдгбца триггеров1 Я.гдся и 1.-й строки триггсров раси ь;ел 1 Ря), тяк кяк соответствующиеол ".енты И гервой и четвертой группи 15, запираются. При этом триггер1:(ос 01(л запОсов с: гдмощьюл;он ,7 25 26. 27, 28 усганав-,,сли в 1 рупиях триггеров 5 запроу:1 вые строки либо столбцы триг.Ов, гд пд и.нял сфор.ирдвявшес помдщо э: ментов 25 и 26шкоде эем(:.нтя 7, триггер 10сз:51 емеп ИИ 3 л устянявхивяетсз в и;:;Овос состоя:ие, Если триггерыр;Нпс пня 1 ервдЙ гтуппы 7 - Б еди -"и чОм ".0 стд 51 ниит(1 1 я 1 рямом выхдпр 010 элемента И 16 формирует.51 пдсОКРтеспзяыи си 1 ял, Через элепя,ивается в нулевое состояние ос 1;Явливая раб гу у .тройства и опре 5 Отсуг ст вие у 1 икдвой сРтуяции(та+и) ,50 длительность тактового имгде пульса;суммарное количество процессов, владеющих ресурсами, запросы на которые отсут 55 временные потери на обнаупиковой ситуации известОценим ружение тменты И второй и третьей групп (первой и четвертой групп) запираются,При этом триггер 10 проверки распределений с помощью элементов 7, 30,31, 32, 33 устанавливается в единичное состояние,Если были нулевые строки либостолбцы триггеров распределения 6групп, то по сигналу, сформировавшемуся с помощью элементов 30 и 31 на 1 Овыходе элемента 32, триггер 9 черезэлемент 29 устанавливается в нулевоесостояние. Если триггеры 9 и 10 находятся одновременно в единичном состоянии и не все триггеры управления 15первой 7 группы находятся в единичном состоянии, то по единичному сигналу с инверсного выхода первогоэлемента И 16 открывается четвертыйэлемент И 19 и устанавливает триггер 204 тупика в единичное состояние, Свыхода 35 устройства выдается сигнал признака тупиковой стуации,Через элемент И 11 И 24 триггер 3 режима устанавливается в нулевое состояние, прекращая работу устройства.Номера процессов и ресурсов, вовлеченных в тупик, - это номера триггеров управления первой 7 и второц8 групп сОответственно, оставшихсяв нулевом состоянии.Технико-экономическая эффективность предлагаемого устройства состоит в повышении быстродействия засчет сокращения числа рабочих тактовпри контроле распределения ресурсов,а также расширения функциональныхвозможностей по выяснению виновников" тупиковой ситуации,Максимальные временные затратына обнаружение тупиковой ситуации вВС с п ресурсами и тп одновременнофункционирующими процессами известным и предлагаемым устройствами оп -ределяются выражениями (1) и (2) 45соответственноцым и предла аемь:м устройствами дляслучая, когда в ВС все ресурсы заняты и ее состояние описывается, например, следующими матрицами запросов и распределений 01000 1 0 0 0 0 00100 00010 О 000 0000 10000, 00010 00000 00010 Относительное повышение быстродействия с учетом формул (1) и (2) может быть оценено по формуле 75-4- 1007.= в1002=17757. (3) 2 Ф о р м у л г и з о б р е т е н и я Устройство для обнаружения тупиковьх ситуаций, содержащее две группы блоков элементов И, триггер режима и триггер тупика, прямой выход которого являе гся выходом признака тупиковой ситуации устройства, вход пуска устройства соединен с входом установки в ну:ть триггера тупика и с входом установки в единицу триггера режима, ццверецый выход которого соединен с первымц входами элементов И всех блоков обеих групп, разряды входов кода запроса и кода распределения устройства соединены с вторымц входгмц соответствующих элементов И всех б в ,екоц гервой и второй групп соатцетст еццо, о т л и ч аю ш е е с я тем, что, с целью повышения быстродействия устройства, оцо содержит М 1 ру:цо М триггеров запроса,групп цо М триггеров расцределецц (где- число параллельных процессов, М - число ресурИз выражения (3) следует, что предлагаемое устройство примерно на 17757. превосходит известное по быстродействию. Прц этом расширяются функциональные возможности устройства по выясцецию процессов и ресурсов, вовлеченных в тупиковую ситуацию, При обнаружении тупика номера этих процессов и ресурсов определяются по номерам триггеров первой и второй групп управления соответственно, оставшихся в нулевом состоянии. Указание виновников тупиковой ситуации позволяет использовать различные методы выхода из тупика.сов в системе), цверуиць; г-)1: Гс;.:Св УПРаВЛЕНИЯ, ТРИГГЕР ПРЛтЕРКИ:3 ПРЛ - сов, триггер проверки рас.Г.едсз:сий) ГЕНЕРатОР ИМПУЛтСС)В, тЕтЫРЕ ГРУ.ПЬ элементов И, четыре э)еьезта И цве ГруПГЫ уцраВ 1)ЯЮВтИХ ЭЛЕМЕтОВ ИЛИ) с групп по т запросЬ)х эемецто)3 ИЛИ) групп по ) рас)преде)ьтег)с 1)с элс - ментов ИГИ и одинадцать элементов ИЛИ, причем прямой Выход .-Го три - ГЕра ЗаПрОСа 1- Гру)ПЫ СдЕ Ес 1=1,10 подключен к е-у входу ;-гс элемента И первой гру)тпы и к .-ыу входу е-го элемена И второй группы, прямой выход )- го три) гера ра( - пределения е-й груг:пы поключе к т-му входу З.-га элеыец,а И трс 1;с группы и к е - му входу -о эсмен)а И четвертой групты) ц)5)с,с 13 т)хлдь ТРИГГЕРОВ УПРаВЗЗЕНтЯ )ЕРРСИ ГРУЦПЫ ПОДКЛЮЧЕНЫ К СОЛТЗСГСТВУЮ)тМ БХОД;.М первого элемента И, и к Бз -м БходаМ ССОТВЕтСтвуЮ)ИХ ),СМЕтОВ 1 П- рв ой и четвертой .-, р упи, пр Рые вы - хОДы тригГ 21 ОВ УПРР 11 лоция тОРОЙ ГруППЫ ПОДКЛЮЧЕНЫ К с 51 - М ВХОД(1 М С 0 О Т В Е Т С Т В УЮЩИ Х Э)16 )с Е.: с Т Л В . )З ." О т) Ои третьей групп,. 1+2-рые г:ходы )лс - ментов И первой:; руш,1 г:адктночецы к 1+2-м входсм элементов И )зтлрс)й Группы к иерВОмч еьходу 1 с)цератс)а импульсоВ и к .сГ)вам ч ходу Бтс рого элемента И, 1+2-рые ехогть О.т)(- ментов И третьей группы подключены к 1)1+2-м входам элемагов И чег 1)ертай группы, к второму выходу(са- тора импульсов и к первому вхо ту третьего элемента И, выход 1- о эзе-. МЕнта И е-го блока первой 1 оу ггыПОДКЛЮЧЕН К ВХОДУ УСтСНОВК "с ДИИ цу е - го триг)ера Нг:рлса 1-:1 груп-. ПЫ) ВХОД УСТс)НО)ЭКИ Г У 1: Кат ЛРЛ 1 Л подклк)чен к выходу 1.-10 за,рлснагс элемента ИИ 1-Й рупы, вьхлд . -л элемента И 1-го б;ока вторсй гау)тиь: ПОДКЛЮЧЕН К РХОДЧ УСТ)1 ОВКИ Б СЦ)11:)" ЦУ т-ГО тРИГГЕРБ РаСЦРС".ДЕГЕИЯ Е-й группы, вход устацлвк, в узь "отс 1- рого годключек )3)слцу -га - ,.)ас)пределительцого элемт и 11:1 И .-й груи - ПЫ) ПЕРВЫЕ ВХОтЬ "И Рс 1(:.ПРЕДЕ;ттв)сс" ных эгементое И,; всех групп г:;.)ц;Бочены к вяходу- г о э:2 ец.га .".;ерВай ГРУППЫ К ИСт) БОКУ 1 ХЛ ЦУО равеяющего элеме:т,1:ст;)лй )р тг.ПЫ И КЯУ ЗХЛ, с ТР. Ь(.11 0 ЗЗ 2 1 сЦТ(1ИЛИ, вь:ход котс;л л и.),:)кгот:ец кВОМУ РХОДЧ тЕГ(5;)т О: (, .)СЕЕ(снса с)Ли второму вхл у гл;)О: л зле:си га 1 рт:ии вхл, кл) )г ) Оцл)-. Сц к втароку БХЛду СТт)ТО ГС ЭЛСМЕНТВ И 1 Ис к 1 ыхОДУ втОРс л э;211 ен 1 а 1111)-и группы, гьхад е - Го элемента Итрстьей груп.ь. лцкгьючен к вгоромувходу е-го угре)ге)51 осего элемец:а иЛИБт с )ОЙ Г;)уппь ) с 12 лвы " Вха;.1 ас еЗаросных з)1 с."с 1 гав 1) И:сх ГрупГИ К Е - Му ВХОч 1)ОСЬМОГО ЭЕ:ЕМЕ)1 та ИЛИт)с" Орые входя зс)прасцгх злесс с. В ИЛИ/ "й ГРЧ ГПЬ 1 ПотКЛС 1 СНЬ К ВТОРОМУ ВХО -с Ч1 О ЪПР ВЕ)З 5 Ют 21 0 Э)ЕЬента ИЕРВОЙ1; ЧГИ 1 Ы ) К -) ХОЛУ СЕЬМОГС ЭЛЕмс ига 1 тИ и к выходу )- го элементат ЕТБЕГОЙ 1 ТтстП-т 3,Г 0 1 Ь сЧ)РсВЕЯС) -.НХ ЭЛЕМЕта). .1:." т СР Ой И ВтОРСРРУЦП ПОДКЛЮЧ ЕНЫ К Рхоца) УСГст:. 0 ЗК)),ЛОРЬХ 1 ЛДКЗс)Ч(ЗЦЫ К БХОДУ:1 УСКаЧ С.ТЛЛЙ СТ 13 С- и с И(ЗР 1 С Ь БХОДам ЦЕ СТО) л и с;цад;.;(тога э.ементов ИЛИ,е;)эый и Бторсй вхс)н) ервого элемен 15 О;КЛтте)ЗЬ С Л; тнтСтБЕ НО К1;)ит21:)а тчпика : .;:кому 13 Хсцу пср) ого элеента И) НИЕРСЫй ВЬХа СОТОРаГО От КЗ)ЮЧЕН К ЦЕРБОМУ ВХО.У тЕПСР)ОГО ЭЗ;Е;(ЕНта , второй вхо( ка 1 ср 010 подключен к ;Р).с 0)У ВЫХСДУ ТРИ 1 ГЕРа ПРОВЕРКИ За . Р(,СОЕ,ВХО),Ы У, а. ОВКИ В Е)ЕИ.-.ИПУНУЛЬ КОТОРО О ПС),т(КЛОЧепь: К ВЫХОС. С Л Т Б с) Т С Т ) , .И 10 П Я Т 0 Г а И ЬЗЕ С т О Га с)211011 И 1) Пс:р),ь:й БХОД цятОГО тт";сС"с) И) 1 ) пт т т лсс к ВЬХО 1" т 1 ТОСсс т 3 с 1,т- -. Л-;Л; О -, )Е;Сс."Га,".", -.; - . БЫХСДУ Ч(1 БЕР(1Е) С)сГ 1 И с . Б ) Ор Оку З)СОД у л;и.Гнсдц;)гс э эгс)т( т а 11:, Бь"ход с."ь,;01 о эл- С гс ИЛ :Одключс. к ",-.риму )ЗХСД 5 Т т(1) БЕГС СЛ 2 МЕНТ". И (тс 1 ОМУ Б)сч це 35 0)О элсмец ."- тИ ,. РОЙ ВХС)Д С) Г; )Л) С ПО; КСЛЮссс К )С ГЬСсУ Х(т; с ", .;Ь(т; ЭгС:; -Ц. с 1 И 1: БЫХО)у )Л ГЬ: :)С) Л.".С:Гс1., )СО Г. (11 с ( -, 2; т, а 1 - ,; (- С)ЧЕ 1нуль триггера проверки распределеий,прямоЙ выход оро подключе ктретьему входу четвертого элемента И,1выход которого подключен к входуусТановки в единицу триггеоа тупика, 5 вьхоп перво о:1 с. ета ИЗЮ подклк 1 чек входу устаовлп вупь триггерарейма, выход к торо о подключен квходу запускаеерятора мнут -сов