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

СОЮЗ СОВЕТСКИХйащеРЕСПУБЛИК ааЯОио 1 2 А дэ 4 С 06 Р 11/00 ОПИСАНИЕ ИЗОБРЕТЕНИЯН АВТОРСНОМУ СВИДЕ 1 ВЪСТВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И 07 НРЬПЮ(54) УСТРОЙСТВО ДЛЯ КОНТРОЛЯ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ(57) Изобретение относится к области вычислительной техники и может ьытьиспользовано в современных высокопроизводительных вычислительных системах. Целью изобретения являетсяповышение быстродействия устройстваи расширение области его применения.Устройство содержит блоки регистров,блок синхронизации, распределителиимпульсов, мультиплексоры, схемусравнения, триггеры, группы блоковэлементов И, элементы И, ИЛИ, ИЛИНЕ, Устройство решает задачу распределения ресурсов между процессами ианализа тупиковых ситуаций. 1 ил.1 1Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных вычислительных системах.Цель изобретения - повышение быстродействия устройства и расширение области его применения.На чертеже приведена блок-схема предлагаемого устройства.Устройство для контроля распределения ресурсов содержит первый блок 1 регистров, второй 2.1-Ь+1)-й 20 блоки регистров группы 2 блоков регистров, блок 3 синхронизации, первый 4, второй 5 и третий 6 распредепители импульсов, первый управляю щий мультиплексор 7, второй 81- (11+1)-й 8, П управляющие мультиппексоры группы 8 управляющих мультиплексоров, первый 9 и второй 10 мультиплексоры информации, схему 11 сравнения, первый триггер 12 управления, триггер 13 совпадения, триггер 14 тупика, второй триггер 15 управления, триггер 16 анализа, четвертый 17 и пятый 18 триггеры управления, первую группу блоков 19 элементов И, в торую 20, 1- (И+1) -й 20 11 группу блоков элементов И, блок 21 элементов И, восьмой 22, третий 23, одиннадцатый 24, первый 25, второй 26,. шестой 27, четвертый 28, пятый 29, десятый 30, двенадцатый 31, девятый 32, тринадцатый 33 и седьмой 34 элементы И, пятый 35 и первый 36 элементы ИЛИ, элемент ИЛИ-НЕ 37, четвертый 38, второй 39 и третий 40 элементы ИЛИ, элемент НЕ 41, информационный вход 42 устройства, вход 43 "Пуск" устройства и выход 44 устройства.Блок, 1 регистров предназначен для приема, хранения и выдачи кодов номеров процессов, которые владеют ресурсами, а блок 2, регистров - для приема, хранения и выдачи кодов номеров процессов, которые запрашивают ресурсы.Блок 3 синхронизации предназначен для синхронизации работы элементов устройства.Распределитель 4 (6,5) импульсов предназначен для формирования на своих выходах последовательности из и 00,11) импульсов, распределенных во времени.Управляющий мультиплексор 7 предназначен для Формирования сигналов управления в зависимости от информации, которая поступает на его вход. 215112 2Управляющий мультиплексор 8,1предназначен для формирования сигнала управления в зависимости от инФормации, поступающей на его вход.Мультиплексор 9 предназначен дпяформирования на своих выходах одного из совокупности кодов, которыепоступают на его входы 45. 1-45 М.,в зависимости от группы управляющихсигналовМультиплексор 10 предназначендля формирования на выходной шинеодного из кодов, которые поступаютна его входы (46. 1-46.1 и, 47. 1-4 ЛМ,в зависимости от групп управляющихсигналов.Триггеры 12,17 и 18 управленияпредназначены для управления работой распределителей 4,6 и 5 импульсов соответственно.Триггер 13 совпадения предназначен для фиксации наличия номера анализируемого процесса, владеющегоресурсом среди множества процессов,запрашивающих ресурсы, а также дляФормирования сигнала разрешения выбора следующего кода номера процес-са, владеющего каким-либо ресурсом.Триггер 14 тупика предназначен ЗО для формирования сигнала тупика,Триггер 15 управления предназначен для формирования сигнала, указывающего на то, что в результатеанализа были удаления процессов,Триггер 16 анализа предназначендля Формирования сигнала окончанияанализа.Группа 19. 1-19,1 блоков элементовИ предназаначена для одновременнойпередачи информации о кодах номеров 40 процессов, владеющих ресурсами, свхода устройства в регистры блокарегистров.Группа 20, 1-20.Й блоков элементов.И предназначены для одновременной передачи информации о кодах номеров процессов, запрашивающих ресурсы, с входа устройства в регистрыблоков 2.1-2. И регистров.Элементы 21.1-21.Н предназначены о для формирования сигналов установкив ноль регистров блока 1 регистров.Элементы И 22,23,30,31,32,33 и 34предназначены для синхронизации работы элементов устройства.Элемент И 23 предназначен дляформирования сигнала установки в нулевое состояние триггера 15 управления.3 1252 4Элемент И 25 предназначен для фор- мации через группы блоков элементовмирования сигнала разрешения выбора И 19 и 20 в блокрегистров и групследующего кода номера процесса, вла- пу 2 блоков регистровЭтим же сиг. -деющего каким-либо ресурсом системы, налом управляющий мультиплексор 7Элемент И 26 предназначен для фор- и группа 8 управляющих мультиплексомирования сигнала установки в единич- ров закрыты, запрещая тем самым взаное состояние триггера 14 тупика. имную установку в нулевое состояниеЭлемент И 27 предназначен для регистров блока 1 и группы 2 блоковформирования сигнала, указывающего регистров соответственно,на то, что при анализе были удаления 0 По сигналу пуска (начало анализа)поступающему на вход 43 устройства,процессов.Элемент И 28 предназначен для фор- разрешается формирование управляющихмирования сигнала разрешения нового последовательностей импульсов на выцикла анализа. ходах блока 3 синхронизации, блокиЭлемент И 29 предназначен для фор руется прием информации в регистрымирования сигнала установки в единич- блока 1 и группы 2 бгр ппы локов регистровное состояние триггера 16 анализа. и разрешается перепись фрепись информации вЧЭлементы ИЛИ 35 и 36 предназначены мультиплексор 7 и группу 8 мульти-для формирования сигнала разрешения плексоров из соответствующих, блоковпервого и последующих выборок кодов регистров, Если 1-й.регистр блока 1номеров процессов, владеющих ресурса- содержит нулевой код, то на выходе .ми, а также установки в ноль распреде- -го разряда группы выходов мультилителей 5 и 6 имп льсов плексора 7 вырабатывается единичныйЭлемент ипи-НЕ 37 е37 предназначен сигнал, являющийся сигналом установдля формирования сигнала, управляю ки в ноль всех регистров блока 2.1щего работой элемента И 25. группы 2 блоков регистров, КромеЭлементы ИЛИ 38 и 40 предназначе- того, единичный сигнал формируетсяны для формирования сигналов разреше- на выходе мультиплекс а 8ор .1, дляния выбора кодов номеров процессов, которого все регистры соответствующего блока 2.3 группы 2 блоков реЭлемент ИЛИ 39 предназначен для гистров хранят нулевые коды.формирования сигнала установки в ноль Этот сигнал является сигналомраспределителя 6 импульсов и тригге- установки в нольноль 1-го регистра блока 1 регистров. Физическая сущностьЭлемент НЕ 41 предназначен для этих операций состоит в удалении израссмотрения процессов,синхронизации работы распределителя З 5 дальнейшего рассм4 импульсов, мультиплексора 9 и рас- которые заведомо могут быть завершепределителей 5 и 6 импульсов а так-. ны и вследствиеУ этого не приведутже мультиплексора 10.Гк тупику. Далее производится переходруппа 42 информационных входовк выявлению процессов, которые являпредназначена для приема кодов номе ются только вла ело владельцами некоторыхров процессов, владеющих ресурсами ресурсов, а сами дополнительно нисистемы и запрашивающих.их. какие другие ресурсы не запрашивают.Вход 43 пуска предназначен для по- Если некоторый процесс является тольдачи сигнала, осуществляющего нача- ко владельцем ресурса, то его номерло работы предлагаемого устройства. 45 не должен быть записан ни в одномиз регистров группы 2 блоков регисВыход 44 устройства предназначен ров. На проверке этого факта основыдля выдачи сигнала - признака тупи- вывается выявление процессов, котоковой ситуации в вычислительной сис-. рые только владеют ресурсами.теме,50 По сигналу начала анализа на вхоУстройство работает следующим де 43 устройства через элементобразом. ИЛИ 36 открывается элемент И 22, имВ исходном состоянии все тригге- пульс с первого выхода блока 3 синры находятся в нулевом состоянии.Входы начальной установки на фигу в единичное состоян еояние, сигнал с едирах условно не показаны. Единичный ничного выхода кода которого открываетсигнал с четвертого выхода блока 3 элемент И 23 Им пульс с третьего высинхронизации разрешает прием инфор- хода блока 3 синхронизации через от 1215112крытый элемент И 23 проходит на счетный вход распределителя 4 импульсов,сигнал с первого выхода которогоразрешает через мультиплексор 9 подключение выходов первого регистраблока 1 регистров к первой группевходов схемы 11 сравнения. По сигналус выхода элемента И 23 триггер 12устанавливается в нулевое состояниеи блокирует подачу импульсов на входраспределителя 4,Если код процесса в первом регистре блока 1 регистров оказался нулевым, то элемент И 25 вырабатываетсигнал, инициирующий переход к исследованию содержимого следующего регистра в блоке 1 регистров. В противном случае нулевой сигнал с выходаэлемента И 25 инвертируется элементом НЕ 41 и через элементы ИЛИ 38 и40 открывает элементы И 30 и 33 соответственно, Импульсом с второго выхода блока 3 синхронизации через открытый элемент И 30 триггер 17 уста 25навливается в единичное состояние иоткрывает элемент И 32. Импульсом стретьего выхода блока 3 синхронизации через открытый элемент И 33 триггер 18 устанавливается в единичноеЗОсостояние и открывает элемент И 34,Очередные импульсы с первого и второго выходов блока 3 синхронизациичерез открытые элементы И 32 и 34соответственно поступают-.на счетныевходы распределителей б и 5 импульсов. По сигналу с выхода элементаИ 34 триггер 18 устанавливается внулевое состояние и блокирует подачутактовых импульсов на вход распределителя 5 импульсов, На первых вы 40ходах распределителей 6 и 5 импульсов появляются сигналы, которые поступают на входы мультиплексора 10,обеспечивая подключение через элементы выходов первого регистра блока2. 1 группы 2 блоков регистров к второй группе входов схемы 11 сравнения.Если сравнения кодов не происходит,то далее работает распределитель 6.По каждому очередному импульсу первого блока 3 синхронизации на выходах распределителя последовательновырабатываются разнесенные во временисигналы, которые через вторую группууправляющих входов управляют работоймультиплексора 10, Мультиплексор 10осуществляет выбор содержимого очередного регистра блока 2,1 регистров запросов, Е сли в се запросы квыбранному ресурсу исчерпались, асравнения кодов не произошло, то на1+1) -м выходе распределителя6 импульсов вырабатывается сиг-.нал, инициирующий переход к анализузапросов очередного ресурса, которыйчерез элементы ИЛИ 39 и 40 открываетэлементы И 31 и 33. Очередным импульсом с третьего выхода блока 3 синхронизации через открытый элементИ 3 1 устанавливаются в ноль триггер17 и распределитель б импульсов, атакже через открытый элемент И 33триггер 18 устанавливается в единичное состояние и открывает элементИ 34, Очередной импульс с второго выхода блока 3 синхронизации черезоткрытый элемент И 34 поступает навход распределителя 5 импульсов, наочередном выходе которого формируется импульс, который через первуюгруппу управляющих входов поступаетна мультиплексор 10. Одновременно носигналу с выхода элемента И 34 триггер 18 устанавливается в нулевое состояние, а также через элементИЛИ 38 и через открытый импульсом свторого выхода блока 3 синхронизации элемент И 30 он поступает наединичный вход триггера 17, который устанавливается в единичное состояние и открывает элемент И 32,При поступлении импульсов с первого выхода блока 3 синхронизации возобновляет свою работу распределитель 6 импульсов, который совместно с распределителем 5 импульсовуправляет выборкой запросов уже кследующему ресурсу,Если во время последовательногосравнения с кодами из регистров группы 2 блоков регистров запросов происходит хотя бы одно совпадение,т,е, исследуемый процесс не тольковладеет ресурсами, но и запрашиваетих, то срабатывает триггер 13 иустанавливается в единичное состояние, По этому сигналу производитсявыбор содержимого очередного регистра блока 1 регистров, а также установка в ноль распределителей 5 и6 импульсов. Если же в результатеанализа всех просителей для выбранного владельца совпадений не произошло (исследуемый процесс не запрашивает ресурсы), т.е. триггер 13находится в нулевом состоянии и1215112присутствует сигнал с последне В противном случае триггер 14 выхода распределителя 5 импля 5 импульсов, устанавливается в единичное состоято срабатывает элемент И 27ент И 27, которыи ние и с выхода 44 выдается сигнал . станавливает т иггер р 15 в единичное обнаружения тупиковой ситуации в высостояние. О нд овременно сигналом с5числительной системе. выхода элемента И 27 открываетсяэлемент И 21 блока, соответствующий Ф ормула изобретения исследуемому процессу, и своим выходом подключается к первой гр ппеР Руппе 1 О устройство для контроля распредеуправляющих входов блока 1 регист- ления ресурсов, содержащее. первый и ров, устанавливая тем самым егиамым регистр, второй блоки регистров, первый и в котором хранится код исследуемого второй распределители импульсов, .процес"а, в нулевое состояние. Через первый и второй управляющие мульти- мультиплексор 7 осуществляется кор- е соры, перв и второй мультирекция содержимого соответствую егоующ го плексоры информации, схему сравнения, блока группы 2 блоков регистров. первый и второй триггеры управления,Аналогично описанному анализ оу ализ про- триггер совпадения, триггер тупика, должается до окончания исследования триггер анализа, первую и вторую содержимого последнего регистра бло- группы блоков ем20оков элементов И, блок злека 1 регистров. Сигнал с выхода рас- ментов И, семь элементов И, первый пределителя 4 импульсов поступает элемент ИЛИ, элемент ИЛИ-НЕ, причем на элементы И 28 и 29, Если в дан групп выходов е бгрупп выходов первого блока ре-ном цикле анализа были удаления про- гистров (где Ъ - число ресурсов в цы, то сигало с единичного вы системе) соединены с группами инхода триггера 15 открывается элемент формационных входов первого управ- И 28 сигнал с кокоторого устанавливает ляющего мультиплексора и первого в ноль распределитель 4 импульсов, мультиплексора информации, груп- через элемент ИЛИ 35 распределитель па выходов которого соединена с пер импульсов, через элементы ИПИ 35 вой группой входов схемы сравненияи группой инверсных входов первого пульсов, а также через элементы ИЛИ элемента И,1 т 1 групп выходов второго 35 и Зб открывает элемент И 22. Им- блока регистров (дока регистров (где щ - число едипульсом с первого выхода блока 3 син- ниц данного типа ресурса) соединехронизации триггер 12 устанавливает- ны с группами информационных входов ся в единичное состояние и ин и -яние и иниции- второго управляющего мультиплексора рует тем самым начало нового цикла и с первои по Ф - ю группами инчанализа. формационных входов второго мультиЕсли оказывается что в очто в очередном плексора информации, группа выходовцикле анализа удалений процессов, которого соединена с второй группой которые могут заве шитьс н т 40р т ся, не бьло, входов схемы сравнения, выход котото срабатывает элемент И 29, сигнал рой соединен с единичньщ входом с которого устанавливает триггер 16в единичное состояние. Сигнал окон- мационных входов блоков элементов чания анализа с выхода триггера 16 И первой и второй групп образуютинформационный вход устройства, груп" синхрониза ии. К омер ц и. Кроме того, сигнал пы выходов блоков элементов И первой с выхода триггера 16 является разре- и второй групп соединены соответ- шающим сигналом для элемента И 26. ственно с группами информационныхЕсли в результате анализа все входов первого и второго блоков репроцессы в системе могут быть реаль- гистров, группа выходов блока элено завершены, то все регистры блока ментов И соединена с первой группой 1 регистров устанавливаются вР У ливаются в ну- входов сброса первого блока регистлевое состояние. Сле ова еСл довательно. на ров, вход началвной установки кото- выходе управляющего мультиплексорасигнал отсутствует и элемент 26 55 равляющего мультравляющего мультиплексора, вход не срабатывает. Т игге 14риггер 14 остается сброса второго блока регистров соев нулевом состоянии, С выхо аи, С выхода 44 динен с первым выходом первого управ" устройства сигнал тупика не выдается ляющего мультипле ксора, второи выходч1 О которого соединен с первым входомвторого элемента И, вход пуска устройства соединен с первым входом первого элемента ИЛИ, нулевыми входамитриггера. тупика и триггера анализа,единичный выход которого соединен свторым входом второго элемента И,выход которого соединен с единичнымвходом триггера тупика, единичныйвыход которого является выходом устройства, единичный выход первоготриггера управления соединен с первымвходом третьего элемента И, выход которого соединен с нулевыми входами15первого триггера управления, тригге-.ра совпадения и счетным входом первого распределителя импульсов, группа И. выходов которого соединена сгруппой входов элемента И-НЕ, груп 20пой управляющих входов первого мультиплексора информации и первой группой входов блока элементов И,9+1)-й выход первого распределителя импульсов соединен с первыми входами четвертого и пятого элементовИ, а вход сброса - с выходом четвертого элемента И, выход пятого элемента И - с единичным входом триггераанализа, выход элемента И-НЕ - с инверсным входом первого элемента И,выход которого .соединен с вторымвходом первого элемента ИЛИ, нулевойвыход триггера совпадения соединенс первым входом шестого элемента И,выход которого соединен с единичным 35входом второго триггера управленияи второй группой входов блока элементов И, выход седьмого элемента Исоединен со счетным входом второгораспределителя импульсов, группа 40выходов которого соединена с первой группой управляющих входов второго мультиплексора информации, а(И+1)-й выход - с вторым входом шестого элемента И, единичный и нулевой 45выходы второго триггера управления соединены соответственно с вторыми входами четвертого и пятогоэлементов И, о т л и ч а ю щ е е с ятем, что, с целью повышения быстродействия и расширения области применения устройства, в него введенытретий - (И +1)-й блоки регистров;блок синхронизации, третий распределитель импульсов, третий - (И +1) -й 55управляющие мультиплексоры, четвертый и пятый триггеры управления, третья - (11+1)-ягруппа блоков элементов И, шесть элементов И, четыре элемента ИЛИ, элемент НЕ, причем М груйп выходов каждого из блоков регистров с третьего по (11+1)-й соединены соответственно с И+1)-й по.Ит 1 - ю группами информационных входов второго мультиплексора информации и с группами информационных входов соответствующих управляющихмультиплексоров с третьего по (И+1)-йвыходы которых соединены с группой входов начальной установки первого блока. регистров, первый выход блока синхронизации соединен с первыми входами восьмого и девятого элементов И, выход девятого элемента И соединен со счетным входом третьего распределителя импульсов, группа 1 т 1 выходов которого соединена с второй группой управляющих входов второго мультиплексора информации, п+1)-й выход - с первыми входами второго и третьего элементов ИЛИ, второй выход блока синхронизации - с первыми входами седьмого и десятого элементов И, выход которого соединен с единичным входом четвертого триггера управ ления, единичный выход которого соединен с вторым входом девятого эле 7мента И, третий выход блока синхронизации соединен с вторым входом третьего элемента И, первыми входамиодиннадцатого, двенадцатого и тринадцатого элементов И выход тринадцатого элемента И соединен с единичным входом пятого триггера управления, единичный выход которого соединен с вторым входом седьмого элементаИ, выход которого соединен с нулевым входом пятого триггера управления и первым входом четвертого элемента ИЛИ, четвертый выход блока синхронизации соединен с управляющими входами с первого по (И +1)-й управляющих мультиплексоров и вторыми входами блоков элементов И с первой по (И+1)-ю .групп, группы выходов с третьего по (11+1)-ю групп блоков элементов И соединены с группами информационных входов соответствующих блоков регистров с третьего по (И+1)-й, входы сброса которых соединены с третьего по (И+1)-й выходами первого управляющего мультиплексора, выход первого элемента И через элемент НЕ соединен с вторыми входами третьего и четвертого элементов ИЛИ, выход которого соединен с1215112 12 Составитель И.ХазоваТехред О.Неце Корр дакто ежнина яско 73 Подписнокомитета СССР Заказ 907/5 ВНИИПИ по д 113035, ТиражственногобретенийЖ, Ра о суд ам открытии ская наб., д, 4 ква,"Патент", г.ужг л.Проектная, 4 вторым входом десятого элемента И, первый выход группы выходов первого распределителя импульсов соединен с вторым входом одиннадцатого элемента И, выход которого соединен с нулевым входом второго триггера управления, первые группы входов с третьей по ф+1)-ю групп блоков элементов И соединены с информационным входом . устройства, единичный выход триггера совпадения соединен с первым входом пятого элемента ИЛИ, выход шестого элемента И - с вторым входом пятого элемента ИЛИ, выход которого соединен с третьим входом первого элемента ИЛИ, вторым входом второго элемента ИЛИ и входом сброса второго распределителя импульсов, выход второго элемента ИЛИ соединен с вторым выходом двенадцатого элемента И, выход которого соединен с нулевым входом четвертого триггера управления и входом сброса третьего распределителя импульсов, выход третьего элемента ИЛИ соединен с вторым входом тринадцатого элемента И, выход четвер 1 п того элемента И - с третьим входомпятого элемента ИЛИ, выход триггера анализа соединен с входом "Стоп" блока синхронизации, входПуск" которого соединен с входом пуска устройства, выход первого элемента ИЛИ соединен с вторым входом восьмого элемента И, выходкоторого соединен с единичным входом первого триггера управления.