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

СОЮЗ СОВЕТСНИХСОЦИДЛИСТИЧЕСНРЕСПУБЛИК И 11 Е 51) С 0 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИПРИ МНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИ ВТОРСКОМУ СВИ ЬСТВУ(57) Изтельной РОИСТВ ГАНИ ЗАЦИЬ ретен ехник тноси яисл ожет быть пол ных вычислиизации до ван многопроце тельных системах при орга ступа к однотипным ресурс изобретения - повьппение н устройства за счет перера ния потока заявок при отк сов, Устройство для орган реди содержит 1 с блоков Ф ния очереди, блок управле дежност пределе зах ресурзации очермироваия регистИзобретение относитсятельной технике и можетзовано в многопроцессорньтельных системах при орг к вычислиыть испольх вычислинизации до ам, ьппение натупа к однотипным Цель изобретения ежности за ечет пеесурс - пов ерасп ресур а стр устро еделени заявок при от На фиг,1 п зах еде уктурнаяйства дляиг.2 - струкения; наблока Форхема предлагаемо рганиэации очере турная схемафиг.3 - струкмирования оче равл хема локаурнаяеди.(56) Авторское свидетельство СССРМ 1479930, кл, С 06 Р 9/4 б, 1987. ра заявок, буферный регистр заявок, регистр отказов ресурсов, буферный регистр отказов ресурсов, регистр готовности ресурсов, восемь групп элементов И, группу элементов ИПК-НЕ, блок, из 1 групп элементов И ф - число ресурсов) пять элементов задержки, три элемента И, элемент ИЛИ, два триггера, генератор импульсов, Устройство может работать в режимах формирования очереди при отсутствии и наличии отказов ресурсов, При наличии отказов какого-либо ресурса очередь заявок из соответствующего блока формирования очереди перераспределяется между работоспособными ресурсами, а поступающие заявки во время цикла пе-рераспределения запоминаются во входном регистре заявок. После перераспределения заявок из очереди к отказавшему ресурсу производится формирование очередей из регистра заявок, 3 ил. Устройство для организации очереди (фиг,1) содержит блок 1 управления, блоки 2 формирования очереди, ре;. гистр 3 заявок, буферный регистр 4 заявок, триггер 5, генератор 6 импулвсов, элемент И 7, элементы 8-12 задержки, группу элементов И 13, группу элементов И 14, элементы И 15 и 1 б, триггер 17, группу элементов ИЛИ 18, группу элементов И 19, регистр 20 готовности ресурсов, группы элементов И 21 и 22, блок 23 групп элементов И, группу элементов И 24, буферный регистр 25 отказов ресурсов, группу элементовИ 26, группу элементов ИЛИ-НЕ 27,группу элементов И 28, регистр 29 отказов ресурсов, элемент ИЛИ 30, шифратор 31, тактовый вход 32 блока 2,вход 33 считывания блока 2, вход 34управления блока 2, вход 35 выбора элемента блока 2, вход 36 восстановленияблока 2; вход 37 готовности блока 2,вход 38 выбора блока 2 группу ннфор 10мационных выходов 39 блока 2, группу информационных выходов 40 блока2 группу информационных выходов 41блока 2, группу информационных входов42 блока 2, входы 43 и 44 пуска и ос"такова устройства соответственно, входы 45 готовности ресурсов устройства,сигнальные входы 46 и 47 устройства,запросные входы 48 устройства, входы49 готовности блоков 2 устройства.30Блок 1 управления (фиг,2/ содержитгруппы элементов 50 запрета, группушифраторов 51, группу элементов ИЛИ52, группу элементов 53 запрета, группу блоков элементов И 5 и дешифратор 55,Каждый блокФормироньнич очереди фиг,3) содержит групу регистрон56 сдвига, группы элементов И 57,группу элементов ИЛИ-НЕ 58., группуэлементов ИЛИ 59 и дешифратор 60.30Устройство работает следующим .оразом,Исходное состояние устройства характеризуется тем что регистры 56 сдвига в каждом блоке формирования очередищ регистры 20, 25 и 29 триггеры 5 и 17 установлены в состояние 11 110 . Работа устройства по форми ро ванию очереди выполняется как при о тсутс твии отказов ресурсов , т ак и и ри поступлении от одного иб о н ес к ольких ресурсов сигналов отказов , При необходимо с ти использования устройства для формирования очереди к одно типным ресурсам опер ацио нна я система ЭВМ определяет число исп оль э уемых н вычислительном процессе ресурсов , Для исключения из цикла формир ования очереди к неиспользованным ресурсам 50 по соответствующим входам 4 9 подаются единичные сигналы , посредством кото, рых ус т ананлив аются в единичное с остояние в се разряды регистров 5 6 сдвига , Э тим самым имитируется пол ное э аполнение очереди к данному р есурсу и соответствующий блок 2 Формирон ания очереди исключается и з анализа состояния очередей к остальнымресурсам,Рассмотрим работу устройства приготовности к обслуживанию всех ресурсов, когда от них не поступают сигналы отказов. В данном случае работаустройства состоит из двух этапов.На первом этапе производится формиронание очереди, а на втором - обслуживание заявок.Формирование очереди производитсядля каждого свободного ресурса ЭВМс учетом наличия заявок в каждом блоке 2. Поступающая заявка направляется в тот блок 2, где сформировананаименьшая очередь, Если число заявокв ряде блоков 2 одинаково, то заявка ставится в очередь н блоке с наименьшим номером, Распределение поступающих заявок производится блоком 1управления на основе анализа состояний очередей и блоках 2 Формиронания очереди,Очередь заянок Формируется следующим образом,Если нсе ресурсы готовы к обслуживанию, то по входам 37 в блоки 2сигналы не поступают, регистры 56находятся н состояниях 0, Все блоки 2 работают одинаково, Так как регистры 29 и 56 нахоцятся н нулевыхсостояниях, то на выходе последнегоэлемента ИЛИ-НЕ 58 формируется единичный сигнал, открывающий последниеэлементы И 57 во всех группах, Поединичному сигналу с выхода элементаИЛИ-НЕ 58 все остальные элементыИЛИ-НЕ 58 формируют нулевые сигналы,которыми закрыты остальные элементыИ 57 всех групп,Таким образом, только на последних входах 40 сформированы единичныесигналы поступающие (Фиг,2) на входыэлементов 50 запрета, Элементы 50 запрета каждой группы по входам подключены к позициям входов 40 так, что спомощью элементов 50 запрета определяется наименьший номер из блоков 2 формирования очереди с ранными очередями, Элементами ИЛИ 52 формируетсякод, позиционно указывающий свободные разряды регистра 56 сдвига в блоках 2, Шифраторами 51 формируетсядвоичный код наибольшего номера разрядов регистров 56 из блоков 2 с одинаковой очередью, С помощью элементов 54 запрета, подключенных к выходам элементов ИЛИ 52, определяется75184 6 510 5 ,15наименьший номер блока 2 с наибольшимномером свободных разрядов регистров56 сдвига, Этот номер блока 2 в двоичном коде передается на дешифратор55, на выходе которого формируетсяединичный сигнал, позиционно указывающий номер направления передачи заявок, т,еномер соответствующегоблока 2,В рассматриваемом случае в блоке 1единичным сигналом с входа 40 закрыты по инверсным входам все элементы50 запрета. При этом на входах шифратора 511 формируется позиционныйкод, имеющий единицу в первом разряде, т,е. 0,01, а на выходе шифратора 51 - двоичный код единицы, Кроме того, на выходе элемента ИЛИ 52также сформирован единичный сигналкоторым закрыты по первым инверсньмвходам элементы 53 запрета и открытпо управляющему входу блок элементовИ 54, При этом двоичный код единицыпередается на входы дешифратора 55,на первом выходе которого появляетсяединичный сигнал, который поступаетпо входу 381 в блок 2 1 формированияочереди, Таким образом, из совокупности всех блоков 2 выбран блок 2,т,е, блок с наименьшим номером,Так как триггер 17 находится в состоянии "0", то единичным сигналом сего нулевого выхода открыты йо первым входам элементы И 4 и по вто-:рым входам - элементы И 13, 14 иИ 28,Работа устройства начинается посигналу пуска, поступающему по входу43 на установку в "1" триггера 5,По единичному сигналу с единичноговыхода триггера 5 открывается элементИ 7, обеспечивающий прохождение импульсов генератора 6 на элементы схемыустройства,Поступающие заявки.по входам 48фиксируются в соответствующих разрядах регистра 3, а по импульсу генератора с выхода элемента И 7 поступающему на синхронизирующий вход регистра 4, передаются в него на цикл работы устройства, Этот регистр необходим для исключения воздействия поступающих заявок й цикле работы устройства на состояние элементов схемы,С помощью элементов И 14, включенных с единичными и нулевыми выходамирегистра 4 по приоритетной схеме(приоритет заявок уменьшается с рос 15 20 25 30 35 40 45 50 55 том номера разряда регистра 4), производится формирование унитарного ко.да, поступающего на входы шифратора31, С помощью указанного шифратораэтот код преобразуется в двоичныйкод номера приоритетного на данныймомент времени абонента (заявки) иподается на информационные входы 42блоков 2 формирования очереди и далее на элементы И 57,Так как только на входе 37 блока 1 управления присутствует единичный сигнал, то по импульсу с выходаэлемента 9 задержки, проходящемучерез открытый элемент И 27.1 н поступающему по входу 33 в блок 21, двоичный код номера заявки записывается впоследние разряды регистров 56,Вследствие этого на выходе последнего элемента ИЛИ-НЕ 58 формируетсянулевой сигнал, закрывающий последние элементы И 57 всех групп. Этимже сигналом на выходе предпоследнегоэлемента ИЛИ-НЕ 58 Формируется единичный сигнал, которым открываются предпоследние элементы И 57 всех групп, ана выходах элементов ИЛ 1-НЕ 58 устанавливаются нулевые сигналы,Таким образом, на входах 40 блока 1 Формируется позиционный код,имеющий единицу в предпоследней позиции т,е, 01000, В данном случаена входах шифратора 51 элементами 50,запрета устанавливается позиционныйкод 0,01, Кроме того, на выходахэлементов ИЛИ 52 Формируется код0011. Единичным сигналом с выходаэлемента ИЛИ 57. элементы 53 запрета удерживаются в закрытом .состояниипоэтому двоичный код с выхода шифратора 51 поступает через блок элементов И 54 на входы девфратора 54При этом на втором выходе дешифратора 54 Формируется единичный сигнал,открывающий элементы И 57 всех группуже во втором блоке 2 Формированияочереди . Двоичный код погтупающейзаявки записывается в последние разряды регистров 56 блока 2 аналогично рассмотренному,В дальнейшем работа устройства поФормированию очереди производится таким образом, пока все заявки не разместятся поочередно в каждом блоке 2. Устройство совместно с обслуживающими ресурсами работает следующим образом, 575184Пусть в регистр 3 поступили заявки от первогои второго абонентов, а сигнал готовности от К-го ресурса, т.е. после завершения обслуживания предыдущей заявки, по входу 45 через элемент ИЛИ 18на единичный вход разряда 20.регистра готовности ресурсов, По импульсу генератора 6 с выхода элемента И 7 заявки с выходов разрядов 3 и 3 устанавливают в "1" разряды 4 и 4 . Так как сигналы отказов ресурсов отсутствуютна выходе элемента ИЛИ 30 формируется нулевой сигнал, которым закрыт элемент И 61 а по инверсному входу открыт элемент И 15. Поэтому сигналом с выхода элемента 8 задержки подтверждается нулевое состояние триггера 17. Время задержки элементом 8 определяется временем переходных процессов в элементах И 28, регистре 25 и элементе ИЛИ 30.Импульсом с выхода элемента 9 задержки двоичный код первого абонента с выходов шифратора 31 записывается в тот блок 2 формирования очереди, где имеется наименьшая очередь через соответствующий элемент И 22. Время задержки элементов 9 задержки определяется временем переходных процессов в элементе И 15 и триггере 17.По импульсу с выхода элемента 10 задержки, время которого определяет 35 ся переходными процессами в элементах И 57 и регистрах 56, в блоке 2через открытый элемент И 21 производится сдвиг содержимого регистров 56, По импульсу с выхода элемента 11 задержки, время которого определяется переходными процессами в регистрах 56, через открытый элемент И 19 к ус 11 11 танавливае тся в состояние 0 р аз - 45ряд 20 кПо очередному импульсу г енера тора 6 номер второго абонента передается в блок 2где сфо рмирована наименьшая очередь , При наличии отказов ресурсов производится внач але перераспределение заявок из очереди неисправного ресурса, а затем распределение поступивших заявок из регистра 3 , Пусть о т первого р есур са по входу 4 6 1 в первый разряд 2 1 регистра 2 1 поступил сигнал отказа , а в первый разряд 3регистра 3 - сигнал заявки от первого абонента Но импульсу генератора 6 с выхода. эл емента И 7 заявка из разряда 3 передается в первый разряд регистра 4.Элемент И 28 открыт по второмувходу единичным сигналом с нулевоговыхода триггера 17, по третьему входу - единичным сигналом с единичноговыхода разряда 29 а по инверсномупри наличии очереди в блоке 2; - нулевым сигналом с выхода элемента ИЛИ-НЕ27 , Поэтому импульсом с выхода элемента И 7 через открытый элемент И 28.устанавливаются в состояние "1" первый разряд регистра 25 и через элементИЛИ 18 - первый разряд регистра 20,После установки разряда 25 веди очное состояние на выходе элемента ИЛ 30 формируется единичный сигнал, которым открывается элемент И 16,а по инверсному входу закрывается элемент И 15. Поэтому импульсом с выходаэлемента,8 задержки триггер 17 устанавливается в состояние "1", Нулевым сигналом с нулевого выхода триггера 17 закрываются элементы И 13 и14, блокируя для анализа выходныесигналы регистра 14, и элементы И 28,исключая на время перераспределениязаявок из очереди к первому ресурсупоступающие сигналы отказов от других ресурсов,Единичным сигналом с единичноговыхода триггера 17 открываются группы элементов И 23, обеспечивая поступление двоичных кодов абонентов из блока 2, С помощью элементов И 24, включенных с выходами регистра 25 по приоритетной схеме (приоритет убываетс ростом номера разряда), из единичных сигналов формируется унитарныйкод. В данном случае нулевым сигналомс нулевого выхода разряда 251 закрыты все элементы И 24, а единичнымсигналом с единичного выхода разряда25 открыты по вторым входам все элементы И 23 первой группы блока. Приэтом двоичный код номера заявки с выходов последних разрядов регистров 56блока 2 с его выходов 41 через открытые элементы И 23 поступает навходы 42 блоков 2. Единичным сигналомс единичного выхода первого разрядарегистра 29, поступающим по входу 34в блок 2 на элементы ИЛИ-НЕ 58, принудительно на выходах 401 элементовИЛИ-НЕ 58 формируют нулевые сигналы.Этим самым производится исключениеиз анализа в блоке 1 состояния очереди заявок в блоке 2, 1575184 1 ОПо сигналу с выхода элемента 9 за- держки двоичный код номера абонента записывается в регистры 56 выбранного блока 2, имеющего наименьшую очередь, После записи заявки в очередь производится сдвиг кодов в регистрах 56 в блоке 21 по сигналу с выхода элемента 11 задержки через открытый элемент И 211 и гашение первого разряда регистра 20 через открытый элемент И 191. Время задержки элементом 11 определяется временем переходных процессов в элементах И 57 и регистре 56. По завершении сдвига кодов в регистрах 56 на выходах 41 блока 2 устанавливается двоичный код номера очередного абонента либо нулевой код при отсутствии в данном блоке очереди заявок.Так как в блоке 2 имеется очередь, то на выходе элемента ИЛИ-НЕ 27 удерживается нулевой сигнал, которым элемент И 26 закрыт. Поэтому первый разряд регистра 25 остается в единичном 25 состоянии. По очередному импульсу генератора 6 выполняется передача двоичного кода номера абонента из блока 2 в другой блок 2 с наименьшей очередью в соответствии с рассмотренным. После сдвига кодов в регистрах 56 ,блока 2 на его выходах 41 устанавливается нулевой код. При этом на выходе элемента ИЛИ-НЕ 27 формируетСя единичный сигнал, открывающий элемент И 26, через который по импульсу с выхода элемента 11 задержки устанавливается в состояние "0" первый разряд регистра 25. Так как все разряды регистра 25 после этого . оказываются в нулевых состояниях, то на выходе элемента ИЛИ 30 формируется нулевой сигнал, открывающий по инверсному входу элемент И 15, через который по импульсу с выхода элемента 12 задержки триггер 17 устанавливается в нулевое состояниеВ дальнейшем при наличии заявки в первом разряде регистра 3 производится передача двооо кода первого абонента 50 в блок 2 с наименьшей очередью.Если в процессе работы произошло восстановление работоспособности отказавшего ранее ресурса, то по соответствующему входу 47 поступает сигнал восстановления. По этому сигналу одноименный разряд регистра 29 и регистры 56 в соответствующем блоке 2 устанавливаются в нулевые состояния,тем самым включая данный блок в процесс формирования очереди,ф о р м у л а изобретенияУстройство для организации очереди по авт.св. У 1479930, о т л и ч аю щ е е с я тем, что, с целью повышения надежности за счет перераспределения заявок при отказах ресурсов, оно содержит регистр заявок, единичные входы разрядов которого являются запросными входами устройства, буФерный регистр заявок, регистр отказов ресурсов, единичные и нулевые входы которого являются сигнальными входами устройства, буферный регистр отказов ресурсов, регистр готовности ресурсов, восемь групп элементов И, группу элементов ИЛИ-НЕ, блок из К групп элементов И (К - число ресурсов), пять элементов задержки, три элемента И, элемент ИЛИ, первый триггер, второй трйггер, единичный и нулевой входы которого являются входами пуска и останова устройства соответственно, генератор импульсов, выход которого подключен к первому входу первого элемента И, второй вход которого соединен с единичным выходом второго триггера, а выход первого элемента И соединен с первыми входами элементов И первой группы, с входом синхронизации буферного регистра заявок, информационные входы которого подключены к выходам регистра заявок, выход первого элемента И через первый элемент задержки соединен с входом второго элемента задержки и с первым входом второго элемента И, выход которого соединен с единичным входом первого триггера, единичный выход которого подключен к первым входам элементов И всех групп блока и вторым входам элементов И седьмой группы, нулевой выход первого триггера соединен с первыми входами элементов И второй группы и с первыми входами элементов И третьей группы, выход второго элемента задержки подключен к первым входам элементов И четвертой группы и через третий элемент задержки - к первым входам элементов И пятой группы и к входу четвертого элемента задержки, выход которого соединен с первыми входами элементов И шестой группы, с первыми входами элементов И седьмой группы, через пятый элемент задерж ки - с прямым входом третьего элемента И, выход которого подключен к нулевому входу второго триггера, выход четвертого элемента задержки соединен с вторыми входами элементов И вто-рой группы, выходы которых подключены к нулевым входам одноименных разрядов регистра заявок, единичные выходы разрядов регистра готовности ресур 10 сов соединены с вторыми входами одноименных элементов И пятой и шестой групп, выходы элементов ИЛИ группы подключены к единичным входам одноименных разрядов регистра готовности ресурсов, нулевые выходы разрядов которого соединены с вторыми входами одноименных элементов И четвертой группы, единичные выходы разрядов буферного регистра заявок подключены к вторым входам одноименных элементов И третьей группы, инверсный выход разряда буферного регистра заявок соеди.нен с соответствующими входами всех последующих элементов И второй груп пы, выходы элементов И третьей группы подключены к входам шифратора и к третьим входам одноименных элементов И второй группы, выходы шифратора объединены с выходами одноименных элементов И всех групп блока, единичные выходы разрядов регистра отказов ресурсов соединены с входами управления одноименных блоков формирования очереди и третьими входами одноименных элементов И первой группы, выходы которых подключены к единичним входам одноименных разрядов буферного регистра отказов ресурсов и с.первыми входами одноименных элемен О тов ИЛИ группы, вторые входы которых являются соответствующими входами готовности устройства, нулевой выход каждого разряда регистра отказов ресурсов подключен к входу выбора абонента одноименного блока формирования очереди, третья группа информационных выходов каждого из которых соединена с входами одноименного элемента ИЛИ-НЕ группы выходы коф5 О торых подключены к инверсным входам одноименных элементов И первой группы и к третьим входам одноименныхэлементов И седьмой группы выходыкоторых соединены с нулевыми входамиодноименных разрядов буферного регистра отказов, единичный выход первогоразряда которого подключен к первомувходу элемента ИЛИ и к вторым входам элементов И первой группы блока,единичный выход 1-го (1=1К) разряда буферного регистра отказов ресурсов соединен с первым входом (1-1)го элемента И восьмой группы и с 1-мвходом элемента ИЛИ, выход которогоподключен к второму входу второгоэлемента И и инверсному входу третьего элемента И, нулевой выход каждого разряда буферного регистра отказов соединен с соответствующими входами одноименного и всех последующихэлементов И восьмой группы, выходЦ)-го элемента И восьмой группыподключен к вторым входам элементов И-й группы блока, третий вход каждого элемента И каждой группы блока соединен с одноименным выходом третьейгруппы информационных выходов одноименного блока формирования очереди,выходы элементов И четвертой и пятойгрупп подключены соответственно к так.тоьым входам и входам считывания одноименных блоков формирования очереди, входы восстановления которых соединены с нулевыми входами одноименныхразрядов регистра отказов ресурсов, вкаждом блоке формирования очередивход выбора абонента подключен к синхронизирующему входу дешифратора, авход управления соединен с соответствующими входами элементов ИЛИ-НЕ,выходы последних разрядов регистровявляются третьей группой информационных выходов блока формирования очереди, вход восстановления которогосоедлнен с входами установки в "Орегистров сдвига этого блока, выходыэлементов И шестой группы соединеныс нулевыми входами регистра готовности ресурсов.1575184 Составитель М, КудряшевРедактор Р.Середа Техред Л.Сердюкова Корректор Э.Лончакова Яака тельский комбинат "Патент", г. Ужгород, ул. Гагарина,роизводствен 85 Тираж 573 Подписное ВНИИПИ Государственного комитета по изобретениям и открытия 113035, Москва, Ж, Раушская наб., д. 4/5 ри ГКНТ СЧС1