Устройство для выбора по приоритету

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в многопроцессорных вычислительных системах для разрешения конфликтов при одновременно обращении нескольких процессеров к общей памяти. Цель изобретения - расширение области применения а счет введения дополнительной дисциплины обслуживания запросов типа кольцевого изменения кодов приоритетов источников запросов. Цель изобретения достигается за счет введения блока формирования кода йриоритета, группы блоков элементов ИЛИ, двух групп элементов И, элемента ИЛИ и элемента НЕ. При этом обслуженному в данном цикле источнику присваивается наибольший номер (младший приоритет), номера источников запросов, для которых они больше номера обслуженного, уменьшаются на единицу. Источник запроса с меньшим номером имеет больший приоритет . 1 з.п.ф-лы, 4 ил. а $ (Л

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

SSi)S О 06 F 9/46

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОЕРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4655555/24 (22) 28.02.89 (46) 07,01.91. Бюгг. Ф 1 (72) Г.С.Тимофеев, М.В.Визенько, А.И,Поясков и В.В.Белянова (53) 681 ° 325(088.8) (56) Авторское свидетельство СССР

Р 920702, кл. G 06 F 7/04> 1980.

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

Ф 1024921, кл. G 06 F 9/46, 1981. (54) УСТРОЙСТВО ДЛЯ ВЫБОРА ПО ПРИОРИТЕТУ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в многопроцессорных вычислительных системах для разрешения конфликтов при одновременно обращении нескольких процессоИзобретение относится к автоматике и вычислительной технике и может быть использовано в миогоцроцессорных вычислительных системах для разрешения конфлихтов при одновременном обраще-.. нии нескольких процессоров к общей памяти.

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

На фиг.1 представлена структурная схема устройства для выбора по приоритету; на фиг.2 — структурная схема блока формирования кода приоритета; на фиг.3 - структурная схема блоков опроса: на фиг.4 — структурная схема блока анализа, ÄÄSUÄÄ 1619274 A 1

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

При этом обслуженному в данном цикле источнику присваивается наибольший номер (младший приоритет), номера источников запросов, для которых они больше номера обслуженного, уменьшаются на единицу. Источник запроса с меньшим номером имеет больший приоритет. 1 з.п.ф-лы, 4 ил, Устройство содержит матрицу бло" ков 1 опроса, группу блоков 2 анализа, группу элементов ИЛИ 3, группу триггеров 4, группу счетчиков 5, группу регистров 6,элемент HE 7, блок 8 " формирования кода приоритета, группу блоков элементов И 9, группу блоков элементов ИЛИ 10, группу блоков эле- Ю ментов И 11, элемент ИЛИ 12, входы 13 запроса устройства, вход 14 вы- 4 бора дисциплины обслуживания устрой ства, тактовый вход 15 устройства.

Глок 8 формирования кода приоритета содержит группу блоков элемен-,Ь тов И 16, группу счетчиков 17, груп- а, пу дешифраторов 18, группу блоков элементов И !9, группу "элементов

ИЛИ 20, группу элементов ИЛИ 21, группу блоков элементов И 22 и группу элементов ИЛИ 23.

1619274

Блок 1 опроса содержит регистр 24, элемент И-ИЛИ 25, элемент ИЛИ 26, элемент И 27.

Блок 2 анализа. содержит элементы НЕ 28 и элемент И 29.. Элементы 26

5 и 27 задействованы только в блоках 1 последнего столбца матрицы.

Устройство позволяет выделять код приоритета процессора в соответ" ствии с минимальным числом обращений процессоров (минимальным значением, записанным на счетчиках 5) при отсутствии сигнала на входе 14 устройства или в соответствии с кольцевым изменением приоритета при наличии сигнала на входе 14 устройства.

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

