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

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

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

На фиг,1 приведена структурная схема предлагаемого устройства для организации очереди; на фиг.2 - структурная схема блока управления; на фиг.З - структурная схема блока формирования очереди.

Устройство для организации очереди (фиг,1) содержит блок 1 управления, блоки 2 формирования очереди, peV гистр 3 заявок, буферный регистр 4 заявок, триггер 5, генератор 6 импулысов, элемент И 7, элементы 8-12 задержки, группу элементов И 13, группу элементов И 14, элементы И 15 и 16, триггер 17, группу элементов ИЛИ 18, группу элементов И 19, регистр 20 готовности ресурсов, группы элементов И 21 и 22, блок 23 групп элементов И, группу элементов И 24, буферный регистр 25 отказов ресурсов, группу элементов

сд

vl

ел

00 4

ю

И 26, группу элементов Ш1И-НЕ 27, группу элементов И 28, регистр 29 отказов ресурсов, элемент ИЛИ 30, шифратор 31, тактовый вход 32 блока 2, вход 33 считывания блока 2, вход 34 управления блока 2, вход 35 выбора элемента блока 2, вход 36 восстановления блока 2,- вход 37 готовности блока 2, вход 38 выбора блока 2, группу инфор- мационных выходов 39 блока 2, группу информационных выходов 40 блока 2, группу информационных выходов 41 блока 2, группу информационных входов 42 блока ., входы 43 и 44 пуска и ос- танова устройства соответственно, входы 45 готовности ресурсов устройства, сигнальные входы 46 и 47 устройствat запросные входы 48 устройства, входы 49 готовности блоков 2 устройства,

