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

 

1o УСТРОЙСТВО КОНТРОЛЯ, coдёрж нцее два блока ре гистров, три группы блоков элемеитов И, триггер режима, элемент ИШ, два мультиплексора и триггё|э тупика, выход которого соединен с выходом у&тройства, выходы блоков элементов И первой и второй групп подключены еортветственнО К первым .входам установки и входам данных соответствующих р ёгистров первого блока, а выходы блоков элементов И третьей группы соединены с входами данных соответствующих регистров второго блока, первые входы блоков элементов И второй и третьей групп подключены соответстве «но к первому и второму входам данных устройства, а вторые входы этих блоков элементов И соединены с инверсным выходом триггера режима, вход установки которого подключен к управляю|щему входу устройства , первому входу элемента ИЛИ и входу сброса триггера тупика, пер-выё входы первого и второго мультиплексоров соединены с выходами соот .ветствующих регистров первого и второго блоков , отличающееся .тем, что, с целью расширения функцио-. наЛьных возможностей, оно содержит два упр авляющих мул ь ти пле ксо ра, два распределителя кмпульсов, два Tj irre ра управления, триггер совпадения, Триггер анализа, элемент ИЛИ-НЕ и восемь элементов И, при этом входы данных первого и второго управляющих Мультиплексоров подключены к выходам соответствукщйх регистров первого и второго блоков, управляющие входы эТих мультиплексоров соединены с инверсным выходом триггера режима, первые выходы первого и второго управляющих мультиплексоров подключены .соответственно к входам установки регистров второго блока и вторым входам установки регистров первого блока, вход установки первого триггера управления соединен с выходом элемента .ИЛИ, выход этого триггера подключен к первому входу первого элемента И, выход которого соединен с входом пер-, вого. распределителя импульсов, входами сброса первого триггера управления и триггера совпадения, первые выходы лервого распределителя имсл nyjibcoB подключены к первым входам 00 соответствующих блоков элементов И с первой группы, соответствующим вхоО1 дам элемента ИЛИ-Н и соответствующим первым входам первого мультиплексора , вторые входа которого соединены с выходами соответствующих регистров первого блока, выход первого мультиплексора подключен к первому входу схемы сравнения и первым входам второго элемента И, выход которого соединен с вторым входом элемента ИЛИ и первым входом третьего элемента И, выход элемента ИЛИ-НЕ подключен к ВТОРЫМ входам второго и третьего эле

СОО3 СОВЕТСНИХ

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

РЕСГЗУЬЛИН

ОПИСАНИЕ ИЗОБРЕТЕНИЯ и 4RIPCNONI!f CBH4!IWlhCTRV

-нальных возможностей, оно содержит два управляющих мультиплексора, два распределителя импульсов, два триггера управления, триггер совпадения, триггер анализа, элемент ИЛИ-HE u восемь элементов И, при этом входы данных первого и второго управляющих мультиплексоров подключены к выходам соответствующйх регистров первого и. в1орого блоков, управляющие входы этих мультиплексоров соединены. с ин.версным. выходом триггера режима, первые выходы первого и второго управляющих мультиплексоров подключены соответственно к входам установки ре" гистров второго блока и вторым входам установки регистров первого блока, вход установки первого триггера уп" равления соединен с выходам элемента

ИЛИ,. выход этого триггера подключен к первому входу первого элемейта И, выход которого соединен с входом пер-.

"Ф вого. распределителя импульсов вхоУ дами сброса первого триггера управления и триггера совпадения, первые выходы первого распределителя импульсов подключены к первым входам Ю . .соответствующих блоков элементов И М первой группы, соответствующим вхо- Q© дам элемента ИЛИ-Hf и соответствую- Q3 щим первым входам первого мультиплексора, вторые входы которого соединены с выходами соответствующих регистров nepaoro блока, выход первого мультиплексора подключен к первому входу,фЬ схемы сравнения и первым входам второго элемента И, выход которого соединен с вторым входом элемента ИЛИ и.первым входом третьего элемента И, выход элемента ИЛИ-НЕ подключен к вторым входам второго и третьего эле10СУДАРСТОЕННЬЙ КОМИТЕТ СССР

00 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНР1ЫТИЙ

;(21) 3287775/18-24 (22).16 03.81 .(:46)- 30.64 83. Бюл. Н 16 (72) С.Н. Ткаченко, В.С. Харченко, Г .Н. Тимонькин и .А.П; Пузырев (53) 681 325(088.8) . °

{56) 1. Авторское свидетельство СССР

9 572787, кл.: 6 06 F. 9/00, 1977.

