Устройство для выбора по приоритету Советский патент 1991 года по МПК G06F9/46 

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

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

На фиг.1 представлена структурная схема устройстьа для выбора по приоритету; на фкг.2 - структурная схема блока формирования кода приоритета; на фиг.З - структурная схема блоков с.лроса; на фиг.4 - структурная схема блока анализа.

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

Глок 8 формирования кода приоритета содержит группу блоков элементов И 16, группу счетчиков 17, группу дешифраторов 18, группу блоков элементов И 19, группу элементов ИЛИ 20, группу элементов ИЛИ 21, группу блоков элементов И 22 и группу элементов ИЛИ 23.

О5

QD № J

4ь

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

Блок 2 анализа содержит элементы НЕ 28 и элемент И 29. Элементы 26 и 27 задействованы только в блоках } последнего столбца матрицы.

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

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

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

Коды счетчиков 5 используются при выделении кода номера процессора в

0

г

5

0

0

5

0

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, по которому код номера процессора, которому разрешено обратиться в память, с выхода соответствующего регистра 6 через блок элементов ИЛИ 3 выдается на1 выход устройства.

Кроме того, управляющий сигнал с выхода соответствующего блока 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. В результате, 1код, записанный на счетчике 17 блока 8, уменьшается на единицу.

0

5

0

5

0

5

0

5

0

5 J

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

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

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

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

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

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

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

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

2. Устройство по п,1, отличающееся тем, что блок формирования кода приоритета содержит две группы блоков элементов И, группу счетчиков, группу дешифраторов, m групп элементов И, три группы элементов ИЛИ, причем информационные входы блока соединены с информационными входами блоков элементов И лервой группы, управляющие входы каждого блока элементов И первой и второй групп соединены с одноименным управляющим входом блока, группа выходов каждого блока элементов И первой группы соединена с группой информационных входов одноименного счетчика группы, инверсные выходы счетчиков группы являются выходами блока, прямые выходы каждого счетчика группы соединены с входами одноименного дешифратора группы, выходы каждого дешифратора группы, кроме последнего выхода, соединены с информационными входами одноименного блока элементов И второй группы, одноименные выходы групп выходов каждого блока элементов И второй группы соединены с входами одноименного элемента ИЛИ первой группы, выход каждого элемента ИЛИ первой группы соединен с входами одноименного и всех последующих элементов ИЛИ второй группы, выход каждого элемента ИЛИ второй группы соединен с первым входом одноименного элемента И каждой из m групп, второй вход i-го (i 1...Ш-1) элемента И

каждой из m групп соединен с (1+1)-мэлемента ИЛИ третьей группы, выхо

выходом одноименного дешифратора труп-каждого элемента ИЛИ третьей группы

ггы, выходы элементов И каждой из шсоединен со счетным входом одноименногрупп соединены с входами одноименного сго счетчика группы.

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

Фигл

блок опроса

Фиг. з

блок анализа