Перед началом работы все блоки устанавливаются в исходное состояние: регистры 24 блоков 1 опроса и счетчики 5 — в нулевое состояние, триггеры 4 — в единичное состояние, в регистры 6 записывается код номера ис.5 точника запроса (процессора), в счетчики 17 блока 8 формирования кода приоритета. также записывается код номера источника запроса. В процессе работы устройства содержимое счетчиков 17 блока 8 формирования кода приоритета изменяется в соответствии с алгоритмом кольцевого изменения приоритета по следующему правилу. B счетчик 17, соответствующий обслуженному процессору, записывается максимальный код, а содержимое других счетчиков 17, значения которых на момент обслуживания больше значения счетчика 17 обслуженного процессора, уменьшается на единицу. Содержимое счетчиков 17, 4О для которых это. условие не выполняется остается без изменения. При этом начало цикла выделения номера очередного процессора начинается только после окончания предыдущего

45 цикла, а регистры 24 блоков 1 опроса устанавливаются в нулевое состояние после окончания каждого цикла выделения номера процессора. Через входы 13 в устройство поступают импульсы за- 0

l проса от каждого процессора, которые устанавливают в нулевое состояние соответствующий триггер 4 и одновременно поступают на вход соответствующих счетчиков 5 и суммируются с их содержимым, Коды счетчиков 5 используются при выделении кода номера процессора в соответствии с минимальным числом обращений (отсутствие сигнала на входе 14). При кольцевом изменении приоритета (наличие сигналов на входе 14) вместо соответствующих разрядов кодов счетчиков 5 на вход блоков 1 опроса поступают коды нулей. Двоичный код номера процессора, которому разрешено обратиться в память, выдается с соответствующего регистра 6 через блоки элементов И 11 и блок элементов ИЛИ 3 на выходы устройства, Рассмотрим работу устройства при наличии сигнала на входе 14. При поступлении импульсов запроса на входы 13 соответствующий триггер 4 устанавливается в нулевое состояние. Прямые коды номеров источников запросов с счетчиков 17 блока 8 формирования кода приоритета поступают на соответствующие дешифраторы 18. Обратные коды со счетчиков 17 поступают на выход блока 8 формирования кода приоритета и далее на входы блоков элементов И 9. С выходов блоков элементов И 9 коды через блоки элементов

ИЛИ 10 поступают на входы соответствующих блокоч 1 опроса, причем в разрядах, соответствующих разрядам счетчиков 5,,записаны коды нуля, На первый разряд блоков 1 опроса поступает инверсное значение с соответствующего триггера 4. Таким образом, на вход блока 1 опроса, в общем случае, поступят различные числа в обратном коде. Каждое число под действием тактового сигнала, поступающего на вход 15 проходит через свою группу блоков 1 опроса, На входы блока 2 анализа. Если одноименные разряды всех чисел равны нулю или единице, то все числа передаются без изменения в регистры 24 соответствующих блоков 1 опроса для дальнейшего анализа. Если же для одних чисел разряды равны единице, а для других — равны нулю, то последние в дальнейшем не рассматриваются и в регистры 24 блоков 1 опроса соответствующие группы не записываются.

Выделенное на последнем шаге число записывается в регистр 24 последнего блока 1 опроса последнего столбца и через элементы ИЛИ 26,И 27 выдается управляющий сигнал. Этот сигнал поетупает на соответствующий блок эле-! ментов И 11, по которому код номера пропессора, которому разрешено обра1619274

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

Кроме того, управляющий сигнал с

5 выхода соответствующего блока 1 опроса поступает на установку в единичное состояние соответствующего триггера 4 и на соответствующий управляющий вход блока 8 формирования кода .приоритета для изменения кодов прио ритетов, записанных в счетчиках 17 блока 8.

Изменение кода приоритета осуществляется следующим образом.