Блок 1 управления (фиг,2/ содержит группы элементов 50 запрета, группу шифраторов 51, группу элементов ИЛИ 52, группу элементов 53 запрет, группу блоков элементов И У р дешифра- тор 55.

Каждый блок фо мчрон т,нич очереди (фиг.З) содержкгг группу регистров 56 сдвига, группы элементов И 57S группу элементов ИПИ-НЕ 58, группу элементов ИЛИ 5V и дешифратор 60,

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

Исходное состояние устройства характеризуется тем, что регистры 56 сдвига в каждом блоке формирования очереди регистры 20, 25 и 29, триггеры 5 и 17 установлены в состояние О, Работа устройства по формированию очереди выполняется как при отсутствии отказов ресурсов так и при поступлении от одного либо нескольких ресурсов сигналов отказов. При необходимости использования устройства для формирования очереди к однотипным ресурсам операционная система ЭВМ определяет число используемых в вычислительном процессе ресурсов t Для исключения из цикла формирования очереди к неиспользованным ресурсам по соответствующим входам 49 подаются единичные сигналы, посредством кото- . рых устанавливаются в единичное состояние все разряды регистров 56 сдвига, Этим самым имитируется пол- ное заполнение очереди к данному ресурсу и соответствующий блок 2 формирования очереди исключается из ана

Q л

5

0 5

0

0

5

лиза состояния очередей к остальным ресурсам,

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

Формирование очереди производится для каждого свободного ресурса ЭВМ с учетом наличия заявок в каждом блоке 2„ Поступающая заявка направляется в тот блок 2, где сформирована наименьшая очередь. Если число заявок в ряде блоков 2 одинаково, то заявка ставится в очередь в блоке с наименьшим номером. Распределение поступающих заявок производится блоком 1 управления на основе анализа состояний очередей в блоках 2 формирования очереди.

Очередь заявок формируется следующим образом.

Если зсе ресурсы готовы к обслуживанию, то по входам 37 в блоки 2 сигналы не поступают,регистры 56 находятся в состояниях О, Все блоки 2 работают одинаково. Так как регистры 29 и 56 находятся в нулевых состояниях, то на выходе последнего элемента ИЛИ-НЕ 58 формируется единичный сигнал, открывающий последние элементы И 57 во всех группах. По единичному сигналу с выхода элемента ИЛИ-НЕ 58 все остальные элементы ИЛИ-НЕ 58 формируют нулевые сигналы, которыми закрыты остальные элементы И 57 всех групп.

Таким образом, только на последних входах 40 сформированы единичные сигналы,, поступающие (фиг,2) на входы элементов 50 запретае Элементы 50 запрета ктждой группы по входам подключены к позициям входов 40 так, что с помощью элементов 50 запрета определяется наименьший номер из блоков 2 формирования очереди с равными очередями. Элементами ИЛИ 52 формируется код, позиционно указывающий свободные разряды регистра 56 сдвига в блоках 2, Шифраторами 51 формируется двоичный код наибольшего номера разрядов регистров 56 из блоков 2 с одинаковой очередью. С помощью элементов 54 запрета, подключенных к выходам элементов ИЛИ 52, определяется

наименьший номер блока 2 с наибольшим номером свободных разрядов регистров 56 сдвига. Этот номер блока 2 в двоичном коде передается на дешифратор 55, на выходе которого формируется единичный сигнал, позиционно указывающий номер направления передачи заявок, т.е. номер соответствующего блока 2.

В рассматриваемом случае в блоке единичным сигналом с входа 40 закрыты по инверсным входам все элементы 50 запрета. При этом на входах шифратора 51 формируется позиционный код, имеющий единицу в первом разряде, т.е. 0,.,,018 а на выходе шифратора 51 - двоичный код единицы. Кроме того, на выходе элемента ИЛИ 524 также сформирован единичный сигнал, которым закрыты по первым инверсным входам элементы 53 запрета и открыт по управляющему входу блок элементов И 54. При этом двоичный код единицы передается на входы дешифратора 55, на первом выходе которого появляется единичный сигнал, который поступает по входу 38 в блок 2 формирования очереди. Таким образом, из совокупности всех блоков 2 выбран блок 2., , т,е, блок с наименьшим номером.

Так как триггер 17 находится в состоянии О, то единичным сигналом с его нулевого выхода открыты по первым входам элементы И 4 и по вто- рым входам - элементы И 13, 14 и И 28.

Работа устройства начинается по сигналу пуска, поступающему по входу 43 на установку в 1 триггера 5. По единичному сигналу с единичного выхода триггера 5 открывается элемент И 7, обеспечивающий прохождение импульсов генератора 6 на элементы схем устройства.

Поступающие заявки.по входам 48 фиксируются в соответствующих разрядах регистра 3, а по импульсу генератора с выхода элемента И 7, поступающему на синхронизирующий вход регистра 4, передаются в него на цикл работы устройства. Этот регистр необходим для исключения воздействия поступающих заявок Ё цикле работы устройства на состояние элементов схемы,

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

5

0

5

том номера разряда регистра 4), производится формирование унитарного кода, поступающего на входы шифратора 31, С помощью указанного шифратора этот код преобразуется в двоичный код номера приоритетного на данный момент времени абонента (заявки) и подается на информационные входы 42 блоков 2 формирования очереди и далее на элементы И 57,

Так как только на входе 37 блока 1 управления присутствует единичный сигнал, то по импульсу с выхода элемента 9 задержки, проходящему через открытый элемент И 7.2 и поступающему по входу 33 в блок 2, ный код номера заявки последние разряды регистров 56,

Вследствие этого на выходе последнего элемента ИЛИ-НЕ 58 формируется нулевой сигнал, закрывающий последние элементы И 57 всех групп. Этим же сигналом на выходе предпоследнего элемента ИЛИ-НЕ 58 формируется единичный сигнал, которым открываются предпоследние элементы И 57 всех групп, а на выходах элементов KJIK-HR 58 устанавливаются нvлeвыe сигналы.

. ( двоич- записывается в

30

Таким образом, на входах 404 блока 1 формируется позиционный код, имеющий единицу в предпоследней позиции } т.е. 010...00. В данном случае на входах шифратора 51 элементами 50,,

