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

 

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

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

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

РЕСПУБЛИК (Д1) С 06 F 9/46

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

К А BTOPCHOMV СВИДЕТЕЛЬСТВУ

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

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

ПРИ fKHT СССР (61) 1479930 (21) 4415964/24-24 (22) 03.05g88 (46) 30.06 90. Вюл. N- 24 (72) В.Г.Попов, А.Х.Ганитулин, И.В,Ступин и В.В,Туравинин (53) 681,325(088,8) (56) Авторское свидетельство СССР

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

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

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

3 ил.

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

25 отказов ресурсов, группу элементов

1575184

И 26, группу элементов ИЛИ-НЕ 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 блока 2, входы 43 и 44 пуска и ос" такова устройства соответственно, входы 45 готовности ресурсов устройства, сигнальные входы 46 и 47 устройства, запросные входы 48 устройства, входы

49 готовности блоков 2 устройства.

Блок 1 управления (фиг,2) содержит группы элементов 50 запрета, группу шифраторов 51, группу элемеHToH ИЛИ

52, группу элементов 53 запрета, группу блоков элементов И 5 - I ленифратор 55.

Каждый блок ? формиро.н-.íè÷ очереди (фиг,3) содержит гру пу регистров

56 сдвига, группы элементов И 57, группу элементов ИЛИ-НЕ 58., группу элементов ИЛИ 59 и дешифратор 60.

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

Исходное состояние устройства характеризуется тем, что регистры 56 сдвига в каждом блоке формирования очереди регистры 20, 25 и 29,, триггеры 5 и 17 установлены в состояние

"0". Работа устройства по формирова40

HHIo очереди выполняется как при отсутствии отказов ресурсов. так и при поступлении от одного .тибо нескольких ресурсов сигналов отказов, При необходимости использования устройства для формирования очереди к однотип45 ным ресурсам операционная система

ЭВМ определяет число используемых н вычислительном процессе ресурсов, Для исключения из цикла формирования очереди к неиспользованным ресурсам 50 по соответствующим входам 49 подаются единичные сигналы, посредством кото. рых устананливаются в единичное состояние все разряды регистров 56 сдвига, Этим самым имитируется пол- 55 ное заполнение очереди к данному ресурсу и соответствующий блок 2 формирования очереди исключается из анализа состояния очередей к остальным ресурсам, Рассмотрим работу устройства при готовности к обслуживанию всех ресурсов, когда от них не поступают сиг налы отказов. В данном случае работа устройства состоит из двух этапов.

На первом этапе производится формиронание очереди, а на втором — обслуживание заявок.

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

ИЛИ-НЕ 58 все остальные элементы

ИЛИ-НЕ 58 формируют нулевые сигналы, которыми закрыты остальные элементы

И 57 всех групп, Таким образом, только на последних входах 40 сформированы единичные сигналы, поступающие (фиг,2) на входы

"-.ëåèeíòoI 50 запрета, Элементы 50 запрета каждой группы по входам подключены к позициям входов 40 так, что с помощью элементов 50 запрета определяется наименьший номер из блоков 2 формирования очереди с ранными очередями, Элементами ИЛИ 52 формируется код, позиционно указывающий свободные разряды регистра 56 сдвига в блоках 2, Шифраторами 51 формируется двоичный код наибольшего номера разрядов регистров 56 из блоков 2 с одинаковой очередью, С помощью элементов 54 запрета, подключенных к выходам элементов ИЛИ 52, определяется

75184 6

10

5,15 наименьший номер блока 2 с наибольшим. номером свободных разрядов регистров

56 сдвига, Этот номер блока 2 в двоичном коде передается на дешифратор

55, на выходе которого формируется единичный сигнал, позиционно указывающий номер направления передачи заявок, т,е ° номер соответствующего блока 2, В рассматриваемом случае в блоке 1 единичным сигналом с входа 40 закрыты по инверсным входам все элементы

50< запрета. При этом на входах шифратора 51< формируется позиционный код, имеющий единицу в первом разряде, т,е. 0...,01, а на выходе шифратора 51 — двоичный код единицы, Кроме того, на выходе элемента ИЛИ 52 также сформирован единичный сигнал, которым закрыты по первым инверснь м входам элементы 53 запрета и открыт по управляющему входу блок элементов

И 54, При этом двоичный код единицы передается на входы дешифратора 55, на первом выходе которого появляется единичный сигнал, который поступает по входу 38 в блок 2 формирования очереди, Таким образом, из совокупности всех блоков 2 выбран блок 2, т,е, блок с наименьшим номером, Так как триггер 17 находится в состоянии "0", то единичным сигналом с его нулевого выхода открыты йо первым входам элементы И 4 и по вто- рым входам — элементы И 13, 14 и

