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

.с ОПИСАНИЕ ИЗОБРЕТЕНИ АВТОРСКОм СвиДЕтедьСтаУ СС8 СП тов И, элеи,ют тригге(56) Авторское свидетельство С Р И 866560, кл, С 06 Г 9/46, 197 .Авторское свидетельство СССР ю 1151965, кл, с 06 г 9/46, 1983. (54) УСТРОЙСТВО ДЛЯ РА РЕДЕЛЕНИЯ ЗАДАЧ МЕЖДУ ПРОЦЕССОРАМИ(57) Изобретение относится к вычислительной технике и предназначено для распределения задач между процессорами в мультипроцессорных системах, Цель изобретения - повышение надежИзобретение относится к вычисли" тельной технике и может испольэоваться в многопроцессорных вычислительных системах.Цель изобретения - повышение надежности обслуживания заданий за счет уменьшения вероятности потери заданийНа фиг,1 представлена структурная схема устройства, на Фиг.2 - структурная схема регистра сдвига; на Фиг.3 - структурная схема регистра поиска.Устройство содержит регистр 1, элемент 2 задержки, блок 3 элементов И, триггер 4, элементы 5 и 6, элемент ИЛИ 7, элемент И 8, элемент НЕ 9, элемент И 10, регистр 11 сдвига, элемент ИЛИ 12, элемент И 13, элемент НЕ 14, элементы ИЛИ 15 и 16, группу 17 элементов ИЛИ, регистр 18, группу ности обслуживания заданий за счет уменьшения вероятности потери заданий. Устройство содержит четыре регистра, группу регистров, регистр сдвига, две группы блоков элементов И, четыре группы элементов ИЛИ, триггер, элемент задержки, элементы И, ИЛИ, НЕ. Входная заявка содержит информацию о номере задачи и количестве потребных для ее решения процессоров. Устройство сопоставляет информацию о потребных процессорах с имеющимися ресурсами системы и распределяет задачу по процессорам. В случае одиночного либо группового отказа процессоров нерешенные задачи распре-деляются по свободным процессорам. 3 ил. блоков 19 элементов И, группу 20 регистров, группу блоков 21 элеменгруппу 22 элементов И, группу 23ментов ИЛИ., регистр 24 готовнострегистр 25 отказов, группы 26 и 27элементов ИЛИ, группу 28 элементов И,первую группу сигнальных входов 29устройства, выходы 30 элементов ИЛИ23, выходы 31 элементов И 3, выход .32 элемента ИЛИ 12, выход 33 элемента И 10, информационные входы 34устройства, вторую группу сигнальныхвходов 35 устройства, группу выходов36 устройства и выходы 37 регистра.Регистр 11 состоит из триггеров38, элемента И 39, элемента 40 задержки и элемента НЕ 41.Регистр 18 поиска .образуры 42, элемент 43 задержки,И 44, элемент НЕ 45 и элеме1532929, Устройство работает следующим об-.,разом,В исходном состоянии в первом разряде регистра 18 записан единичныйсигнал, все процессоры готовы к работе, а следовательно, в регистре 21записаны единичные сигналы во всеразряды по группе входов 35, по этимже сигналам обнулены все регистрыгруппы 20, по группе входов 29 сигналов не поступало, регистр 25 находится в нулевом состоянии.Регистр 11 сдвига находится в нулевом состоянии, нулевой. сигнал с выхода элемента ИЛИ 12 поступает наэлемент НЕ 9, с которого единичныйсигнал поступает на элемент И 8, остальные входы которого соединены синверсными выходами регистра 25, накоторых присутствуют единичные потенциалы, Элемент И 8 открыт, сигнал снего устанавливает триггер ч в нулевое состояние. Регистр 1 готов к приему информации. Разрешения на сдвигединичного сигнала в регистре 18 нет,так как на прямых выходах регистра25 находятся нулевые уровни сигналов,В процессе работы с процессоров могутпоступать сигналы готовности к выпол 30нению задачи по группе входов 35 исигналы отказов по группе входов 29в виде коротких единичных сигналов.Очередь задач устанавливается планировщиком и находится в запоминающемустройстве, откуда задачи в порядкеочереди поступают на регистр 1 посигналу разрешения записи в регистр1, поступающему с выхода элемента И 8.40Заявка представляет собой совокупность кода номера задачи и кода числа потребных процессоров, представляющего собой позиционный код гдечисло единиц соответствует количествупотребных процессоров, С групп выхо 45дов регистра 1 код номера задачи поступает на группу элементов ИЛИ 17,а с их выходов - на группу блоков 19элементов И. Квд количества потребныхпроцессоров поступает на входы блокаэлементов И 3 и записывается по группе входов 31 на регистр 11 сдвига,После записи кода потребных процессоров на регистр 11 сдвига данный кодпоявляется на его выходах 31 в видеединичных уровней в соответствующихразрядах. Затем эти уровни подаютсяна элемент ИЛИ 12, выходной сигналс которого разрешает сдвиг содержимого регистра 11 сдвига. Частота генератора регистра 11 сдвига, собранного на элементах И 39, НЕ ч 1, элементе 10 задержки, выбирается такой, чтобы в случае записи задачи на процессор (процессоры) сигнал обнуления с соответствующего элемента группы элементов ИЛИ 23 успел обнулить соответствующий разряд регистра сдвига до того, как произойдет очередной циклический сдвиг содержимого регистра 11 сдвига на один разряд. Одновременно сигналы с выходов регистра 11 сдвига поступают на соответствующие блоки 19 элементов И, При этом, те блоки, на которые поступили единичные сигналы от регистра 11 сдвига и регистра 21, открываются и разрешают запись кода номера задачи по группе выходов 3 б на нужный Свободный процессор (процессоры), причем одновременно происходит запись кода номера задачи на соответствующий регистр группы 20 регистров и обнуление через элементы ИЛИ 23 соответствующего разряда регистра 24 и регистра 11 сдвига, После того, как все разряды регистра сдвига 11 окажутся обнуленными, т,е. заявка распределена, единичный сигнал с выхода элемента И 8 разрешает запись на регистр 1 очередной задачи, Элемент 2 задержки предназначен для того, чтобы вследствие разного быстродействия регистра 1 и элементов И 3 код количества процессоров старой задачи по разрешающему сигналу вновь не переписался на регистр 11 сдвига,Процесс распределения задачи повторяется, Если количество свободных процессоров меньше, чем потребных, или есть свободные процессоры, но их местоположение не соответствует положению единичных сигналов в определенных разрядах регистра 11 сдвига, т.е. нет разрешения на блоках элементов И 19, то по единичному сигналу с элемента ИЛИ 12 содержимого регистра 11 сдвига циклически сдвигается на один разряд и вновь происходит сопоставление сигналов разрешений на блоках элементов И 19. Если есть свободный процессор и он потребен для решения задачи, то происходит запись кода номера задачи по группе выходов 36 устройства через определенный блок 19 элементов И на этот процессор и определенный регистр группы 20, а .5 15329также обнуление разрядов в регистре24 и регистре 11 сдвига. В процессеработы устройства процессоры освобождаются по мере решения задач. Импульсы готовности от процессора, поступающие по соответствующим входамгруппы входов 35, записываются в соответствующие разряды регистра 24 иобнуляют содержимое по старой задаче 1 Осоответствующего регистра группы регистров 20, подготавливая регистрдля приема кода номера задачи очередной. заявки.В процессе работы устройства могут происходить как единичные, так имассовые отказы процессоров, причемэтот процессор (процессоры) можетбыть занят решением задачи, а можетнаходиться и в режиме ожидания новой 20задачи,Рассмотрим случай, когда отказывает процессор (процессоры), занятыйрешением задачи.В ходе распределения задачи при 25отказе процессора сигнал отказа поступает по соответствующему входугруппы входов 29 на соответствующийэлемент группы 28 элементов И, а таккак есть разрешающие сигналы с выхо- ЗОдов соответствующих элементов ИЛИ 27,на входы которых поступает нулевоесодержимое регистров группы 20 регистров, в которых записаны коды номе"ров решаемых задач, то с выхода соответствующего (или соответствующихпри групповом отказе процессоров)элемента И группы 28 элементов И "1"записывается в определенный разрядрегистра 25.40В дальнейшем рассматривается групповой отказ, т,е. случай, когда в регистре 25 записано несколько единичных сигналов.С группы инверсных выходов регистра 25 нулевые сигналы поступают наэлемент И 8, запрещая подачу сигналаразрешения записи на регистр 1,послеокончания распределения текущей задачи. Одновременно единичные сигналы сгруппы прямых выходов регистра 25 поступают на элемент ИЛИ 16, с его выхода единичный сигнал поступает наэлемент И 6 и 13 и разрешает циклический сдвиг единичного сигнала в регистре 18 поиска,После окончания распределения те-.кущей заявки на группе выходов регистра 11 сдвига появляются нулевые потен 296циалы, на выходе элемента НЕ 9 появляется единичный сигнал, который раз" решает запись единичного сигнала с выхода элемента И 13 через элемент ИЛИ 7 в младший разряд регистра 11 сдвига. Одновременно единичный сигнал с элемента НЕ 9 поступает на элементы И 8 и 6. Но так как элемент И 8 закрыт, а на элемент И 6 поступает разрешающий сигнал с элемента ИЛИ 16, то с выхода элемента И 6 этот сигнал устанавливает триггер 4 в единичное состояние. Данный сигнал является стирающим для регистра 1, т.е, происходит чистка регистра 1. В это время на выходах регистра сдвига 11 появляется единичный сигнал в одном из разрядов, при этом нулевой сигнал с элемента НЕ 9 закрывает элемент И 13, чтобы во время циклического сдвига содержимого регистра сдвига 11 на его вход не поступала информация с элемента ИЛИ 7. Два единичных сигнала с выхода триггера 4 и с выхода элемента ИЛИ 12 открывают элемент И 5, единичный сигнал с которого присутствует на синхровходе регистра 25 до тех пор, пока есть единичный сигнал на выходах регистра сдвига 11. Единичный сигнал с выхода триггера обеспечивает работу группы элементов И 22. Как только единичный сигнал с группы выходов регистра 18 поступает на тот элемент И группы элементов И 22, на другом входе которого присутствует единичный сигнал с одного из прямых выходов регистра 25, единичный сигнал с выхода этого элемента И прекращает циклический сдвиг содер" жимого регистра 18 по группе входов 36, единичный сигнал с данного элемента И группы элементов И 22 поступает на соответствующий вход группы входов обнуления по синхроимпульсу, при этом данный разряд обнуляется по окончании распределения данной задачи по синхроимпульсу. Кроме того, единичный сигнал с этого элемента И группы элементов И 22 поступает на элемент ИЛИ 15, с выхода элемента ИЛИ 15 на вход элемента НЕ 14, с выхода которого нулевой сигнал закрывает элемент И 13 до тех пор, пока есть единичный сигнал с данного элемента И группы элементов И 22, а следовательно, пока присутствует код номера задачи на входах блоков элементов И 19 после ее распределения.По разрешающему сигналу с соответствующего элемента И группы элементов И 22 открывается один из блоков группы блоков элементов И 21, код номера отказавшей задачи через этот блок поступает на группу элементов ИЛИ 17 с группы выходов соответствующего ре,гистра группы регистров 20, с выходов группы элементов ИЛИ 17 код номера этой задачи поступает на входы блоков элементов И 19 и происходит распределение задачи по процессорам, каки при работе без отказавших процесса ров. Как только код номера задачи 15 , распределен, на выходах 37 регистра , сдвига 11 появляются нулевые сигналы,при этом с выхода элемента ИЛИ 12 нулевой сигнал поступает на элементы НЕ 9 и И 5, Нулевой перепад с выхо да элемента И 5 поступает на вход синхронизации регистра 25, По нулевому перепаду обнуляется тот разряд,в котором находится единичный сигнал с выхода элемента И группы элементов 25 И 22. Одновременно единичный сигнал с элемента НЕ 9 поступает на элемент И 13. Как только код номера задачи исчезает с выходов группы элементов ИЛИ 17, с выхода элемента И 13 запи- ЗО сывается очередной единичный сигналв регистр 11 сдвига через элементИЛИ 7. Нулевые сигналы с выходов элементов И группы элементов И 22 разрешают циклический сдвиг единичногосигнала в регистре 18 поиска. Если врегистре 25 записаны единичные сигналы, то обработка задач отказавших процессоров протекает аналогично описанному, 40В случае распределения последнейзадачи отказавших процессоров послесинхроимпульса с выхода элемента И 5на прямых выходах регистра 25 оказываются все нулевые сигналы, элементИ 8 открывается, так как на него поступил единичный сигнал с выхода элемента НЕ 9 и все единичные сигналы сгруппы инверсных выходов регистра 25,при этом единичный сигнал с выходаэлемента И 8 обнуляет триггер ч и разрешает запись на регистр 1 очереднойзаявки, В это время нулевой сигналс выхода элемента ИЛИ 16 поступаетна элемент И 13 быстрее, чем единичный сигнал с элемента НЕ 11 за счет35различной глубины прохождения сигнала,что предотвращает запись единичногосигнала с выхода элемента И 13 через элемент ИЛИ 7 в младший разряд регистра 11 сдвига.Нулевой сигнал с выхода элемента ИЛИ 16 прекращает циклический сдвиг содержимого регистра 18 и подает запрещающий нулевой сигнал на элемент И 6. Устройство переходит в режим распределения входного потока заявок по процессорам.Рассмотрим случай, когда отказывают процессоры, не занятые решением задачи, находящиеся в режиме ожидания,Сигналы отказа поступают по группе входов 29 и обнуляют соответствующие разряды регистра 2 ч через элементы группы элементов ИЛИ 26 чтобы задача не распределилась на отказавшие процессоры. Одновременно эти поступившие сигналы отказов поступают на один из входов элементов И группы элементов И 28. Но в регистрах группы 20 регистров отказавших процессоров инФормации не записано (она обнулена предшествовавшим отказу сигналом готовности с процессоров), и на выходах соответствующих элементов ИЛИ группы элементов ИЛИ 27 присутствуют нулевые сигналь 1, которые запрещают запись сигналов отказа на регистр 25, чтобы устройство не работало вхолостую. В процессе работы процессоры могут восстанавливать свою работоспособность, при этом сигналы готовности по группе входов 35 записываются в регистр 21 и обнуляют содержимое соответствующих регистров группы регистров 20, подготавливая их к приему новой задачи. Формула изобретенияУстройство для распределения задач между процессорами, содержащее четыре регистра, регистр сдвига, три группы элементов ИЛИ, группу регистров, две группы блоков элементов И, две группы элементов И, пять элементов И, два элемента НЕ, три элемента ИЛИ, блок элементов И, причем группа инФормационных входов устройства соединена с группой входов первого регистра, первая группа выходов которого соединена с груг 1 пой инФормационных входов блока элементов И, группа выходов которого, кроме последнего выхода, соединена с первой группой инФормационных входов регистра сдвига, последний выход группы выходов блока элементов И соединен с первым входомпервого элемента ИЛИ, выход которого соединен с последним входом первой группы входов регистра сдвига, выход первого элемента И соединен с входом5 управления записью первого регистра, каждый выход второго регистра соединен с первым управляющим входом одноименного блока элементов И первой группы, выходы которых являются груп- о пами выходов устройства, второй управляющий вход каждого блока элементов И первой группы соединен с выходом одноименного разряда регистра сдвига, ГРУппы инФОРл 1 дционных ВХОДОВ блокОВ. 15 элементов И первой группы соединены с выходами элементов ИЛИ первой группы, группа выходов каждого блока элементов И второй группы соединена с входами одноименного элемента ИЛИ второй группы, выходы которых соединены с группой входов сброса регистра сдвига, первый выход группы выходов регистра сдвига соединен с первыми входами первого элемента И и второго 25 элемента ИЛИ, выход второго элемента ИЛИ соединен с Вторым входом первого элемента И, выход которого соединен с входом запуска регистра сдвига, Вход управления записью первого реги- ЗО стра соединен с выходом второго элемента И, о т л и ц а ю щ е е с я тем, цто, с целью повышения надежности обслуживания заданий за счетуменьшения вероятности потери зада 35 ний, в него введены четвертая группа элементов ИЛИ, триггер и элемент задержки Выход которого соединен с уп" равляющим входом блока элементов И, вход элемента задержки соединен с вы О ходом второго элемента И, первый вход которого соединен с выходом первого элемента НЕ и с первыми входами третьего и четвертого элементов И, второй вход которого соединен с выходом 45 третьего элемента ИЛИ, с входом синхронизации третьего регистра и с вторым входом третьего элемента И, выход которого соединен с единичным входом триггера, выход которого соединен с входом сброса первого регистра, с первым входом пятого элемента И, второй вход которого соединен с тактовым входом регистра сдвига, с входом первого элемента НЕ и с выходом второго элемента ИЛИ, второй вход которого соединен с последнии выходом группы выходов регистра сдвига, входы второго элемента И соединены с группой инверсных выходов четвертого регистра,каждый прямой выход которого соединенс первым входом одноименного элемента И первой группы и с входами третьего элемента ИЛИ, единичные входычетвертого регистра соединены с выходами элементов И второй группы, первые входы которых соединены с первойгруппой сигнальных входов устройстваи с первыми входами одноименных элементов ИЛИ третьей группы, вторыевходы и выходы которых соединены соответственно с выходами элементов ИЛИвторой группы и с группой входов сброса второго регистра, единичные входыкотороо соединены с второй группойсигнальных входов устройства и с входами сброса регистров группы, информационные входы каждого из которых соединены с группой выходов одноименного блока элементов И первой группы,группа выходов каждого регистра группы соединена с группой входов одноименного блока элементов И второйгруппы и с входами одноименного элемента ИЛИ четвертой группы, выход каждого из которых соединен с вторым входом одноименного элемента И второйгруппы, выход групп выходов каждогоблока элементов И второй группы соединен с соответствующим входом одноименного элемента ИЛИ первой группы,выход каждого элемента И первой группы соединен с одноименным входомсброса четвертого регистра, с управляющим входом одноименного блока элементов И второй группы, с одноименныминФормационным входом третьего регистра и с соответствующим входом четвертого элемента ИЛИ, выход которогочерез второй элемент НЕ соединен стретьим входом четвертого элемента И,выход которого соединен с вторым входом первого элемента ИЛИ, каждый выход третьего регистра соединен свторым входом одноименного элементаИ первой группы, третий вход которого соединен с выходом триггера, каждый Выход второй группы выходов первогорегистра соединен с соответствующим .входом одноименного элемента ИЛИ первой группы, выход второго элемента Исоединен с входом сброса триггера ис входом элемента задержки, единичный вход триггера соединен с выходомтретьего элемента И, выход пятогоэлемента И соединен с тактовым входомчетвертого регистра..Редактор Л.пчолинская Техред И.Ходанич Корректор О.кра Тираж 668 Подмитета по изобретениям и от ква, Ж, Раушская наб.,омбикат "Патент", г. Ужгород,01 роизводственно-издательс агари Заказ 8101/54 писное ВНИИПИ Государственного ко крытиям при ГКНТ СССР 113035, Иос д. 4/5