Устройство приоритета

 

УСТРОЙСТВО ПРИОРИТЕТА по :авт.св. №721816, отличающееся тем, что, с целью расширения функциональных возможностей путем выдачи максимально приближенного к заданному количества, запросов, в него дополнительно введены п двухвходовых элементов И, вогходной п-разрядный триггерный регистр, два триггера , три элемента ИЛИ, элемент за.держки, одновибратор, элемент И-НЕ, счетчик, элемент И, мультиплексор и генератор, выход которого подключен к первому входу дополнительного элемента И и первому входу мультиплексора, каждый вход группы входов которого соединен с выходом соответствующего из П двухвходовых элементов ИЛИ и соответствующим входом первого дополнительного элемента ИЛИ, выход которого соединен с входами элемента задержки и одновибратора , выходы которых соединены с соответствующими входами второго дополнительного элемента ИЛИ, выход которого подключен к первому входу элемента И-НЕ и второму входу дополнительного элемента И, третий вход которого соединен с вторым входом мультиплексора и выходом первого триггера, первый и второй входы которого соединены соответственно с первым и вторым входами второго триггера, первый входкоторого подключен к первому входу сброса устройства , а выходы мультиплексора подключены к первым входам входного и выходного П-разрядных триггерных регистров, вторые входы которых являются cooтвeтcтвyюDl и входами сброса устройства, выходы выходного f)-разрядного триггерного регистра С соединены с первыми входами И дополнительных двухвходовых элементов И, вторые входы которых подключены к выходу второго триггера, второй вход которого соединен с выходом элемента И-НЕ, второй вход которого подключен к выходу третьего дополнительного элемента ИЛИ, входы котою рого coeд iнeны с выходами счетчика, вход которого подключен к выходу ® дополнительного элемента И, а групОд па входов является группой установочных входов устройства, выходы 17 дополнительных двухвходовьсх элементов И являются выходами устройства.

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

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

РЕСПУБЛИК

09) (11) А дц C 06 Г 9/46

