Устройство для распределения заявок по процессорам

 

Изобретение относится к вычислительной технике и может быть использовано в многопроцессорных вычислительных системах при обслуживании потока заявок. Цель изобретения - повышение достоверности обслуживания заявок за счет их перераспределения при отказах процессоров. Новым в устройстве является Использование двух блоков элементов И, rpyrtn -эл ментов И, Т регистра сдвига, одновибратора, третьего элемента ИЛИ , группы элементов запрета, четырех элементов И, второго триггера, а в каждом канале - элемента задержки и блока элементов И. Устройство обеспечивает распределение потока заявок по свободным процессорам в двух режимах. В одном из них при отсутствии сигналов отказов от процессоров в соответствии с циклической дисциплиной обслуживания производится поиск свободного процессора посредством регистра сдвига и передача в регистр одноименного канала поступившей заявки. Если в рроцессе обслуживания заявки поступил сигнал отказа процессора, то производится переход устройства в другой режим работы, В данном случае распределение поступившей заявки приостанавливается, а вместо нее свободному процессору передается заявка от отказавшего процессора. 1 ил. ел с

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

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

РЕСПУБЛИК е:=, ф и р

<я с G 06 F 9/

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

1 (21) 4813434/24 (22) 11.04.90 (46) 28.02.93, Бюл. йф8

-(72) В,Г,Попов и А.Х.Ганитулин (56) Авторское свидетельство СССР

N 1291982, кл. G 06 F 9/46, 1987.

Авторское свидетельство СССР

N 1695302, кл. G 06 F 9/46, 1988,. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

ЗАЯВОК ПО ПРОЦЕССОРАМ (57) Изобретение относится к вычислительной технике и может быть использовано в многопроцессорных вычислительных системах при обслуживании потока заявок. Цель изобретения — повышение достоверности обслуживания заявок за счет их перераспределения при отказах процессоров. Новым в устройстве является использование двух блоков элементов И, г1эуйпМ-рл4ментов .И, (Изобретение относится -к вычислительной технике и может быть использовано в многопроцессорных вычислительных системах при обслуживании потока заявок.

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

На чертеже показана структурная схема устройства.

Устрбйство содержит каналы 1, каждый из которых включает в себя регистр 2, блок

3 элементов И, элемент И 4 и элемент 5 задержки, регистр 6 сдвига, регистр 7 готовности процессоров, регистр 8 отказов про., Я3.м, 1798782 А1 регистра сдвига, одновибратора, третьего элемента ИЛИ; группы элементов запрета, четырех элементов И, второго триггера, а в каждом канале — элемента задержки и блока элементов И, Устройство обеспечивает распределение потока заявок по свободным процессорам в двух режимах. В одном из них при отсутствии сигналов отказов от процессоров в соответствии с циклической дисциплиной обслуживания производится . поиск свободного процессора посредством регистра сдвига и передача в регистр одноименного канала поступившей заявки. Если в процессе обслуживания заявки поступил

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

В данном случае распределение поступившей заявки приостанавливается, а вместо нее свободному процессору передается заявка от отказавшего процессора, 1 ил, I

Q цессорав, блок 9 элементов И, блок 10 эле- Щ ментов И, группу элементов И 11, группу элементов 12 запрета, элемент И 13, генера- ©ф тор 14 импульсов, элемент И 15, элемент 16 задержки, триггер 17, одновибратор 18, элемент ИЛИ 19, элемент ИЛИ 20, элемент И

21, элемент И 22, элемент 23 задержки, эле- б мент И 24, триггер 25, элемечт ИЛИ 26, вход

27 пуска устройства, сигнальный выход 28 устройства, информационные входы 29 устройства, информационные входы 30 регистра отказа процессоров устройства; информационные выходы 31 устройства, группу выходов 32 готовности процессоров устройства и информационные входы 33 регистра готовности процессоров устройства, 1798782

Устройство работает следующим образом, Исходное состояние устройства характеризуется тем, что регистры 2, 7, 8, триггеры 17 и 25 установлены в нулевые состояния, а первый разряд регистра 6 сдвига — в единичное (на чертеже не показано).

Устройство обеспецивает передачу кодов заявок при их поступлении по входам 29 исправным и свободным процессорам, а также перераспределение выполняемых заявок при отказах процессоров, Каждый процессор принимает код заявки с выходов 31 из регистров 2 соответствующих каналов 1, В этих регистрах фиксируется код заявки, когда от соответствующего процессора поступает сигнал готовности по входу 33 B одноименный разряд регистра 7. От каждого процессора мо>кет поступить сигнал отказа по входам 30 в одноименный разряд регистра 8, Эти сигналы формируются только теми процессорами, которые прийяли на обслуживание заявки из регистров 2 соответствующих каналов 1.

Устройство работает в двух ре>кимах.

В первом из них обеспечивается передача заявок, поступающих по входам 29, в регистры 2 каналов 1, для которых зафиксиpoBBHbt сигналы готовности от cooTBBTOTBvющих процессоров в регистре 7. Поиск готового к работе процессора производится

B соответствии с циклической дисциплиной обслуживания посредством регистра 6 сдвига.

Во втором режиме при фиксации сигналов отказов от процессоров в регистре 8 производится перераспределение выданHbtx ранее заявок. Для обеспечения данного режима код заявки сохраняется B соответствующем регистре 2 до поступления очередного сигнала готовности от одноименного процессора. В этом режиме возможны два варианта работы устройства. Первый иэ них характеризуется поступлением сигналов отказов от процессоров, когда подана очередная заявка на входы 29, а второй — когда сигналы отказов приходят при отсутствии новой заявки на входах 29, Устройство при отсутствии сигналов отказов от процессоров работает следующим образом.

Работа устройства совместно с источником заявок организована по схеме "запросответ". исключающей потерю информации, Совместно с процессорами вычислительной системы работа устройства 1,k>trB организована по схеме "запрос-ответ".

В качестве сиг I;)llB запроса Во взаимодействии с ис очником заявок исг1;льзуется единичный сигнал с нулевого выхода триггь рл 17, поступающий на выход 28 устройства

