Устройство для обслуживания запросов Советский патент 1982 года по МПК G06F9/455 G06F9/50 

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

Известно устройство для обслуживания запросов, содержащее блок приоритета, триггер, счетчик, дешифратор, регистр, генератор, элементы И, ИЛИ и НЕ .

Недостатком этого устройства является возможность управления очередностью обращения абонентов только к одному общему ресурсу, а при наличии нескольких таких устройств (для кс1ждоГо ресурса) не учитываются возможность возникновения тупиковых .ситуаций. .

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

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

перемножения матриц логических переменных для последовательного вычис- ления К-ых степеней матрицы смежности.

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

Поставленная достигается тем, что в.устройстве, содержащем регистр, п групп элементов И (п - количество распределяемых ресурсов), две группы элементов ИЛИ, п элемен20тов И обратной связи, п элементов И пррверки. и элемент ИЛИ, разрядные выходы регистра соединены с первыми входами, элементов .И соответствующих групп, выходы элементов И 1-ой (i 1. ..п) группы соединены с соотвeтcтвyющи в входами i-ro элемента ИЛИ первой группы, выходы всех элементов И проверки соединены с соот ветствующими входами элемента ИЛИ, выход которого являетря выходом

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

На чертеже представлена блок-схема устройства для случая п 4, кото-: рое содержит регистр 1, элементы И 2 .группы, элементы ИЛИ 3 первой группы, элементы ИЛИ 4 второй группы, элементы И 5 обратной связи, элементы И 6 проверки, элемент ИЛИ 7, группу управляю1дих входов 8, управляющий вход 9.

Устройство работает следующим образом.

Предлагаемое устройство так же, как и известное позволяет обнаружить тупиковые ситуации, возникающие при р.аспределении системных ресурсов. Кроме того,, оно само является ресурсом в том смысле, что каждый из процессов (абонентов) должен в порядке очередности (или иной дисциплины обслуживания) получить данное устройство, с помощью которого он получает ответ на запрос о состоянии других требуемых ресурсов: могут быть даны обслуживаемому процессу (абоненту) или нет.

Первоначально в регистр 1 записывается матрица смежности А. Трактовка значений ее элементов зависит от решаемой задачи.

Если решается задача обнаружения тупиков, сформулированная в 2 , . то А (i , j ) 1 при i j в том и только в том случае, когда один из процессов имеет ресурс с номером i и требует себе дополнительно ресурс с номером j, причем А (i, i)0,

Если решается за,цача предотвращения тупиков, то A(i, j)l при в том случае, когда один из процессов имеет ресурс с номером i и может потребовать себе в дальнейшем дополнительно ресурс с номером j, а также и в том случае, когда обслуживаемый в данный Момент процесс требует себе ресурс с номером i и в дальнейшем может потребовать севе дополнительно ресурс с Номером j . Диагональный элемент матрицы смежности A(i, 1)1 в том случае, когда

ресурс с номером i уже принадлежит какому-либо процессу.

Каждый из входов 8 соответствует одному из распределяемых ресурсов одной из вершин ориентированного графа. Возбуждение одного из входов 8 возбуждает также и вертикальную линию, являющуюся входом соответствующего им элемента ИЛИ 4, Этот сигнал с помощью элементов И 2 выделяет из регистра. 1 соответствующий столбец матрицы смежности, так что сигнал на выходе элемента И 2 свидетельствует о том, что в ориентированном графе к данной вершине существует дуга от исходной вершины.

Элементы ИЛИ 3 сумлшруют эти сигналы для данной вершины по всем исходным вершинам. Дашее обратной связью через элементы И 5 суммирован-Q ные сигналы передаются на входы

элементов ИЛИ 4, как если бы эти сигналы -были входными. Таким образом, сигналы на выходах элементов И 5 оп|ределяют все вершины, к которым от хотя бы одной из исходных вершин существует хотя бы один путь. С помощью элементов И б, ИЛИ 7 осуществляется проверка совпадения этих вершин с хотя бы одной из исходных вершин, т.е. проверяется наличие цикла

0 (тупика).

После того, как цикл (тупик) обнаруживается, все выходы элементов И 5, соответствующие вершинам, состоящим в цикле, остаются возбужденными независимо от сигналов на входах 8, но при наличии единичного сиг нала на входе 9, разрешающего обрат-; ную связь. Это позволяет анализи ровать обнаруженный тупик с целью

Q его устранения, т.е. получаемая

таким образом информаци-я на выходах Элементов И 5, ИЛИ 4 конкретно указывает на те ресурсы, среди которых должно быть произведено перераспределение.

. Приведение устройства в исходное состояние осуществляется отключением обратной связи, т.е. обнулением входа 9.

Для случая, когда решается задача обнаружения тупиков, входы 8 возбуждаются поочередно.

Для случая, когда решается задача предотвращения тупиков, сигналы на входах 8 имеют смысл вектора

5 запроса: возбуждаются одновременно те входы 8, которым соответствуют требуемые ресурсы. Если при этом на выходе элемента ИЛИ 7 появляется положич ельный сигнал, то это означает отказ обслуживаемому процессу на его запрос либо потому, что хотя бы один из требуемых ресурсов занят, либо иначе возможен тупик.

В предлагаемом техническом реше5 НИИ по сравнению с известным сокращение аппаратурных затрат имеет место для каждого типА используемых элементов, причем для известного аппаратурные затраты оцениваются как п, а для предлагаемого решения как п. Этот эффект обусловлен тем, что вместо схемы перемножения матриц логических переменных применяется схема умножения матрицы логических переменных на столбец логических переменных, полученная соединением выходов элементов ИЛИ 4 с входами , элементов И 2.

Сокращение аппаратурных затрат произведено без ушерба для быстродействия устройства.

Формула изобретения

Устройство для обслуживания запросов, содержащее регистр, п групп элементов И {п - количество распрёд еляемых ресурсов) , две группы элеbteHTOB ИЛИ, п элементов И обратной связи, п элементов И проверки и элемент ИЛИ, разрядные выходы регистра соединены с первыми входами элементов И соответствующих групп, выходы элементов И Г-й (,..., п) группы соединены с соответствУкадими входами i-ro элемента ИЛИ первой группы, выходы всех элементов И проверки со

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

Источники информации, принятые во внимание при экспертизе

1.Авторское свидетельство СССР №.724128, кл. F 9/46, 1979.

2.Rootenberg Jacob, Waxman Jerry, A Hardware Approach to Deadlock Detection In Computer Systems, International Journal Systems Science, 1979, vol. 10 5, pp 477-483 (nporoTHn).

ff f ff U

Ш

« и

E

у s s U

ЛГТ1ГГ1Г7

-tl

гД1