2."Эпйегпай1опаВ.доигпаф of system вс1епсе", 1979 v. 10, И 5, р.482, fig. 3 (прототип). (54)(57) 1. УСТРОЙСТВО КОНТРОЛЯ, содержащее два бсюка регистров, три группы блоков элементов И, триггер

° режима, элемент ИЛИ, два мультиплексора и триггер тупика, выход которого соединен с выходом устройства, выходы блюков элементов И пераой и второй групп подключены соответственнО к первым .входам: установкй и входам данйых соответствующих регистров nepsего .блока, а выходы блоков элементов И третьей группы соединены с входами данных соответствующих регистров второго блока, первые входы блоков элементов Й второй и третьей групп подключены соответственно к первому и второму входам данных устройства, а вторые входы этих блюков элементов И. соединены с инверсным выходом триггера режима, вход установки которого подключен к управляющему входу устройства, первому входу элемента ИЛИ и входу сброса триггера. тупика, пер.-вые входы первого.и второго мультиплексоров соединены с выходами соот,ветствующих регистров nepsoro и вто рогоблоков, о тли ч ающее ся .тем, что, с целью расширения функцио-;

Я0„„3 015385 Д

1015385 ментов И, выход которого соединен с .первым входом четвертого элемента И, вторые входы первого и четвертого элементов И подключены к тактовому входу устройства, вход второго распределителя импульсов соединен с выходом четвертого элемента И, первые выходы этого распределителя подключены к соответствующим первым входам второго мультиплексора, вторые входы которого соединены с выходами соответствующих регистров второго- блока, а выход этого мультиплексора подключен к второму входу схемы сравнения, выход которой соединен с входом уста- новки триггера совпадения, первый, второй и третий. входы пятого элемента И подключены к выходам соответственно первого и второго управляющих мультиплексоров и триггера анализа, а выход этого элемента И соединен с входом установки триггера тупика, инверсный выход триггера совпадения под-. ключен к первому входу шестого элемента И, выход которого соединен с входом установки второго триггера уп" равления и вторыми входами блоков эле. ментов И первой группы, прямой и ин"

Изобретение относится к вычислительной технике и может быть использовано в современных высокопроизводительных мультипрограммных вычислитель., ных системах.

