Устройство для обслуживания группы запросов Советский патент 1990 года по МПК G06F9/50 

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

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

На чертеже представлена блок- схема устройства.

Устройство содержит регистр 1, счетчики 2 приоритета, счетчики 3 заявок, две группы из п схем 4 и 5 сравнения, четыре группы из п элементов И 6-9, группу из п элементов

ИЛИ 10, первый и второй счетчики 11 и 12, триггер 13, первый дешифратор 14, генератор 15 тактовых импульсов, делитель 16 частоты, первый и второй элементы И 17 и 18, первый - третий элементы ИЛИ 19-21, четвертый и пятый счетчики 22 и 23, третий дешифратор 24, вторую группу из m элементов ИЛИ 25, шифратор 26, сумматор по mod2 27, четвертый элемент ИЛИ 28, второй дешифратор 29, третий счетчик 30, регистр 31 длины очереди, пятую группу элементов И 32, запросные входы 33, кодовые входы 34, вход 35 запуска, ответный вход 36, кодовый выход 37, выходы 38 инициирования обслуживания.

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

Коды приоритетов абонентов по кодовым входам ЗА устройства поступают на установочные входы счетчиков 2 приоритета. Абоненту самого высокого приоритета соответствует наибольший из используемых кодов. Реред началом работы устройства счетчики 3, 11, 12, 22 и 23 устройства и триггер 13 находятся в нулевом состоянии. Импульсы с выходов генератора 15 постоянно поступают на вход суммирующего счетчика 30 устройства, емкость которого равна (п+2). В результате на выходе счетчика 30 формируется циклическая последовательность кодов чисел в диапазоне от нуля до максимально возможного (.. .,0,1 ,2, .. .,n, п+1,п+2, 0,1,2,...). Код с выхода счетчика 30 поступает на вход дешифратора 29 на (п+2) выходах которого будут последовательно появляться единичные сигналы Появления единичных сигналов на (1,2, ...,п) выходах дешифратора 29 соответствует появлению кодовых комбинаций чисел 1,2,...,п на входе дешифратора 29 и приводит к поочередному опросу разрядов регистра .1 заявок на наличие сигналов прерывания. Единичные сигналы с (п+1) и (п+2) выходов дешифратора 29 управляют соответственно записью в регистр 31 содержимого счетчика 22 длины очереди заявок и обнулением счетчика 2-2. Таким образом, за один цикл работы счетчика 30 последовательно опрашиваются п разрядов регистра 1 заявок (в результате в счетчике 22 формируется код чис- ла заявок, находящихся в очереди), содержимое счетчика 22 переписывается в регистр 31 и счетчик 22 обнуляется.

Запросы от абонентов поступают по входам 33 устройства в соответствующие разряды n-разрядного регистра 1 заявок, где п- - число обслуживаемых устройством абонентов . С приходом очередного 1-го запроса соответствую- щий разряд -регистра 1 устанавливается в единичное состояние и сигнал с его выхода открывает i-элементы И 6-8 и . 32 групп. Импульсы с выхода генератора 14 через делитель 16 частоты, в качестве которого может быть использован обычный счетчик, и через открытые по вторым входам элементы И 6 и 7 поступают на счетные входы соответствующих счетчиков 2 приоритета и счетчиков 3 группы. При этом на вход 1-го счетчика 2 импульсы поступают с первого выхода делителя 16 частоты, а на вход 1-го счетчика 3 - с второго выхода делителя 16 частоты (частота импульсов на втором выходе делителя 16 выше, чем на первом). Таким образом, в счетчиках 2 и 3, соответствующих абонентам, запросы от которых зафиксированы в регистре 1 заявок, формируются возрастающие последовательности кодов чисел, начиная соответственно от приоритетного кода в счетчике 2 и от нуля в счетчике 3. В счетчике 2 с увеличением времени ожидания запроса на обслуживание будет увеличиваться приоритетный код соответствующего абонента. В счетчике 3 формируется код, пропорциональный времени пребывания запроса з очереди на обслуживание.

