Устройство для формирования очереди запросов Советский патент 1986 года по МПК G06F9/50 

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

четвертого блока элементов И,выход четвертого блока элементов И соединен с вторыми входами схем сравнения всех каналов, вход индикации выдачи кода приоритета устройства соединен с вторым входом первого ЭJfeмeнтa ИЛИ и с вторым входом второго элемента

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

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

1

Изобретение относится к вычислительной технике и может быть использовано для формирования очереди запросов в соответствии с их приоритетами.

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

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

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

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

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

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

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

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

15

tu-l Ы-ьИ,

(1)

где ti - код атрибута;

- код, соответствующий времени, затраченному на пе- 20редачу сообщения из i-ro

узла в (i + 1)-й узел. Код,соответствующий времени, затраченному на передачу сообщения из i-ro узла в (i + 1)-й узел определя- 25 ется соотношением:

i 4, -М,

(2)

Д L S tJ код таймера СЕВ в момент приема сообщения на

(i + 1)-й узел;

К; - КОД метки.

Если во время передачи сообщения произошло восстановление таймера СЕВ (в связи с переполнением), то код определяется соотношением:

t-. Ки,,.к, (3)

где К - код таймера СЕВ, после которого осуществляется его восстановление. Соотношение (2) реализуется путем

сложения на сумматоре прямого кода

