Устройство для контроля распределения ресурсов

, 6 06 Р 9/00,1983.Авто рсМ 129705154) УСТРОПРЕДЕЛЕН ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР ВТОРСКОМУ СВИДЕТЕЛЬСТВУ(56) Авторское свидетельстМ 1015385, кл. 6 06 Р 11/ кое свидетельство СССР кл. 6 06 Р 11/00, 1987.ЙСТВО ДЛЯ КОНТРОЛЯ РАСИЯ РЕСУРСОВ(57) Изобретение относится к вычислительной технике и может найти применение в высокопроизводительных вычислительных системах для контроля корректности распределения ресурсов. Цель изобретения - повышение оперативности контроля, Устройство содержит и регистров 1.1-1,п запросов, и регистров распределения ресурсов, регистр 3 свободных ресурсов, триггер 4 режима, и триггеоов 5.1-5.п тупика, и тригеров 6 1-6 и управления, (пхгп) блоков сравнения 7.1-7,п.щ, первую группу элементов И 8.1-8.п, первую группу элементов ИЛИ 9.1- 9 и, вторую группу элементов И 10,1-10,п, третью группу элементов И 11.1-11,п, чет,у/ О1702372 Регистр 3 свободных ресурсов выполняет функции приема и хранения векторасвободных ресурсов и результата сложениястроки матрицы распределения ресурсов5 процессам с вектором свободных ресурсов,Триггер 4 режима выполняет переводустройства из режима ожидания в режимработы и обратно.Триггеры 5.1 - 5.п тупика служат для ин 10 дикации процессов, вовлеченных в тупиковую ситуацию.Триггеры 6,1 - б.п управления необходимы для организации операции сложения,моделирующей освобождение ресурсов,15 (пхв) блоков 7.1.1-7.п.в сравнения (выполняют поэлементное сравнение строкматрицы запросов процессов с элементамивектора свободных ресурсов.Первая группа элементов И 8.1-8.п фик 20 сирует тот факт, что все элементы строкиматрицы запросов процессов меньше илиравны элементам вектора свободных ресурсов.Первая группа элементов ИЛИ 9.1 - 9,п25 осуществляет выбор обнуляющих сигналовдля триггеров 6.1-6,п управления с двух входов,Вторая группа элементов И 10,1-10.пвыполняет формирование сигналов, необ 30 ходимых для выполнения операции суммирования,Третья группа элементов И 11.1-11.пформирует сигналы обнуления триггеров6.1-6,п управления в том случае, если соот 35 ветствующий процесс не владеет ни однойединицей ресурсов.Четвертая группа элементов И 12.112,(п) служит для разрешения или запрещения прохождения тактовых импульсов в40 зависимости от сигналов, выставленных навыходах элементов И 10.1 - 10.п,Пятая группа элементов И 13.1-13.ппредназначена для регулирования сигналов, необходимых для выполнения опера 45 ций сложения. вертую и пятую группы элементов И, генератор тактовых импульсов, вторую группу элементов ИЛ И, группу коммутаторов 16.1 - 16 в, в блоков элементов И, в сумматоров, коммутатор 19, первый и второй элементы И, первый, второй, третий и четвертый элементы ИЛИ, одновибратор 32, Новыми элеИзобретение относится к вычислительной технике и может найти применение в овременных высокопроизводительных вычислительных системах для контроля корректности распределения ресурсов.Цель изобретения - повышение оперативности контроля,На фиг,1, 2 представлена функциональНая схема устройства для контроля распределений ресурсов,Устройство для контроля распределения ресурсов содержит п регистров 1,1 - 1,п запросов, и регистров 2.1-2.п распределения ресурсов, регистр 3 свободных ресурсов, триггер 4 режима, и триггеров 5,1 - 5.п тупика, и триггеров 6 Л-б.п управления, (пхв) блоков 7.1.1-7.п.в сравнения первую группу элементов И 8 Л - 8.в, первую группу элементов ИЛИ 9.1 - 9.п, вторую группу элементов И 10.1-10 и, третью группу элементов И 11.1 - 11,п, четвертую группу элементов И 12 Л.(п), пятую группу элементов И 13.1-13.п, генератор 14 тактовых импульсов, вторую группу элементов ИЛИ 15.1-15.п, группу коммутаторов 16,1 - 1 б.в, в блоков элементов И 17.1-17 в, в сумматоров 18 Л.в, коммутатор 19, второй элемент И 20, третий и первый элементы ИЛИ 21, 22, первый элемент И 23, второй и четвертый элементы ИЛИ 24, 25, вход 26 пуска устройства, вход 27.1(1 = 1,п) группы входов запросов устройства, вход 28 свободных ресурсов устройства, вход 29.11 группы входов распределения ресурсов устройства, выход 301) группы выходов ресурсов в тупике устройства, выход 31.1 группы выходов процессов в тупике устройства, одновибратор 32.Регистры 1.1-1.п запросов служат для приема и хранения матрицы запросов от процессов на ресурсы системы,Регистры 2.1-2,п распределения ресурсов предназначены для приема и хране-. ния матрицы распределения ресурсов процессам. ментами в устройстве являются (и) триггеров 6.6-6.п управления, птриггеров 5.2- 5,п тупика, триггера 4 режима, (пхв) блоков сравнения 7.2.2-7.п в, (5 п - 20) элементов И, (2 п - 4) элементов ИЛИ, в коммутаторов, в сумматоров, одновибратор 32, 2 ил.Генератор 14 тактовых импульсов слу-, входов 28 через коммутатор 19 и устанавлижит для формирования последовательности ваются в единичное состояние все триггерытактовых импульсов. 5.1 - 5.п тупика, э по заднему фронту устаВторая группа элементов ИЛИ 15,1 - навливается вединичноесостояниетриггер15 и предназначена для фиксации отсутст 4 режима. Длительность сигнала пуска тавия распределения ресурсов кова, что позволяет закончиться переходсоответствующим процессом. ным процессам в схеме по цепи: регистрыГруппа коммутаторов 16.1 - 16.в. выпал.1 - 1,п запросов и регистр 3 свободных реняет функцию коммутации -й группы выхо- сурсов, блоки 7.1 - 7.п,в сравнения, элемендов регистров 2.1-2,п распределения 10 товИ 8.1 - 8.птриггеры 6.1 - б,пуправленияиресурсов к первым входам сумматоров элементы И 10.1 - 10.п,18.1-18. а, Регистры 1.1 - 1 и запросов и регистрыБлоки 17.1-17.а элементов И предназ.1-2.п распределения ресурсов закрепленачены для подключения выходов регистра ны за процессами, то есть в регистр зап оЗ свободных ресурсов к вторым входам сум сов 1,( = 1, й, где и - число одновременноматоров 18 1-18 п 1. функционирующих процессов) заноситсяСумматоры 18.1 - 18.в выполняют опе- информация о запросах -го процессаоцесса, а врегистр 2, распределения ресурсов - инКоммутатор 19 коммутирует по входу формация о ресурсах, распределенных эторегистра 3 свободных ресурсов выходы сум му процессу.маторов 18 1 - 18.в и третью группу инфор- Выходы каждого регистра 1., 2, и 3мационных входов. разделены на группы выходов (полей) поЭлемент И 20 служит для формирования числу типов ресурсов, которыми располэгасигнала, по которому инициируется работа ет контролируемая система. В /-м полеустройства. 25 0=1,гп) каждого регистра запросов 1.и расЭлемент ИЛИ 21 вырабатывает сигна- пределения ресурсов 2. содержатся коды,лы, по которым осуществляется занесение отражающиечисло ресурсов)-го типа запрасов,информации в регистр 3 свободных ресур- шиваемых и распределенных -му процепроцессусоответственно. В -м поле регистра 3 своЭлемент ИЛИ 22 служит для формиро бодных ресурсов содержится код, равныйвания сигнала запуска генератора 14 такто- числу свободных ресурсов)-го типа в систевых импульсов, ме на момент контроля.Элемент ИЛИ 24 управляет подключе- Информация о запросах на ресурсы синием выходов регистра 3 свободных ресур- стемы с выходов регистров 1.1 - 1,п запросов к вторым входам сумматоров 18,1-18,щ 35 сов поступает на первые входы блоковчерез блоки 17.1 - 17.в элементов И, 7,1 - 7.п,в сравнения, на вторые входы котоЭлемент ИЛИ 25 формирует сигнал, по рых с выходов регистра 3 свободных ресуркоторому заносится информация в регистр сов поступает информация о числе3 свободных ресурсов с выходов суммато- свободных ресурсов в системе. Единичныйров 8.1-18.гп. 40 сигнал блока 7.Ц сравнения (=1, и;) = 1,и)Одновибратор 32 формирует сигнал за- вырабатывается в том случае, когда код, пописи информации в триггеры 5,1-5,п; 6.1 - ступающий на первый вход, меньше или раУвен коду, поступающему на второй вход.стройство работает следующим абра- Физически это значит, что -м процессомзом. 45 запрашивается ресурсов )-го типа не больВ исходном состоянии триггер 4 режи- ше, чем есть свободных ресурсов)-го типа вма и триггеры 6.1 - 6,п управления находятся системе.в нулевом состоянии, Когда на выходах всех блоков сравнео сигналу пуска, поступающему на ния -й группы (=1,п) установятся единичвход 6 пускаустройства,навыходеэлемен ные сигналы, на выходе элемента И 8,та 20 формируетсяимпульс,попереднему формируется единичный сигнал с выходафронту которого заносится информация об одновибратора 32, устанавливающий в нуимеющихся запросах на ресурсы системы в левое состояние триггер 5тупика и в едирегистры 1.1 - 1,п запросов с первой группы ничное состояние - триггер 6,1,информационных входов 27,1-27.п, о рас управления. Это значит, что -й- и процесс впределенных ресурсах - в регистры 2.1 - 2.п тупиковую ситуацию при текущем распре 291-29,п о вс третьей группы информационных входов делении не вовлечен. Вс е ресурсы, которы,и, о свободных на текущий момент ми он владеет, будут возвращены в систему.евремени ресурсах - в регистр 3 свободных Единичный сигнал с выхода триггера 6.р сурсов с второй группы информационных равления поступает на вторые входы -хуп 1702372элементов И первой 10. и второй 11. групп элементов И.В случае, если в регистре 2.1.распределения ресурсов содержится нулевая информация, -му процессу не распределен ни один из гп типов ресурсов, на выходе элемента ИЛИ 15. второй группы элементов ИЛИ формируется нулевой потенциал, который поступает на первый вход элемента И 10первой группы элементов И и запрещает прохождение через него единичного потенциала с выхода триггера 6управления, а также поступает на первый инверсный вход элемента И 11. второй группы элементов И, на третий инверсный вход которого поступает нулевой потенциал с выхода элемента ИЛИ 9. первой группы элементов ИЛИ, в результате чего на выходе элемента ,И 11. формируется единичный потенциал, поступающий на второй вход элемента ИЛИ 9., на выходе которого формируется единичный потенциал, поступающий на третий инверсный вход элемента И 11 в результате этого на его выходе формируется нулевой потенциал,Таким образом, на выходе элемента И 11, формируется единичный импульс, поступающий через элемент ИЛИ 9. на вход установки в "О" триггера 6, управления, и по заднему фронту обнуляет его,В том случае, когда в регистре 2. распределения ресурсов записана ненулевая информация, то есть -му процессу распределен хотя бы один ресурс любого типа, на выходе элемента ИЛИ 15, второй группы элементов ИЛИ формируется единичный потенциал, который поступает на первый вход элемента и 10, первой группы элементов И, и на его выходе формируется единичный сигнал, поступающий на второй инверсный вход элемента И 12 третьей группы, на второй вход элемента И 13, четвертой группы, на -й инверсный вход второго элемента И 23 и на -й вход элемента ИЛИ 22. На выходе последнего формируется единичный потенциал, поступающий на управляющий вход генератора 14 тактовых импульсов, который начинает вырабатывать последовательность тактовых импульсов, поступающих на первые входы элементов И 12.1 и 13.1 третьей и четвертой групп. Длительность тактового импульса такова, что позволяет осуществить формирование суммы на выходах сумматоров 18.1 - 18 л, занесение ее в регистр 3 свободных ресурсов, сравнение в блоках 7,1.1-7.пл сравнения и формирование соответствующих сигналов на выходах элементов И 10.1-10,п. Пауза между тактовыми импульсами равна сумме длительности тактового импульса и времени распространения его по цепи элементов И 12,1 - 12,(п) и 13.п, В случае, если на выходе элемента И 10. выставлен единичный потенциал (-й процесс в тупиковую ситуа цию не вовлечен), который поступает на второй инверсный вход элемента И 12, и запрещает прохождение через него тактовых импульсов, потенциал с выхода элемента И 10. поступает на второй вход элемента 10 И 13., разрешая прохождение через неготактовых импульсов.Тактовый импульс с выхода генератора14 через цепь элементов И 12.1 - 12 (-1) и 13, поступает на- е управляющие входы 15 коммутаторов 16.1-16 л, разрешая тем самым прохождение информации с выходов регистра 2, распределения ресурсов на первые входы сумматоров 18,1 - 18,в (в - число типов ресурсов в системе), а также 20 поступает на -й вход элемента ИЛИ 24, навыходе которого формируется единичный сигнал, поступающий на управляющие входы группы блоков элементов И 17,1 - 17.в и разрешающий прохождение информации с 25 выходов регистра 3 свободных ресурсов навторые входы сумматоров 18.1-18,е, на выходах которых формируется сумма свободных и распределенных -му процессу ресурсов, то есть моделируется освобожде ние ресурсов -м процессом.Кроме того, единичный импульс с выхо. да элемента И 13, поступает через элементИЛИ 9. на вход триггера 6. управления и по заднему фронту обнуляет его. Информа ция с выходов сумматоров 18,1 - 18 лп поступает на входы четвертого элемента ИЛИ 25, на выходе которого формируется единичный потенциал, поступающий на второй вход элемента ИЛИ 21, на выходе которого 40 формируется единичный потенциал, по которому происходит занесение в регистр 3 свободных ресурсов информации, сформированной на выходах сумматоров 18.1-18,а и поступающей на информационные входы 45 регистра 3 свободных ресурсов через коммутатор 19, В случае, если на выходе элемента И 10выставлен нулевой потенциал (-й процесс на данном этапе анализа не может получить запрашиваемые ресурсы), 50 который поступает на второй инверсныйвход элемента И 12. и разрешает прохождение через него тактовых импульсов, а также нулевой потенциал с выхода элемента И 10. поступает на второй вход элемента И 55 13., запрещая прохождение через него тактовых импульсов, Тактовый импульс с выхода генератора 14 через цепь элементов И 12.1-12. поступает на входы элементов И 12. (+1) и 13 (+1) и, если на выходе элемента И 10, (+1) выставлен единичный потенциал, 1702372 1010 20 25 30 45 том, что вданный момент устройство занято 50 55 происходит цикл обработки информации, аналогичный описанному выше для -го процесса, а если на выходе элемента И 10, (+1) выставлен нулевой потенциал, тактовый импульс поступает через элемент И 12. (+1) на входы элементов И 12,(+2) и 13. (+2) и т.д. В результате накопления суммы в регистре 3 свободных ресурсов (моделирование освобождения ресурсов незаблокированными процессами) происходит сравнение этой суммы с информацией с выходов регистров 1.1 - 1.п запросов и на выходах элементов И 10,1 - 10.п формируются соответствующие сигналы, то есть моделируется разблокировка процессов за счет удовлетворения их запросов на ресурсы. Порядок появления единичных потенциалов на выходах элементов И 10,1 - 10.п может быть любым, так как -й процесс может инициировать разблокирование любого другого процесса путем освобождения ресурсов, занятых им.Когда произойдет обнуление всех триггеров б,1 - 6,п управления в результате циклов обработки информации, описанных выше, на выходах элементов И 10,1 - 10.п сформируются нулевые потенциалы, которые поступают на инверсные входы элемента И 23, и на его выходе формируется единичный сигнал, обнуляющий триггер 4 режима. На этом анализ состояния системы устройством завершается.На второй группе информационных выходов 31.1-31 и выставляются индикаторы процесов, вовлеченных в тупик: номер разряда, на котором выставлен единичный потенциал, соответствует процессу, вовлеченному в тупиковую ситацию,На первой группе информационных выходов ЗО.Ц выставляется информация, по каким типам ресурсов процесс вовлечен в тупик: номер разряда в)-й группе (=1,в), на котором выставлен нулевой потенциал, соответствует номеру типа ресурсов, по которому -й (=1,п) процесс вовлечен в тупик,Нулевой потенциал на сигнальном выходе 32 устройства свидетельствует о том, что анализ состояния системы завершен, единичный потенциал свидетельствует о и осуществляет анализ состояния системы.Формула изобретения Устройство для контроля распределения ресурсов, содержащее и регистров запросов, и регистров распределения ресурсов, регистр свободных ресурсов, пять триггеров управления, триггер тупика, два блока сравнения, генератор тактовых импульсов, триггер режима, двадцать четыре элемента И, е блоков элементов И, восемь 35 40 элементов ИЛИ, коммутатор, причем Я-входы с первого по пятый триггеров управления соединены с выходами соответственно с первого по пятый элементов И, выход первого триггера тупика является первым выходом группы выходов процессов в тупике устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения оперативности контроля, в устройство дополнительно введены итриггеров управления, итриггеров тупика, пхвблоков сравнения, 5 п - 23 элементов И, (2 п - 4,элементов ИЛИ, в коммутаторов, а сумматоров, одновибратор, причем -й вход (=1,п), где и - число одновременно функционирующих процессов) группы входов запросов устройства соединен с информационным входом -го регистра запроса, )-й выход=1,е, где в - число типов разделяемых процессами ресурсов системы) которого соединен с первым входом блока Ц сравнения, выход которого соединен с Ц- выходом группы выходов ресурсов в тупике устройства и с +1)-м входом -го элемента И первой группы, выход которого соединен с входом установки в нуль -го триггера тупика, а выходы с шестого по и-й элементов И первой группы .соединены с Я-входами соответственно с шестого по и-й триггеров управления, прямой выход -го триггера тупика соединен -м выходом группы выходов процессов в тупике устройства и с первым входом -го элемента И первой группы, прямой выход -го триггера управления соединен с первыми прямыми входами -х элементов И второй и третьей групп, выход -го элемента И второй группы соединен с инверсными входом -го элемента И четвертой группы, с первым входом -го элемента И пятой группы, с -м входом первого элемента ИЛИ и с -м инверсным входом первого элемента И, выход -го элемента И третьей группы соединен с первым входом -го элемента ИЛИ первой группы, выход которого соединен с входом установки в "0 "-го триггера управления и с первым инверсным входом -го элемента И третьей группы, выход -го элемента И четвертой группы соединен с прямым входом (+1)-го элемента И четвертой группы и с вторым входом (+1)- го элемента И пятой группы, выход -го элемента И пятой группы соединен с вторым входом -го элемента ИЛИ первой группы, с -м входом второго элемента ИЛИ и с -ми разрешающими входами каждого коммутатора с первого по гп-й, -й вход группы входов распределения ресурсов устройства соединен с информационным входом -го регистра распределения ресурсов,)-й выход которого соединен с -м входом -го элемента ИЛИ второй группы элементов ИЛИ и с3-м информационным входом 3-го коммутатора, выход которого соединен с первым входом -го сумматора, выход 1-го элемента ИЛИ второй группы соединен с вторым входом 1-го элемента И второй группы и с вторым инверсным входом 1-го элемента И третьей группы, выход первого элемента ИЛИ соединен с управляющим входом гене ратора тактовых импульсов, выход которого соединен с прямым входом первого элемента И четвертой группы и с вторым , входом первого элемента И пятой группы, , вход пуска устройства соединен с первым входом второго элемента И, выход которого , соединен с первым входом третьего элемента ИЛИ, с выходом установки в единичноесостояние триггера режима, с входами уста, новки в единичное состояние всех тригге; ров тупика и с С-входами всех регистров ; запросов и регистров распределения ресур сов, инверсный выход триггера" режима со; единен с вторым входом второго элемента 1 И, прямойвыход триггера режима соединен , с выходом занятости устройства, с первыминверсным и вторым управляющим входами(в+1)-го коммутатора и с прямым входом первого элемента И, вход свободных ресурсов устройства соединен с первым информационным входом (а+1)-го коммутатора, 5 выход которого соединен с информационным входом регистра свободных ресурсов, выход третьего элемента ИЛИ соединен с С-входом регистра свободных ресурсов и входом одновибратора, выход которого сое О динен с (в+2)-ми входами элементов И первой группы, )-й выход регистра свободных ресурсов соединен с вторыми входами Ц блока сравнения и с информационным входом -го блока элементов И, выход которого 15 соединен с вторым блоком )-го сумматора,выходы сумматоров соединены с вторым информационным входом (в+1-го коммутатора, с входами четвертого элемента ИЛИ, выход которого соединен с вторым входом 20 третьего элемента ИЛИ и с (1+1)-м инверсным входОм первого элементу И, выход которого соединен с входом установки в нулевое состояние триггера режима, выход второго элемента ИЛИ соединен с разреша ющими входами всех блоков элементов И.1702372 Составитель Д.Ванюхиня Техред М.Моргентал Корректор М,Кучерявая едактор А.Мако изводственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 каз 4544 Тираж ВНИИПИ Государственного комитета по изоб 113035, Москва, Ж, РауПодписноеениям и открытиям при ГКНТ СССРая наб 4/5