Приоритетное устройство Советский патент 1987 года по МПК G06F9/50 

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

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

На фиг. 1 приведена функциональная схема устройства; на фиг. 2 - схема блока формирования резрешений; на фиг. 3 - схема логического узла; на фиг.4-10 - мнемонические схемы,пояс- няющие принцип работы устройства.

Устройство содержит блок 1 формирования разрешений, блок 2 анализа запросов, блок 3 памяти, запросные входы 4 устройства, выходы 5 разрешений устройства, выходы 6 блока 2 анализа запросов, управляющие входы 7 блока 1 формирования разрешений и тактовый вход 8 устройства.

Блок 1 формирования разрешений со- держит треугольную матрицу 9 из

N(N-1) узлов 10 приоритета с первым

11, вторым 12, третьим 13 входами и первым 14 и вторым 15 выходами.

приоритета содержит элеУзел 10

мент И 16, первый 17 , второй 17 и третий 17 элементы запрета.

На мнемонических схемах (фиг.4-10) узловые точки обозначают логические блоки 10. Стрелка на первом 11 или втором 12 входе блока 10 показывает приоритет этого входа по отношению к входу, не имеющему стрелки. Управляю- щие (третьи) входы 13 блоков 10 на мнемосхемах не показаны. Утолщенными линиями изображены траектории прохождения запросных сигналов, поступивших с входов 4 через логические блоки 10 на выходы 5 устройства.

Узел приоритета 10 реализует функцию двувходового арбитра по отношению

11 и 12. При отсутствии конфликтов между входными сигналами (комбинации 00, 01, 10), они передаются на соответствующие выходы 14 и 15 независимо от сигнала на управляющем входе 13. При наличии конфликтной ситуации на входе (комбинация 11) узел 10 приоритета отдает приоритет тому или иному сигналу в зависимости от сигнала на управляющем входе 13.

Работа узла 10 приоритета описывается таблицей истинности.

Таблица истинности узла 10 приоритета

Блок 1 формирования разрешений осуществляет разрешение конфликтов между единичными сигналами на запросных входах 4 в соответствии с приоритетной дисциплиной обслуживания, заданной управляющим кодом на входе 7.

При отсутствии запросных сигналов (О на всех входах 4) на всех выходах 5 разрешений также формируются сигналы О, свидетельствующие об отсутствии .разрешений.

При наличии сигнала 1 только на одном из запросных входов 4 . этот сигнал проходит через все встречающиеся на его пути логические блоки 10 и поступает в виде сигнала 1 на соответствуюш;ий выход разрешений

40

35 независимо от значения кода на управляющих входах 7.

Если на входы 4 устройства одновременно поданы несколько сигналов 1, то эти сигналы, встречаясь в узлах 10 треугольной матрицы 9, подвергаются отбору в соответствии со значением кода на управляющих входах 7, На выходы 5 проходит только один единичный сигнал.

Значение кода на управляющих входах 7 устанавливается в соответствии с требуемой приоритетной дисциплиной обслуживания.

Допустим требуется обеспечить дующую дисциплину обслуживания запросных входов 4 -4g пятивходового приоритетного устройства:

45

55

,- ,

Направление стрелки показывает переход от более приоритетных входов к менее приоритетным.

Для обеспечения указанной дисциплины обслуживания код на управляющем

31304025

входе 7 блока 1 формирования разрешений должен управлять узлами приоритета 10 следующим образом:

к с с

3

2

4

1

2

2

4з-А,;

.

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

10.

ff

10,1 10,

10

аг

10.

Юз, 10

10,

44

30

следуютета

Юзз 41

щее 1111101111 (фиг. 4).

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

Так как количество управляющих

входов 7

равно С

N(N-1)

и равно

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

Гибкие режимы характеризуются тем, что приоритет между запросными сигналами определяется не только управляющим кодом, подаваемым на управляющие входы 7 блока 1, но и зависит от числа поступивших запросов и их распре- 45 заданная дисциплина приоритетного обделения по запросным входам 4.

Если в ранее рассмотренном примере изменить значение только одного (восьмого) бита в управляющем коде, а

именно бита, определяющего взаимоот- 50 налов на определенных входах 4, то

вощение между входами ч «

ловие HS ложное::