По этому сигналу источник злявок выдав| потенtièàëüttûé код заявKè на входы 29 усt ройства в сопровождении импульсного сигнала пускл по входу 27, выступлющего в качестве сигнала ответа, Пусть вычислительная система ñîäåðжит К процессоров и на данный цикл распределения поступают две заявки, а в регистре 7 зафиксированы сигналы готовности от первого и К-ro процессоров. Сигналы готовности являются сигналами запроса заявки на обслу>кивание. Остальные процессоры заняты обслуживанием заявок.

Сигналами готовности от первого и К-ro процессоров устанавливаются в нулевые состояния регистры 2 в соответствующих каналах

1, Сигналом пуска с входа 27 в единичное состояние устанавливаются триггер 25 и через элемент ИЛИ 19 — триггер 17. По единичному сигналу с единичного выхода триггера

17 открываются элементы И 9 и элемент И

15.

Триггер 25 в данном режиме не влияет на работу устройства, так как при отсутствии сигналов отказов в регистре 8 на выходе элемента И 13 формируется единичный сигнал, которым открыты элементы И 9 и элемент И 22 и закрыт по инверсному входу элемент И 24.

Так как первые разряды регистров 6 и 7 установлены в единичные состояния; в первом канале 1 открыт элемент И 4 по первому и третьему входам, Первым импульсом генератора 14. проходящим элементы И 15 и И 4 на вход разрешения записи регистра 2 первого канала, обеспечивается запись в этот регистр кода заявок с выходов элементов И 9, Затем задержанным импульсом с выхода элемента задержки 5 устанавливается в нулевое состояние первый разряд регистрл 7 и через элементы ИЛИ 26, И 22 и ИЛИ 20 — в нулевое состояние триггер 17. Через некоторое время, определяемое элементом задержки 16, производится перемещение единицы в регистре 6 из первого разряда во второй. Время задер>кки элементами задержки 16 и 5 выбирается, исходя из времени для надежной записи информации в регистр 2.

Единичный сигнал с нулевого выхода первого разряда регистра 7 (равно и для других разрядов} поступает на соответствующий выход 32 устройств 1. в качестве сигнала ответа, разрешающего с итывание кода заявки с выходов 31 первого канлла соответствующему процессору.

30

40

t дини litèé сигнал с нулевого выхода

-риггерл 17 запрашивает код очередной заявки.

Источник заявок по этому сигналу выдает код очередной заявки и сигнал пуска.

В дальнейшем устройство обеспечивает поиск свободного процессора, от которых зафиксированы сигналы готовности s регистре 7, с помощью регистра сдвига 6.

После установки триггера 17 в единичное состояние импульсами генератора 14 с выхода элемента задержки 16 производится дальнейшее перемещение единицы в регистре 6, пока она не окажется в К-м разряде, В этом случае в К-м канале открывается элемент И 4, и работа устройства производится аналогично рассмотренной выше, Единица из К-го разряда регистра 6 передается в первый его разряд, обеспечивая новый цикл последовательнбго поиска свободного процессора, После завершения обслуживания заявки процессор выдает в устройство сигнал готовности по соответствующему входу 33.