И 28, Работа устройства начинается по сигналу пуска, поступающему по входу

43 на установку в "1" триггера 5, По единичному сигналу с единичного выхода триггера 5 открывается элемент

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

55 том номера разряда регистра 4), производится формирование унитарного кода, поступающего на входы шифратора

31, С помощью указанного шифратора этот код преобразуется в двоичный код номера приоритетного на данный момент времени абонента (заявки) и подается на информационные входы 42 блоков 2 формирования очереди и далее на элементы И 57, Так как только на входе 37 бло1 ка 1 управления присутствует единичный сигнал, то по импульсу с выхода элемента 9 задержки, проходящему через открытый элемент И 22 н поступающему по входу 33 в блок 2, двоичный код номера заявки записывается в последние разряды регистров 56, Вследствие этого на выходе последнего элемента ИЛИ-НЕ 58 формируется нулевой сигнал, закрывающий последние элементы И 57 всех групп. Этим же сигналом на выходе предпоследнего элемента ИЛИ-НЕ 58 формируется единичный сигнал, которым открываются предпоследние элементы И 57 всех групп, а на выходах элементов ИЛИ-HF. 58 устанавливаются нулевые сигналы.

Таким образом, на входах 40 блока 1 формируется позиционный код, имеющий единицу в предпоследней позиции т,е. 010...00. В данном случае на входах шифратора 51 элементами 50, запрета устанавливается позиционный код 0....01, Кроме того, на выходах элементов ИЛИ 52 формируется код

0....011. Единичным сигналом с выхода элемента ИЛИ 52< элементы 53 запрета удерживаются в закрытом .состоянии> поэтому двоичный код с выхода шифратора 51 поступает через блок элементов И 54< на входы дежфратора 54 °

При этом на втором выходе дешифратора 54 формируется единичный сигнал, открывающий элементы И 57 всех групп уже во втором блоке 2 формирования очереди . Двоичный код погтупающей заявки записывается в последние разряды регистров 56 блока 2 аналогично рассмотренному, В дальнейшем работа устройства по формированию очереди производится таким образом, пока все заявки не разместятся поочередно в каждом блоке 2.

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

1.575184

Пусть в регистр 3 поступили заявки от первого и второго абонентов, а сигнал готовности от К-ro ресурса, т.е. после завершения обслуживания предыдущей заявки, по входу 45 через элемент ИЛИ 18 < на единичный вход разряда 20.регистра готовности ресурсов, По импульсу генератора 6 с выхода элемента И 7 заявки с выходов разрядов 31 и 3 устанавливают в "1" разряды 4 и 4 . Так как сигналы отказов ресурсов отсутствуют на выходе элемента ИЛИ 30 формируется нулевой сигнал, которым закрыт элемент И 16> а по инверсному входу открыт элемент

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

ИЛИ 30.

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

И 22. Время задержки элементов 9 задержки определяется временем переходных процессов в элементе И 15 и триггере 17. !

По импульсу с выхода элемента 10 задержки, время которого определяет35 ся переходными процессами в элементах И 57 и регистрах 56, в блоке 2 через открытый элемент И 21 производится сдвиг содержимого регистров 56, По импульсу с выхода элемента 11 задержки, время которого определяется переходными процессами в регистрах

56, через открытый элемент И 19 q yc11 11 танавливае тся в состояние 0 р аз - 45 ряд 20 ° По очередному импульсу г енера тора 6 номер второго абонента передается в блок 2 » где сфо рмирована наименьшая очередь, При наличии отказов ресурсов производится внач але перераспределение заявок из очереди неисправного ресурса, а затем распределение поступивших заявок из регистра 3, Пусть о т первого р есур са по входу 4 6 » в первый разряд 2 1 регистра 2 1 поступил сигнал отказа, а в первый разряд 3 1 регистра 3 — сигнал заявки от первого абонента., Но импульсу генератора 6 с выхода. эл емента И 7 заявка из разряда 3< передается в первый разряд регистра 4.

Элемент И 28< открыт по второму входу единичным сигналом с нулевого выхода триггера 17, по третьему входу — единичным сигналом с единичного выхода разряда 29»» а по инверсному при наличии очереди в блоке 2; — нулевым сигналом с выхода элемента ИЛИ-НЕ