Единичные сигналы с выходов дешифратора 29 через соответствующие открытые элементы И 32 и элемент ИЛИ 28 последовательно поступают на счетный суммирующий вход счетчика 22„ В счетчике 22 формируется код числа заявок, находящихся в очереди на обслуживание в регистре 1. Подсчет числа заявок осуществляется в каждом цикле работы счетчика 30 устройства, после чего по единичному управляющему сигналу с (п+1) выхода дешифратора 29 осуществляется запись в регистр 31 содержимого счетчика 22. По единичному управляющему сигналу с (п+2) выхода дешифратора 29 счетчик 22 обнуляется. Таким образом, периодически, в конце каждого цикла работы счетчика 30, обновляется содержимое регистра 31 длины очереди заявок. С выхода регистра 31 код числа запросов, ожидающих обслуживание, поступает на вход дешифратора 24 устройства. Выходы дешифратора 24 последовательно объединены в га групп соответствующими элементами ИЛИ 25, так что г .

m

J

li i j 1, m; 2 m n

де п - число абонентов устройства (число задействованных выходов дешифратора 24) ш - максимальное число каналов обслуживания, которые могут быть предоставлены устройству (число элементов ИЛИ 25);

- число выходов дешифратора 24, объединенных в j-ю группу соответствующим элементом ИЛИ 25.

При поступлении одного или нескольких запросов на обслуживание в регистр 1 заявок в счетчике 22 будет формироваться код числа запросов, находящихся в регистре 1. После переписи содержимого счетчика 22 в регистр 31 на соответствующем выходе дешифратора 24 появится единичный сигнал, который проходит на выход j-ro элемента ИЛИ 25. На выходе пер- вого (j I) элемента ИЛИ 25 единичный сигнал появляется, если в очереди зафиксирован хотя бы один запрос на обслуживание (но не более 1 запросов) . Если число запросов в очереди превышает пороговую величину

