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

..Изобретение относится к вычисли тельной технике и может быть исполь зовано в многопроцессорных системах обслуживания заявок. Устройство приоритета по авт.св. № 721816 содержит входной триггерны il-разрядный регистр (П- число запр сов), п двухвходовьх злементоз ИЛИ, 11 двухвходовых элементов И, (П-1) элементов НЕ и п входовые элементы Hj к .первым входам которых подключены единичные выходы триггеров, Нулевой выход триггера .п-го разряда соединен с (П+1)-ми входамиП-входо вых элементов И разрядов от (п + О-г до(1й-го включительно. Первый вход каждого двухвходового элемента ИЛИ подсоединен к выходу П-входового элемента И своего разряда, а второй вход - к выходу двухвходового 3JJ:eMe та И, а выход каждого двухвходового элемента ИЛИ соединен, с первым входом двухвходов.ого элемента И и с соответствующим выходом устройства, каждьш из которьк до (П-1)-го включительно подключен к входу элемента НЕ своего разряда. Второй выход каж дого двухвходового элемента И соеди нен с едитшчньич выходом триггера входного регистра своего разряда„ Выходы П-входовых элементов И каждо го П-го и всех предьздущих разрядов подключены к выходу элемента НЕ (П+1)-го разряда. Недостаток устройства-прототипа заключается в том, что на обслуживание вьщается только одна заявка и только после обслуживания предыду щей, тогда как в многопроцессорной системе одновременно могут обслуживаться несколько заявок, количество которых ограничено количеством свободных процессов в системе или чис лом поступивших запросов на обслужи вание . I Цель изобретения расширение функциональных возможностей устройства за счет вьщачи максимально при ближенного к заданному количества запросов. Поставленная цель достигается тем, что в устройство приоритета по авт.св. № 721816 дополнительно введены п двухвходовых элементов И, выходной Г) -разрядный триггерный регистр, два триггера, три элемента ШТИ., элемент задержки, одновибратор, элемент И-НЕ, счетчик элемент 12 И, мультиплексор и генератор, выход которого подключен к первому входу дополнительного элемента И и перв.ому входу мультиплексора, каждый вход группы йходов которого соединен с выходом соответствующего из Я двухвходовых элементов 1ШИ и соответствующим входом первого дополнительного элемента ИЛИ, вьосод которого соединен с входами элемента задержки и одновибратора, выходы которых соединены с соответствую цими входами второго дополнительного элемента ИЛИ, выход которого подключен к первому входу элемента И-НЕ и второму входу дополнительного элемента И, третий вход которого соединен с вторым входом мультиплексора и выходом первого триггера, первьш и второй входы которого соединены соответственно с первым и вторым входами второго триггера, первый вход которого подключен к первому входу сброса устройства, а выходы мультиплексора подключены к первым входам выходного и входного П-разрядных триггерных регистров, вторые зходь которых являются соответствуюшиг 1 входами сброса устройства, выходы выходногоh -разря,цного трнггерного регистра соединены с первызш входами П дополнительных двухвходовых элементов И, вторые входы которых подключены к выходу второго триггера, второй вход которого сое.динен с выходом элемента И-НЕ, второй вход которого подключен к выходу третьего дополнительного элемента ИЛИ, входы которого соединены с выходами счетчика, вход которого подключен к выходу дополнительного элемента И, а группа входов является группой установочньк входов ус тройства 5 вых-оды п дополнктех:. двухвходовых элементоа И являются выходами устройства. Указанная совокупность элементов и связей позволяет осуществить выдачу в систему максимально приближепное заданному количество запросов путем последовательной записи в выходной триггерный регистр запросов в порядке возрастания приоритетов до момента набора количества запросов, соответствующего заданному на счетчике, или до момента, когда все поступившие запросы записаны в выходной триггерный регистр.

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

Устройство содержит генератор 1, элемент И 2, мультиплексор 3,У1 -вхо довой элемент ИЛИ 4 элемент 5 задержки, опновибратор 6 элемент ИЛИ 7. элемент И-НЕ 8, триггеры 9 и 10. триггеры 11-15 выходного регистра, элементы И 16-20, элемент . ИЛИ 21, счетчик 22, вход 23 сброса, входы 24 установки, входы 25-29 входы 30-34 сброса, выходы 35-39, блок 40 заявок, входы 41-45, выходы 46-50.

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

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

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

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

После включения питания триггеры 51-55;10 и входы 41-45 устройства обнулены, счетчик 22 установлен в состояние не равное нулю. Генератор 1 вьщает непрерывную последовательность импульсов. Мультиплексор 3 и элемент И 2 закрыты сигналом низкого уровня с выхода триггера 9

Элементы И 16-20 закрыты сигналом .низкого уровня с выхода триггера Ю и на выходах 46-50 устройства - cm налы низкого уровня, что соответствует отсутствию заявок на обслуживание. Система, определив количество свободных процессоров, через входы 24 установки заносит в счетчик 22 двоичный код этого числа и импульсным сигналом, подаваемым на вход 23 включает устройство в режим набора заявок.

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

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

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

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

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

Вариант 1.

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

Импульсы с генератора 1 проходят через мультиплексор 3 на выход 000...О, который никуда не подключен. Элемент И 2 закрыт нулевым сигналом с выхода элемента ИЛИ 7.

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

При поступлении запросов на входы 30-34 блок 40 запросов выбирает запрос с наивысшим приоритетом и на соответствующем выходе 35-39 устанавливается сигнал 1 . Единичный сигнал также установится на выходе элемента ИЛИ 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 одновременно поступили сигналы запроса, установнпвшие триггеры 51, 54, 55 в единичное состояние. На выходе элементов ИЛИ 4 и 7 устанавливаются единичные сигналы, а на выходе элемента И-НЕ 8 нулевой сигнал. Блок 40 заявок вь бирает, как наиболее приоритетный, запрос с триггера 51 и выставляет на выходе 35 единич ный сигнал. Ближайший импульс с генератора 1 вычитает единицу из содержимого счетчика 22, устанавливает триггер 11 выходного регистра в единичное состояние и сигналом с соответствующего выхода мультиплексора 3 через вход 25 сбрасывает триггер 51 в нулевое состояние, После сброса триггера 51 блок 40 заявок выбирает запрос с триггера 54 и выставляет единичный сигнал на выходе 38, триггер 14 устанавливается в единичное состояние, а триггер 54 - в нулевое. Содержимое счетчика 22 после вычитания единицы становится равным нулю, т,е, количество запросов в выходном регистре равно количеству свободных процес соров. На выходе элемента ИЛИ 21 также устана зливается нулевой сигнал, который изменяет уровень сигна ла на выходе элемента И-НЕ В с нуле вого на единичный. По изменению (по положительному фронту) сигнала на выходе элемента И-НЕ 8 триггер 9 устанавливается в нулевое состояние, запрещая прохождение импульсов с генератора 1 через мультиплексор 3 и элемент И 2, а триггер 10 устанавливается в единичное состояние, разрешая прохождение запросов с триггеров 11-15. через элементы И 16-20 на выходы 46-50 устройства, В результате на выходах 46 и 50 будут единичные сигналы, а на остальных - нулевые. Запрос по входу 34 остается не обслуженным в этом цикле,45 чем

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

соров и подает сигнал запуска на вход 23„

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

одновибратором 6 импульса, то сигнал на выходе элемента ИЛИ 7 переходит из единицы в нуль и через элемент И-НЕ 8 устанавливает фронтом триггер

10 - в единичное. На выходы 46-50 поступает содержимое триггеров 11-15, единичные сигналы с триггеров 12 и 15 и нулевые с остальньк.

По завершению обслуживания этих запросов система устанавливает триггеры 12, 15 в нулевое, состояние сигналом на входы 42, 45. поступивший по входу 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 вьтрабатывает единичный импульс, но так как нулевой сигнал имеет длительность большую, длительность вьзэабатываемого нулевое состояние, а триггер

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

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

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

J 1гП ffl W Ш

юшшшш

Z

27

LH.