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

СООЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК 19) (1 4 вход которого под дополнительного эл лючен к выход емента И, а г группой уста тва, выходы И па входов являетс ных входов устрой ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) 1. Авторское свидетельство СССР 11 721816, кл. С 06 1= 9/46, 1976 (прототип).(54)(57) УСТРОЙСТВО ПРИОРИТЕТА по :авт,св. Ф 721816, о т л и ч а ю - щ е е с я тем, что, с целью расширения Функциональных возможностей путем выдачи максимально приближенного к заданному количества. запросов, в него дополнительно введены И двухвходовых элементов И, выходной П -раз рядный триггерный регистр, цва триггера, три элемента ИЛИ, элемент задержки, одновибратор, элемент И-НЕ, счетчик, элемент И, мультиплек сор и генерат р, выход которого подключен к первому входу дополнительного элемента И и первому входу мультиплексора, каждый вход группы входов которого соединен с выходом соответствующего из 11 двухвходовых элементов ИЛИ и соответствующим входом гервого допслнительного элемента ИЛИ, выход которого соединен с входами элемента задержки и одновибратора, выходы которых соединены с соответствующими входами второго дополнительного элемента ИЛИ, выходкоторого подключен к первому входуэлемента И-НЕ и второму входу дополнительного элемента И, третий входкоторого соединен с вторым входоммультиплексора и выходом первоготриггера, первый и второй входыкоторого соединены соответственнос первым и вторым входами второготриггера, первый вход которого подключеч к первому входу сброса устройства, а выходы мультиплексораподключены к первым входам входногои выходного И -разрядных триггерныхрегистров, вторые входы которыхявляются соответствующими входамисброса устройства, выходы выходного11-разрядного триггерного регистрасоединены с первыми входами И дополнительных двухвходовых элементовИ вторые входы которых подключенык выходу второго триггера, второйвход которого соединен с выходомэлемента И-НЕ, второй вход которогоподключен к выходу третьего дополнительного элемента ИЛИ, входы которого соецинены с выходами счетчика,полнительных двухвходовых элементовИ являются выходами устройства.-Изобретение относится к вычисли -тельной технике и может бьггь использовано в многопроцессорных системахобслуживания заявок,Устройс гво приоритета по авт.св. 5У 721816 содержит входной триггерныйЬ -разрядный регистр ( Р - число запросов), и двухвходовьх элементов ИЛИ,И двухвходовых элементов И, (П)элементов НЕ и и входовые элементы 1 ОИ, к первым входам которых подключены единичные выходы триггеров,Нулевой выход триггера и -го разрядасоединен с (и+1)-ми входами Р -входовых элементов И разрядов от (г 1+1)-го 15доО-го включительно. Первый входкаждого двухвходового элемента ИХУподсоединен к выходу П -входовогоэлемента И своего разряда, а второйвход - к выходу двухвходового элемен Ота И, а выход каждого двухвходовогоэлемента ИЛИ соединен с первым входом двухвходового элемента И и ссоответствующим выходом устройства,каждый из которых до (Д)-го включительно подключен к входу элементаНЕ своего разряда. Второй выход каж-дого двухвходового элемента И соединен с единичным выходом триггеравходного регистра своего разряда. ЗОВыходы 11 -входовых элементов И каждого П -го и всех предыдущих разрядовподключены к выходу элемента НЕ(0+1)-го разряда.Недостаток устройства-прототипазаключается в том, что на обслуживание выдается только одна заявкаи только после обслуживания предыдущей, тогда как в многопроцессорнойсистеме одновременно могут обслужи- щваться несколько заявок, количествокоторых ограничено количеством свободных процессов в системе или числом поступивших запросов на обслуживанне. 45Цел изобретения - расширение функциональных возможностей устроиства за счет выдачи максимально приближенного к зацанному количества запросов. 5 ОПоставленная цель достигается тем, что в устройство приоритета по авт,св, У 721816 дополнительно введены и двухвходовых элементов И, выходкой П -разрядный триггерный ре гистр, два триггера, три элемента ИЛИ, элемент задержки, одновибратор, элемент И-НЕ, счетчик, элемент И, мультиплексор и генератор, выходкоторого подключен к первому входудополнительного элемента И и первомувходу мультиплексора каждый входгруппы йходов которого соединен с выходом соответствующего из И двухвходовых элементов ИЛИ и соответствующим входом первого дополнительногоэлемента ИЛИ, выход которого соединенс входами элемента задержки и одновибратора, выходы которых соединеныс соответсгвующими входами второгодополнительного элемента ИЛИ, выходкоторого подключен к первому входуэлемента И-НЕ и второму входу дополнительного элемента И, третий входкоторого соединен с вторым входоммультиплексора и выходом первоготриггера, первый и второй входы которого соединены соответственно с первым и вторым входами второго триггера, первый вход которого подключенк первому входу сброса устройства,а выходы мультиплексора подключенык первым входам вьгходного и входногоЦ -разрядных триггерных регистров,вторые входь; которых являются соот -ветствуюшими входами сброса устройства, выходы вьгходного Й -разрядноготриггерного регистра соединены спервьг.;и входами П дополнительныхдвухвходовых элементов И, вторыевходы которых подключены к выходуьторого триггера, второй вход которого соепинен с выходом элементаИ-НЕ, второй вход которого подключенк выходу третьего дополнительногоэлемента ИЛИ, входы которого соединены с выходаьи счетчика, вход которого подключен к выходу дополнительного элемента И, а группа входовявляется группой установочньп входовустройства, выходы П дополнительныхдвухвходовых элементов И являютсявыходами устройства. Указанная совокупность элементов и связей позволяет осуществить выдачу в систему максимально приближенное заданному количество запросов путем послецовательной записи в выходной триггерный регистр запросов в порядке возрастания приоритетов до момента набора количества запросов, соответствующего заданному на счетчике, или до момента, когда все поступившие запросы записаны в вьподной триггерный регистр,1126961 На фиг. 1 представлена схема устройства, на фиг. 2 - схема блока приоритета.йУстройство содержит генератор 1, элемент И 2, мультиплексор 3,11 -входовой элемент ИПИ 4 элемент 5 запержки. опновибратор 6 элемент ИЛИ 7, элемент И-НЕ 8, триггеры 9 и 10, триггеры 11- 15 выходного регистра, элементы И 16-20, элемент 1 О ИЛИ 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, элементы НЕ 71-74 20Элемент 5 задержки задерживает сигнал на время, равное времени задержки срабатывания одновибратора 6.Одновибратор .6 по отрицательному 25 фронту входного сигнала вырабатывает положительный импульс с длительностью, равной сумме времени задержки элемента НЕ 72, элемента И 57, элемента ИЛИ 62. 30 Устройство р аб от ает следующим образомм.После включения питания триггеры 51-55;10. и входы 41-45 устройства З 5 обнулены, счетчик 22 установлен в состояние не равное нулю. Генератор 1 выдает непрерывную последовательность импульсов, Мультиплексор 3 и элемент И 2 закрыты сигналом низкого 40 уровня с выхода триггера 9Элементы И 16-20 закрыты сигналом .низкого уровня с выхода триггера 10 и на выходах 46-50 устройства - сигналы низкого уровня, что соответст вует отсутствию заявок на обслуживание. Система, определив количество свободных процессоров, через входы 24 установки заносит в счетчик 22 двоичный код этого числа и импульс ным сигналом, подаваемым на вход 23, включает устройство в режим набора заявок. В режиме набора заявок возможны следующие варианты: 55 1. До момента подачи сигнала на вход 23 запросы на входы 30-34 не поступали, 42, Количество поступивших на входы 30-34 запросов больше числа свободных процессоров (кода в счетчике 22),3, Количество поступивших на входы 30-34 зяпоосов меньше числа свободных процессоров,4, Количество поступивших запросов равно числу свободных процессоров. Вариант 1.При отсутствии запросов на входах 30-34 триггеры 51-55 блока 40 заявок находятся в исходном (нулевом) состоянии и на выходах 35-39 блока 40 заявок сигналы также нулевые. На выходе элемента И-НЕ 8 - единичный сигнал.Импульсы с генератора 1 проходят через мультиплексор 3 на выход 11 110000, который никуда не подключен. Элемент И 2 закрыт нулевым сигналом с выхода элемента ИПИ 7.Устройство ожидает поступления запросов.При поступлении запросов на входы 30-34 блок 40 запросов выбирает запрос с наивысшим приоритетом и на соответствующем выходе 35-39 устанавливается единичный сигнал 1 . Единичный сигнал также ус.тановится на выходе элемента ИЛИ 7, На выходе элемента И-НЕ 8 устанавливается нулевой сигнал, а на счетный вход (вычитающий) счетчика 22 через элемент И 2 проходят импульсы с генератора 1.Единичный сигнал с выходов 35-39 поступает также на адресные входы мультиплексора 3, и импульс с генератора через мультиплексор 3 уста,новит в единичное состояние соответ 1 ствующий триггер 11-15 выходного регистра и в нулевое - соответствующий триггер 51-55 (через входы 25- 29) входного регистра. Блок 40 заявок выбирает из оставшихся запросов наиболее приоритетный.Дальнейшая работа устройства соответствует вариантам 2 и 3.Работу устройства в вариантах 2 и 3 рассмотрим на примере. Перед подачей на вход 23 сигнала в счетчик 22 было записано число 2 т.е, система имеет два свободных процессора для обслуживания запросов. На входы 30, 33. 34 одновременно поступили сигналы запроса, устано 1126961вйвшие триггеры 51, 54, 55 в единичное состояние. На выходе элементов ИЛИ 4 и 7 устанавливаются единичные сигналы, а на выходе элемента И"НЕ 8 нулевой сигнал, Блок 540 заявок выбирает, как наиболееприоритетный, запрос с триггера51 и выставляет на выходе 35 единичный сигнал. Ближайший импульс с генератора 1 вычитает единицу из содержимого счетчика 22, устанавливает триггер 11 выходного регистрав единичное состояние и сигналомс соответствующего выхода мультиплексора 3 через вход 25 сбрасывает 5триггер 51 в нулевое состояние,.После сброса триггера 51 блок40 заявок выбирает запрос с триггера 54 и выставляет единичный сигнална выходе 38, триггер 14 устанавли 20вается в единичное состояние, атриггер 54 - в нулевое, Содержимоесчетчика 22 после вычитания единицы,становится равным нулю, т.е. коли 21чество запросов в выходном регистреравно количеству свободных процес соров, Ва выходе элемента ИЛИ 21также устанавливается нулевой сигнал, который изменяет уровень сигнала на выходе элемента И-НЕ 8 с нуле- ЗОвого на единичный. По изменению(по положительному Фронту) сигналана выходе элемента И-НЕ 8 триггер9 устанавливается в нулевое состояние, запрещая прохождение импульсов 35с генератора 1 через мультиплексор3 и элемент И 2, а триггер 10устанавливается в еднничное состояние, разрешая прохождение запросовс триггеров 11-5, через элементы40И 16-20 на выходы 46-50 устройстваВ результате на выходах 46 и 50 будут единичные сигналы, а на остальных - нулевые. Запрос по входу 34остается не обслуженным в этом цикле,45По окончании обслуживания запросовсистема подает сигналы сброса триггеров 11 и 14 на входы 41 и 44,устанавливает через вход 23 в счетчик 22 новое число свободных процес- Исоров и подает сигнал запуска навход 23.Пусть для следующего цикла (вариант 3) система записана в.счетчик 22 число 4 щ и дополнительно поступил запрос по входу 31, В соот ветствии с И блок 40 запросов выделил из поступивших запросов запрос,поступивший по входу 34, как более ранний, хотя и менее приоритетный, Соответственно единичный сигнал установлен на выходе 39 блока 40 запросов. После подачи сигнала запуска на вход 23 устройство работает аналогично вышеописанному, После сброса запроса с триггера 55 блок 40 запроса выставит единичный сигнал на выходе 36 (соответствующий запросу, записанному в триггер 52) не сразу, а через время равное времени задержки цепи: элемент НЕ 72 - элемент И 57 - элемент ИЛИ 62, На это время на выходе элемента ИЛИ 4 установится нулевой сигнал для исключения ложного срабатывания триггеров 9 и 10. По этому сигналу применяется схема, состоящая из элемента 5 задержки,одновибратора 6 и элемента ИЛИ 7, При появлении на выходе элемента ИЛИ 4 отрицательного фронта одновибратор 6 вырабатывает единичный импульс, длительность которого не менее воемени задержки пепи. элемент НЕ 72 - элемент И 57 элемент ИЛИ 62 и если нулевой сигнал на выходе элемента ИЛИ 4 вызванпереходом единичного сигнала с менее приоритетного выхода блока 40 запросов на более приоритетный, то на выходе элемента ИЛИ 7 будет удержан единичный сигнал и ложного срабатывания триггеров 9 и 10 не произойдет,После установки в единичное состояние триггера 12, триггер 52 сбрасывается и так как запросов большенет, то на выходах 35-39 блока 40запросов устанавливаются нулевыесигналы. По переходу сигнала из единицы в нуль на выходе элемента ИЛИ 4одновибратор 6 вырабатывает единичный импульс, но так как нулевойсигнал имеет длительность большую,чем длительность вырабатываемогоодновибратором 6 импульса, то сигнална выходе элемента ИЛИ 7 переходитиз единицы в нуль и через элементИ-НЕ 8 устанавливает фронтом триггер9 в нулевое состояние а триггер10 - в единичное. На выходы 46-50поступает содержимое триггеров11-15, единичные сигналы с триггеров12 и 15 и нулевые с остальных.По завершению обслуживания этихзапросов система устанавливает триггеры 12, 15 в нулевое состояниесигналом на входы 42, 45,26961 акав 87 ч 1/38 Тираж 698 ое ал ППП "Патен", г.Ужго л.Проектн 7 11Вариант 4 работы устройства представляет собой одновременное выполнение вариантов 2 и 3,Таким образом, введение в устройство приоритета совокупности дополнительных элементов и связей позволяет, сохраняя быстродействие и относительную дисциплину обслуживания заявок, выдавать на выходы максимально приближенное к заданному количе ство запросов, что выгодно отличаетпредлагаемое устройство от устройства-прототипа.