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

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

Иллюстрации

Показать все

Реферат

 

СОЮЗ СОВЕТСНИХ

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

РЕСПУБЛИК

А1 (19) (11) (51) 4 G 06 F 9/46 с

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

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

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

llO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3862104/24-24 (22) 21.02.85 (46) 30.12,86. Бюл, К- 48 (72) В.А.Батраков, С.В.Трунков, А.И.Квасов, А.В.Мурин и С.В.Назаров (53) 681.325 (088. 8) (56) Авторское свидетельство СССР

1)» 855663, кл. G 06 F 9/46, 1981.

Авторское свидетельство СССР

Ф 1068941, кл. G 06 F 9/46, 1983, (54)(57) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ

ОЧЕРЕДИ ЗАПРОСОВ, содержащее регистр приоритета, два элемента ИЛИ,, элемент задержки и каналы, каждый из которых, кроме последнего канала,содержит регистр приоритета,. блок элементов ИЛИ, три блока элементов И,схему сравнения и элемент НЕ, а последний канал содержит регистр приоритета, блок элементов ИЛИ, два блока элементов И и схему сравнения, причем в каждом канале выход регистра приоритета соединен с. первым входом первого блока элементов И канала,спервым входом схемы сравнения канала, и, кроме последнего канала, с первым входом второго блока элементов И канала, вход сброса устройства подключен к входу сброса регистра приоритета каждого канала, .выход схемы сравнения каждого ,канала соединен .с первым входом третьего блока элементов И своего канала, и кроме последнего канала, с вторым входом второго блока элементов И своего;канала и через элемент НЕ своего канала с вторым входом третьего блока элементов И последующего канала, первый вход блока элементов ИЛИ каждого канала соединен с выходом третьего блока элементов И своего канала, второй и третий входы блока элементов

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

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

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

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

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

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

1280630 первого веходов регистров метки, атрибута, в ходам приоритета и адреса подключены к аданалов, ресному входу устройства, второй вход о канала, первого элемента ИЛИ соединен с втоэлемен- рым входом первого блока элементов группы И каждого канала.

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

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

Сеть 38M представляет собой совокупность вычислительных машин и терминалов, соединенных с помошью средств передачи цанных в ециную систему. В определенном смысле ее можно рассматривать как совокупность узлов, выполняющих те или иные функции. Узлы сети, которые выполняют функции ретрансляции информации,циркулирующей в сети, называются коммутационными. В процессе функционирования в узлах коммутации образуются очереди сообщений. Выбор очередного сообщения для передачи осуществляется в соответствии с присвоенными обо.бщенными приоритетами. Значение обобщенного приоритета определяется важ.ностью сообщения (код статического приоритета) и временем нахождения сообщения в сети (код динамического

,.приоритета).

Обобщенный приоритет сообщения формируется следующим образом.

В сети функционирует система ед& ного времени (СЕВ). Любое сообщение, поступающее в сеть и циркулирующее

2 между узлами коммутации, в адресной части содержит код адреса (имя сообщения), код приоритета (статический приоритет),код атрибута (код, соответствующий времени нахождения сообщения в сети в момент начала передачи его из i-ro узла) и код метки (код таймера СЕВ в момент начала передачи сообщения .из i-го узла). Тогда

10 динамический приоритет сообщения в момент прихода на (i + 1)-й узел определяется соотношением где (t<) — код атрибута;

1 ;) — код, соответствующий времени, затраченному на пе20 редачу сообщения из i-го узла в (i + 1)-й узел.

Код,соответствующий времени, затраченному на передачу сообщения из

i-го узла в (i + 1) -й узел определя25 ется соотношением: где (К,, ) — код таймера СЕВ е момент

ЗО приема сообщения на (i + 1) -й узел;

К; 1 — код метки.

Если во время передачи сообщения произошло восстановление таймера

35 СЕВ (в связи с переполнением), то код (7;) определяется соотношением:

40 где К вЂ” код таймера СЕВ, после которого осуществляется его восстановление.

Соотношение (2) реализуется путем сложения на сумматоре прямого кода