/ - =

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (61) 721816 (21) 3629559/24-24 (22) 03.08.83 (46) 30. 11. 84. Бюл. К- 44 (72) В.П.Игнатович и В.В.Камынов (53> 681. 14 (088. 8) (56) 1. Авторское свидетельство СССР

М- 721816, кл. С 06 F 9/46, 1976 (прототип) . (54) (57) УСТРОЙСТВО ПРИОРИТЕТА по

:авт.св. М- 721816, о т л и ч а ю—

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

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

11-разрядного триггерного регистра соединены с первыми входами И дополнительных двухвходовых элементов

И„ вторые входы которых подключены к выходу второго триггера, второй вход которого соединен с выходом элемента И-НЕ, второй вход которого подключен к выходу третьего дополнительного элемента ИЛИ, входы которого соединены с выходами счетчика, вход которого подключен к выходу дополнительного элемента И, а группа входов является группой установоч ных входов устройства, выходы IT дополнительных двухвходовых элементов

И являются выходами устройства.

1126961

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

Устройс:во приоритета по авт.св.

У 721816 содержит входной триггерный

11 -разрядный регистр (Р— число запросов), г1 двухвходовьх элементов ИЛИ, И двухвходовых элементов И, (й-l ) элементов НЕ и п входовые элементы 10

И, к первым входам которых подключены единичные выходы триггеров, Нулевой выход триггера и -го разряда соединен с (1 +1)-ми входами Р -входовых элементов И разрядов от (г1+1)-го 15 до<А -го включительно. Первый вход каждого двухвходового элемен2 а ИЗМ подсоединен к выходу 0 -входового элемента И своего разряда, а второй вход — к выходу двухвходового элемен- 2Î та И., а выход каждого двухвходового элемента ИЛИ соединен с первым входом двухвходового элемента И и с соответствующим выходом устройства, каждый из которых до (г1-1)-го вклю- 25 чительно подключен к входу элемента

HE своего разряда. Второй выход каж-* дого двухвходового элемента И соединен с единичным выходом триггера входного регистра своего разряда. Зр

Выходы 11 -входовых элементов И каждого П -ro » всех предыдущих разрядов подключены к выходу элемента НЕ (0+1) -r о разряда.

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

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

Поставленная цель достигается тем, что в устройство приоритета по авт,св. У 721816 дополнительно введены и двухвходовых элементов И, выходной Д -разрядный триггерный ре- 55 гистр, два триггера, три элемента

ИЛИ, элемент задержки, одновибратор, элемент И-НЕ, счетчик, элемент

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

Ц -разрядных триггерных регистров, вторые входь; которых являются соот— ветствуюшими входами сброса устройства, выходы вьгходного и -разрядного триггерно" о регистра соединены с первьГ и вхг>дами tl дополнительнь1х двухвходовых элементов И, вторые входы которых подключены к выходу второго триггера, второй вход которого соепинен с выходом элемента

И-НЕ, второй вход которого подключен к выходу третьего дополнительного элемента ИЛИ, входы которого соединены с вьгходаьпг счетчика, вход которого подключен к выходу дополнительного элемента И, а группа входов является группой установочньп< входов устройства, выходы П дог|олнгтельнь2х двухвходовых элементов И являются выходами устройства.

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

1126961

На фиг. 1 представлена схема устройства, на фиг. 2 — схема блока приоритета.

Устройство сбдержит rенератор 1, элемент И 2, мультиплексор 3,11 -входовой элемент ИПИ 4 элемент 5 за1 пержки. опновибратор 6 элемент

ИЛИ 7. элемент И-НЕ 8, триггеры 9 и 10, триггеры 11-15 выходного регистра, элементы И 16-20, элемент 10

ИЛИ 21, счетчик 22, вход 23 сброса, входы 24 установки, входы 25-29 входы 30-34 сброса, выходы 35-39, блок 40 заявок, входы 41-45, выходы

46-50. 15

Блок 40 содержит входной регистр . с триггерами 51-55, и -входовые элементы И 56-60. двухвходовые элементы ИЛИ 61-65> двухвходовые элементы

И 66-70, элементы HF. 71-74

Элемент 5 задержки задерживает сигнал на время, равное времени задержки срабатывания одновибратора 6.

Одновибратор .6 по отрицательному фронту входного сигнала вырабатывает положительный импульс с длительностью, равной сумме времени задержки элемента НЕ 72, элемента И 57, элемента

ИЛИ 62. 30

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

После включения питания триггеры

51-55;10. и входы 41-45 устройства обнулены, счетчик 22 установлен в состояние не равное нулю. Генератор

1 выдает непрерывную последовательность импульсов. Мультиплексор 3 и элемент И 2 закрыты сигналом низкого 40 уровня с выхода триггера 9

Элементы И 16-20 закрыты сигналом низкого уровня с выхода триггера 10 и на выходах 46-50 устройства — сигналы низкого уровня, что соответст- 45 вует отсутствию заявок на обслуживание. Система, определив количество свободных процессоров, через входы

24 установки заносит в счетчик 22 двоичный код этого числа и импульс- 50 ным сигналом, подаваемым на вход 23, включает устройство в режим набора заявок.

В режиме набора заявок возможны следующие варианты: 55

1. До момента подачи сигнала на вход 23 запросы на входы 30-34 не поступали.

2, Количество поступивших на входы 30-34 з апр осов б ольше числа свободных процессоров (кода в счетчике 22), 3. Количество поступивших на входы 30-34 зяпоосов меньше числа свободных процессоров.

4. Количество поступивших запросов равно числу свободных процессоров.

Вариант 1.

При отсутствии запросов на входах

30-34 триггеры 51-55 блока 40 заявок находятся в исходном (нулевом} состоянии и на выходах 35-39 блока 40 заявок сигналы также нулевые. На выходе элемента И-НЕ 8 — единичный сигнал.

Импульсы с генератора 1 проходят через мультиплексор 3 на выход

1l lt

000...0, который никуда не подключен. Элемент И 2 закрыт нулевым сигналом с выхода элемента ИПИ 7.

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

При поступлении запросов на входы 30-34 блок 40 запросов выбирает запрос с наивысшим приоритетом и на соответствующем выходе 35-39 устанавливается единичный сигнал 11) .

Единичный сигнал также ус.тановится на выходе элемента ИЛИ 7. На выходе элемента И-НЕ 8 устанавливается нулевой сигнал, а на счетный вход (вычитающий) счетчика 22 через элемент И 2 проходят импульсы с генератора 1.

Единичный сигнал с выходов 35-39 поступает также на адресные входы мультиплексора 3, и импульс с генератора через мультиплексор 3 уста,новит в единичное состояние соответ ствующий триггер 11-15 выходного регистра и в нулевое — соответствующий триггер 51-55 (через входы 2529) входного регистра. Блок 40 заявок выбирает из оставшихся запросов наиболее приоритетный.

Дальнейшая работа устройства соответствует вариантам 2 и 3.

Работу устройства в вариантах

2 и 3 рассмотрим на примере. Перед подачей на вход 23 сигнала в счетчик 22 было записано число 2,, т.е. система имеет два свободных процессора для обслуживания запросов.

