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

 

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

(19) (1!) СОЮЗ COBETCHHX

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

РЕСГ)УБЛИК рц С 06 Р 9146

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

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

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

Il0 ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (2)) 4454543 j24-24 (22) 05.01.88 (46) 07 .05.90. Бюл. М - 17 (72) A.Ì. Белан и В.В. Макрусев (53) 681 .325(088.8) (56) Авторское свидетельство СССР !

) 1070551, кл. G.06 F 9/46, 1984.

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

В 1256030, кл. G 06 F 9!46, 1986. (54) УСТРОЙСТВО ДЛЯ ОБСЛУЖИВАНИЯ ГРУППЫ ЗАПРОСОВ (57) Изобретение может быть использо.вано в вычислительной технике,- в частности в устройствах приоритетного обслуживания запросов, Целью изобретения является повышение быстродействия устройства при обслуживании группы запросов за счет обеспечения возможности выделения нескольИзобретение относится к вычислительной технике, в частности к устройствам приоритетного обслуживания запросов.

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

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

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

ИЛИ 10, первый и второй счетчики 1! и 12, триггер 3, первый дешифратор

l4, генератор 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 инициирования обслуживания, 1562913

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

Коды приоритетов абонентов по кодовым входам 34 устройства поступают на установочные входы счетчиков 2 приоритета. Абоненту самого высокого приоритета соответствует наибольший из используемых кодов. Перед началом работы устройства счетчики 3, 11, l 2,,22 и 23 устройства и триггер 1 3 находятся в нулевом состоянии. Импульсы с выходов генератора 15 постоянно поступают на вход суммирующего счетчика 30 устройства, емкость 15 которого равна (и+2) . В результате на выходе счетчика 30 Формируется циклическая последовательность кодов чисел в диапазоне от нуля до максимально (° ° .,0,1,2, . ° °,и, n+1 и+2,2О

0,1,2,...) . .Код с выхода счетчика 30 поступает на вход дешифратора 29 на (n+2) выходах которого будут последовательно появляться единичные сигналы.

Появления единичных. сигналов на (1,2, 25 ...,n) выходах дешифратора 29 соответствует появлению кодовых комбинаций чисел .1,2,...,n иа входе дешифратора 29 и приводит к поочередному опроеу разрядов регистра,l заявок на ЗО наличие сигналов прерывания. Единичные сигналы с (n+1) и (и+2) выходов дешифратора 29 управляют соответственно записью в регистр 31 содержимого счетчика 22 длины очереди заявок и обнулением счетчика 22. Таким образом, за один цикл работы счетчика 30 последовательно опрашиваются и разрядов регистра 1 заявок (в результате в счетчике 22 Формируется код чис- 40 ла заявок, находящихся в очереди), содержимое счетчика 22 переписывается. в регистр 31 и счетчик 22 обнуляется.

Запросы от абонентов поступают по входам 33 устройства в соответствующие разряды и-разрядного регистра I заявок, где n — число обслуживаемых устройством абонентов . С приходом очередного i-го запроса соответствую50 щий разряд регистра 1 устанавливается в единичное состояние и сигнал с его выхода открывает i-элементы И 6"8 и

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

1которых зафиксированы в регистре 1 заявок, Формируются возрастающие последовательности кодов чисея, начиная соответственно от приоритетного кода в счетчике 2 и от нуля в счетчике 3. В счетчике 2 с увеличением времени ожидания запроса на обслуживание будет увеличиваться приоритетный код соответствующего абонента.

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