Этим сигналом устанавливается в единичное состояние одноименный разряд регистра 7 и в нулевое — регистр 2 соответствующего канала 1.

Работа устройства при наличии сигналов отказов от процессоров заключается в следующем, Пусть после второго запроса заявки поступил сигнал отказа от i-го процессора (1

И 13 формируется нулевой сигнал. Этим сигналом закрываются элементы И 9, И 21 и И

22 и открываются по инверсным входам элементы И 10.и И 24.

Отрицательным перепадом с выхода элемента И 13 запускается одновибратор

18, импульсом с выхода которого подтверждается единичное состояние триггера 17. .Единичным сигналом с выхода i-го разряда регистра 8 обеспечивается формирование единичного сигнала с выхода (i-1)-го .элемента запрета 12, которым открывается в i-м канале 1 блок элементов И 3, При этом код заявки с выходов регистра 2 I-ro канала

1 через открытые элементы N 10 и монтажное ИЛИ с выходами элементов И 9 подается íз информационнгн. входы регистр(в 2 всех каналов 1, Запись этого кода производится в регистр 2 К-го канала 1, когда единица окажется в К-ом разряде регистра 6.

Задержанным импульсом с выхода элемента ИЛИ 26 через открытый по инверсному входу элемент И 24 нулевым сигналом с выхода элемента И 13 I-й разряд регистра 8 устанавливается в нулевое состояние через открытый I-й элемент И 11, Так как триггер 25 остается в единичном состоянии, элемент И 21 закрыт, поэтому задержанный импульс элементом задержки

23 не оказывает влияние на состояние триггера 17, Время задержки элементом 23 выбирается, исходя из надежной установки в нулевое состояние разрядов регистра 8.

Так как триггер 17 находится в единичном состоянии, на входах 29 сохраняется потенциальный код заявки, подлежащей распределению в очередном цикле. Перемещением единицы в регистр 6 обеспечивается поиск свободного процессора аналогично рассмотренному выше. . Рассмотрим работу устройства, когда сигнал отказа от i-ro процессора поступает во время ожидания поступления кода очередной заявки на входы 29.

Работа устройства по распределению первой заявки в регистр 2 первого канала аналогичная рассмотренной выше, После поступления сигнала отказа от

i-го процессора отр цательным перепадом с выхода элемента И I3 запускается одновибратор 18, импульсом с выхода которого триггер 17 и через элемент ИЛИ 19 устанавливается в единичное состояние. Триггер.25 остается в нулевом состоянии, единичным сигналом с нулевого выхода которого открыт элемент И 21 по первому входу.

Перемещением единицы в регистре 6 производится поиск свободного процессора. Когда единица окажется в К-м разряде регистра 6, в К-м канале откроется элемент

И 4, и код заявки с выходов регистра 2 i-го канала 1 через элементы И 3 этого канала и элементы И 10 запишется в регистр 2 К-го канала 1. Задержанным импульсом с выхода элемента ИЛИ 26 через открытый по инверсному входу элемент И 24 устанавливается в нулевое состояние i-й разряд регистра 8, При этом на выходе элемента И 13 устанавливается единичный сигнал, открывающий элемент И 21. Затем импульсом выхода элемента задержки 23 через элементы И 2.1 и

ИЛИ 20 устанавливается в нулевое состояние триггер 17, так как триггер 25 находится в нулевом состоянии, 1798 ПХ2

20

50

В дальнейшем работа устройства производится аналогично рассмотренной выше.

Если в регистре 8 приняты сигналы отказов от других процессоров, то после установки в нулевое состояние i-ro его разряда на выходе элемента И 13 удерживается ну левой сигнал, которым закрыт элемент И 21.

При этом триггер 17 остается в единичном состоянии после К-ro импульса генератора.

Устройство начинает новый цикл распределения поиска свободного процессора, начиная с первого.

Если же после последнего сигнала отказа, когда триггер 17 установится в единичное состояние импульсом одновибратора

18, поступит сигнал пуска по предыдущему нулевому состоянию триггера 17, то триггер

25 установится в единичное состояние. При этом после передачи кода заявки от отказавшего процессора свободному и отсутствии сигналов отказов в регистре 8 задержанный импульс с выхода элемента задержки 23 не установит триггер 17 в нулевое состояние, так как элемент И 21 закрыт нулевым сигналом с нулевого выхода триггера 25. В дальнейшем производится поиск свободного процессора для заявки, находящейся на входах 29, В предложенном устройстве на основе анализа сигналов отказов при обслуживании полученных заявок процессорами производится перераспределение этих заявок свободным процессорам, Причем, эта задача выполняется с приостановкой распределения очередной заявки, поступившей на вход устройства, Формула изобретения

Устройство для распределения заявок по процессорам, содержащее первый триггер, два элемента задержки, регистр отказа процессоров, регистр готовности процессоров, генератор импульсов, первый элемент

И, два элемента ИЛИ и каналы, каждый из которых включает в себя регистр, выходы которого являются информационными выходами устройства, и элемент И, информационн ые входы регистра отказов процессоров являются входами отказов процессоров устройства, информационные входы регистра готовности процессоров являются входами готовности процессоровустройства, группа нулевых выходов регистра готовности процессоров является группой выходов готовности процессоров устройства, i-й единичный выход (1 =- 1„...К, К вЂ” число процессоров) регистра готовности процессоров соединен с первым входом элемента

И i-го канала, выход которого соединен с входом разрешения записи регистра канала, единичный вход первого триггера соединен с входом пуска устройства, выход генератора импульсов соединен с первым входом первого элемента И, выход которого соединен с входом первого элемента задержки, о т л и ч а ю щ е е с я тем, что, с целью повышения достоверности обслуживания заявок за счет их перераспределения при отказах процессоров, в него введены два блока элементов И, >руппэ элементов И, группа элементов И, регистр сдвига, одновибрагор, третий элемент ИЛИ. группа элементов ЗАПРЕТ, четыре элемента И, второй триггер, а в каждый канал — элемент задержки и блок элементов И, причем единичный выход второго триггера соединен с первыми входами первого блока элементов И и с вторым входом первого элемента И, выход которого соединен с вторыми входами элементов И каждого канала, выход первого элемента задержки соединен с тактовым входом регистра сдвига, выход одновибратора подключен к первому входу первого элемента ИЛИ, второй вход которого соединен с входом пуска устройства, нулевой вход первого триггера соединен с выходом второго элемента И и первым входом второго элемента ИЛИ, второй вход которого подклloчен к выходу третьего элемента И, первый вход которого соединен с нулевым выходом первого триггера, выход первого элемента ИЛИ соединен с единичным входом второго триггера, нулевой вход которого подключен к выходу второго элемента

ИЛИ, нулевые выходы регистра отказов процессоров подключены к соответствующим входам четвертого элемента И, выход которого соединен с инверсными входами второго блока элементов И, вторыми входами первого блока. элементов И, с входом одновибрэторэ, с инверсным входом пятого элемента И и вторым входом третьего и первым входом второго элементов И, выход пятого элемента И подключен к первым входам элементов И группы, выходы которых соединены с нулевыми входами одноименных разрядов регистра отказов процессоров, единичный выход 0+1)-ro разряда регистра отказов процессоров соединен с первым входом J-ro элемента запрета группы, нулевой выход j-го разряда регистра отказов процессоров (j = 1, 2...„К-1) соединен с соответствующими входами J-ro u последующих элементов запрета группы, единичный выход nepeoro разряда отказов процес=оров подключен к второму входу первого элемента И группы и к первым входам блока элементов И первого канала, выход j-ro элемента ЗАПРЕ группы подключен к первым входам блока элемен10

1 7!ЗЯ 782

Составитель В.Попов

Редактор Н.Коляда Техред M,Moðãåíòàë Корректор A,Moòûëü

Заказ 773 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 тов И (j->1)-го канала и к второму входу (> -1)го элемента И группы, выходы регистра канала соединены с второй группой входов блока элементов И своего канала, выходы блоков элементов И всех каналов объединены через монтажное ИЛИ и подключены к группе прямых входов второго блока элементов И, выходы которого через монтаж. ное ИЛИ объединены с выходами первого блока элементов И и подключены к информационным входам регистров всех каналов, выход элемента И канала через элемент задержки этого канала подключен к нулевому входу одноименно о разряда регистра готовности процессоров и соответствующему входу третьего элемента ИЛИ, выход которого соединеH с вторым входом второго элемента И, прямым входом пятого элемента И

5 и через второй элемент задержки — с третьим входом третьего элемента И, вход сброса регистра каждого канала подключен к соответствующему входу готовности процессо- ров устройства, нулевой выход второго

10 триггера является сигнальным выходом устройства, выход (-го.разряда регистра сдвига соединен с третьим входом элемента И

I-го канала,