Устройство для формирования очереди запросов

"7 М,ЬСТВ И Н АВТОРСК 9 48С.В.Трунков,ин и С.В,Назаров тво СССР198 1.о СССР6, 1983,етел Р 9/ ельс Р 9а ОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ(54)(57) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯОЧЕРЕДИ ЗАПРОСОВ, содержащее регистрприоритета, два элемента ИЛИ элемент задержки и каналы, каждый из которых, кроме последнего канала,содержит регистр приоритета,. блок элементов ИЛИ, три блока элементов И,схемусравнения и элемент НЕ, а последнийканал содержит регистр приоритета,блок элементов ИЛИ, два блока элементов И и схему сравнения, причем в каждом канале выход регистра приоритетасоединен с. первым входом первого блока элементов И канала,спервым входомсхемы сравнения канала, и, кроме последнего канала, с первым входом второго блока элементов И канала, входсброса устройства подключен к входусброса регистра приоритета каждогоканала, .выход схемы сравнения каждогоканала соединен .с первым входом третьего блока элементов И своего канала,икроме последнего канала, с вторымвходом второго блока элементов И своего;канала и через элемент НЕ своегоканала с вторым входом третьего блока элементов И последующего канала,первый вход блока элементов ИЛИ каждого канала соединен с выходом третьего блока элементов И своего канала,второй и третий входы блока элементовИЛИ каждого канала, кроме первого ипоследнего каналов, соединены соответственно с выходом второго блокаэлементов Ипредыдущего каналаи с выходом первого блока элементов И последующего канала, второй вход блокаэлементов ИЛИ первого канала подключен к выходу первого блока элементов И последующего канала, второи входблока элементов ИЛИ последнего канала соединен с выходом второго блокаэлементов И предыдущего канала,информационный вход регистра приоритетакаждого канала подключен к выходу блока элементов ИЛИ своего канала, выхопервого блока элементов И первого канала является выходом приоритета устройства, выход второго элемента ИЛИподключен к входу первого элементазадержки, о т л и ч а ю щ е е с ятем, что, с целью расширения функциональных возможностей за счет фор. -мирования динамического приоритета,в устройство введены два триггера,четыре элемента задержки, схема сравнения, регистр метки, регистр атрибута, регистр адреса, накапливающийсумматор, четыре блока элементов И,блок элементов ИЛИ, элемент И, а вкаждый канал, кроме первого, введены элемент ИЛИ, регистр адреса, счетчик, три элемента И и триггер, а впервый канал введены элемент ИЛИ,регистр адреса, счетчик, элементИ и триггер, причем вход запросаустройства подключен к второму входу элементов И первого блока и к пер"вому входу схемы сравнения, выход1280 б схемы сравнения подключен к первому входу элемента И, выход которого со единен со счетным входом младшего разряда накапливающего сумматора, выход первого блока элементов И подключен к первому входу накапливающего сумматора, первый выход регистра метки соединен с вторым входом схемы сравнения, второй выход регистра метки подключен к первому входу второго блока элементов И,. выход которого соединен с первым входом блока элементов ИЛИ, выход регистра атрибута подключен к первому входу третьего блока элементов И, выход которого соединен с вторым входом блока элементов ИЛИ, выход, которого соединен с вторым входом накапливающего сумматора, выход которого соединен с первым входом четвертого блока элементов И, с третьим входом третьего блока элементов И всех каналов, кроме первого канала, и вторым входом третьегоблока элементов И первого канала,выход регистра приоритета соединен с первым входом четвертого блока элементов И, с третьим входом третьего блока элементов И всех каналов,кроме первого канала, и вторым входом третьего блока элементов И. первого канала, выход регистра адреса соединен с третьим входом третьего блока элементов И всех каналов, кроме первого канала, и вторым входом,третьего блока элементов И первого канала, вход индикации приема сообщения устройства подключен к первому входу первого элемента ИЛИ, к первому входу первого блока элементов И и к входу второго элемента задержки, выход которого соединен с вторым входом элемента И и с входом третьего элемента задержки, выход которого соединен с вторым входом второго блока элементов И и с входом четвертого элемента задержки, выход которого соединен с вторым входом третьего блока элементов И и с входом пятого элемента задержки, выход которого ,подключен к первому входу второго элемента ИЛИ и к второму входу четвертого блока элементов И,выход четвертого блока элементов И соединен с вторыми входами схем сравнениявсех каналов, вход индикации выдачикода приоритета устройства соединенс вторым входом первого элемента ИЛИи с вторым входом второго элемента 30ИЛИ; выход которого подключен к входу установки в единичное состояние второго триггера, выход первого элемента задержки соединен с входами установки в нулевое состояние первого и второго триггеров, выход первого элемента ИЛИ соединен с входом установки в единичное состояние первого триггера, прямой выход которого является выходом прерывания устройства, выход блока элементов ИЛИ каждого канала соединен с информационным входом регистра адреса своего канала, выход которого, кроме первого канала, подключен к первому входу первого блока элементов И и, кроме последнего канала, к первому входу второго блока элементов И своего канала, выход регистра адреса первого канала подключен к выходу адреса максимального обобщенного запроса устройства, выход блока элементов ИЛИ каждого канала соединен с информационным входом счетчика своего канала, выход которого подключен кпервому входу первого блока элементов И своего какала, к первому входу схемы сравнения своего канала, и, кроме последнего канала, к первому входу вто-. рого блока элементов И своего канала, выход схемы сравнения каждого канала, кроме первого, подключен к первому входу второго элемента И канала,выход схемы сравнения первого канала подключен к входу установки в единичное состояниетриггера первого канала, единичный выход триггера каждого канала соединен с первым входом первого элемента И своего канала и, кроме последнего канала, с вторым входом второго элемента И последующего канала, инверсный выход второго триггера подключен к вторым входам первых элементов И каналов, вход сетевого единого времени устройства подключен к третьим входам первых элементов И каналов, выходы которых соединены со счетными входами счетчиков своих каналоввторой вход первого элемента ИЛИ соединен с первыми входами третьих элементов И каналов, кроме первого канала, и вторым входом элемента ИЛИ последнего канала, вход сброса устройства подключен к входам сброса регистров адреса и счетчиков каналов ипервым входам элементов ИЛИ каналов,выходы которых соединены с входами установки в нулевое состоянйе триггеров своих каналов, инверсные выхо ды триггеров каналов, кроме канала, подключены к вторым третьих элементов И своих к выходы которых кроме первогсоединены с вторыми входами тов ИЛИ предыдущих каналов,1280630первого веходов регистров метки, атрибута, в ходам приоритета и адреса подключены к аданалов, ресному входу устройства, второй вход о канала, первого элемента ИЛИ соединен с втоэлемен- рым входом первого блока элементов группы И каждого канала.Изобретение относится к вычислительной технике и может быть использовано для формирования очереди запросов в соответствии с их приоритетами,Цель изобретения - расширение функциональных возможностей за счет формирования динамического приоритетасообщения (кода запроса) в моментпоступления в устройство и измененияего значения при нахождении в нем,Необходимость н этом возникает,например, при решении задачи выбора изочереди сообщений узла коммутации сети сообщения с максимальным приоритетом. Приоритет сообщения н .этом случае зависит от времени нахождения сообщения в сети.Сеть ЭВ 11 представляет собой совокупность вычислительных машин итерминалов, соединенных с помощьюсредств передачи цанных в ециную систему. В определенном смысле ее можно рассматривать как совокупностьузлов, выполняющих те или иные функции, Узлы сети, которые выполняютфункции ретрансляции информации,циркулирующей в сети, называются коммутационными. В процессе функционирования в узлах коммутации образуютсяочереди сообщений. Выбор очередногосообщения для передачи осуществляется в соответствии с присвоенными обобщенными приоритетами, Значение обобщенного приоритета определяется важ.ностью сообщения (код статическогоприоритета) и временем нахождениясообщения в сети (код динамического,приоритета).Обобщенный приоритет сообщенияформируется следующим образом.В сетй функционирует система ед- ного времени (СЕВ). Любое сообщение,поступающее в сеть и циркулирующее 2между узлами коммутации, в адресной части содержит код адреса (имя сооб" щения), код приоритета (статический приоритет),код атрибута (код, соответствующий времени нахождения сообщения в сети в момент начала передачи его из -го узла) и код метки (код таймера СЕВ в момент начала передачи сообщения .из 1-го узла). Тогда 1 О динамический приоритет сообщения вмомент прихода на (х + 1)-й узел определяется соотношениемгде Г - код атрибута;17;1 - код, соответствующий времени, затраченному на пе редачу сообщения из х-гоузла в ( + 1)-й узел,Код,соответствующий времени, затраченному на передачу сообщения из -го узла в ( + 1) -й узел определя ется соотношением:(2)где СВ ) - код таймера СЕВ е моментЗО приема сообщения на(3. + 1)-й узел;К; - код метки.Если во время передачи сообщенияпроизошло восстановление таймера35 СЕВ (в связи с переполнением), токод 7;1 определяется соотношением:40где К - код таймера СЕВ, после которого осуществляется его восстановление.Соотношение (2) реализуется путемсложения на сумматоре прямого кодаК;+,1 с дополнительным кодомК;1, асоотношение (3) - путем сложения насумматоре прямого кода К;,Д с обратным кодом К;1 . Полученное сообщение ставится в очередь на обслуживание в соответствии. с его обобщеннымприоритетом (старшие разряды - кодстатического приоритета, младшие разряды - код динамического приоритета).Время. нахождения сообщения на узле 10коммутации подсчитывается путем добавления к коду динамического приоритета тактовых импульсов таймеров СЕВ(число поступивших импульсов будетсоответствовать времени нахождения со общения в узле коммутации до моментавыдачи его снова в сеть). Первым наобслуживание выбирается сообщение,имеющее максимальный обобщенный приоритет. 20На фиг.1 изображена структурнаясхема устройства для формированияоереди запросов; на фиг.2 - структурная схема блока формирования приоритета.1Устройство содержит каналы 1,регистр 2 приоритета канала, блок 3элементов ИЛИ канала, блоки 4 и 5элементов И канала, элемент ИЛИ 6 30канала, схему 7 сравнения канала,элемент НЕ 8 канала, блок 9 элементов И канала, регистр 10 приоритета,элементы ИЛИ 11 и 12, элемент 13 задержки, блок 14 формирования приоритета (БФП), регистр 15 адреса канала, счетчик 16 канала, элементы И17 и 18 канала, триггер 19 канала,элемент И 20 канала, триггеры 21и 22 , элементы 23 - 26 задержки, 40схему 27 сравнения, регистр 28 метки, регистр 29 атрибута, регистр 30адреса, накапливающий сумматор 31,блоки 32 - 35 элементов И, элементИ 36, блок 37 элементов ИЛИ, вход 4538 запроса устройства, вход 39 сбро-са устройства, вход 40 сетевого единого времени устройства, вход 41 индикации выдачи кода приоритета устройства, вход 42 индикации приемасообщения устройства, выход 43 прерывания устройства, входы 44 и 45 БФП,выход 46 БФП, группы 47 и 48 выходовБФП, входы 49 и 50 БФП, группу 51входов БФП, выход 52 приоритетаустройства, выход 53 адреса максимального обобщенного запроса устройства, адресный вход 54 устройства игруппу 55 входов БФП,Устройство работает следующим образом.В исходном состоянии регистры 2 и15, счетчик 16 через входы сброса обнулены сигналом, поступившим по входу39 устройства. Этот же сигнал черезэлементы ИЛИ 6 обнуляет триггеры 19,Устройство готово к работе.Возможны два режима работы: первый связан с приемом информации иформированием очереди, второй в , свыдачей информации и перестройкойочереди.гСигнал на прием сообщения (кодазапроса) поступает на вход 42 устройства, проходит через элемент ИЛИ11 и устанавливает в единичное состояние триггер 21. Высокий потенциал с единичного выхода указанноготриггера выдается на выход 43 устройства, сигнализируя о занятостиустройства.К рассматриваемому моменту времени в регистры 28, 29, 10 и 30 черезадресный вход 54 устройства занесенысоответственно код таймера СЕВ в момент начала передачи сообщения,кодатрибута данного сообщения, код статического приоритета данного сообщенияи код адреса (имя данного сообщения),т.е. информация, содержащаяся в адресной части принятого сообщения.Разрядность указанных регистров определяется принятым форматом адресной частисообщения.Состояние таймера СЕВ, выдаваемоена вход 38 устройства, поступает напервую группу входов схемы 27 сравнения и группу входов блока 32 элементов И,1Сигнал, поступающий на вход 42 устройства,одновременно приходит на входэлемента 23 задержки и вход блока 32элементов И, разрешая занесение кодатаймера СЕВ на данный момент временина накапливающий сумматор 31,Содержимое регистра 28 поступаетна вторую группу входов схемы 27 сравнения, которая имеет на выходе высокий потенциал, открывающий по первомувходу элемент И 36 только в случае,если код метки меньше кода таймераСЕВ, При этом сигнал с выхода элемента 23 задержки, пройдя через элементИ 36, поступает на счетный вход младшего разряда сумматора 31 и добавляетк его содержимому единицу, позволяяв дальнейшем реализовать соотношение128063 О 6щегося в регистре. 2 и счетчике 16своего канапа,При приходе первого сообщения всесхемы 7 вырабатывают сигнал.Для каждого канапа, кроме последнего, сигналс выхода схемь 1 7 сравнения открываетблок 9 элементов И своего канала,обеспечивая перезапись содержимого регистра 15, регистра 2 и счетчика 161 О своего канала через блок 3 элементовИЛИ последующего канала соответственно в регистр 15 , регистр 2 и счетчик 16 последующего канала. Этот жесигнал, пройдя через элемент НЕ 815 своего канала, закрывает блок 5 элементов И последующего канала с цельюблокировки записи информации, поступающей на него с группы 47 выходовБФП, Кроме того, сигнал с выхода схе 20 мы 7 сравнения первого канала поступает на вход установки в единицу триггера 19 первого канала, Для остальныхканалов сигнал с выхода схемы 7 сравнения поступает на вход элемента И18 своего канала, устанавливая в единичное состояние триггер 19 своегоканала, если триггер 19 предыдущего(2) . В противном случае, т, е. когда код метки больше кода таймера,единица к содержимому сумматора 31 не добавляется и на нем будет реализовываться соотношение (3).Сигнал с выхода элемента 23 задер жки поступает также на вход элемента 24 задержки, с выхода которого он проходит на вход элемента 25 задержки и второй вход блока 33 элементов И, разрешая выдачу содержимого регистра 28, снимаемого в обратном коде с второй группы вьходов указанного регистра через блок 33 элементов И и блок 37 элементов ИЛИ на вторую группу входов сумматора 31. В резуль тате сложения на сумматоре 31 получается код, соответствующий времени передачи данного сообшения,Сигнал с выхода элемента 25 задержки поступает на вход элемента 26 задержки и второй вход блока 34 элементов И, разрешая выдачу содержимого регистра 29 через блок 34 эле ментов И и блок 37 элементов ИЛИ на сумматор 31, В результате сложения на сумматоре 31 получается код,соответствующий времени нахождения данного сообщения в сети на данный момент времени (динамический приоритет) . Сигнал с выхода элемента 26 задержки поступает на вход блока 35элементов И, разрешая поступление35содержимого регистра 10 и сумматора31 на соответствующие выходы группы48 выходов БФП, т.е, выдачу кодаобобщенного приоритета (старшиеразряды - код статического приорите Ота, младшие - код динамического приоритета), Содержимое регистра 30,регистра 10 и сумматора 31 поступает на соответствующие выходы группы47 выходов БФП,45Код обобщенного приоритета с группы 48 выходов БФП поступает на первыегруппы входов схем 7 сравнения, навторые группь 1 входов которых поступа-.ют коды с регистров 2 и счетчиков 16своих каналов (старшие разряды - кодстатического приоритета, хранящийсяна регистре 2, младшие разряды - коддинамического приоритета, хранящийсяна счетчике 16), Схема 7 сравнениявырабатывает. сигнал на своем выходев том случае, если код обобщенногоприоритета, поступающего с группы48 выходов БФП, больше кода, храняканала находится в единичном состоянии, Нахождение триггера 19 в единичном состоянии сигнализирует о том, что в данном канале записана информация, и разрешает поступление тактовых импульсов СЕВ через элемент И 17 своего канала на счетный входсчетчика 16 своего канала.Сигналы с выхода схем 7 сравнения поступают также на блок 5 элементов Й своего канала, обеспечивая запись содержимого регистра 30, регистра 10, сумматора 31, снимаемого с группы 47 выходов БФП, через незаблокированный блок 5 элементов И (в данном случае первого канала) и блок 3 элементов ИЛИ данного канала соответственно в регистры 15 и 2 и счетчик 16 данного канала,Сигнал с выхода элемента 26 задержки через элемент ИЛИ 12 устанавливает в единичное состояние триггер 22 Нулевой потенциал с инверсного выхода указанного триггера поступает на вход элемента И 17 каждого канала, запрещая на период формирования очереди поступление тактовых импульсов СЕВ на счетный вход счетчиков 16,Сигнал с выхода элемента ИЛИ 12 через интервал времени, определяемый параметрами элемента 13 задержки,ус 7 12806танавливает в нулевое состояние триггеры 2 1 и 22, сигнализируя о готовности устройства к работе и разрешаяпоступление на счетчики 16 тактовыхимпульсов СЕВ. Далее в этом режимеустройство работает аналогично,размещая сообщения в очереди в соответствии с их обобщенными проритетами,В регистре 15 первого канала всетда будет находиться код адерса (имя) Юсообщения,имеющего максимальный обобщенный приоритет, Этот код выдаетсяна выход 53 устройства. Пока сообще"ния находятся в очереди, значение ихдинамических приоритетов изменяется 15путем добавления тактовых импульсовСЕВ, поступающих на счетный вход счетчиков 16 через элементы И 17 с входа40 устройства,Сигнал на выдачу обобщенного приоритета поступает на вход 41 устройства,проходит через элемент ИЛИ 11и устанавливает в единичное состояниетриггер 21. Высокий потенциал с единичного выхода указанного триггеравыдается на выход 43 устройства,сигнализируя о занятости устройства.Одновременно сигнал на выдачуобобщенного приоритета поступает навход элемента ИЛИ 12, сигнал с выхода 30которого устанавливает в единичноесостояние триггер 22. Нулевой потенциал с инвереного выхода указанноготриггера поступает на вход элементаИ 17 каждого канала, запрещая на период перестройки очереди поступлениетактовых импульсов СЕВ,30 8Сигнал с входа 41 устройства открывает блоки 4 элементов И, и коды статического приоритета (содержимое регистра 2 первого канала) и динамического приоритета (содержимое счетчика 16 первого канала) выдаются на выход 52 устройства. Эта информация используется при формировании адресной части выдаваемого в сеть сообщения, По этому же сигналу осуществляется сдвиг содержимого регистров 15 и 2 и счетчика 16 последующего канала, кроме первого, через блок 4 элементов И этого канала и блок 3 элементов ИЛИ предыдущего канала соответственно в регистры 15 и 2 и счетчик 16 предыдущего канала. Одно" временно этот сигнал через элемент ИЛИ б последнего канала поступает на вход установки в нуль триггера 19 последнего канала. Кроме того, он поступает на входы элементов И 201 кроме первого канала, и, если триггеры 19 своих каналов находятся в нулевом состоянии, уетанавливает через элементы ИЛИ 6 предыдущих каналов в нулевое состояние триггеры 19 предыдущих каналов. Сигнал с выхода элемента ИЛИ 12 через интервал времени, определяемый параметрами элемента 13 задержки, устанавливает в нулевое состояние триггеры 21 и 22, сигнализируя о готовности устройства к работе и разрешая поступление на счетчики 16 тактовых импульсов СЕВ, 1280 б 301280630 Составитель М,Сорочанактор А.Лежнина Техред Л.Сердюкова Корректо учар ака 4/5 Производственно-полиграфическое пред тие, г.ужгород оектна 068/55 ВНИИПИ по 11303Тираж б 71Государственного коми елам изобретений и от Москва, Ж, Раушск Подписиоа СССРтий наб., д.