Устройство для организации очереди

 

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

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

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

РЕСПУБЛИК

ÄÄSUÄ14 99

А2 (51)4 С 06 F 9 46

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

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

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

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

ПРИ ГКНТ. СССР (61) 1126964 (21) 4247324/24-24 (22) 19.05.87 (46) 15,05.89. Вюл. Р 18 (72) В,Г.Попов, А.lO.Äóáðîâ и О.В.Михайлов (53) 681.325 (088.8) (56) Авторское свидетельство СССР

М 1126964, кл. G 06 F 9/46, 1983, (54) УСТРОЙСТВО ДЛЯ ОРГАНИЗАЦИИ ОЧЕРЕДИ (57) Изобретение относится к вычислительной технике. Цель изобретения— расширение области применения эа счет распределения заявок между ресурсами. Устройство для органиэации очереди содержит блок 1 формирования очереди, шифратор 2 и блок 3 управления. Распределение поступающих заявок производится блоком управления на основе анализа состояния очередей к каждому ресурсу. При этом заявка направляется в очередь ресурсу, в котором имеется наименьшая очередь, а при равных очередях — ресурсу с наименьшим его номером. 3 ил.

1479930

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

Цель изобретения — расширение области применения устройства эа счет распределения заявок между ресурсами, На фиг. 1 изображена бло " — схема 10 предлагаемого устройства; на фиг,2— структурная схема блока формирования очереди; на фиг, 3 — структурная схема блока управления.

Устройство содержит блоки 1,-1, формирования очереди, шифратор 2, блок 3 управления, выходы 4,-4 блока 3 управления, запросные входы 5,—

5 „ устройства, выходы 6 „-6 шифратора 2, выходы 7 „— 7 < блоков 1,-1„, так- 20 тогые входы 8,-8 „ устройства, вторые группы информационных выходов 9,-9 устройства, сигнальные входы 10,-10 и входы 11 -11 считывания устройст1 1;

H B. 25

Каждый блок 1 формирования очереди содержит дешифратор 12, группу элементов ИЛИ-НЕ 1",-13„, элемент ИЛИ 14, группу элементов И 15 „-15 и регистры 16 сдвига. 30

Блок 3 управления содер>кит группу элементов 17 запрета, элементы 18

