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

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

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

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

Устройство содержит каналы 1, каждый из которых включает в себя регистр 2, блок 3 элементов И, элемент И 4 и элемент 5 задёржки,регистр 6 сдвига, регистр 7 готовности процессоров, регистр 8 отказов процессоров, блок 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 регистра готовности процессоров устройства.

Ю 00 VJ 00 hO

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

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

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

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

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

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

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

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

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

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

единичный сигнал с нулевого выхода триггк ра 17, поступающий на выход 28 устройства По этому сигналу источник заявок выдает потенциальный код заявки на входы 29 уст

ройства в сопровождении импульсного сигнала пуска по входу 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. Через некоторое время, определяемое элементом задержки 1.6, производится перемещение единицы в регистре 6 из первого разряда во второй. Время задержки элементами задержки 16 и 5 выбирается, исходя из времени дл я надежной записи информации в регистр 2.

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

Единичный сигнал с нулевого выхода триггера 17 запрашивает код очередной заявки.

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

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

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

Единица из К-го разряда регистра 6 передается в первый его разряд,обеспечивая новый цикл последовательного поиска свободного процессора,

После завершения обслуживания заявки процессор выдает в устройство сигнал готовности по соответствующему входу 33. Этим сигналом устанавливается в единичное состояние одноименный разряд регистра 7 ив нулевое - регистр 2 .соответствующего канала 1,

; Работа устройства при наличии сигналов отказов от процессоров заключается в следующем.

: Пусть после второго запроса заявки поступил сигнал отказа от 1-го процессора (1 i К), причем, в системе на момент распределения заявок свободны первый и К-й процессоры, от которых зафиксированы сигналы готовности соответственно в первом-и К-м разрядах регистра 7.

Работа устройства до момента поступления сигнала отказа от 1-го процессора аналогична рассмотренной выше. После поступления сигнала отказа от i-rp процессора в i-й разряд регистра 8 на выходе элемента И 13 формируется нулевой сигнал. Этимсиг- налом-закрываются элементы И 9, И 21 и И 22 и открываются по инверсным входам элементы И 1.0. и И 24.

Отрицательным перепадом с выхода элемента И 13 запускается одновибратор 18. импульсом с выхода которого подтверждается единичное состояние триггера 17,

.Единичным сигналом с выхода j-.го разряда регистра 8 обеспечивается формирование единичного сигнала с выхода (И)-го .элемента запрета 12, которым открывается в i-м канале 1 блок элементов И 3. При этом код заявки с выходов регистра 2 1-го канала 1 через открытые элементы И 10 и монтажное ИЛ И с выходами элементов И 9 подается на информационные; входы регистров 2 всех каналов 1.

Запись этого кода производится в регистр 2 К-го канала 1, когда единица окажет5 ся в К-ом разряде регистра б.

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

0 устанавливается в нулевое состояние через открытый. 1-й элемент И 11.

Так как триггер 25 остается в единичном состояний, элемент И 21 закрыт, поэтому задержанный импульс элементом задержки

5 23 не оказывает влияние на состояние триг- . гера 17. Время задержки элементом 23 выбирается, исходя из надежной установки в нулевое состояние разрядов регистра 8. Так как триггер 17 находится в единич0 ном состоянии, на входах 29 сохраняется потенциальный код заявки, подлежащей распределению в очередном цикле. Перемещением единицы в регистр 6 обеспечивается поиск свободного процессора

5 аналогично рассмотренному выше.

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

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

После поступления сигнала отказа от 1-го процессора: отрицательным перепадом

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

0 сигналом с нулевого выхода которого открыт элемент И 21 по первому входу.

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

И 4, и код заявки с выходов регистра 2 1-го канала 1 через элементы ИЗ этого канала и элементы И 10 запишется в регистр 2 К-го

0 канала 1. Задержанным импульсом с выхода элемента ИЛИ 26 через открытый по инверсному входу элемент И 24 устанавливается в нулевое состояние 1-й разряд регистра 8. При этом на выходе элемента И 13 устанав5 ливается единичный сигнал, открывающий элемент И 2t, Затем импульсом выхода элемента задержки 23 через элементы И 2.1 и ИЛИ 20 устанавливается в нулеаое состояние триггер 17, так как триггер 25.находится в нулевом состоянии,

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

Если в регистре 8 приняты сигналы отказов от других процессоров, то после установки в нулевое состояние 1-го его разряда на выходе элемента И 13 удерживается нулевой сигнал, которым закрыт элемент И 21. При этом триггер 17 остается в единичном состоянии после К-го импульса генератора. Устройство начинает новый цикл распределения поиска свободного процессора, начи- н-ая с первого.

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

В предложенном устройстве на основе анализа сигналов отказов при обслуживании полученных заявок процессорами производится перераспределение этих заявок свободным процессорам. Причем, эта задача выполняется с приостановкой распределения очередной заявки, поступившей на вход устройства.

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

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

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

0 блока элементов И, Группа элементов И, группа элементов И, регистр сдвига, одно- вибратор, третий элемент ИЛИ. группа элементов ЗАПРЕТ, четыре элемента И, второй триггер, а в каждый канал - элемент задер5 жки и блок элементов И, причем единичный выход второго триггера соединен с первыми входами первого блока элементов И и с вторым входом первого элемента И, выход которого соединен с вторыми входами

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

0. первый вход которого соединен с нулевым выходом первого триггера, выход первого элемента ИЛИ соединен с единичным входом второго триггера, нулевой вход которого подключен к выходу второго элемента

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

5 входам элементов И группы, выходы которых соединены с нулевыми входами одноименных разрядов регистра отказов .процессоров, единичный выход (j+T)-ro разряда регистра отказов процессоров соеди0 нен с первым входом j-ro элемента запрета группы, нулевой выход j-ro разряда регистра отказов процессоров (j 1, 2,...,К-1) соединен с соответствующими входами j-ro и последующих элементов запрета группы,

5 единичный выход первого разряда отказов процессоров подключен к второму входу первого элемента И группы и к первым входам блока элементов И первого канала, выход j-ro элемента ЗАПРЕТ группы подключен к первым входам блока элемемтов И (j-M)-ro канала и к второму входу Q4-)-- го элемента И группы, выходы регистра канала соединены, с второй группой входов блока элементов И своего канала, выходы блоков элементов И всех каналов объединены через, монтажное ИЛИ и подключены к группе-прямых входов второго блока элементов И, выходы которого через монтажное ИЛИ объединены с выходами первого блока элементов И и подключены к информационным входам регистров всех каналов, выход элемента И канала через элемент задержки этого канала подключен к нулевому входу одноименного разряда регистра го0

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

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