На входы 30, 33. 34 одновременно поступили сигналы запроса, устано1126961 вывшие триггеры 51, 54, 55 в единичное состояние. На выходе элементов ИЛИ 4 и 7 устанавливаются единичные сигналы. а на выходе элемента И"НЕ 8 нулевой сигнал, Блок 5

40 заявок выбирает, как наиболее приоритетный, запрос с триггера

5t и выставляет на выходе 35 единичный сигнал. Ближайший импульс с генератора 1 вычитает единицу из содержимого счетчика 22, устанавливает триггер 11 выходного регистра в единичное состояние и сигналом с соответствующего выхода мультиплексора 3 через вход 25 сбрасывает триггер 51 в нулевое состояние, После сброса триггера 51 блок

40 заявок выбирает запрос с триггера 54 и выставляет единичный сигнал на выходе 38, триггер 14 устанавли20 вается в единичное состояние, а триггер 54 — в нулевое. Содержимое счетчика 22 после вычитания единицы, становится равным нулю, т.е. коли21 чество запросов в выходном регистре равно количеству свободных процес соров. На выходе элемента ИЛИ 21 также устанавливается нулевой сигнал, который изменяет уровень сигнала на выходе элемента И-НЕ 8 с нуле- ЗО вого на единичный. По изменению (по положительному фронту) сигнала на выходе элемента И-НЕ 8 триггер

9 устанавливается в нулевое состояние, запрещая прохождение импульсов И с генератора 1 через мультиплексор

3 и элемент И 2, а триггер 10 устанавливается в еднничное состояние, разрешая прохождение запросов с триггеров 11-!5. через элементы 40

И 16-20 на выходы 46-50 устройства;

В результате на выходах 46 и 50 будут единичные сигналы, а на остальных - нулевые. Запрос по входу 34 остается не обслуженным в этом цикле <5

По окончании обслуживания запросов система подает сигналы сброса триггеров 11 и t4 на входы 41 и 44, устанавливает через вход 23 в счетчик 22 новое число свободных процес- О соров и подает сигнал запуска на вход 23.

Пусть для следующего цикла (вариант 3) система записана в.счетчик 22 число 4щ и дополнительно по- 55 ступил запрос по входу 31. В соот ветствии с И блок 40 запросов выделил из поступивших запросов запрос, поступивший Ilo входу 34, как более ранний, хотя и менее приоритетный, Соответственно единичный сигнал установлен на выходе 39 блока 40 запросов.

После подачи сигнала запуска на вход 23 устройство работает аналогично вышеописанному. После сброса запроса с триггера 55 блок 40 запроса выставит единичный сигнал на выходе

36 (соответствующий запросу, записанному в триггер 52) не сразу, а через время равное времени задержки цепи: элемент НЕ 72 — элемент И 57 - элемент ИЛИ 62. На это время на выходе элемента ИЛИ 4 установится нулевой сигнал для исключения ложного срабатывания триггеров 9 и IО. По этому сигналу применяется схема, состоящая из элемента 5 задержки.одновибратора

6 и элемента ИЛИ 7. При появлении на выходе элемента ИЛИ 4 отрицательного фронта одновибратор 6 вырабаты-. вает единичный импульс, длительность которого не менее воемени задержки пепи . элемент НЕ 72 — элемент И 57 элемент ИЛИ 62 и если нулевой сигнал на выходе элемента ИЛИ 4 вызван переходом единичного сигнала с менее приоритетного выхода блока 40 запросов на более приоритетный, то на выходе элемента ИЛИ 7 будет удержан единичный сигнал и ложного срабатывания триггеров 9 и 10 не произойдет.

После установки в единичное состояние триггера 12, триггер 52 сбрасывается и так как запросов больше нет, то на выходах 35-39 блока 40 запросов устанавливаются нулевые сигналы. По переходу сигнала из единицы в нуль на выходе элемента ИЛИ 4 одновибратор.б вырабатывает единичный импульс, но так как нулевой сигнал имеет длительность большую, чем длительность вырабатываемого одновибратором 6 импульса, то сигнал на выходе элемента ИЛИ 7 переходит из единицы в нуль и через элемент

И-НЕ 8 устанавливает фронтом триггер

9 в нулевое состояние, а тригге1

10 - в единичное. На выходы 46-50 поступает содержимое триггеров

11-15 единичные сигналы с триггеров

12 и 15 и нулевые с остальных.

По завершению обслуживания этих запросов система устанавливает триггеры 12, 15 в нулевое. состояние сигналом на входы 42, 45.

26961

ВНИИПИ Заказ 8741/38 Тираж 698 Подписное

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

7 11

Вариант 4 работы устройства представляет собой одновременное выполнение вариантов 2 и 3.

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