4(; 4 изменится

и 4g , то ус- на противопо2 5

в %том случае управляющий код примет вид: 1111101011 и при наличии всех сигналов запроса на входах 4 дисциплина приоритетного обслуживания

55

будет следующая: 4

4, - 4.

4,-

дисциплины приоритетного обслуживан становятся другими (фиг. 7 - 9).

Таким образом, блок 1 разрещений предложенной структуры при N 5 запросных входах можно настроить на одну из 1024 дисциплин приори тетного обслуживания, прич-ем имеетс

дисциплин жесткого и 2-51

304025

;

;

;

W

15

ь, так как

4 сигнал

по

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

входу 4j, сигнал 4

, будет побежден 4 и 4,, соответ- 10 приоритета.

о

Очевидно, что при отсутствии запросных сигналов на входах 4з и 4 приоритетная дисциплина обслуживания примет вид: 4j- , (фиг. 5).

Если в управляющий код внести еще изменения во 2-м, 4-м, 7-м и 10-м разрядах, то он примет вид 1010100010 (приоритет прохождения сигналов через узлы приоритета 10 при таком управляющем коде показаны стрелками на мнемосхеме фиг. 6).

Из фиг. 6 следует, что при наличии запросных сигналов на всех входах дисциплина приоритетного обслу20

25

живания -н 4

4

При

сохраняется 4,- 4.

заданной: 4 г- 4.

запросного сигнала tj дисциплина приориг 1 отсутствии

только на входе 4j

тетноГо обслуживания принимает вид:

4, 4, (фиг. 7).

При отсутствии запросного сигнала только на входе 4 дисциплина приоритетного обслуживания имеет другой вид:

Если

4, 4 (фиг. 8).

запросные сигналы отсутству5

0

ют одновременно на входах 4,j и 4з,то дисциплина приоритетного обслуживания принимает новый вид: 4 - 4 - 4:

(фиг. 9)..14

Таким образом, при управляющем коде 1111101111, определяющем жесткую дисциплину приоритетного обслуживания, заданная дисциплина обслуживания

4,- 4, сохраня-

висимости от числа и распределения сигналов запроса по входам 4, - 4j (фиг. 4). При управляющем коде 1010100010, определяющем гибкую дисциплину приоритетного обслуживания,

s ется

э вне

служивания 4 - 4 -- 4,j- 4 будет при наличии сигналов запроса на всех входах (фиг. 6). Если отсутствует один или несколько запросных сиг

5

дисциплины приоритетного обслуживания становятся другими (фиг. 7 - 9).

Таким образом, блок 1 разрещений предложенной структуры при N 5 запросных входах можно настроить на одну из 1024 дисциплин приоритетного обслуживания, прич-ем имеется

дисциплин жесткого и 2-51

904 дисциплины гибкого задания приоритетов .I

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

Если при выбранной приоритетной дисциплине обслуживание всех поступаФо рмула изобретения Приоритетное устройствб, содержающих на входы 4 запросов происходит в 20 щее блок формирования разрешений,блок

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

Если какие-либо запросы долгое вреанализа запросов и блок памяти, а блок анализа запросов содержит группу из N счетчиков и группу из N элементов ИЛИ (N - число запросных вхо- 25 доз устройства), причем группа информационных входов блока формирования резрешений является группой запросных входов устройства и соединена с входами сброса соответствующих счетчиков

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

мя не обслуживаются, то на соответст- ЗО группы блока анализа запросов,группа вующих выходах 6 блока 2 анализа запросов появляются единичные сигналы, свидетельствующие о необходимости перестройки дисциплины приоритетного обслуживания в направлении повьшения вероятности обслуживания зтих запро- сов. Перестройка дисциплины обслужи35

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

вания осуществляется изменением кода на управляющих входах 7 блока 1 формирования разрешений. Значения управ- 40 пой выходов разрешения обслуживания

ляющего кода, соответствующие опреде- леннымОдисциплинам обслуживания, находятся в ячейках блока 3 памяти.Адрес ячеек формируется за счет появления единиц на выходах 6 блока 2 анализа запросов, соответствующих необслуживаемым запросным входам.Проиллюстрируем одну из возможных перестроек дисциплин обслуживания пятивходового -приоритетного устройства, на входы 4 которого поступают запросы. Допустим, что при дисциплине приоритетного обслуживания

. 4 - 4 - 4. - 4 и управляющем коде 1010100010 (фиг. 6) вход 4, долгое время не обслуживается. Тогда на первом выходе выходов 6 блока 2 анализа запросов появляется сигнал 1. На входах блока 3 памяти

формируется код 10000, по которому находится управляющих код, соответствующий, например , дисциплине приоритетного обслуживания вида: 4 - 4,j-

- .

Для данной дисциплины приоритетного

обсл5окивания управляющий код может, например, иметь вид 0000010000 (фиг. 10).

После обслуживания входа 4у, на первом выходе тзыходов б блока 2 анализа запросов устанавливается сигнал О и по адресу ООООО из блока 3 памяти на входы 7 блока 1 разрешений снова поступает управляюгций код 1010100010.

Фо рмула изобретения Приоритетное устройствб, содержащее блок формирования разрешений,блок

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

группы блока анализа запросов,группа

группы блока анализа запросов,группа

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

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

N(N-i)

узлов приоритета.

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

7 . 1304025 (i 27)соединен с первым входом первого элемента запрета и первьм входом элемента И (i-l)-ro узла приоритета первого столбца матрищ, первый, информационный вход блока формирования разрешений соединен с. первыми входами второго и третьего элементов запрета первого узла приоритета первого столбца матрицы, вторые входы

8

соединен с первым входом первого элемента запрета и первым входом элемента И узла приоритета (1-1)-й строки (j+1)-ro столбца (при j i), выход третьего элемента запрета узла приоритета (1-1)-й строки j-ro столбца соединен с вторым входом второго и третьего элементов запрета узла приоритета i-й строки j-ro столбца (при

элементов И и второго элемента запре-10 j i, i 3 N), выход третьего элемента запрета узла приоритета (К-1)-й строки j-ro .столбца соединен с j-M входом блока формирования разрешений, выход первого элемента запрета узла

та каждого узла приоритета матрицы соединены с соответствующими входом изменения приоритета группы блока формирования разрешений, выход элемента И каждого узла приоритета блока 5приоритета (1-1)-й строки j-ro столб- формирования разрешений соединен сца (при i N) соединен с вто- вторым входом третьего элемента запре-рыми входами второго и третьего эле- та этого же узла приоритета, выходментов запрета узла приоритета i-й второго элемента запрет каждого уз-строки (j+1)-ro столбца, выход перво- ла приоритета блока формирования раз-20то элемента запрета узла приоритета решений соединен с вторым входом пер-(К-1)-й строки (N-.1)ro столбца соевого элемента запрета узла приоритетадинен с N-M выходом блока формирова-- (1-1)-й строки j-ro столбца (,N-1)ния разрешений.

8

соединен с первым входом первого элемента запрета и первым входом элемента И узла приоритета (1-1)-й строки (j+1)-ro столбца (при j i), выход третьего элемента запрета узла приоритета (1-1)-й строки j-ro столбца соединен с вторым входом второго и третьего элементов запрета узла приоритета i-й строки j-ro столбца (при

та запрета узла приоритета (К-1)-й строки j-ro .столбца соединен с j-M входом блока формирования разрешений, выход первого элемента запрета узла

приоритета (1-1)-й строки j-ro столб- ца (при i N) соединен с вто- рыми входами второго и третьего эле- ментов запрета узла приоритета i-й строки (j+1)-ro столбца, выход перво- то элемента запрета узла приоритета (К-1)-й строки (N-.1)ro столбца соединен с N-M выходом блока формирова-- ния разрешений.

Изобретение относится к цифровой вычислительной технике и может быть использовано в. вычислительных системах, имеющих несколько активных источников информации, подключенных к общему ресурсу. Целью изобретения является расширение области применения путем организации любого числа запросных входов при упрощении устройства. Устройство приоритета содержит блок 1 формирования разрешений, блок 2 анализа запросов, блок 3 памяти, запросные входы 4, выходы 5, входы 6 блока 2 анализа запросов, управляющие входы 7 блока 1, тактовый вход 8. Новое выполнение блока формирования . разрешений в виде треугольной матрицы и упрощение конструкции узла приоритета, позволяет организовать произвольное число запросных входов и упростить конструкцию устройства. 10 ил. 1 табл. с S (Л со о N о to СП

7 .

ГI s

iif « I

V/yly

.-И

A

w-r

/ -w,

Si 5г

5u 65

Управляющий

11 7 11011 17 ФигЛ

1 2 3 if 5 - 5

Управляющей код

1 11 1101011 Фиг.5

-,

5-f 62 5j 5 5$

Управляющий

101 Q 1 О О О 1 О Фиг. 6

5j 5i 5j 5«

i 1 Упра&ляющий ffod

10101 0 ООШ Фиг.8

5/ 5/ 5j 5 5у

Упроёляющий под1010100010(Риг. 7

5, -5, 15, 5s

Управляющий tfO& 10 Ч0100010

Фиг. 9

1 52 5j 5 5s

,- Улра6/гяюЩ1/1} 0 000 70000 Фиг. Ю