j-( p. t 21. (J 2) , то единичный j«

нал появляется на выходе соответствующего j -го элемента ИЛИ 25, т.е. при определенном увеличении длины очереди (превышении значений p1t р2, Рг,. .. .) происходит переключение единичного сигнала с выхода (j-l)-ro элемента ИЛИ 25 на выход j-ro элемента ИЛИ 25 (j 2, 3,...,m). Соответственно изменяется код на выходе шифратора 26, определяющий номер j-ro элемента ИЛИ 25 группы и число подключаемых к устройству каналов обслуживания. Код с выхода шифратора 26 поступает на кодовый выход 37 устройства, запрашивая предоставление устройству j-ro числа каналов обслуживания, и на вход сумматора по mod2 27.

На выходе сумматора по mod2 27 единичный сигнал появляется только при совпадении не нулевых кодов на вы-

10

20

15

5629136

11 и 12 и триггера 13. Сигнал с ep,i ничного выхода триггера 13 отктэьгеае элемент И 17 и подготавливает эле- 5 мент И 18, закрытый нулевым сигналом

с выхода элемента ИЛИ 21. Элемент ИЛИ 21 объединяет вторую группу выходов дешифратора 14, соответствующую входным кодовым комбинациям дешифратора 14, содержащим две и более единиц. Импульсы с выхода генератора 15 через элемент И 17 поступают на счетный вход счетчика 11, на выходе которого формируется убывающая последовательность кодов чисел, начиная от максимально возможного. При совпадении кодов на выходе счетчика 11 с кодом в каком-либо счетчике 2 приоритета 2 на выходе соответствующей 1-й схемы 4 сравнения появится единичный сигнал. Если в i-м разряде регистра 1 заявок зафиксирован запрос на обслуживание, то единичный сигнал с выхода i-й схемы 4 сравнения через откры25 тый по второму входу i-й элемент И 8 группы поступает на первый вход 1-го элемента И 9 группы, подготавливая его открытие, и на i-й вход дешифратора 14. В дешифраторе 14 выделена

30 первая группа из п выходов, каждый из которых соответствует кодовой комбинации на входе дешифратора 14, содержащей один единичный разряд (например, IOO...O; 010...0; 0...01). Появление единичного сигнала на i-м выходе в первой группе выходов дешифратора 14 означает, что выявлен i-й запрос на обслуживание, имеющий наивысший приоритет в очереди. Через соответствующий элемент ИЛИ 10 группы этот сигнал проходит на i-й выход 38 устройства.

При обспуживании устройством потока разноприоритетных заявок изме35

40

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

ходах шифратора 26 и счетчика 23 уст- 45 нение приоритетных кодов запросов в

ройства.

Двоичный код числа на кодовом выходе 37 устройства воспринимается обслуживающим прибором как запрос на предоставление j-ro числа каналов Обслуживания (1 jЈ m). Сигнал за- пуска, означающий готовность каналов обслуживания к приему запросов, поступает из обслуживающего прибора на вход 35 запуска устройства. Ii

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

очереди с течением времени может привести к совпадению приоритетных кодов нескольких заявок, поступивших в разное время. В этом случае при просмотре очереди единичные сигналы могут появиться на выводах одновременно двух или нескольких схем 4 сравнения, С выходов схем 4 сравнения через соответствующие элементы И 8

сигналы поступают на входы дешифратора 14. При появлении на входах дешифратора 14 кодовой комбинапли, содержащей две или более единиц (например, 1010 ...0; 10. ..01; О...ОП),

соответствующем выходе во второй руппе выходов дешифратора 14 появ- |яется единичный сигнал, который через элемент ИЛИ 21 поступает на входы элементов И 17 и 18. Элемент И 17 оказывается закрытым, и поступление импульсов на счетный вход счетчика 17 прекращается. Импульсы с выхода генератора 15 через открытый элемент И 18 начинают поступать на счетный вход счетчика 12, на выходе которого формируется убывающая последовательность кодов чисел, начиная от максимально возможного. При совпадении кодов на выходе счетчика 12с кодом в каком-либо счетчике 3 На выходе соответствующей схемы 5 Сравнения появляется единичный сигнал, который поступает на второй элемента И 9 группы. Если на первом входе элемента И 9 присутствует единичный уровень сигнала, т.е. данный абонент уже опрашивался на на Личие приоритетного запроса на об- Служивание, то на выходе элемента И 9 появится единичный сигнал, который через соответствующий элемент ИЛИ 10 поступит на информационный выход 38 устройства.

Сигнал с выхода 1-го элемента ИЛИ 10 инициирует обслуживание соответствующего абонента. Устанавливаются в Нулевое состояние i-й разряд регистра 1 заявок, i-й счетчик 2 приорите- та и i-й счетчик 3 группы,, после чего в i-й счетчик 2 приоритета по кодовым входам 34 устройства вновь заносится приоритетный код соответствующего абонента. Сигнал с выхода 1-го элемента ИЛИ 10 проходит также через элемент ИЛИ 19 на счетный суммирующий вход счетчика 23. Код с выхода счетчика 23 поступает на второй вход сумматора по mod2 27, на первый В1ход которого поступает с выхода дешифратора 26 код, определяющий число требуемых устройству каналов обслуживания . Код в счетчике 23 определяет число поставленных в данный момент на обслуживание запросов от абонентов . Совпадение кодов в счетчике 23 и шифраторе 26 означает, что устройству выделено требуемое число каналов обслуживания и соответствующее число заявок поставлено на обслуживание. При совпадении кодов в счетчике 23 и шифраторе 26 на выходе сумматора по mod2 27 появится единичный

о

0

сигнал, который закрывает по инверсным входам элемента И 17 и 18 и устанавливает в нулевое состояние счетчики 11 и 12 и триггер 13 устройства . Если коды числа каналов обслуживания и числа обслуживаемых заявок не совпадают, то на выходе сумматора по mod2 27 останется нулевой сигнал, разрешающий дальнейшее поступление импульсов с выхода генератора 15 через элемент И 1 7 на счетный вход счетчика 11 или через элемент И 18 на счетный вход счетчика 12 . Соответственно. продолжится опрос абонентов либо на наличие наиболее приоритетного запроса, либо среди высокоприоритетных абонентов будет выявляться запрос, находящийся дольше в очереди. Цикл работы устройства заканчивается, когда инициировано обслуживание такого числа абонентов, сколько требовалось каналов обслуживания.

Сигнал инициирования обслуживания 1-го абонента с выхода 38 устройства поступает в i-й разряд регистра 1, устанавливая его в нулевое состояние. В результате в очередном цикле рабо- ты счетчика 30 при опросе разрядов регистра 1 код числа запросов в очереди, формируемый в счетчике 22, изменится. Если в процессе работы устройства число запросов в очереди

уменьшится до пороговой величины

j-

р -

}где j 2 - номер группы выходов дешифратора 24, а 1j - число выходов в j-й группе, то произойдет переключение единичного сигнала с выхода j-ro элемента ИЛИ 25 на выход (j-l)-ro элемента ИЛИ 25. Соответственно изменится код на выходе шифратора 26 и число выделенных устройству каналов обслуживания умень шится на один канал.