В счетчик 17 через соответствующий блок элементов И по соответствующему управляющему сигналу на входе блока 8 записывается код с выхода регистра 6, т.е. код номера старшего процессора. Одновременно по соответствующему управляющему сигналу, поступающему на входы блоков 19 элементов И определяется текущий номер обслуженного процессора. Для этого прямые коды со счетчиков 17 поступают на входы соответствующих дешифраторов 18. Сигнал с выхода дешифратора 18, соответствующего текущему номеру процессора, поступает на входы элементов И соответствующих блоков элементов И 19,22. С выхода блока 19 код поступает на входы элементов ИЛИ 20 и далее на входы элементов ИЛИ группы 21, С выходов группы элементов ИЛИ 21 полученный код поступает на входы блоков элементов

И 22. На первые входы элементов И поступают сигналы с выходов соответствующих дешифраторов 18 в блоке 8 формирования кода приоритета. Если в каком-либо блоке 22 на входах окажутся две единицы, то с выхода И выдается код единицы. Таким образом, с выходов элементов И каждого блока 22 код единицы выдается только с выхода одного элемента И, в противном случае с выходов всех элементов И соответствующего блока 22 выдаются коды нуля. Коды с выходов блоков 22 поступают на входы соответствующих элементов ИЛИ 23. Если на одном из входов элемента ИЛИ присутствует единица, то с выхода этого элемента поступает код единицы на вычитающий вход соответствующего счетчика 17. В результате код, записанный на счетчике 17 блока 8, уменьшается на единицу.

Таким образом, после окончания цикла .работы в счетчике 17 будет записан максимальный код приоритета, в счетчиках 17д коды которых были больt

1 ше кода в указанном счетчике, будут получены ко ы единиц меньше соответствующих предшествующих кодов. В остальных счетчиках значения кодов не изменяются. Полученные текущие значения кодов приоритетов в обратном коде с выходов счетчиков 17 поступают на соответствующие выходы блока 8 формирования кода приоритета.

При поступлении на входы 13 следующего импульса запроса или наличии единицы в триггерах 4 работа устройства повторяется. При отсутствии сигнала на входе 14 элемента НЕ 7 открываются первый и последний блоки элементов И 9. Коды приоритета с выходов счетчиков 5 и регистров 6 поступают через эти блоки и на входы блоков 1 опроса первого столбца. Далее устройство работает аналогично описанному. Причем коды приоритетов с выходов блока 8 формирования кода приоритета на входых первых блоков I опроса не поступают.

При отсутствии необслуженных запросов триггеры 4 находятся в единич". ном состоянии. Нулевые сигналы с инверсных выходов триггеров 4 поступают на входы элемента ИЛИ 12, а с его выхода через четвертый управляющий вход блоков 1 опроса последнего столбца на первый вход элемента И 27 и закрывает его.

После поступления на один из выходов 13 устройства импульса запроса соответствующий триггер 4 устанавливается в нулевое состояние, элемент

И 27 блоков 1 опроса открывается, а устройство будет осуществлять выделение номера процессора в соответствии с описанным алгоритмом.

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

1. Устройство для выбора по приоритету, содержащее матрицу п-блоков .опроса, группу блоков анализа, группу триггеров, группу счетчиков, группу регистров, группу блоков элементов ИЛИ, причем группы выходов блоков опроса 1-ro {1 = 1,...,m — 1, m — число разрядов кода приоритета) соединены с группами входов блоков опроса,(1 + 1)-, го столбца матрицы, первый информационный вход i ro (i l,,....,rr,, и, — число запросов) блока опроса первого столбца матрицы соединен с выходом i-ro триггера .группы, с первым управляющим входом i-ro блока опроса и с соответствующиминформацион-, ным входом первого блока анализа группы, первые управляющие входы блоков 1О опроса j-ro (j = 2,...ш} столбца матрицы соединены с j-м информационным входом группы информационных входов. своего блока опроса и с соответствующим информационным входом 1-го блока анализа группы, вторые управляющие входы блоков опроса К-ro (К = 1...m) столбца матрицы соединены с выходом К-ro блока анализа группы, третьи управляющие входы всех блоков опроса матрицы соединены с тактовым входом устройства каждый вход запроса устройства соединен с нулевым входом одноименного триггера групп, единичный вход каждого триг- 25 гера группы соединен с управляющим выходом одноименного блока опроса