Известно устройство управления содерщещее регистры и деиифретори(1 р

Недостатком этого устройства является невозможность контроля распределения ресурсов в вычислительной сис-.

10 теме.

Йаиболее близким к предлагаемому является устройство для контроля распределения ресурсов в вычислительной .15 системе, содержащее триггер режима, триггер фиксации тупика, четыре группы элементов И, две группы элементов

ИЛИ, первый элемент ИЛИ и два блока регистров, причем единичный вход триг-20 гера режима подключен к входу пуска версный выходы второго триГгера управления подключены к первым входам соответственно седьмого и восьмого элементов И, вторые входы которых соединены с вторым выходом первого распределителя импульсов, выход седь:мого элемента И подключен к входу сброса второго триггера управления и третьему вход„ элемента ИЛИ, а выход восьмого элемента И соединен с входом установки триггера анализа, вход сброса которого подключен к управляющему входу устройства, а выход - к входу сброса триггера режима, причем второй выход второго распределителя импульсов соединен с вторым входом шестого элемента И и четвертым входом элемента ИЛИ.

2. Устройство по и. 1, о т л ич а ю щ е е с я тем, что распределитель импульсов содержит счетчик и дешифратор, вход данных которого под" ключен к выходу счетчика, управляющий вход дешифратора и вход счетчика соединены с входом распределителя, а выходы дешифратора подключены к первым и вторым выходам распределителя.

2 устройства, нулевой вход триггера режима подключен к первому входу пер вой группы элементов И, второй вход первой группы элементов И подключен к первому информационному входу устройства, а выходы nepsoA группы эле- . ментов И подключены к информационнымвходам первого блока регистров,. выход которого подключен к первым выходам элементов И второй группы,. выходы которых подключены к входам. элементов

ИЛИ первой группы, а выходы элемен-. тов И третьей группы соединены с первыми входами элементов ИЛИ второй группы, выходы четвертой группы эле ментов И подключены к первой группе управляющих входов второго блока ре,гистров.

Известное устройство предназначе но для контроля распределения ресур-.. сов в вычислительной системе на осно385 - 4 выходом триггера режима, вход установки которого подключен к управляющему входу устройства, первому входу элемента ИЛИ и входу сброса триггера тупика, первые входы первого и второго мультиплексоров соединены с выходами соответствующих регистров перво-. го и второго блока, введены два управляющих мультиплексора, два распределителя импульсов, два триггера управления, триггер совпадения,: триг-. гер анализа, элемент ИЛИ-НЕ и. восемь элементов И, при этом входы данных первого и второго управляющих мультиплексоров подключены к выходам соответствующих регистров первого и второго .блоков, управляющие входы этих мультиплексоров соединены с инверсным выходом триггера режима, первые выхо" ды первого и второго управляющих куль° типлексоров подключены соответственно к входам установки регистров второго блока и вторым входам установки регистров nepeoro блока, вход ус-. ,тановки первого триггера управления соединен с выходом элемента ИЛИ, выход этого. триггера подключен к первому входу первого элемента И, выход которого соединен с входом первого рас-. пределителя импульсов, входами сброса первого триггера .управления и триггера совпадения, первые выходы первого распределителя импульсов подключены к первым входам соответствующих блоков элементов И первой группы, соответствующим входам элемента ИЛИ-НЕ и соответствующим первым входам первого мультиплексора, вторые входы которого соединены с выходами соответствующих регистров первого блока, выход первого мультиплексора подключен к первому входу схемы сравнения и первым входам второго элемента И, выход которого соединен с вторым входом элемента ИЛИ и первым входом третьего элемента И, выход элемента. ИЛИ-НЕ подключен к вторым входам второго и третьего элементов И, выход которого соединен с первым входом четвертого элемента И, вторые входы первого и четвертого элементов И подключены к тактовому входу устройства, вход второго распределителя импульсов соединен с выходом четвертого элемента И, первые выходы этого распределителя

I ,подключены к соответствующим первым входам второго мультиплексора, вторые входы которого соединены с выхо дами соответствующих регистров втооо3 1015 ве выявления тупиковых ситуаций. Ту.пиковая ситуация (клинч) возникает вследствие перехода в состояние ожидания освобождения ресурсов всех проФ цессов, функционирующих в вычислительной системе (ВС). В известном объекте производится обнаружение тупиков при распределении ресурсов, в качестве которых могут в принципе выступать компоненты программных или аппаратных средств ВС, предоставляемые ВС для выполнения вычислительных процессов (2 $. Ограниченные .функциональные возможности известного устройства обусловлены тем, что для его. работы необходимо построение матрицы, описывающей: граф распределения ресурсов, .который получают вне устройства, например программными средствами. При этом используется первичная информация о владельцах ресурсов и запросах на них. Необходимость предварительного. построения матрицы приводит к существенному снижению быстродействия

ВС. -Кроме того, сужение функциональных возможностей прототипа обусловле. но возможностью .решения задач только для фиксированного числа процессов в системе; Изменение числа процессов приводит к.необходимости изменения связей между элементами устройства. ,Это свидетельствует об отсутствии — универсальности устройства. Таким образом, перечисленные недостатки снижают экономичность и ухудшают функциональные возможности устройства..

Цель изобретения - расширение функциональных возможностей устройства.

С этой целью в устройство контроля, содержащее два блока регистров, три группы блоков элементов И, триггер режима, элемент ИЛИ, два мультиплексора и триггер тупика, выход которого соединен с выходом устройства, выходы блоков элементов И первой и второй групп подключены соответственно к первым входам установки и входам данных соответствующих регистров первого блока, а выходы блоков элементов И третьей группы соединены с входами данных соответствующих регист" ров второго блока, -первые входы блоков элементов И второй и третьей групп подключены соответственно к. 3S первому и второму входам данных уст" ройства, а вторые входы этих блоков элементов И соединены с инверсным5 101538 го блока, а выход этого мультиплексора подключен к второму входу схемы сравнения, выход которой соединен с входом установки .триггера с1овпадения, первый, второй и третий входы пятого элемента И подключены к выходам соответственно первого и второго управляющих мультиплексоров и триггера анализа, а выход этого элемента И соединен с входом установки триггера Фупи- >В ка, инверсный выход триггера совпадения подключен к первому входу. шестого элемента И, выход .которого соединен с входом установки второго триггера управления и вторыми входами блоков элементов И первой группы, прямой и инверсный выходы второго триггера управления подключены к первым входам соответственно седьмого и восьмого элементов И, вторые входы которых сое.20 .динены с вторым выходом первого распределителя импульсов, выход седьмого элемента И подключен к входу сброса второго триггера управления и третьему входу элемента ИЛИ, а выход ,восьмого элемента И соединен с входом установки триггера анализа, вход сброса которого подключен к управляющему входу устройства, а выход - к входу сброса триггера режима, причем ЗО второй выход второго распределителя импульсов соединен с вторым входом шестого элемента И и четвертым входом элемента ИЛИ.

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

На фиг. 1 и 2 изображена функциональная схема предлагаемого устройства; на фиг. 3 - Функциональная схема первого (второго) распределителя им° ° ° пульсов, на фиг. 4 - пример временной диаграммы работы устройства.

Устройство содержит (Фиг. 1) первую группу блоков 1 элементов И, первый информационный вход (вход данных)

2 устройства соединен с первыми входами блоков 3 элементов И второй группы. Первый блок 4 регистров содержит регистры 5,. входы данных которых сое, динены с выходами соответствующих блоков 3, а первые .установочные входц регистров 5 подключены к выходам соответствующих блоков 1. Первый управляю5 6 щий мультиплексор 6 содержит элементы

И и элемент И-НЕ, первые входы элементов И 7 соединены с выходами соответствующих регистров 5, а выходыс .входами элемента И-НЕ 8, Устройство содержит та ке элемент ИЛИ 9. Второй информационный вход 10 (вход данных) устройства подключен к первым входам блоков 11 элементов И третьей группы.

Второй блок 12 регистров содержит регистры 13, входы данных которых соединены с выходами соответствующих блоков 11, а установочные входы подключены к выходам соответствующих элементов 7. Второй управляющий мультиплексор 14 содержит элементы И 15 и элемент И-НЕ 16. Первые входы элементов 15 соединены с выходами соответствующих регистров 13, а выходы подключены к соответствующим входам элемента l6 и вторым установочным входам регистров 5. Управляющий вход

17 устройства соединен с установочным входом триггера 18 режима, инверсный выход которого подключен к вторым входам блоков 3 и".11. Позиционные обозначения (входы и выходы)

19-31 использованы для обеспечения однозначности перехода с Фиг. 1 на фиг. 2.

Устройство содержит (фиг. 2) пер-. вый триггер 32 управления, установочный вход которого соединен с выходом элемента ИЛИ 9. Тактовый вход 33 устройства подключен к первому входу пер.

coro элемента И 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 1-01 5385 8 элементов 49 и 50, вторые входы эле" первый выход распределителя 35; ементов 36 подключены к выходам сост- второй выход распределителя 35; ветствуюцих регистров 5, а выходы со- 1,2...,,n,n+f, - номера тактовых имединены с входами элемента 37. Выход пульсов в случае, если устройство ра= элемента 37 подключен к первым BxO S ботает с h ресурсами. Формирование дам элемента 39 и схемы 40, выход,третьего и последующих импульсов на элемента 38,соединен с" вторым входом выходах распределителя 35 осуществляэлемента 39 и первым входом элемента ется аналогично.

42; а выход элемента 39 подключен к второму входу элемента 42 и первому 1ф УстРойство Работает следУюцим об входу элемента 9. Входы элемента 43 разом. соединены с входом 33 устройства и вы. ходом элемента 42, а его выход под- В исходном состоянии все триггеры . ключен.к входу распределителя 52. находятся в нулевом состоянии. ЕдиничВторой вход схемы 40 соединен с вы-- rS ный сигнал с нулевого выхода триггеходом элемента 54, а выход - с уста- ра 18 разрешает прием информации ченовочным входом триггера 41. Вход рез элементы 11 и 3 в регистры 13 и сброса триггера 41 подключен к выхо- 5, а также запрещает прием информации ду элемента 34, а инверсный выход - элементами 7 и 15 мультиплексоров 6 к первому входу элемента 47. Выход щ и 14, т.е. запрещается, взаимная уста элемента 47 соединен .с установочным .новка в .нулевое состояние регистров 5 входом триггера 48 и вторыми входами -и 13 блоков 4 и 12. В каждый регистр блоков 1. Первые выходы распределите- 5 (13) блока 4 (12)заносится код номе" ля 52 подключены к первым входам эле- ра процесса, который владеет этим рементов 53, вторые входы которых сое.- gS сурсом. Информация в регистры постудинены с выходами соответствующих ре- пает с входов.2 и 10 устройства по гистров 13. Второй .выход распредели- командам операционной системы ВС. По теля 52 подключен к второму входу - сигналу пуска (начало анализа), поэлемента 47 и второму входу элемента ступающему на вход 17 устройства триг"

9 Вторые .входы элементов 49 и 50 гера 18 устанавливается в единичное соединены соответственно с прямым и состояние. При этом блокируется приинверсным выходами триггера 48, вход ем информации в регистры блоков 4 и . сброса которого подключен к выходу 12. С помощью мультиплексоров 6 и 14 . .элемента 49 и третьему входу элемен-. устанавливаются в нулевое состояние та 9. Четвертый вход элемента 9. и вхо те регистры 13 блока 12, которые храды сброса триггеров 45 и 51 соединены нят коды номеров процессов;запраши- .

--35 с входом 17 устройства. Устанавочнь1В 1вающих свободные ресурсы.Для таких ре,входы триггеров 45 и 51 подключены сурсов соответствующие регистры 5 в

:к выходам соответственно элементов блоке 4 хранят нулевой код. Кроме то44 и 50. Выход триггера 51 соединен го, пРоисходит установка в нулевое

4О с входом сброса триггера .18 и первым. состояние тех регистров 5 блока 4, ;входом элемента 44, второй и третий которые хранят коды номеров процессов, входы которого подключены. к выходам владеющих ресурсами, запросы на котоэлементов 8 и 16. рые отсутствуют. Для таких ресурсов соответствующий регистр 13 в блоке

lS

Распределители 35 и 54 содержат 12 хранит нулевой код. Сущность этих последовательно соединенные счетчик операций сводится к удалению из даль55 g дешифратор 56 (Фиг. 3) нейшрго рассмотрения процессов, котоНа фиг. 4 приведен пример времен-. Рые заведомо могут быть завершены и. ной диаграммы работы устройства для вследствие этого не приведут. к тупику, случая формирования первого и второго з далее производится переход к выявлевыходных сигналов на выходе распреде- нию процессов, которые являются тольлителя 35,по которым осуществляется ко владельцами некоторых ресурсов, а выбор первого и второго регистров в сами дополнительно никакие другие блоке 4; На этом чертеже использованы ресурсы не запрашивают. Если некотоследующие условные обозначения: à - ss рый процесс является только владельвход тактовом импульсов 33, б выход цем ресурса, то его номер не должен элемента 9, в - единичный выход триг- быть записан ни в одном из регистров гева 32, г - выход элемента 34, д - 13. На проверке этого Факта основыва-.

85 10 цессу, и устанавливает регистр 5 в нулевое состояние. Через мультиплексор 6 осуществляется коррекция содержимого одноименного регистра блока 12.

Анализ продолжается до окончания проверки содержимого последнего регистра 5 блока 4. Сигнал с второго выхода распределителя 35 поступает на элементы 49 и 50, Если в данном цикле проверки были удаления процессов, тех, которые могут реально завершиться, то сигналом с единичного выхода триггера 48 открывается элемент 49, который через элемент 9 устанавливает в единичное состояние триггер 32 и тем самым инициирует начало нового цикла анализа. Если оказывается, что в очереДном цикле анализа удалений процессов, которые могут завершиться не было, то срабатывает элемент 50 и устанавливает триггер 51:в единичное состояние. Сигнал окончания анализа

J с выхода триггера 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 устанавливается в нуль и блокирует выдачу последующих такта= 1$ вых сигналов на вход распределителя

35. Если код процесса в первом регистре 5 блока 4 -оказался нулевым, то элемент 39 вырабатывает сигнал, разрешающий переход к проверке содер- m жимога следующего регистра 5. В противном случае элементы 38 и 39 вырабатывают сигналы, открывающие элемент

42, который в свою очередь разрешает выдачу тактовых сигналов с входа 33 25 через элемент 43 на вход распределителя 52. Распределитель 52 па каждому очередному тактовому импульсу через элементы 53 и 54 подключает поочередно выходы регистров 13 блока 12 к вто-щ рому входу схемы 40.

Если при последовательном сравнении с содержимым регистров 12 происходит хотя бы одно совпадение, т.е. исследуемый процесс не только владеет ресурсами, но и запрашивает их, то срабатывает триггер 41 и устанавли вается в единичное состояние. Сигнал с последнего выхода распределителя 52 устанавливает триггер 32 через элемент 9 в единичное состояние, а также поступает на вход элемента 47. Элемент 47 срабатывает, если совпадения не было, т.е. исследуемый процесс не запрашивает ресурс, и устанавлывает в единичное состояние триггер 48.

Одновременно по сигналу с выхода элемента 47 открывается блок 1, номер. которого соответствует исследуемому праСущественным достоинством устройства .является расширение его функциональных возможностей, что объясняется отсутствием необходимости предвари-. тельного программного построения матрицы графа распределения ресурсов, а также внесения изменений в структуру устройства при изменении размерности решаемых задач. о-з5385

26. и

1015385

1015385

Составитель Г. Виталиев

РедактоР А. Власенко ТехРед В.ДалекоРей - КоРРектоР С, Щекмар ее е

Заказ 3217/46 Тираж 706 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Рауаская наб., д. 4/5 в еаееевееа е «а в е» авве аее е вее е

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