После инициирования обслуживания абонента возможное изменение кода на выходе шифратора 26 произойдет с задержкой, достаточной для срабатывания сумматора по mod2 27.

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

10

в единичное состояние счетчиков 11 и 12 и триггера 13. Если на выходе сумматора по mod2 27 отсутствует единичный сигнал, т.е. имеется свободный канал обслуживания, то элемент И 17 оказывается открытым и импульсы с выхода генератора 15 поступают на счетный вход счетчика П. Далее устройство работает аналогично. Осуществляется выявление наиболее приоритетной заявки в очереди. Если несколько запросов обладают одинаковым приоритетом, то среди них выявляется заявка, время пребывания которойf5 в очереди наибольшее. Соответствующий абонент ставится на обслуживание. Проверяется занятость каналов обслуживания. Если есть свободный канал обслуживания, то вновь выявляется при- 20 оритетный запрос и инициируется его f обслуживание. Если нет свободного каасд5

нала, то цикл работы устройства заканчивается. Новый цикл работы ини

циируется либо сигналом ответа по входу 36, свидетельствующим о завершении обслуживания одной из заявок в соответствующем канале, либо сигнало запуска по входу 35. Сигнал запуска выдается обслуживающим прибором при увеличении входной очереди выше определенных пороговых значений в ответ на увеличение запросного кода на выходе 37 устройства и свидетельствует о выделении устройству дополнительного канала обслуживания. Если, интенсивность входного потока заявок падает, т.е. сокращается очередь заявок на обслуживание, то в соответ ствии с уменьшением кода на выходе 37 обслуживающий прибор уменьшает число предоставляемых устройству каналов обслуживания. Учет числа заявок, находящихся в очереди, в регистре 31 и числа обслуживаемых в данный момент заявок в счетчике 23 позволяет регулировать число предоставляемых устройству каналов обслуживания и организовывать обслуживание группы запросов абонентов./

Формула изобретения

Устройство для обслуживания группы запросов, содержащее п-разрядный

группы из п элементов И, первую группу из п элементов ИЛИ, два сч чика, триггер, первый дешифратор, нератор тактовых импульсов, делите частоты, два элемента И, три элеме та ИЛИ, причем группа информационн входов регистра заявок является гр пой запросных входов устройства, группа информационных входов счетч ков приоритета является группой з просных входов устройства, группа формационных входов счетчиков прио ритета является группой кодовых вх дов устройства, первые входы элеме тов И первой и второй групп подклю чены соответственно к первому и вт рому выходам делителя частоты, вых i-й (i 1,...,п) схемы сравнения вой группы подключен к первому вход 1-го элемента И третьей группы, выход которого соединен с i-м входом первого дешифратора и с первым входом 1-го элемента И четвертой групп второй вход которого подключен к вы ходу i-й схемы сравнения второй групп а выход соединен с первым входом 1элемента ИЛИ первой группы, вторые входы которых подключены к соответствующим выходам первой группы выхо дов первого дешифратора, а выходы соединены с входами первого элемента ИЛИ, с соответствующими i-ми выходами инициирования обслуживания ас устройства, с входами установки в О 1-го счетчика приоритета, 1-го счетчика группы, 1-го разряда регис Ьа заявок, счетные входы 1-х счетчиков приоритета и счетчиков группы подключены к выходам 1-х элементов |И соответственно первой и второй групп, выходы 1-х счетчиков приорит та счетчиков группы соединены с цер ми входами 1-х схем сравнения соот- д5 ветственно первой и второй трупп, в рые входы которых подключены к выхо дам соответственно первого и второг счетчиков, входы установки в единич ное состояние которых соединены с в дом установки в единичное состояние триггера и с выходом второго элемен та ИЛИ, первый вход которого являет входом запуска устройства, единичны вход триггера подключен к первым пр мым входам первого и второго элемен f п f-. -т, -т. ЛЧЛЛЛ Л . 1 X V - ь-«

регистр заявок, где п - число абонен- 55 тов и, прямой вход второго элемента

