Устройство для организации очереди — SU 1479930 (original) (raw)
(5 6 Р 9 46 ИТЕТРЫТИЯМ ГОСУДАРСТВЕННЫИПО ИЗОБРЕТЕНИЯМПРИ ГКНТ.СССР НИЕ ИЗОБРЕТЕН СВИДЕТЕЛЬСТВ К АВТОРСНО(088.8)е свидетелС 06 РВО ДЛЯ ОР ьство СССР /46, 1983. АНИЗАЦИИ О тся к вычис- изобретения(57) Изобретение отнолительной технике, Це расширение области применения засчет распределения заявок между ресурсами. Устройство для органиэацииочереди содержит блок 1 формированияочереди, шифратор 2 и блок 3 управления. Распределение поступающих заявок производится блоком управленияна основе анализа состояния очередей к каждому ресурсу, При этом заявка направляется в очередь ресурсу,в котором имеется наименьшая очередь,а при равных очередях - ресурсу снаименьшим его номером. 3 ил.Изобретение относится к вычислительной технике и может быть использовано в вычислительных системахпри организации доступа к однотип 5ным ресурсам.1 ель изобретения - расширение об.ласти применения устройства эа счетраспределения заявок между ресурсами.На Фиг, 1 изображена блок-схема 10предлагаемого устройства; на фиг,2 -структурная схема блока Формированияочереди; на фиг, 3 - структурнаясхема блока управления.Устройство содержит блоки 1,-1, 15формирования очереди, шифратор 2,блок 3 управления, выходы 4,-4блока 3 управления, запросные входы 5, -5устройства, выходы 6 -6 шифратора 2, выходы 7 - 7блоков 1,-1, тактогые входы 8,-8устройства, вторыегруппы информационных выходов 9,-9устройства, сигнальные входы 10,-10и входы 11 -11 считывания устройствВя, 25Каждый блок 1 формирования очереди содержит дешифратор 12, группуэлементов ИЛИ в13,-13, элементИЛИ 14, группу элементов И 15 -15и регистры 16 сдвига. 30Блок 3 управления содеркит группуэлементов 17 запрета, элементы 18118, запрета, блоки элементов И 19. стройство работает следующим образом.Исходное состояние устройства характеризуется тем, что регистры 16сдвига в каждом блоке 1 формирования 40очереди установлены в состояние "0"(не показано)Работа устройства состоит из двухэтапов, На первом этапе производится Формирование очереди, а на втором -45обслуживание заявок,Формирование очереди производитсядля каждого свободного ресурса ЗВСс учетом наличия заявок в каждомблоке 1, 11 оступающая заявка направляется в тот блок 1, где сформирована наименьшая очередь, Если числозаявок в ряде блоков 1 одинаково,тозаявка ставится в очередь .в блоке снаименьшим номером, Распределениепоступающих заявок производится блоком 3 управления ня основе анализасостояний очередей в блоках 1 формирования очереди,Очереди заявок формируются следующим образом,Если все ресурсы готовы к обслуживанию, то по входам 1.0,-10, в блоки1 - 1сигналы не поступают, в результате чего регистры 16 находятся всостояниях "0", Все блоки 1 работаютодинаково. Так как регистры 16 находятся в нулевых состояниях, то навыходе последнего элемента ИЛИ-НЕ 13формируется единичный сигнал, открывающий последние элементы И 15 вовсех группах, По единичному сигналус выхода последнего элемента ИЛИ-НЕ13 все остальные элементы ИЛИ-НЕ 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 поступает 15на соответствующий вход шифратора 2,код с выходов которого передаетсяпо входам 6 на элементы И 15 всехблоков 1, Так как только на выходе4 присутствует единичный сигнал,то по импульсу, сопровождающему заявку и поступающему в устройство повходу 11, двоичный код номера заявкизаписывается в последние разрядырегистров 16, Вследствие этого на 25выходе элемента последнего ИЛИ-НЕ13 формируется нулевой сигнал, закрывающий последние элементы И 15 всехгрупп. Этим же сигналом на выходепоследнего элемента ИЛИ-НЕ 13 формируется единичный сигнал, которымоткрываются последние элементы И 15всех групп. 04гистров 16 блока 1 аналогично вьппеграссмотренному.В дальнейшем работа устройствапо формированию очереди производитсятаким же образом, пока заявки не. разместятся поочередно в каждом блоке 1.Работа устройства совместно собслуживающим ресурсом выполняетсяследующим образом,Пусть первый ресурс приступил кобслуживанию заявки, На выходе дешифратора 12, соответствующем номеруисточника заявок, формируется единичный сигнал, поступающий на обслуживание,После отработки .заявки по входу8подается сигнал, по которому врегистрах 16 блока 1 производитсясдвиг инФормации в сторону старшихразрядов. При этом код номера очередной заявки подается на дешифратор12, на соответствующем выходе которого формируется сигнал, Если после обработки первой заявки в регистрах16 записаны коды еще одной или. нескольких заявок, то после сдвига содержимого регистров 16 на выходеочередного элемента ИЛИ-НЕ 13 появится единичный сигнал и дальнейшаяработа устройства происходит как указано вьппе, Таким образом, на выходах 7 блока 1 фрирутся позиционный код, имеющий единицу в предпоследней позиции, К моменту поступления очередной заявки в сопровождении синхросигнала по входу 11 аналогично рассмотренному на выходах 7 блока 3 управления формируются коды 1;. 10 - код 001,В данном случае на входах шифратора 21, элементами запрета устанавливается позиционный код 0 " 010, а . на входах шифратора 21 г - код 0 01. 45 Кроме того, на выходах элементов ИЛИ 22 формируется код 0011. Единичным сигналом с выхода элемента ИЛИ 22 элементы 18 запрета удержи 1ваются в закрытом состоянии, поэтому двоичный код с выхода шифратора 21, поступает через блок элементов И 19, на входы дешифратора 20. При этом на втором выходе дешифратора 20 формируется единичный сигнал, открывающий элементыИ 15 всех групп уже во втором блоке 1 г формирования очереди. Двоичный код поступающей заявки записывается в последние разряды реФормула изобретения Устройство для органиэации очереди по авт,св, У 1126964, о т л ич а ю щ е е с я тем, что, с целью расширения области применения.за счет распределения заявокмежду ресурсами, оно содержит (К.-1) блоков Формирования очереди (К-число однотипных ресурсов) и блок управления, который содержит дешифратор и каналы, каждый из которых, кроме последнего, содержит группу элементов запрета, элемент ИЛИ, шифратор, элемент запрета и блок элементов И, последний канал содержит группу элементов запрета, элемент ИЛИ, шифратор и блок элементов И, 1-я группа информационных входов. блока управления (1=1, 2, " , К)подключена к первой группе информационных выходов 1-го блока формирования 5очереди, вход считывания каждого блока формирования очереди соединен с одноименным входом считывания устройства, 1-й тактовый вход которого (1 = 2, 3, ", К) подключен к тактовому входу 1-го блока формирования5 14799 очереди, группа информационных входов которого подключена к группе выходов шифратора, каждый сигнальный вход устройства соединен с входом го 5 товности одноименного блока формирования очереди, вход считывания каждого блока формирования очереди соединен с одноименным выходом группы выходов блока управления, группа выходов дешифратора блока управления является группой выходов блока управления, выходы блоков элементов И каналов блока управления объединены и соединены с входами дешифратора, группа входов блока элементов И каждого канала блока управления соединена с группой выходов шифратора своего канала, управляющий вход блока элементов И каждого канала блока управления, кроме последнего канала,соединен с выходом элемента запрета своего канала, управляющий вход блока элементов И последнего канала блока управления соединен с выходом элемен та ИЛИ своего канала, прямой вход элемента запрета каждого блока управления, кроме последнего канала, соезо6динен с выходом элемента ИЛИ своегоканала, выход элемента ИЛИ каждогоканала блока управления, начиная споследнего, соединен с соответствующими инверсными входами элементовзапрета всех предыдущих каналов,каждый вход первой группы информационных входов блока управления соединен с соответствующими инверснымивходами элементов запрета группы одноименного канала блока управления,с первыми входами шифратора одноименного канала и элемента ИЛИ одноименного канала блока управления, 1-йвход д-й группы информационных входов блока управления ( = 2, 3, "К, 1 = 1, ", и, и - количество выходов блока формирования очереди) соединен с прямым входом ( -1)-гоэлемента запрета группы х-го каналаи с соответствующими инверсными входами всех последующих элементов запрета данной группы, выходы элементов запрета группы каждого каналаблока управления соединены с входами элемента ИЛИ и шифратора своегоканала,1479930 оставитедь М,Кудряшев ехред А.Кравчук Ко Редакт ор Л,Патаи впн аказ 2543/46 Тираж 669 Подписное НИИЛИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, 3-35, Раушская наб., д. 45 Производственно-издательский комбинат "Патент", г,ужгород, уп. Гагарина, 10