1280630 (К;„1 с дополнительным кодом(К;1, а соотношение (3) — путем сложения на сумматоре прямого кода (К;,Д с обратным кодом $K;g . Полученное сообщение ставится в очередь на обслуживание в соответствии. с его обобщенным приоритетом (старшие разряды — код статического приоритета, младшие разряды — код динамического приоритета).

Время. нахождения сообщения на узле 10 коммутации подсчитывается путем добавления к коду динамического приоритета тактовых импульсов таймеров СЕВ (число поступивших импульсов будет соответствовать времени нахождения со-15 общения в узле коммутации до момента выдачи его снова в сеть). Первым на обслуживание выбирается сообщение, имеющее максимальный обобщенный приоритет. 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 элементов ИЛИ, вход 45

38 запроса устройства, вход 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. Высокий потенI циал с единичного выхода указанного триггера выдается на выход 43 устройства, сигнализируя о занятости устройства.

К рассматриваемому моменту времени в регистры 28, 29, 10 и 30 через адресный вход 54 устройства занесены соответственно код таймера СЕВ в момент начала передачи сообщения,код атрибута данного сообщения, код статического приоритета данного сообщения и код адреса (имя данного сообщения), т.е. информация, содержащаяся в адресной части принятого сообщения.Разрядность указанных регистров определяется принятым форматом адресной части сообщения.

Состояние таймера СЕВ, выдаваемое на вход 38 устройства, поступает на первую группу входов схемы 27 сравнения и группу входов блока 32 элементов И.

Сигнал, поступающий на вход 42 устройства,одновременно приходит на вход элемента 23 задержки и вход блока 32 элементов И, разрешая занесение кода таймера СЕВ на данный момент времени на накапливающий сумматор 31, Содержимое регистра 28 поступает на вторую группу входов схемы 27 сравнения, которая имеет на выходе высокий потенциал, открывающий по первому входу элемент И 36 только в случае, если код метки меньше кода таймера

СЕВ, При этом сигнал с выхода элемента 23 задержки, пройдя через элемент

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

1280630 6 щегося в регистре. 2 и счетчике 16 своего канапа °

При приходе перво го сообщения все схемы 7 вырабатывают сигнал.Для каждого канапа, кроме последнего, сигнал с выхода схемы 7 сравнения открывает блок 9 элементов И своего канала,обеспечивая перезапись содержимого регистра 15. регистра 2 и счетчика 16

f0 своего канала через блок 3 элементов

ИЛИ последующего канала соотв1тственно в регистр 15, регистр 2 и счетчик 16 паследуюше го канала. Этот же сигнал, пройдя через элемент НЕ 8 своего канала, закрывает блок 5 элементов И последующего канала с целью блокировки записи информации, поступающей на нега с группы 47 выходов

БФП, Кроме того, сигнал с выхода схемы 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 выходов БФП, т.е. выдачу кода обобщенного приоритета (старшие разряды — кад статического приорите- 10 та, младшие — код динамического при оритета). Содержимое регистра 30, регистра 10 и сумматора 31 поступает на соответствующие выходы группы

47 выходов БФП, 45

Код обобщенного приоритета с группы 48 выходов БФП поступает на первые группы входов схем 7 сравнения, на вторые группы входов которых поступа —. ют коды с регистров 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 первого канала всетда будет находиться код адерса (имя} !О сообщения,имеющего максимальный обоб1 щенный приоритет. Этот код выдается на выход 53 устройства. Пока сообщения находятся в очереди, значение их динамических приоритетов изменяется 15 путем добавления тактовых импульсов

СЕВ, поступающих на счетный вход счетчиков 16 через элементы И 17 с входа

40 устройства, Сигнал на выдачу обобщенного при- 20 оритета поступает на вход 41 устройства,проходит через элемент ИЛИ t1 и устанавливает в единичное состояние триггер 21. Высокий потенциал с единичного выхода указанного триггера выдается на выход 43 устройства,сигнализируя о занятости устройства.

Одновременно сигнал на выдачу обобщенного приоритета поступает на вход элемента ИЛИ 12, сигнал с выхода30 которого устанавливает в единичное состояние триггер 22. Нулевой потенциал с инвереного выхода указанного триггера поступает на вход элемента

И 17 каждого канала, запрещая на пе- 35 риод перестройки очереди поступление тактовых импульсов СЕВ, 30 8

Сигнал с входа 41 устройства открывает блоки 4 элементов И, и коды статического приоритета (содержимое регистра 2 первого канала) и динамического приоритета (содержимое счетчика 16 первого канала).выдаются на выход 52 устройства. Эта информация используется при формировании адресной части выдаваемого в сеть сообщения. По этому же сигналу осуществля. ется сдвиг содержимого регистров 15 и 2 и счетчика 16 последующего канала, кроме первого, через блок 4 элементов И этого канала и блок 3 элементов ИЛИ предыдущего канала соответственно в регистры 15 и 2 и счетчик 16 предыдущего канала. Одно" временно этот сигнал через элемент

ИЛИ 6 последнего канала поступает на вход установки в нуль триггера

t9 последнего канала. Кроме того, он поступает на входы элементов И 20

1 кроме первого канала, и, если триггеры 19 своих каналов находятся в нулевом состоянии, уетанавливает через элементы ИЛИ 6 предыдущих каналов в нулевое состояние триггеры

l9 предыдущих каналов.

Сигнал с выхода элемента ИЛИ 12 через интервал времени, определяемый параметрами элемента 13 задерж-. ки, устанавливает в нулевое состояние триггеры 21 и 22, сигнализируя о готовности устройства к работе и разрешая поступление на счетчики

16 тактовых импульсов СЕВ.

1280б30

1280630 г

Составитель М.Сорочан

Редактор А.Лежнина Техред Л.Сердюкова Корректор А.Обручар

Заказ 7068/55 Тираж б71 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб,, д.4/5

Производственно-полиграфическое предприятие, г.ужгород, ул.Проектная,4