m-го столбца матрицы, счетный вход каждого счетчика группы соединен с соответствующим входом запроса уст- ЗО ройства, выходы блока элементов ИЛИ соединены с выходами устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения за счет введения дополнительной дис циплины обслуживания запросов типа кольцевого изменения кодов приоритетов источников запросов, в него введены блок формирования кода приоритета, группы блоков элементов ИЛИ, 4О две группы блоков элементов И, элемент ИЛИ и элемент НЕ, причем вход выбора дисциплины обслуживания устройства соединен с входом элемента НЕ и с управляющими входами нечетных 45 блоков элементов И первой группы, ин" формационные входы четных блоков элементов И соединены с соответствующими выходами блока формирования кода приоритета, управляющие входы которого соединены с управляющими выходами блоков опроса m-го столбца матрицы и с управляющими входами блоков элементов И второй группы, информационные входы которых соединены с прямы55 ми выходами одноименных регистров группы, нулевые выходы которых соединены с первыми информационными входами нечетных блоков элементов И первой группы, управляющие входы которых соединены с выходом элемента НК, вторые информационные входы всех блоков элементов И первой группы соединены с инверсными выходами соответствующих счетчиков группы, выходы каждой пары блоков элементов И первой группы соединены с входами соответствующего блока элементов ИЛИ группы, выходы которых соединены с группами информационных входов блоков опроса первого столбца матрицы, информационные входы блока формирования кода приоритета соединены с прямыми выходами последнего регистра группы, выход каждого триггера группы соединен с соответствующим входом элемента ИЛИ, выход которого соединен с четвертыми управляющими входами блоков опроса m-го столбца матрицы, выходы блоков элементов И второй группы соединены с группами входов блока элементов ИЛИ.

2 ° Устройство по и, 1, 0 T л и ч а ю щ е е с я тем, что блок формирования кода приоритета содержит две группы блоков элементов И, группу счетчиков, группу дешифраторов, m групп элементов И, три группы элементов ИЛИ, причем информационные входы блока соединены с информационными входами блоков элементов И первой группы, управляющие входы каждого блока элементов И первой и второй групп соединены с одноименным управляющим входом блока, группа выходов каждого блока элементов И первой группы соединена с группой информационных входов одноименного счетчика группы, инверсные выходы счетчиков группы являются выходами блока, прямые выходы каждого счетчика группы соединены с входами одноименного дешифратора группы, выходы каждого дешифратора группы, кроме последнего выхода, соединены с информационными входами одноименного блока элементов И второй группы, одноименные выходы групп выходов каждого блока элементов И второй группы соединены с входами одноименного элемента ИЛИ первой группы, выход каждого элемента

ИЛИ первой группы соединен с входами одноименного и всех последующих элементов ИЛИ второй группы, выход каж" дого элемента ИЛИ второй группы соединен с первым входом одноименного элемента И каждой из ш групп, второй вход i-го (i = 1...ш-1) элемента И

1О

1619274. 9 каждой иэ а групп соединен с (i+1)-м выходом одноименного дешифратофа группы, выходы элементов И каждой иэ m групп соединены с входами одноименного элемента ИЛИ третьей группы, выхщ каждого элемента ИЛИ третьей группы соединен со счетным входом одноименного счетчика группы.

161ez74

Ю ВЮ Ф с ъ 1ф ф

3

i

3 !

В !

С

t

l ! !

В

3Щ

3 a. («Ф

1

1.

3

l е

1 ! .

1 !

1 !

1619274 блок опроса

Фиг. 5

Елои ааалиЗа фиг. 4

Составитель M.Êóäðÿøîâ

Техред М.Дидык Корректор О.Ципле

Редактор А.Мотыль Заказ 48 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101