тов устройства, п счетчиков приоритета, группу из п счетчиков, две группы по п схем сравнения, -четыре

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

10

f5 0

5

30

. д

группы из п элементов И, первую группу из п элементов ИЛИ, два счетчика, триггер, первый дешифратор, генератор тактовых импульсов, делитель частоты, два элемента И, три элемента ИЛИ, причем группа информационных входов регистра заявок является группой запросных входов устройства, группа информационных входов счетчи - ков приоритета является группой запросных входов устройства, группа информационных входов счетчиков приоритета является группой кодовых входов устройства, первые входы элементов И первой и второй групп подключены соответственно к первому и второму выходам делителя частоты, выход i-й (i 1,...,п) схемы сравнения первой группы подключен к первому входу 1-го элемента И третьей группы, выход которого соединен с i-м входом первого дешифратора и с первым входом 1-го элемента И четвертой группы, второй вход которого подключен к выходу i-й схемы сравнения второй группы, а выход соединен с первым входом 1го элемента ИЛИ первой группы, вторые входы которых подключены к соответствующим выходам первой группы выходов первого дешифратора, а выходы соединены с входами первого элемента ИЛИ, с соответствующими i-ми выходами инициирования обслуживания ас устройства, с входами установки в О 1-го счетчика приоритета, 1-го счетчика группы, 1-го разряда регист-. Ьа заявок, счетные входы 1-х счетчиков приоритета и счетчиков группы подключены к выходам 1-х элементов |И соответственно первой и второй групп, выходы 1-х счетчиков приоритета счетчиков группы соединены с цервы- ми входами 1-х схем сравнения соот- 5 ветственно первой и второй трупп, вторые входы которых подключены к выходам соответственно первого и второго счетчиков, входы установки в единичное состояние которых соединены с входом установки в единичное состояние триггера и с выходом второго элемента ИЛИ, первый вход которого является входом запуска устройства, единичный вход триггера подключен к первым прямым входам первого и второго элемен0

ЛЧЛЛЛ Л . 1 X V - ь-«

5 тов и, прямой вход второго элемента

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

1115

второго элементов И соединены со счетными входами соответственно первого и второго счетчиков, i-й выход регистра заявки подключен к вторым входам 1-х элементов И первой, второй и третьей групп, выход генератора тактовых импульсов соединен с входом делителя частоты и вторыми прямыми входами первого и второго эле- ментов И, ответный вход устройства Соединен с вторым входом второго элемента ИЛИ, вход установки в 1:0 триггера соединен с входами установки в О первого и второго счетчиков, Отличающееся тем, что, с Целью повышения быстродействия устройства при обслуживании группы запросов за счет обеспечения возможности выделения нескольких запросов $ зависимости от длины очереди на обслуживание, оно содержит третий, Четвертый и пятый счетчики, регистр длины очереди, второй и третий дешифраторы, пятую группу из п элементов И, вторую группу кз m элементов ИЛИ (где m - максимальное число представляемых каналов обслуживания), шифратор, сумматор по mod 2, четвертый элемент ИЛИ, причем i-й выход регистра заявок подключен к второму входу 1-го элемента И пятой группы, первый вход 1-го элемента И пятой группы соединен с i-м выходом второго дешифратора, входы которого под

Q 5 0

5

0

31

ключены к информационным входам третьего счетчика, счетный вход которого соединен с выходом генератора тактовых импульсов, выходы элементов И пятой группы подключены к входам четвертого элемента ИЛИ, выход которого соединен со счетным суммирующим входом четвертого счетчика, выходы которого подключены к информационным входам регистра длины очереди, вход записи которого и вход установки в нулевое состояние четвертого счетчика соединены соответственно с (п+1) и (п+2) выходами второго дешифратора, выходы регистра длины очереди подключены к входам третьего дешифратора, m групп выходов которого через соответствующие элементы ИЛИ второй группы подключены к входам шифратора, выход которого является кодовым выходом устройства и соединен с первым входом сумматора по mod 2, второй вход которого подключен к выходу пятого счетчика, суммирующий вход которого соединен с выходом первого элемента ИЛИ, вычитающий вход пятого счетчика подключен к ответному входу устройства, выход сумматора по mod 2 подключен к второму инверсному входу первого и инверсному входу второго элементов И, входы третьего элемента ИЛИ соединены с второй группой выходов первого дешифратора.

У