Таким образом, периодически, в конце каждого цикла работы счетчика 30, обновляется содержимое регистра 31 длины очереди заявок . С выхода регистра 31 код числа запросов, ожидаю-. щих обслуживание, поступает на вход дешифратора 24 устройства. Выходы дешифратора 24 последовательно объединены в m групп соответствующими элементами ИЛИ 25, так что (..4 м и 1-; j = 1, m; 2(шс.п

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

562913

5 .1

1 — число выходов дешифра тора

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

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

p-l р. = 7 1 (j 2), то единичный curjc( нал появляется на выходе соответствующего j -го элемента ИЛИ 25, т .е. при определенном увеличении длины очереди (превьппении значений р„, р, p,...,ð ) происходит переключение единичного сигнала с выхода (j-1)-го элемента ИЛИ 25 на выход j-ro элемента ИЛИ 25 (j = 2, З,...,m) .

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

37 устройства, запрашивая предоставление устройству j-ro числа каналов обслуживания, и на вход сумматора по

mod2 27.

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

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

Сигнал запуска через элемент ИЛИ

20 проходит на входы установки в единичное состояние вычитающих счетчиков

11 и 12 и триггера 13. Сигнал с ед ничного выхода триггера !3 открывае элемент И 17 и подготавливает элемент И 18, закрытый нулевым сигналом с выхода элемента ИЛИ 21. Элемент

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

30 первая группа из и выходов,,каждый из которых соответствует кодовой комбинации на входе дешифратора 14, со" держащей один единичный разряд (например, 1 00... 0; 01 0...0; 0...01 ) .

Появление единичного сигнала íà i-м выходе в первой группе выходов дешифратора 14 означает, что выявлен i-й запрос на обслуживание, имеющий наивысший приоритет в очереди. Через

40 соответствующий элемент ИЛИ 10 груп.пы этот сигнал проходит на i-A выход 38 устройства.

При обслуживании устройством потока разноприоритетных заявок изменение приоритетных кодов запросов в очереди с течением времени может привести к совпадению приоритетных кодов нескольких заявок, поступивших в разное время. В этом случае при просмотре очереди единичные сигналы могут появиться на выходах одновременно двух или нескольких схем 4 сравнения. С выходов схем 4 сравнения через соответствующие элементы И 8 сигналы поступают на входы дешифратора 14. При появлении на входах дешифратора 14 кодовой комбинапии, содержащей две или более единиц (например, 1 01 0 ... 0; 1 0 ... 01; 0...01 1) 1 562913

30

55. соответствующем выходе во второй руппе выходов дешифратора 14 появляется единичный сигнал, который через элемент ИЛИ 21 поступает на входы элементов И 17 и 18. Элемент

Й 1.7 оказывается закрытым, и поступление импульсов на счетный вход счетчика 17 прекращается. Импульсы с выхода генератора 15 через открытый

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

12 с кодом в каком-либо счетчике 3

8а выходе соответствующей схемы 5 сравнения появляется единичный сигНал, который поступает на второй

Мход элемента И 9 группы. Если на

Первом входе элемента И 9 присутствует единичный уровень сигнала, т.е. J данный абонент уже опрашивался на на= личие приоритетного запроса на обСлуживание, то на выгоде элемента И 9 появится единичный сигнал, который через соответствующий элемент ИЛИ 10 поступит на информационный выход 38 устройства, Сигнал с выхода i-ro элемента ИЛИ

10 инициирует обслуживание соответствующего абонента. Устанавливаются в

Нулевое состояние i-й разряд регистра 1 заявок, i-й счетчик 2 приоритета и х-й счетчик 3 группы„после чего в 1-й счетчик 2 приоритета по кодовым входам 34 .устройства вновь заносится приоритетный код соответствующего абонента. Сигнал с выхода

i-го элемента ИЛИ 10 проходит также ч!ерез элемент ИЛИ 19 íà счетный суммирующий вход счетчика 23. Код с выхода счетчика 23 поступает на второй вход сумматора по mod2 27, на первый в ход которого поступает с выхода де-. шифратора 26 код, определяющий число требуемых устройству каналов обслуживания. Код s счетчике. 23 определяет число поставленных в данный момент на обслуживание запросов от абонентов. Совпадение кодов в счетчике

23 и шифраторе 26 означает, что устройству выделено. требуемое число кан|алов обслуживания и соответствующее число заявок поставлено на обслуживание. При совпадении кодов в счетчике 23 и шифраторе 26 на выходе сумматора по шой2 27 появится единичный сигнал, который закрывает по инверсным входам элемента И 17 и 18 и устанавливает в нулевое состояние счетчики 11 и 12 и триггер 13 устройства. Если коды числа каналов обслуживания и числа обслуживаемых заявок не совпадают, то на выходе сумматора по шой2 27 останется нулевой сигнал, разрешающий дальнейшее поступление импульсов с выхода генератора 15 через элемент И 17 на счетный вход счетчика 11 или через элемент Й 18 на счетный вход счетчика 12. Соответственно .. продолжится опрос абонентов либо на наличие наибьлее приоритетного загроса, либо среди высокоприоритетных абонентов будет выявляться запрос, находящийся дольme в очереди. Цикл работы устройства заканчивается, когда инициировано обслуживание такого числа абонентов, сколько требовалось каналов обслуживания.

Сигнал инициирования обслуживания

i-го абонента с выхода 38 устройства поступает в i-й разряд регистра 1, устанавливая его в нулевое состояние.

В результате в очередном цикле рабо ты счетчика 30 при опросе разрядов регистра 1 код числа запросов в очереди, Формируемый в счетчике 22, изменится. Если в процессе работы устройства число запросов в очереди уменьшится до пороговой величины

1-1 р, =,7. 1, где ) 2 — номер группы выходов дешифратора 24, а 11 число выходов в j-й rpyrme, то произойдет переключение единичного сигнала с выхода j-го элемента ИЛИ 25 на выход (j-1)-го элемента ИЛИ 25.

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

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

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

ИЛИ 20 поступает на входы установки

1562913 в единичное состояние счетчиков 11 и 12 и триггера 13. Если на выходе сумматора по mod2 27 отсутствует единичный сигнал, т.е. имеется свободный канал обслуживания, то элемент

И 17 оказывается открытым и импульсы с выхода генератора 15 поступают на счетный вход счетчика 11 . Далее устройство работает аналогично. Осу- 1п ществляется выявление наиболее приоритетной заявки в очереди. Если несколько запросов обладают одинаковым приоритетом, то среди них выявляется заявка, время пребывания которой 15 в очереди наибольшее. Соответствующий абонент ставится на обслуживание.

Проверяется занятость каналов обслуживания. Если есть свободный канал обслуживания, то вновь выявляется при- 2g оритетный запрос и инициируется его обслуживание. Если нет свободного канала, то цикл работы устройства за-l канчивается. Новый цикл работы инициируется либо сигналом ответа по 25 входу 36, свидетельствующим о завершении обслуживания одной из заявок в соответствующем канале, .либо сигналом запуска по входу 35, Сигнал запуска выдается обслуживающим. прибором при. 39 увеличении входнои очереди вьппе onpepeaeamrx пороговых значений в ответ на увеличение запросного кода на выходе 37 устройства и свидетельствует о выделении устройству дополни.тельного канала обслуживания. Если интенсивность входного потока заявок падает, т.е, сокращается очередь заявок на обслуживание, то в соответствии с уменьшением кода на выходе 40

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

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

В

Устройство для обслуживания группы запросов, содержащее и-разрядный регистр заявок, где и — число абонен-55 тов устройства „n счетчиков приоритета, группу из и счетчиков, две группы по и схем сравнения, четыре группы из и элементов И, первую группу из п элементов ИЛИ, два счетчика, триггер, первый дешиФратор, генератор тактовых импульсов, делитель частоты, два элемента И, три элемента ИЛИ, причем группа информационных входов регистра заявок является группой запросных входов устройства, группа информационных входов счетчи- . ков приоритета является группой запросных входов устройства, группа информационных входов счетчиков приоритета является группой кодовых входов устройства, первые входы элементов И первой и второй групп подключены соответственно к первому и второму выходам делителя частоты, выход т .-й (i 1,...,a) схемы сравнения пер" вой группы подключен к первому входу

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

" О" i-го счетчика приоритета, i o счетчика группы, i-ro разряда регист-. а заявок, счетные входы i- õ счетиков приоритета и счетчиков группы: подключены к выходам i-х элементов

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

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

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

Входам i-х элементов И первой, второй и третьей групп, выход генерато" ра тактовых импульсов соединен с входом делителя частоты и вторыми прямыми входами первого и второго элементов И, ответный вход устройства

Соединен с вторым входом второго элемента ИЛИ, вход установки в .0 триггера соединен с входами установКи в "О" первого и второго счетчиков, О т л и ч а ю щ е е с я тем„ что, с фелью повьш ения быстродействия устройства при обслуживании группы зайросов за счет обеспечения возможности выделения нескольких запросов 20

В зависимости от длины очереди на обслуживание, оно содержит третий, четвертый и пятый счетчики, регистр длины очереди, второй и третий дешифраторы, пятую группу из и элементов 25

Й, вторую группу из m элементов

ИЛИ (где m — максимальное число представляемых каналов обслуживания), шифратор, сумматор по mod 2, четвертый элемент ИЛИ, причем i-й выход 30 регистра заявок подключен к второму

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

3538 Л

Составитель Г.Пономарева

Техред Л,Серд окова Корректор С.Шекмар

Редактор С, Пекарь

Подписное

Тираж 566

Заказ 1065

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

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101