запрета устанавливается позиционный код 0....01. Кроме того, на выходах элементов ИЛИ 52 формируется код 0....011. Единичным сигналом с выхода элемента ИЛИ 52( элементы 53 запрета Удерживаются в закрытом состоянии поэтому двоичный код с выхода шифратора 51,, поступает через блок элементов И 54 ,j на входы дешифратора 54. При этом на втором выходе дешифратоpa 54 формируется единичный сигнал, открывающий элементы И 57 всех групп уже во втором блоке 2 формирования очереди. Двоичный код поступающей заявки записывается в последние раз

ряды регистров 56 блока 22 аналогично рассмотренному.

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

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

jЈ устанавливают в 1 Так как сигналы отк

71

Пусть в регистр 3 поступили заявки от первого и второго абонентов, а сигнал готовности от К-го ресурса, т.е. после завершения обслуживания предыдущей заявки, по входу 45% через элемент ИЛИ 18к на единичный вхо разряда 20.регистра готовности ресурсов. По импульсу генератора 6 с входа элемента К 7 заявки с выходов разрядов 31 и 3 разряды 4 и 4 г

зов ресурсов отсутствуют на выходе элемента ИЛИ 30 формируется нулевой сигнал, которым закрыт элемент И 16, а по инверсному входу открыт элемент И 15. Поэтому сигналом с выхода элемента 8 задержки подтверждается нулевое состояние триггера 17. Время задержки элементом 8 определяется временем переходных процессов в элементах И 28, регистре 25 и элементе ИЛИ 30.

Импульсом с выхода элемента 9 задержки двоичный код первого абонента с выходов шифратора 31 записывается в тот блок 2 формирования очереди, где имеется наименьшая очередь через соответствующий элемент И 22. Время задержки элементов 9 задержки определяется временем переходных процессов в элементе И 15 и триг 17.

гере I

По импульсу с выхода элемента 10 задержки, время которого определяется переходными процессами в элементах И 57 и регистрах 56, в блоке 2К через открытый элемент И 21 производится сдвиг содержимого регистров 56 По импульсу с выхода элемента 11 задержки, время которого определяется переходными процессами в регистрах 56, через открытый элемент И 19 устанавливается в состояние О раз- ряд 20 к. По очередному импульсу генератора 6 номер второго абонента передается в блок 2, где сформирована наименьшая очередь. При наличии отказов ресурсов производится вначале перераспределение заявок из очереди неисправного ресурса, а затем распределение поступивших заявок из регистра 3. Пусть от первого ресурса по входу 46 в первый разряд 21 нудительно на выходах 40 элементов регистра 21 поступил сигнал отказа, ИЛИ-НЕ 58 формируют нулевые сигналы. а в первый разряд 3, регистра 3 - сигнал заявки от первого абонента. По импульсу генератора 6 с выхода, элеЭтим самым производится исключение из анализа в блоке 1 состояния очере

ди заявок в блоке 2

Г

0

5

5184

0

5

30

35

45

50

8

мента И 7 заявка из разряда 3 передается в первый разряд регистра 4. Элемент И 28, открыт по второму входу единичным сигналом с нулевого выхода триггера 17, по третьему входу - единичным сигналом с единичного выхода разряда 29п а по инверсному

при наличии очереди в блоке 2 - нулевым сигналом с выхода элемента ИЛИ-НЕ 27.. Поэтому импульсом с выхода элемента И 7 через открытый элемент И 28/, устанавливаются в состояние 1 первый разряд регистра 25 и через элемент ИЛИ 18. - первый разряд регистра 20.

После установки разряда 25 в еди тчное состояние на выходе элемента И1Ш 30 формируется единичный сигнал, которым открывается элемент И 16, а по инверсному входу закрывается элемент И 15 о Поэтому импульсом с выхода элемента .8 задержки триггер 17 устанавливается в состояние 1. Нулевым сигналом с нулевого выхода триггера 17 закрываются элементы И 13 и 14, блокируя для анализа выходные сигналы регистра 14, и элементы И 28, исключая на время перераспределения заявок из очереди к первому ресурсу поступающие сигналы отказов от других ресурсов о

Единичным сигналом с единичного выхода триггера 17 открываются группы элементов И 23, обеспечивая поступление двоичных кодов абонентов из блока 2,|. С помощью элементов И 24, включенных с выходами регистра 25 по приоритетной схеме (приоритет убывает с ростом номера разряда), из единич- 4Q ных сигналов формируется унитарный код. В данном случае нулевым сигналом с нулевого выхода разряда 25 закрыты все элементы И 24, а единичным сигналом с единичного выхода разряда 25f открыты по вторым входам все элементы И 23 первой группы блока. При этом двоичный код номера заявки с выходов последних разрядов регистров 56 блока 2 с его выходов 41 через открытые элементы И 23f поступает на входы 42 блоков 2, Единичным сигналом с единичного выхода первого разряда регистра 29, поступающим по входу 34,, в блок 2 на элементы ИЛИ-НЕ 58, принудительно на выходах 40 элементов ИЛИ-НЕ 58 формируют нулевые сигналы.

Этим самым производится исключение из анализа в блоке 1 состояния очеренудительно на выходах ИЛИ-НЕ 58 формируют н

ди заявок в блоке 2

Г

915

По сигналу с выхода элемента 9 задержки двоичный код номера абонента записывается в регистры 56 выбранного блока 2, имеющего наименьшую очередь. После записи заявки в очередь производится сдвиг кодов в регистрах 56 в блоке 2( по сигналу с выхода элемента 11 задержки через открытый элемент И 21 и гашение первого раз- ряда регистра 20 через открытый элемент И 19,. Время задержки элементом 11 определяется временем переходных процессов в элементах И 57 и регистре 56. По завершении сдвига кодов в регистрах 56 на выходах 41 блока 2# устанавливается двоичный код номера очередного абонента либо нулевой код при отсутствии в данном блоке очереди заявок.

Так как в блоке 2t имеется очередь то на выходе элемента ИЛИ-НЕ 27 удерживается нулевой сигнал, которым элемент И 261- закрыт. Поэтому первый разряд регистра 25 остается в единичном состоянии По очередному импульсу генератора 6 выполняется передача двоичного кода номера абонента из блока 2f в другой блок 2 с наименьшей очередью в соответствии с рассмотренным. После сдвига кодов в регистрах 56 -блока 2, на его выходах 41 устанавливается нулевой код. При этом на выходе элемента ИЛИ-НЕ 27f формируется единичный сигнал, открываю- щий элемент И через который по импульсу с выхода элемента 11 задержки устанавливается в состояние О первый разряд регистра 25. Так как все разряды регистра 25 после этого оказываются в нулевых состояниях, то на выходе элемента ИЛИ 30 формируется нулевой сигнал, открывающий по инверсному входу элемент И 15, через который по импульсу с выхода элемён- та 12 задержки триггер 17 устанавливается в нулевое состояние. В дальнейшем при наличии заявки в первом разряде регистра 3 производится передача двоичного кода первого абонента в блок 2 с наименьшей очередью.

Если в процессе работы произошло восстановление работоспособности отказавшего ранее ресурса, то по соответствующему входу 47 поступает сиг- нал восстановления. По этому сигналу одноименный разряд регистра 29 и регистры 56 в соответствующем блоке 2 устанавливаются в нулевые состояния.

84

10

5

0

П

5 0 Q «

тем самым включая данный блок в процесс формирования очереди.

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

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

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

5

одноименных элементов И первой группы и к третьим входам одноименных элементов И седьмой группы, выходы которых соединены с нулевыми входами одноименных разрядов буферного регистра отказов, единичный выход первого разряда которого подключен к первому входу элемента ИЛИ и к вторым входам элементов И первой группы блока, единичный выход j-го (,...,K) разряда буферного регистра отказов ресурсов соединен с первым входом (j-1)- го элемента И восьмой группы и с j-м входом элемента ИЛИ, выход которого

0

5

5

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

5

0

43

.tOt .... ,вя

У

Щ Щ

ФигЛ

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

WIS/1SI

v Составитель М.Кудряшев Редактор Ю.Середа Техред Л.Сердюкова Корректор Э.Лончакова

Заказ 1785

Тираж 573

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ CCJICP 113035, Москва, Ж-35, Раушская наб., д. 4/5

Подписное