Устройство для обслуживания запросов

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспублик оо 972512(61) Дополнительное к авт. свид-ву(22) Заявлено 1 Ь 0581 (2 ) 3287649/18-24с присоединением заявки М(23) ПриоритетР 1 М К з 6 Об Г 9/46 Государственный комитет СССР но делам изобретений н открытийДата опубликования описания 071132(54) УСТРОЙСТВО ДЛЯ ОБСЛУЖИВАНИЯ ЗАПРОСОВ Изобретение относится к вычислительной технике и может быть использовано в систамах обработки информации в составе технических средств цифровых вычислительных машин в час- ти моделирования тупиковых ситуаций, возникающих при обслуживании запросов на системные ресурсы.Известно устройство для обслужи-вания запросов, содержащее блок приоритета, триггер, счетчик, дешифратор, регистр, генератор, элементы И, ИЛИ и НЕ 11.Недостатком этого устройства является возможность управления очередностью обращения абонентов только к одному общему ресурсу, а при наличии нескольких таких устройств (для каждого ресурса) не учитываются возможность возникновения тупиковых . .ситуаций.Наиболее близким по назначению и технической сущности к изобретению является устройство для обслуживания запросов, содержащее три регистра, элементы И, ИЛИ, НЕ и триггер23.Недостатком известного устройства является высокий уровень аппа- ратурных затрат, обусловленный применением в составе устройства схемы перемножения матриц логических переменных для последовательного вычис-еления К-ых степеней матрицы смежносЦель изобретения - сокращениеоборудования за счет того, что вустройстве вместо схемы перемноженияматриц логических переменных используется схема умножения матрицы логических переменных на столбец логических переменных, которая выполняетв п раз меньше логических операцийи, следовательно, требует меньшихаппаратурных затрат,Поставленная цель достигаетсятем, что в.устройстве, содержащемрегистр, и групп элементов И (и - количество распределяемых ресурсов),две группы элементов ИЛИ, и элементов И обратной связи, и элементов Ипроверки. и элемент ИЛИ, разрядныевыходы регистра соединены с первымивходами элементов И соответствующихгрупп, выходы элементов И 1-ой25 ( 1 п) группы соединены с соответствующими входами -го элементаИЛИ первой Группы, выходы всех элЕментов И проверки соединены с соответствующими входами элемента ИЛИ,30 выход которого является выходомУстройства, выходы элементов И обратной связи соединены с первыми входами соответствующих элементов ИЛИ второй группы,-выходы элементов ИЛИ первой группы соединены с первыми входами соответствующих элементов И 5обратной связи, вторые входы и выходы которых соединены соответственнос управляющим входом устройства ис первыми входами соответствующихэлементов И проверки, вторые входы 1 Окоторых соединены с вторыми входамисоответствующих элементов ИЛИ второйгруппы и с соответствующими управляющими входами группы устройства, выход 1-го элемента ИЛИ второй группысоединен с вторыми входами 1-ых элементов И всех групп.На чертеже представлена блок-схема устройства для случая и:=4, кото-,рое содержит регистр 1, элементы И 2группы, элементы ЛИ 3 первой группы, элементы ИЛИ 4 второй группы,элементы И 5 обратной связи, элементы И б проверки, элемент ИЛЙ 7,группу управляющих входов 8, управляющий вход 9.Устройство работает следующимобразом.Предлагаемое устройство так же,как и известное позволяет обнаружитьтупиковые ситуации, возникающие при ЗОраспределении системных ресурсов.Кроме того, оно само является ресурсом в том смысле, что каждый из процессов (абонентов) должен в порядкеочередности (или иной дисциплины обслуживания) получить данное устройство, с помощью которого он получаетответ на запрос о состоянии другихтребуемых ресурсов: могут быть даныобслуживаемому процессу (абоненту) 4 Оили нет.Первоначально в регистр 1 записывается матрица смежности А. Трактов- .ка значений ее элементов зависит отрешаемой задачи. 45Если решается задача обнаружениятупиков, сформулированная в ) 2,то А (1, 3)=1 при 1 Ф) в том и только в том случае, когда один из процессов имеет ресурс с номером 1 итребует себе дополнительно ресурсс номером 1, причем А (1, 1)=О. Если решается зацача предотвращения тупиков, то А(1, =1 при 1 Ф в том случае, когда один из процессов имеет ресурс с номероми может потребовать себе в дальнейшем дополнительно ресурс с номером ), а также и в том случае, когда обслуживаемый в данный момент процесс бО требует себе ресурс с номером 1 и в дальнейшем может потребовать себе дополнительно ресурс с номером ). Диагональный элемент матрицы смежности А(1, 1)=1 в том случае, когда б 5 ресурс с номеромУже принадлежит какому-либо процессУКаждый из входов 8 соответствует одному из распределяемых ресурсов- одной из вершин ориентированного графа, Возбуждение одного из входов 8 возбуждает также и вертикальную линию, являющуюся входом соответствующего им элемента ИЛИ 4. Этот сигнал с помощью элементов И 2 выделяет из регистра. 1 соответствующий столбец матрицы смежности, так что сигнал на выходе элемента И 2 свидетельствует о том, что в ориентированном графе к данной вершине существует дуга от исходной вершины.Элементы ИЛИ 3 суммируют эти сигналы для данной вершины по всем исходным вершинам. Далее обратной связью через элементы И 5 суммированные сигналы передаются на входы элементов ИЛИ 4, как если бы эти сигналы были входными. Таким образом, .сигналы на выходах элементов И 5 оп,ределяют все вершины, к которым отхотя бы одной из исходных вершин существует хотя бы один путь. С помощью элементов И б, ИЛИ 7 осуществляется проверка совпадения этих вершин с хотя бы одной из исходных вершин, т.е. проверяется наличие цикла (тупика).После того, как цикл (тупик) обнаруживается, все выходы элементов И 5, соответствующие вершинам, состоящим в цикле, остаются возбужденными независимо от сигналов на входах 8, но при наличии единичного сигнала на входе 9, разрешающего обрат . ную связь. Это позволяет анализировать обнаруженный тупик с цельюего устранения, т.е. получаемаятаким образом информация на выходахэлементов И 5, ИЛИ 4 коикретно указывает на те ресурсы, среди которыхдолжно быть произведено перераспределение.Приведение устройства в исходноесостояние осуществляется отключением обратной связи, т,е. обнулениемвхода 9.Для случая, когда решается задача обнаружения тупиков, входы 8 возбуждаются поочередно,Для случая, когда решается задача предотвращения тупиков, сигналына входах 8 имеют смысл векторазапроса: возбуждаются одновременноте входы 8, которым соответствуюттребуемые ресурсы. Если при этом навыходе элемента ИЛИ 7 появляетсяположительный сигнал, то это означает отказ обслуживаемому процессу наего запрос либо потому, что хотя быодин из требуемых ресурсов занят,либо иначе возможен тупик,В предлагаемом техническом решении по сравнению с известным сокрэщение аппаратурных затрат имеет место для каждого типа используемых элементов, причем для известного аппаратурные затраты оцениваются как п, а для предлагаемого решениякак и . Этот эффект обусловлен тем, 5 что вместо схемы перемножения матриц логических переменных применяется схема умножения матрицы логических переменных на столбец логических переменных, полученная соединением 10 выходов элементов ИЛИ 4 с входами элементов И 2,Сокращение аппаратурных затрат произведено без ущерба для быстродействия устройства. 15 Формула изобретенияУстройство для обслуживания запросов, содержащее регистр, и групп элементов И (п - количество распределяемых ресурсов), две группы элеМентов ИЛИ, и элементов И обратной связи, и элементов И проверки и элемент ЙЛИ, разрядные выходы регистра соединены с первыми входами элементов И соответствующих групп, выходы элементов И 1-й (1 1 и) группы соединены с соответствующими входами 1-го элемента ИЛИ первой группы, выходы всех элементов И проверки сое-Ж динены с соответствуюьу.ми входамиэлемента ИЛИ, выход которого является выходом устройства, выходы элементов И обратной связи соединены спервыми входамисоответствующихэлементов ИЛИ второй группы, о тл и ч а ю щ е е с я тем, что, сцелью сокращения оборудования, выходы элементов ИЛИ первой группы соединены с первыми входами соответствующих элементов И обратной связи,вторые входы и выходы которых соединены соответственно с управляющимвходом устройства и с первыми входами соответствующих элементов И проверки, вторые. входы которых соединеныс вторыми входами соответствующих элементов ИЛИ второй группы и с соответствующими входами группы устройства,выход 1 го элемента ИЛИ второй группы соединен с вторыми входами 1-хэлементов И всех групп.Источники информации,принятые во внимание при экспертизе1.,Авторское свидетельство СССРМ. 724128, кл, С 06 Г 9/46, 1979,2, йоофепЬег 9 .1 асоЬ, Иахаап .1 еггу,А Нагдиаге АрргоасЬ о Оеад 1 осМОеСесй 1 оп 1 п Соарцйег 5 узйееа, ийегпай 1 опа 1 .1 оцгпа 1 уьйеав 5 с 1 епсе,1979, чо 1, 10 9 5, рр 477-483 (прототип).972512 Составитель Г. ПономаревРедактор В, Иванова Техред М.Гергель Корректор В. Бут писное каз нал ППП "Патент";, г. Ужгород, ул. Проектная,18/41 Тираж 731 ВНИИПИ Государственного по делам изобретений 113035 р Москвар Ж 35 у Раомитета СССР открытий ская наб., д 4/