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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик но972512 (61) Дополнительное к авт. свид-ву(22) Заявлено1Ь0581 (2! ) 3287649/18-24 с присоединением заявки М(23) ПриоритетР1 М К з

G 06 F 9/46

Государственный комнтет

СССР ло делам изобретений н открытнй

Опубликовано 071182. Бюллетень М 41 (33} УДК681. 325 (088.8) Дата опубликования описания 071132 (72) Автор.. изобретения

А.С. Ильин (71) Заявитель (54) УСТРОЙСТВО ДНЯ ОБСЛУЖИВАНИЯ ЗАПРОСОВ

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

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

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

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

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

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

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

25 (i )...ï) группы соединены с соответствующими входами i-ro элемента

ИЛИ первой Группы, выходы всех элЕ ментов И проверки соединены с соответствующими входами элемента ИЛИ, 30 выход которого является выходом

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

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

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

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

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

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

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

Если решается зацача предотвращения тупиков, то A(i, !)=1 при

lФ) в том случае, когда один из процессов имеет ресурс с номером i u может потребовать себе в дальнейшем дополнительно ресурс с номером J„ а также и в том случае, когда обслуживаемый в данный момент процесс 60 требует себе ресурс с номером i u в дальнейшем может потребовать себе дополните чьно ресурс с йомером j.

Диагональный элемент матрицы смежности A(i, i)=1 в том случае, когда 65 ресурс с номером i уже принадлежит какому-либо процессу.

Каждый из входов 8 соответствует одному из распределяемых ресурсоводной из вершин ориентированного графа. Возбуждение одного из входов

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

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

После того, как цикл (тупик) обнаруживается, все выходы элементов

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

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

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

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

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

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

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

Устройство для обслуживания зап: росов, содержащее регистр, и групп элементов И (и — количество распределяемых ресурсов), две группы элеМентов ИЛИ, и. элементов И обратной связи, и элементов И проверки и элемент ЙЛИ, разрядные выходы регистра соединены с первыми входами элементов И соответствующих групп, выходы элементов И i-й (i l,..., n) группы соединены с соответствующими входами i-го элемента ИЛИ первой группы, выходы всех элементов И проверки сое-)© динены с соответствуют.ми входами элемента ИЛИ, выход которого является выходом устройства, выходы элементов И обратной связи соединены с первыми входами соответствующих элементов ИЛИ второй группы, о тл и ч а ю щ е е с я тем, что, с целью сокращения оборудования, выходы элементов ИЛИ первой группы соединены с первыми входами соответствующих элементов И обратной связи, вторые входы и выходы которых соединены соответственно с управляющим входом устройства и с первыми входа ми соответствующих элементов И проверки, вторые. входы которых соединены с вторыми входами соответствующих элементов ИЛИ второй группы и с соответствующими входами группы устройства, выход го элемента ИЛИ второй группы соединен с вторыми входами i-x элементов И всех групп.

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

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

М. 724128, кл. С 06 F 9/46, 1979.

2. Rootenberj Jacob, Waxman Jerry, А Hardware Approach to Deadlock

Detection In Соври ter Systems International Journal Systems Science, 1979, vol. 10 9 5, рр 477-483 (про тотип).

9 72512

Составитель Г. Пономарева

Редактор В. Иванова Техред М.Гергель

Корректор В. Бутяга

Подписное

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

Заказ 8518/41 Тираж 731

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

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