К;, дополнительным кодом К; , а оотношение (3) - путем сложения на умматоре прямого кода °б атным кодом }{{ . Полученное сообщеие ставится в очередь на обслужива- 5 ие в соответствии с его обобщенным риоритетом (старшие разряды - код статического приоритета, младшие разряды - код динамического приоритета).

Время нахождения сообщения на узле tO коммутации подсчитывается путем до- бавления к коду динамического приоритета тактовых импульсов таймеров СЕВ (число поступивших импульсов будет оответствовать времени нахождения co-J5 бщения в узле коммутации до момента ыдачи его снова в сеть). Первым на бслуживание выбирается сообщение, имеющее максимальный обобщенный приоритет.20

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

оритета.

Устройство содержит каналы 1,регистр. 2 приоритета канала, блок 3 злементов ИЛИ канала, блоки 4 и 5 элементов И канала, злемент ИЛИ 6 ЗО канала, схему 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 элементов ИЛИ, вход 5 38 запроса устройства, вход 39 сброса устройства вход 40 сетевого единого времени устройства, вход 41 индикации выдачи кода приоритета устройства, вход 42 индикации приема 0 сообщения устройства, выход 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 элементов И. I

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

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

(2). В противном случае, т.е. когда код метки больше кода таймера,единица к содержимому сумматора 31 не добавляется и на нем будет реализовываться соотношение (3).

Сигнал с выхода элемента 23 задержки поступает также на вход элемента 24 задержки, с выхода которого он проходит на вход элемента 25 задержки и второй вход блока 33 элементов И, разрешая выдачу содержимого регистра 28, снимаемого в обратном коде с второй группы выходов указанного регистра через блок 33 элементов И и блок 37 элементов ИЛИ на вторую группу входов сумматора 31. В результате сложения на сумматоре 31 получается код, соответствующий времени передачи данного сообщения.

Сигнал с выхода элемента 25 задержки поступает на вход элемента 26 задержки и второй вход блока 34 элементов И, разрешая выдачу содержимого регистра 29 через блок 34 элементов И и блок 37 элементов ИЛИ на сумматор 31. В результате сложения на сумматоре 31 получается код,соответствующий времени нахождения данного сообщения в сети на данный момент времени (динамический приоритет) ,

Сигнал с выхода элемента 26 задержки поступает на вход блока 35 элементов И, разрешая поступление содержимого регистра 10 и сумматора 31 на соответствующие выходы группы 48 выходов БФП, т.е. выдачу кода обобщенного приоритета (старшие разряды - код статического приоритета, младшие - код динамического при«- оритета), Содержимое регистра 30, регистра 10 и сумматора 31 поступает на соответствующие выходы группы

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

Код обобщенного приоритета с группы 48 выходов БФП поступает на первы группы входов схем 7 сравнения, на вторые группы входов которых поступают коды с регистров 2 и счетчиков 16 своих каналов (старшие разряды - код статического приоритета, хранящийся на регистре 2, младшие разряды - код динамического приоритета, хранящийся на счетчике 16). Схема 7 сравнения вырабатывает,сигнал на своем выходе в том случае, если код обобщенного приоритета, поступающего с группы

48выходов БФП, больше кода, храня16

0

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

При приходе первог о сообщения все схемы 7 вырабатывают сигнал.Для каждого канала, кроме последнего,сигнал ,с выхода схемы 7 сравнения открывает блок 9 элементов И своего канала,обеспечивая перезапись содержимого регистра 15. регистра 2 и счетчика 16 своего канала через блок 3 элементов ИЛИ последующего канала соотв тствен- . но в регистр 15 , регистр 2 и счетчик 16 последующего каншта. Этот же сигнал, пройдя через элемент НЕ 8

5 своего канала, закрывает блок 5 элементов И последуьхчего канала с целью блокировки записи информации, поступающей на него с группы 47 выходов БФП, Кроме того, сигнал с выхода схемы 7 сравнения первого канала поступает на вход установки в единицу триггера 19 первого канала. Для остальных каналов сигнал с выхода схемы 7 сравнения поступает на вход элемента И 18 своего канала, устанавливая в единичное состояние триггер 19 своего канала, если триггер 19 предыд тцего канала находится в единичном состоянии. Нахождение триггера 19 в единичном состоянии сигнализирует о том, что в данном канале записана информация, и разрешает поступление тактовых импульсов СЕВ через элемент , И 17 своего канала на счетный вход

5 счетчика 16 своего канала.

Сигналы с выхода схем 7 сравнения поступают также на блок 5 элементов И своего канала, обеспечивая запись содержимого регистра 30, регистра 10, сумматора 31, сн1 маемого с группы 47 выходов БФП, через незаблокированный блок 5 элементов И (в данном случае первого канала) и блок 3 элементов ИЛИ данного канала соответственно в регистры 15 и 2 и счетчик 16 данного канала.

5

0

0

5

Сигнал с выхода элемента 26 задержки через элемент ИЛИ 12 устанавливает в единичное состояние триггер 22. . Нулевой потенциал с инверсного выхода указанного триггера поступает на вход элемента И 17 каждого канала, запрещая на период формирования очереди поступление тактовых и 1пульсов СЕВ на счетный вход счетчиков 16.

Сигнал с выхода элемента ИЛИ 12 через интервал времени, определяемый параметрами элемента 13 задержки,ус/1

танавливает в нулевое состояние тригеры 21 и 22, сигнализируя о готовности устройства к работе и разреша поступление на счетчики 16 тактовых импульсов СЕВ. Далее в этом режиме устройство работает аналогично,размещая сообщения в очереди в соответствии с их обобщенными проритетами,

В регистре 15 первого канала вседа будет находиться код адерса (имя сообщения,имеющего максимальный обощенный приоритет. Этот код выдается на выход 53 устройства. Пока сообщения находятся в очереди,значение их динамических приоритетов изменяется путем добавления тактовых импульсов СЕВ, поступающих на счетный вход счтчиков 16 через элементы И 17 с вход 40 устройства.

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

Одновременно сигнал на выдачу обобщенного приоритета поступает на вход элемента ИЛИ 12, сигнал с выход которого устанавливает в единичное состояние триггер 22, Нулевой потенциал с инверсного выхода указанного триггера поступает на вход элемента И 17 каждого канала, запрещая на пе- риод перестройки очереди;поступление тактовых импульсов СЕВ.

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

нулевом

через

налов

состоянии.

устанавливает

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

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

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

I 1 I

I I

фиг./

5

W

9иг.2