Устройство контроля

801015385 Д СОКИ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСГЬЧэЛИН УДАРСТОЕННЬЙ КОМИТЕТ СССР ЛАМ ИЗОБРЕТЕНИЙ И ОТйфЫТИ ЙО ДЕ ЙОПИСАНИЕ ИЗОБРЕТЕНИЯ :-К АТЮСНОЫ сВЩТВ 1 йй(21) 328777 У 18-24 :. нальных возможностей, оно содержит (22)- 16,03.81. . два управляющих мультиплексора, два ,(46) 30.64.83. Бюл, Н 16Распределителя импульсов, два тригге- .(72) С.В. Ткаченко, В.С, Харченко, Ра управления, триггер совпадения, Г.Н, Тимонькин иА.П; Пузырев , триггер анализа, элемент ИЛИ"НЕ и (53) 681,325(088,8) . восемь элементов И, при этом входы (56) 1. Авторское свидетельство СССР данных первогО и второго управляющих . М 572787, кл. 6 06 Г. 9/ОО, 1977. мультиплексоров подключены к выходам2."Эпйегпай 1 опа 1;доцгпа о зузщсоответствующих регистров первого и зсепсе", 1979, ч. 0, У 5, р.482 второго блоков, управляющие входы г 1 д. 3 (прототип). : ,этих мультиплексоров соединены. с ин.версным. выходом триггера режима, первые выходы вервого. и второго управ- (54)(57) 1. УСТРОЙСТВО КОНТРОЛЯ, со- ляющих мультиплексоров подключены держащее два блока Регистров, три . соответственно к входам .установки ре" группы блоков элементов И, триггер гистров второго блока и вторым входам режима, элемент ИЛИ, два мультиплек" -установки регистров первого блока, сора и триггер тупика, выход которого . вход установки первого триггера уп" соединен с выходом устройства, выхо- равления соединен с выходом элемента ды блоков элементов И пераой и вто- . ИЛИ,. выход этого триггера подключен рой группподключены соответственнО к первому входу первого элемента И, к первым, входам: установкй и входам вьвод которого соединен с входом пер-." .й данйых соответствующих регистров пер- вого. Распределителя импульсов вхо- Уай вого .блока,. а выходы блоков элемен- . дами сброса первого триггера управтов И третьей группы соединены с вхо- лейия и триггера совпадения, первые дами данных соответствующих .регистров выходы первого распределителя имвторого блока, первые входы блоков . .пульсов подключены к первым входам Ю элементов Й второй и третьей групп . соответствующих блоков элементов И М подключены соответственно к первому и первой группы, соответствующим вхо второму входам данных устройства, а дам.элемента ИЛИ-НЕ и соответствую- ф 3 вторые входы этих блоков элементов И . щим первым входам первого мультиплек" соединены с инверсным выходом тригге- сора, вторые входы которого соединера режима, вход установки которого . ны с выходами соответствующих регистподключен к управляющему входу уст- ров первого блока, выход первого мульройства, первому входу элемента ИЛИ типлексора подключен к первому входу )Эь и входу сброса триггера. тупика, пер.-. схемы сравнения и первым входам вто" вые входы первого.и второго мульти- рого элемента И, выход которого соеплексоров соединены с выходами соот- динен с вторым входом элемента ИЛИ ,ветствующих регистров первого и вто- и.первым входом третьего элемента И, рого блоков, о т л и ч а ю щ е е с я выход элемента ИЛИ-НЕ подключен к ;тем, что, с целью расширения функцио", вторым входам второго и третьего эле1015385 ментов И, выход которого соединен с,первым входом четвертого элемента И,вторые входы первого и четвертогоэлементов И подключены к тактовомувходу устройства, вход второго распределителя импульсов соединен с вы"ходом четвертого элемента И, первыевыходы этого распределителя подключены к соответствующим первым входамвторого мультиплексора, вторые входыкоторого соединены с выходами соответствующих регистров второго блока,а выход этого мультиплексора подключен к второму входу схемы сравнения,выход которой соединен с входом уста-новки триггера совпадения, первый,второй и третий. входы пятого элемента И подключены к выходам соответственно первого и второго управляющихмультиплексоров и триггера анализа,а выход этого элемента И соединен свходом установки триггера тупика, инверсный выход триггера совпадения подключен к первому входу шестого элемента И, выход которого соединен свходом установки второго триггера уп"рааления и вторыми входами блоков элементов И первой группы, прямой и ин" Изобретение относится к вычислительной технике и можетбыть использовано в современных высокопроизводительных мультипрограммных вычислитель; ных системах.5Известно устройство управления содериещее регистры и деииФРетори,иНедостатком этого устройства явля" ется невозможность контроля распределения ресурсов в вычислительной сис 0 теме. Йаиболее близким к предлагаемому является устройство для контроля распределения ресурсов в вычислительной.15 системе, содержащее триггер режима, триггер фиксации тупика, четыре группы элементов И, две группы элементов ИЛИ, первый элемент ИЛИ и два блока регистров, причем единичный вход триггера режима подключен к входу пуска версный выходы второго триГгеРа управления подключены к первым входамсоответственно седьмого и восьмогоэлементов И, вторые входы которыхсоединены с вторым выходом первогораспределителя импульсов, выход седь.:мого элемента И подключен к входусброса второго триггера управленияи третьему входу элемента ИЛИ, а выход восьмого элемента И соединен свходом установки триггера анализа,вход сброса которого подключен к управляющему входу устройства, а выход - к входу сброса триггера режима,причем второй выход второго распределителя импульсоа соединен с вторымвходом шестого элемента И и четвертым входом элемента ИЛИ,2. Устройство по и. 1, о т л ич а ю щ е е с я тем, что распредели- тель импульсов содержит счетчик и дешифратор, вход данных которого подключен к выходу счетчика, управляющий вход дешифратора и вход счетчика соединены с входом распределителя, а выходы дешифратора подключены к первым и вторым выходам распределителя. 2устройства, нулевой вход триггера режима подключен к первому входу первой группы элементов И, второй вход первой группы элементов И подключен к первому информационному входу устройства, а выходы первой группы эле- . ментов И подключены к информационным . входам первого блока регистров,. выход которого подключен к первым выходам элементов И второй группы,. выходы кь" торых подключены к входам элементов ИЛИ первой группы, а выходы элемен-. тов И третьей группы соединены с пер" выми входами элементов ИЛИ второй группы, выходы четвертой группы элементов И подключены к первой группе управляющих входов второго блока ре,гистров. Известное устройство предназначено для контроля распределения ресур-, сов в вычислительной системе на осно385 - 4выходом триггера режима, вход установки которого подключен к управляющему входу устройства, первому входуэлемента ИЛИ и входу сброса триггератупика, первые входы первого и второго мультиплексоров соединены с выходами соответствующих регистров перво-.го и второго блока, введены два управляющих мультиплексора, деа распределителя импульсов, два триггерауправления, триггер совпадения,: триг-.гер анализа, элемент ИЛИ-НЕ и. восемьэлементов И, при этом входы данныхпервого и второго управляющих мультиплексоров подключены к выходам соответствующих регистров первого и второго .блоков, управляющие входы этихмультиплексоров соединены с инверснымвыходом триггера режима, первые выхо"ды первого и второго управляющих куль типлексоров подключены соответственно к входам установки регистров второго блока и вторым входам установки регистров первого блока, вход ус-.,тановки первого триггера управлениясоединен с выходом элемента ИЛИ, выход этого. триггера подключен к первомувходу первого элемента И, выход которого соединен с входом первого рас-.пределителя импульсов, входами сбросапервого триггера .управления и триггера совпадения, первые выходы первогораспределителя импульсов подключенык первым входам соответствующих блоков элементов И первой группы, соответствующим входам элемента ИЛИ-НЕи соответствующим первым входам первого мультиплексора, вторые входы которого соединены с выходами соответствующих регистров первого блока, выход первого мультиплексора подключенк первому входу схемы сравнения ипервым входам второго элемента И, выход которого соединен с вторым входомэлемента ИЛИ и первым входом третьегоэлемента И, выход элемента. ИЛИ-НЕ подключен к .вторым входам второго итретьего элементов И, выход которогосоединен с первым входом четвертогоэлемента И, вторые входы первого ичетвертого. элементов И подключены ктактовому входу устройства, вход вто"рого распределителя импульсов соеди"нен с выходом четвертого элемента И,первые выходы этого распределителя1,подключены к соответствующим первымвходам второго мультиплексора, вторые Входы которого соединены с выходами соответствующих регистров второ" 3 1015 ве выявления тупиковых ситуаций, Ту.- пиковая ситуация (клинч) возникает вследствие перехода в состояние ожидания освобождения ресурсов всех процессов, функционирующих в вычислительной системе (ВС). В известном объекте производится обнаружение тупиков при распределении ресурсов, в качестве которых могут в принципе вы. ступать компоненты программных или аппаратных средств ВС, предоставляемые ВС для выполнения вычислитель" ных процессов 2 1. Ограниченные .Функциональные возможности известного устройства обусловлены тем, что для его. работы необходимо построение матрицы, описывающей: граф распределения ресурсов, .который получают вне устройства, например программными средствами. При этом используется первичная информация о владельцах ресурсов и запросах на них. Необходимость предварительного. построения матрицы приводит к существенному снижению быстродействия ВС. Кроме того, сужение Функциональных возможностей прототипа обусловле. но возможностью .решения задач только для Фиксированного числа процессов в системе; Изменение числа процессов приводит к необходимости изменения связей между элементами устройства. ,Это свидетельствует об отсутствии - универсальности устройства. Таким образом, перечисленные недостатки фф снижают экономичность и ухудшают Функциональные возможности устройстваЦель изобретения - .расширение Функциональных возможностей устройства.С этой целью в устройство контро- В ля, содержащее два блока регистров, три группы блоков элементов И, триг" гер режима, элемент:ИЛИ, два мультиплексора и триггер тупика, выход которого соединен с выходом устройства, фф выходы блоков элементов И первой и второй групп подключены соответственно к первым входам установки и входам данных соответствующих регистров первого блока, а выходы блоков элемен" Ю тов Итретьей группы соединены с входами данных соответствующих регист" ров второго блока, первые входы бло" ков элементов И второй и третьей групп подключены соответственно к. И первому и второму входам данных уст" ройства, а вторые входы этих блоков элементов И соединены с инверсным .5 101538 го блока, а выход этого мультиплексора подключен к второму входу схемысравнения, выход которой соединен свходом установки триггера с 1 овпаденияпервый, второй и третий входы пятогоэлемента И подключены к выходам соответственно первого и второго управляющих мультиплексоров и триггера анализа, а выход этого элемента И соединен с входом установки триггера глупи- Вка, инверсный выход триггера совпадения подключен к первому входу шестогоэлемента И, выход .которого соединенс входом установки второго триггерауправления и вторыми входами блоков 1элементов И первой группы, прямой иинверсный выходы второго триггера управления подключены к первым входамсоответственно седьмого и восьмогоэлементов И, вторые входы которых сое Ъ.динены с вторым выходом первого распределителя импульсов, выход седьмого элемента И подключен к входу сброса второго триггера управления итретьему входу элемента ИЛИ, а выход 2 З,восьмого элемента И соединен с входом установки триггера анализа, входсброса которого подключен к управляю.щему входу устройства а выход - квходу сброса триггера режима, причем ЗОвторой выход второго распределителяимпульсов соединен с вторым входомшестого элемента И и четвертым входом элемента ИЛИ,Кроме того, распределитель импуль- зсов содержит счетчик и дешифратрр,вход данных которого подключен к выходу счетчика, управляющий вход дешифратора и вход счетчика соединеныс входом распределителя, а выходы. дешифратора подключены к первым .и вторым выходам распределителя.На Фиг. 1 и 2 изображена Функциональная схема предлагаемого устройства; на Фиг. 3 - Функциональная схемапервого (второго) распределителя импульсов, на Фиг, 4 - пример временнойдиаграммы работы устройства.Устройство содержит (Фиг. 1) первую группу блоков 1 элементов И, пер"вый информационный вход (вход данных)2 устройства соединен с первыми входами блоков 3 элементов И второй группы. Первый блок 4 регистров содержитрегистры 5 входы данных которых сое, динены с выходами соответствующих бло"ков 3, а первые .установочные входцрегистров 5 подключены к выходам соответствующих блоков 1. Первый управляю 5 6щий мультиплексор 6 содержит элементы И и элемент И-НЕ, первые входы элементов И 7 соединены с выходами соответствующих регистров 5, а выходыс .входами элемента И-НЕ 8, Устройство содержит та 1 дке элемент ИЛИ 9. Второй информационный вход 10 (вход данных) устройства подключен к первым входам блоков 11 элементов И третьей группы. Второй блок 12 регистров содержит регистры 13, входы данных которыхсоединены с выходами соответствующих блоков 11, а установочные входы подключены к выходам соответствующих элементов 7. Второй управляющий мультиплексор 14 содержит элементы И 15 и элемент И-НЕ 16. Первые входы элементов 15 соединены с выходами соответствующих регистров 13, а выходы подключены к соответствующим входам элемента 16 и вторым установочным входам регистров 5. Управляющий вход 17 устройства соединен с установочным входом триггера 18 режима, ин" версный выход которого подключен к вторым входам блоков 3 и 11, Позиционные обозначения (входы и выходы) 19-31 использованы для обеспечения однозначности перехода с Фиг. 1 на фиг. 2.Устройство содержит (Фиг. 2) пер-. вый триггер 32 управления, установочный вход которого соединен с выходом элемента ИЛИ 9. Тактовый вход 33 устройства подключен к первому входу пер вого элемента И 34, второй вход которого соединен с .выходом триггера 32, а выход - с входом первого распределителя 35 импульсов. Устройство содержит также первый мультиплексор, образованный элементами И 36 и элементом ИЛИ 37, элемент ИЛИ-НЕ 38, второй элемент И 39, схему 40 сравнения, триггер 41 совпадения,. третий элемент И 42, четвертый элемент И 43, пятый элемент И 44, триггер 45 тупика, вы" ход которого соединен с выходом 46 устройства, шестой элемент И 47, второй триггер 48 управления, седьмой элемент И 49, восьмой элемент. И 50, триггер 51 анализа, второй распределитель 52 импульсов и второй мультиплексор, образованный элементами И 53 и элементом ИЛИ 54.Первые вйходы распределителя 35 подключены к вторым входам блоков 1, первым входам элементов 36 и входам элемента 38. Второй выход распределителя 35 соединен с первыми входами7 . 1015385 8элементов 49 и 50, вторые входы эле" первый выход распределителя 35; ементов 36 подключены к выходам сост- второй выход распределителя 35ветствующих регистров 5, а выходы со,2 п,п+1, - номера тактовых имединены с входами элемента 37, Выход пульсов в случае, если устройство рвеэлемента 37 подключен к первым вхо- з ботает с и ресурсами. Формированиедам элемента 39 и схемы 40, выход ,третьего и последующих импульсов наэлемента 38,соединен с" вторым входом выходах распределителя 35 осуществлязлемента 39 и первым входом элементается аналогично,42; а выход элемента 39 подключен квторому входу элемента 42 и первому 1 ф УстРойство Работает следУющим обиходу элемента 9. Входы элемента 43 разом.соединены с входом 33 устройства и выходом элемента 42, а его выход под- В исходном состоянии все триггерыключен.к входу распределителя 52. находятся в нулевом состоянии. ЕдиничВторой вход схемы 40 соединен с вы- тз ный сигнал с нулевого выхода триггеходом элемента 54, а выход - с уста" ра 18 разрешает прием информации ченовочным входом триггера 41. Вход рез элементы 11 и 3 в регистры 13 исброса триггера 41 подключен к выхо, а также запрещает прием информацииду элемента 34, а инверсный выход - элементами 7 и 15 мультиплексоров 6к первому входу элемента 47, Выход щ и 14, т,е. запрещается, взаимная устаэлемента 47 соединен .с установочным новка в .нулевое состояние регистров 5входом триггера 48 и вторыми входами и 13 блоков 4 и 12. В каждый регистрблоков 1. Первые выходы распределите (13) блока 4 (12)заносится код номе"ля 52 подключены к первым входам эле- ра процесса, который владеет этим рементов 53, вторые входы которых сое з сурсом. Информация в регистры постудинены с выходами соответствующих ре- пает с входов.2 и 10 устройства погистров 13. Второй.выход распредели" командам операционной системы ВС. Потеля 52 подключен к второму входу сигналу пуска (начало анализа), поэлемента 47 и второму входу элемента ступающему на вход 17 устройства триг"9 Вторые .входы элементов 49 и 50. ф гера 18 устанавливается в единичноесоединены соответственно с прямым и состояние. При этом блокируется приинверсным выходами триггера 48, вход ем информации в регистры блоков 4 и. сброса которого подключен к выходу . 2. С помощью мультиплексоров 6 и 14,,элемента 49 и третьему входу злемен- устанавливаются в нулевое состояниета 9. Четвертый вход элемента 9. и вхо те регистры 13 блока 12, которые храды сброса триггеров 45 и 51 соединены . нят коды номеров процессов;запращи--33с входом 17 устройства. Устанавочнь 1 В 1 вающих свободные ресурсы.Для таких ре,входы триггеров 45 и 51 подключены сурсов соответствующие регистры 5 в:к выходам соответственно элементов блоке 4 хранят нулевой код. Кроме то 44 и 50. Выход триггера 51 соединен го, происходит установка в нулевое4 Ос входом сброса триггера,18 и первым состояние тех регистров 5 блока 4,,входом элемента 44, второй и третий которые хранят коды номеров процессов,входы которого подключены. к выходам владеющих ресурсами, запросы на котоэлементов 8 и 16. рые отсутствуют. Для таких ресурсов.соответствующий регистр 13 в блоке4Распределители 35 и 54 содержат . 12 хранит ну 4 н-вой код. Сущность этихпоследовательно соединенные счетчик операций сводится к удалению из даль".55 и дешифратор 56 (фиг. 3). нейшрго рассмотрения процессов, кото,На фиг. 4 приведен пример времен-. рые заведомо могут быть завершены и.ной диаграммы работы устройства для вследствие этого не приведут. к тупику,случая формирования первого и второго ф Далее производится переход к выявле"выходных сигналов на выходе распреде- нию процессов, которые являются толь"лителя 35,по.которым осуществляется ко владельцами некоторых ресурсов, авыбор первого и второго регистров в сами дополнительно никакие другиеблоке 4; На этом чертеже использованы ресурсы не запрашивают. Если некотоследующие условные обозначения: а - зз рый процесс является только владель,вход тактовом импульсов 33, бвыход цем ресурса, то его номер не долженэлемента 9, в - единичный выход триг- быть записан ни в одном из регистровгеоа 32, г - выход элемента 34, д - 13. На проверке этого факта основыва-.185 10цессу, и устанавливает регистр 5 в нулевое состояние. Через мультиплексор б осуществляется коррекция содер.- жимого одноименного регистра блока 12, Анализ продолжается до окончания проверки содержимого последнего регистра 5 блока 4, Сигнал с второго выхо" да распределителя 35 поступает на элементы 49 и 50, Если в данном цикле проверки были удаления процессов, тех, которые могут реально завершиться, то сигналом с единичного выхода триггера 48 открывается элемент 49, который через элемент 9 устанавливает в единичное состояние триггер 32 и тем самым инициирует начало нового цикла анализа. Если оказывается, что в очереДном цикле анализа удалений процессов, которые могут завершиться не было, то срабатывает элемент 50 и устанавливает триггер 51 в единичное состояние. Сигнал окончания анализа с выхода триггера 51 устанавливает триггер 18 в нулевое состояние и, кроме того, является разрешающим сиг налом для элемента 44, Если в резуль- . тате анализа все процессы в системе могут быть реально завершены, то все регистры блоков 4 и 12 устанавливаются,в нулевое состояние. Следовательно, на выходах элементов 8 и 16 сигналы отсутствуют и элемент 38 не срабатывает, а триггер 45 остается в нулевом состоянии. При этом сигнал тупика с выхода 46 устройства не выдается. В противном случае триггер 45 уста. навливается в единичное состояние и с выхода 46 выдается сигнал тупиковой ситуации. 9 10153ется выявление процессов, которыетолько владеют ресурсами,По сигналу начала анализа на вхо-де 17 триггер 32 через элемент 9 устанавливается в единичное состояниЕ Зи открывает элемент 34, который разрешает прохождение тактового импульсас входа 33 на вход распределителя 35.Сигнал с первого выхода распределителя 35 подключает через элементы 36 10и 37 выходы первого регистра 5 блока 4 к первому входу схемы 40. Одна"временно по сигналу с выхода элемента34 триггер 32 устанавливается в нульи блокирует выдачу последующих такта= 13вых сигналов на вход распределителя35. Если код процесса в первом регистре 5 блока 4 оказался нулевым,то элемент 39 вырабатывает сигнал,разрешающий переход к проверке содержимого следующего регистра 5. В противном случае элементы 38 и 39 вырабатывают сигналы, открывающие элемент42, который в свою очередь разрешаетвыдачу тактовых сигналов с входа 33 2через элемент 43 на вход распределителя 52. Распределитель 52 по каждомуочередному тактовому импульсу черезэлементы 53 и 54 подключает поочередно выходы регистров 13 блока 12 к вто-зврому входу схемы 40.Если при последовательном сравнении с содержимым регистров 12 происходит хотя бы одно совпадение, т.е.исследуемый процесс не только владеетресурсами, но и запрашивает их, тосрабатывает триггер 41 и устанавли вается в единичное состояние. Сигналс последнего выхода распределителя 52устанавливает триггер 32 через элемент 9 в единичное состояние, а такжепоступает на вход элемента 47. Элемент 47 срабатывает, если совпаденияне было, т,е. исследуемый процесс незапрашивает ресурс, и устанавлываетв единичное состояние триггер 48.Одновременно по сигналу с выхода элемента 47 открывается блок 1, номер. которого соответствует исследуемому проСущественным достоинством устройства .является расширение его функциональных возможностей, что объясняетсяотсутствием необходимости предвари-, тельного программного построения матрицы графа распределения ресурсов, а также внесения изменений в структуру устройства при изменении размерности решаемых задач.11015385 Составитель Г. Виталиевор А. Власенко Техред В.Далекорей КорректорС. Шекмарааее ае 17/46 а ПП "Патент", г. Ужгород,л. Проектная, 4 фил Тираж 706 ВНИИПИ Государственно по делам изобретен 13035 Москва, Ж, Подписно комитета СССР и открытий аская наб., д. а а е ееае ае