27 . Поэтому импульсом с выхода эле-! мента И 7 через открытый элемент И 28. устанавливаются в состояние "1" первый разряд регистра 25 и через элемент

ИЛИ 18 — первый разряд регистра 20, После установки разряда 251 в еди" очное состояние на выходе элемента ИЛ!» 30 формируется единичный сигнал, которым открывается элемент И 16, а по инверсному входу закрывается элемент И 15. Поэтому импульсом с выхода элемента .8 задержки триггер 17 устанавливается в состояние "1". Нулевым сигналом с нулевого выхода триггера 17 закрываются элементы И 13 и

14, блокируя для анализа выходные сигналы регистра 14, и элементы И 28, исключая на время перераспределения заявок из очереди к первому ресурсу поступающие сигналы отказов от других ресурсов.

Единичным сигналом с единичного выхода триггера 17 открываются группы элементов И 23, обеспечивая поступление двоичных кодов абонентов из блока 2„. C помощью элементов И 24, включенных с выходами регистра 25 по приоритетной схеме (приоритет убывает с ростом номера разряда), из единичных сигналов формируется унитарный код. В данном случае нулевым сигналом с нулевого выхода разряда 25» закрыты все элементы И 24, а единичным сигналом с единичного выхода разряда

25< открыты по вторым входам все элементы И 23 первой группы блока. При этом двоичный код номера заявки с выходов последних разрядов регистров 56 блока 2» с его выходов 41 через открытые элементы И 23< поступает на входы 42 блоков 2. Единичным сигналом с единичного выхода первого разряда регистра 29, поступающим по входу 34 в блок 2(на элементы ИЛИ-НЕ 58, принудительно на выходах 40< элементов

ИЛИ-НЕ 58 формируют нулевые сигналы.

Этим самым производится исключение из анализа в блоке 1 состояния очереди заявок в блоке 2, l 575184

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

56 в блоке 2 по сигналу с выхода элемента ll задержки через открытый элемент И 21 и гашение первого разряда регистра 20 через открытый элемент И 19 . Время задержки элементом

ll определяется временем переходных процессов в элементах И 57 и регистре 56. По завершении сдвига кодов в регистрах 56 на выходах 41 блока 2 устанавливается двоичный код номера очередного абонента либо нулевой код при отсутствии в данном блоке очереди заявок.

Так как в блоке 2 имеется очередь, то на выходе элемента ИЛИ-НЕ 27 удерживается нулевой сигнал, которым элемент И 26 закрыт. Поэтому первый разряд регистра 25 остается в единичном состоянии. По очередному импульсу генератора 6 выполняется передача двоичного кода номера абонента из блока 2 в другой блок 2 с наименьшей очередью в соответствии с рассмотренным.

После сдвига кодов в регистрах 56 .блока 2 на его выходах 41 устанавливается нулевой код. При этом на выходе элемента ИЛИ-НЕ 27(формируется единичный сигнал, открывающий элемент И 26, через который по импульсу с выхода элемента ll задержки устанавливается в состояние "0" первый разряд регистра 25. Так как все разряды регистра 25 после этого 0 оказываются в нулевых состояниях, то на выходе элемента ИЛИ 30 формируется нулевой сигнал, открывающий по инверсному входу элемент И 15, через который по импульсу с выхода элемен- 45 та 12 задержки триггер 17 устанавливается в нулевое состояние ° В дальнейшем при наличии заявки в первом разряде регистра 3 производится передача pso Horo кода первого абонента 50 в блок 2 с наименьшей очередью.

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

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

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

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

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

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

4i0 торых подключены к инверсным входам одноименных элементов И первой группы и к третьим входам одноименных элементов И седьмой группы> выходы которых соединены с нулевыми входами одноименных разрядов буферного регистра отказов, единичный выход первого разряда которого подключен к первому входу элемента ИЛИ и к вторым входам элементов И первой группы блока, единичный выход j-го (j.=l,...,Ê) разряда буферного регистра отказов ресурсов соединен с первым входом (j-1)го элемента И восьмой группы и с j --м входом элемента ИЛИ, выход которого подключен к второму входу второго элемента И и инверсному входу третьего элемента И, нулевой выход каждого разряда буферного регистра отказов соединен с соответствующими входами одноименного и всех последующих элементов И восьмой группы, выход (j 1)-ro элемента И восьмой группы подключен к вторым входам элементов И

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

575!о

)5751o4

1575I84

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

Редактор Р.Середа Техред Л.Сердюкова Корректор Э.Лончакова

Заказ 1785

Тираж 573

Подписное

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

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

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