18, запрета, блоки элементов И 19 (i1 iI >

19„, шифратор 20. Шифраторы 21,-21, и элементы ИЛИ 22,-22, .

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

Исходное состояние устройства характеризуется тем, что регистры 16 сдвига в каждом блоке 1 формирования 40 очереди установлены B состояние "0" (не показано),, Работа устройства состоит из двух этапов. На первом этапе производится формирование очереди, а на втором -45 обслуживание заявок, Формирование очереди производится для каждого свободного ресурса ЗВС с учетом наличия заявок в каждом блоке 1. Поступа|ощая заявка направляется в тот блок 1, где сформирована наименьшая очередь. Если число заявок в ряде блоков 1 одинаково,то заявка ставится в очередь .в блоке с наименьшим номером, Распределение поступающих заявок производится блоком 3 управления ня основе анализа состояний очередей в блоках 1 формирования очереди.

Очереди заявок формируются следующим образом, Если все ресурсы готовы к обслуживанию, то по входам 10,-10, в блоки

1 „- 1 „ сигналы не поступают, в результате чего регистры 16 находятся в состояниях "0". Все блоки i работают одинаково, Так как регистры 16 находятся в нулевых состояниях, то на выходе последнего элемента ИЛИ-HF. 13 формируется единичный сигнал, открывающий последние элементы И 15 во всех группах, По единичному сигналу с выхода последнего элемента ИЛИ-НЕ

13 все остальные элементы ИЛИ-HF. 13 формируют нулевые сигналы, которыми будут закрыты остальные элементы И

15 всех групп, Таким образом, только на последних выходах 7 будут сформированы единичные сигналы, поступающие (фиг.3) на входы первых элементов 17 запрета, причем элементы запрета каждой группы по входам подключены к позициям выходов 7 так, что с помощью элементов 17 запрета определяется наименьший номер из блоков формирования очереди с равными очередями. Элементами ИЛИ 22,-22 „ формируется код, позиционно указывающий свободные разряды регистров 16 сдвига в блоках 1,-1 . Шифраторами 21,—

21 „ формируется двоичный код наибольшего номера разрядов регистров 16 из блоков 1 -1 с одинаковой очеред < постыл. С помощью элементов 18,-18„, запрета, подключенных к,выходам элементов ИЛИ 22 „ — 22 » определяется наи— меньший помер блока 1 с наибольшим номером свободных разрядов регистров

16 сдвига. Этот номер блока 1 в двоичном коде передается на дешифратор

20, на выходе которого формируется единичный сигнал, позиционно указывающий номер направления передачи заявок, т.е. номер соответствующего блока 1.

В рассматриваемом случае в блоке

3 управления единичным сигналом последнего входа первой группы закрыты по инверсным входам все элементы запрета. При этом на входах шифратора

21„ формируется позиционный код, имеющий единицу в первом разряде, а. на выходе шифратора 21, — двоичный код единицы. Кроме того, на выходе эле«: мента ИЛИ 22, также. будет сформирован единичный сигнал, которым закры147993 ты по первым инверсным входам элементы 18 запрета и открыт по управляющему входу блок элементов И 19,.

При этом двоичный код единицы пере5 дается на входы шифратора 20, на первом выходе которого появляется единичный сигнал, который поступает по входу 4, в блок 1, формирования очереди. Таким образом, из совокупности всех блоков 1 выбран блок 1, т.е, Э блок с наименьшим номером.

Сигнал первой заявки по одному из запросных входов 5 в сопровождении синхросигнала по входу 11 поступает на соответствующий вход шифратора 2, код с выходов которого передается по входам 6 на элементы И 15 всех блоков t. Так как только на выходе

4 присутствует единичный сигнал, то по импульсу, сопровождающему заявку и поступающему в устройство по входу 11 двоичный код номера заявки записывается в последние разряды регистров 16, Вследствие этого на выходе элемента последнего ИЛИ-НЕ

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

4 гистров 16 блока 1 аналогично выше г рассмотренному.

В дальнейшем работа устройства по формированию очереди производится таким же образом, пока заявки не. разместятся поочередно в каждом блоке 1.

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

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

8 „ подается сигнал, по которому в регистрах 16 блока 1„производится сдвиг информации в сторону старших разрядов. При этом код номера очередной заявки подается на дешифратор

12, на соответствующем выходе которого формируется сигнал. Если после обработки первой заявки в регистрах

16 записаны коды еще одной или. нескольких заявок, то после сдвига содержимого регистров 16 на выходе очередного элемента ИЛИ-НЕ 13 появится единичный сигнал и дальнейшая работа устройства происходит как указано выше, Таким образом, на выходах 7 блока

1 формируется позиционный код, имею- 35 щий единицу в предпоследней позиции.

К моменту поступления очередной заявки в сопровождении синхросигнала по входу 11 аналогично рассмотренному на выходах 7 блока 3 управления формируются коды 1;. 10 — код 0 01.

В данном случае на входах шифратора 21, элементами запрета устанавливается позиционный код 0 " 010, а . на входах шифратора 21г — код 0 01, 45

Кроме того, на выходах элементов

ИЛИ 22 формируется код 0 011.-Единичным сигналом с выхода элемента

ИЛИ 22 элементы 18 запрета удержи1 ваются в закрытом состоянии, поэтому двоичный код с выхода шифратора 21, поступает через блок элементов И 19, на входы дешифратора 20. При этом на втором выходе дешифратора 20 формируется единичный сигнал, открывающий элементыИ 15 всех групп уже во втором блоке 1 формирования очереди.

Двоичный код поступающей заявки записывается в последние разряды реФормула изобретения

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

ИЛИ, шифратор и блок элементов И, 1-я группа информационных входов. блока управления (1=1, 2, ", К)подключена к первой группе информационных выходов 1-ro блока формирования

Ю очереди, вход считывания каждого блока формирования очереди соединен с одноименным входом считывания устройства, j-й тактовый вход которого (j = 2, 3, ", К) подключен к тактовому входу j-ro блока формирования

5 14799 очереди, группа информационных входов которого подключена к группе выходов шифратора, каждый сигнальный вход устройства соединен с входом го5

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

6 динен с выходом элемента ИЛИ своего канала, выход элемента ИЛИ каждого канала блока управления, начиная с последнего, соединен с соответствующими инверсными входами элементов запрета всех предыдущих каналов, каждый вход первой группы информационных входов блока управления соединен с соответствующими инверсными входами элементов запрета группы одноименного канала блока управления, с первыми входами шифратора одноименного канала и элемента ИЛИ одноименного канала блока управления, j-й вход i-й группы информационных входов блока управления (i = 2, 3, "

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

1479930

Составитель И,Кудряшев

Техред А.Кравчук Корректор Л,Патай

Редактор А.Ревпн

Заказ 2543/46 Подписное

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

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

Тираж 669

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