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

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

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

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

Устройство содержит регистр 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 элементов ИЛИ 23, выходы 31 элементов И 3, выход ; 32 элемента ИЛИ 12, выход 33 элемента И 10, информационные входы 3, устройства, вторую группу сигнальных входов 35 устройства, группу выходов 36 устройства и выходы 37 регистра.

Регистр 11 состоит из триггеров 38, элемента И 39, элемента 0 задержки и элемента НЕ 41,

Регистр 18 поиска образуют тригге ры 42, элемент 43 задержки, элемент И 44, элемент НЕ 45 и элемент ИЛИ 46.

СП

с ьэ со to

ф

31

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

В исходном состоянии в первом разряде регистра 18 записан единичный сигнал, все процессоры готовы к работе, а следовательно, в регистре 2k записаны единичные сигналы во все разряды по группе входов 35, по этим же сигналам обнулены все регистры группы 20, по группе входов 29 сигналов не поступало, регистр 25 находится в нулевом состоянии.

Регистр 11 сдвига находится в нулевом состоянии, нулевой сигнал с выхода элемента ИЛИ 12 поступает на элемент НЕ 9, с которого единичный сигнал поступает на элемент И 8, остальные входы которого соединены с инверсными выходами регистра 25, на которых присутствуют единичные потенциалы. Элемент И 8 открыт, сигнал с него устанавливает триггер k в нулевое состояние. Регистр 1 готов к приему информации. Разрешения на сдвиг единичного сигнала в регистре 18 нет так как на прямых выходах регистра 25 находятся нулевые уровни сигналов В процессе работы с процессоров могу поступать сигналы готовности « выполнению задачи по группе входов 35 и сигналы отказов по группе входов 29 в виде коротких единичных сигналов.

Очередь задач устанавливается планировщиком и находится в запоминающе устройстве, откуда задачи в порядке очереди поступают на егистр 1 по сигналу разрешения записи в регистр 1, поступающему с выхода элемента И 8 Заявка представляет собой совокупность кода номера задачи и кода числа потребных процессоров, представляющего собой позиционный код, где число единиц соответствует количеств потребных процессоров. С групп выходов регистра 1 код номера задачи поступает на группу элементов ИЛИ 17, а с их выходов --на группу блоков 19 элементов И. Кед количества потребны процессоров поступает на входы блока элементов И 3 и записывается по группе входов 31 на регистр 11 сдвига. После записи кода потребных процессоров на регистр 11 сдвига данный код появляется на его выходах 37 в виде единичных уровней в соответствующих разрядах. Затем эти уровни подаются на элемент ИЛИ 12, выходной сигнал с которого разрешает сдвиг содержи

5

0

5

0

5

0

5

0

5

мого регистра 11 сдвига. Частота генератора регистра 11 сдвига, собранного на элементах И 39, НЕ t1 , элементе 40 задержки, выбирается такой, чтобы в случае записи задачи на процессор (процессоры) сигнал обнуления с соответствующего элемента группы элементов ИЛИ 23 успел обнулить соответствующий разряд регистра сдвига до того, как произойдет очередной циклический сдвиг содержимого регистра 11 сдвига на один разряд. Одновременно сигналы с выходов регистра 11 сдвига поступают на соответствующие блоки 19 элементов И. При этом, те блоки, на которые поступили единичные сигналы от регистра 11 сдвига и регистра 2, открываются и разрешают запись кода номера задачи по группе выходов 36 на нужный свободный процессор (процессоры), причем одновременно происходит запись кода номера задачи на соответствующий регистр группы 20 регистров и обнуление через элементы ИЛИ 23 соответствующего разряда регистра 2k и регистра 11 сдвига. После того, как все разряды регистра сдвига 11 окажутся обнуленными, т.е. заявка распределена , единичный сигнал с выхода элемента И 8 разрешает запись на регистр 1 очередной задачи. Элемент 2 задержки предназначен для того, чтобы вследствие разного быстродействия регистра 1 и элементов И 3 код количества процессоров старой задачи по разрешающему сигналу вновь не переписался на регистр 11 сдвига.

Процесс распределения задачи повторяется. Если количество свободных процессоров меньше, чем потребных, или есть свободные процессоры, но их местоположение не соответствует положению единичных сигналов в определенных разрядах регистра 11 сдвига, т.е. нет разрешения на блоках элементов И 19, то по единичному сигналу с элемента ИЛИ 12 содержимого регистра 11 сдвига циклически сдвигается на один разряд и вновь происходит сопо- ставление сигналов разрешений на блоках элементов И 19. Если есть свободный процессор и он потребен для решения задачи, то происходит запись кода номера задачи по группе выходов 36 устройства через определенный блок 19 элементов И на этот процессор и определенный регистр группы 20, а

также обнуление разрядов в регистре 2Ц и регистре 11 сдвига. В процессе работы устройства процессоры освобождаются по мере решения задач. Импуль- сы готовности от процессора, поступающие по соответствующим входам группы входов 35, записываются в соответствующие разряды регистра 2k и обнуляют содержимое по старой задаче соответствующего регистра группы регистров 20, подготавливая регистр для приема кода номера задачи очередной заявки.

В процессе работы устройства мо- гут происходить как единичные, так и массовые отказы процессоров, причем этот процессор (процессоры) может быть занят решением задачи, а может находиться и в режиме ожидания новой задачи Г

Рассмотрим случай, когда отказывает процессор (процессоры), занятый решением задачи.

В ходе распределения задачи при отказе процессора сигнал отказа поступает по соответствующему входу группы входов 29 на соответствующий элемент группы 28 элементов И, а так как есть разрешающие сигналы с выхо- дов соответствующих элементов ИЛИ 27, на входы которых поступает нулевое содержимое регистров группы 20 регистров, в которых записаны коды номеров решаемых , то с выхода соответствующего (или соответствующих при групповом отказе процессоров) элемента И группы 28 элементов И 1 записывается в определенный разряд регистра 25.

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

С группы инверсных выходов регистра 25 нулевые сигналы поступают на элемент И 8, запрещая подачу сигнала разрешения записи на регистр 1 после окончания распределения текущей задачи. Одновременно единичные сигналы с группы прямых выходов регистра 25 поступают на элемент ИЛИ 16, с его выхода единичный сигнал поступает на элемент И 6 и 13 и разрешает циклический сдвиг единичного сигнала в регистре 18 поиска.

После окончания распределения текущей заявки на группе выходов регистра 11 сдвига появляются нулевые потен

с

5 0

5 о

5

5

0

S

0

циалы, на выходе элемента НЕ 9 появляется единичный сигнал, который разрешает запись единичного сигнала с выхода элемента И 13 через элемент ИЛИ 7 в младший разряд регистра t1 сдвига. Одновременно единичный сигнал с элемента НЕ 9 поступает на элементы И 8 и 6. Но так как элемент И 8 закрыт, а на элемент И 6 поступает разрешающий сигнал с элемента ИЛИ 16, то с выхода элемента И 6 этот сигнал устанавливает триггер k в единичное состояние. Данный сигнал является стирающим для регистра 1, т.е. происходит чистка регистра 1. В это время на выходах регистра сдвига 11 появляется единичный сигнал в одном из разрядов, при этом нулевой сигнал с элемента НЕ 9 закрывает элемент И 13, чтобы во время циклического сдвига содержимого регистра сдвига 11 на его вход не поступала информация с элемента ИЛИ 7. Два единичных сигнала с выхода триггера 4 и с выхода элемента ИЛИ 12 открывают элемент И 5, единичный сигнал с которого присутствует на синхровходе регистра 25 до тех пор, пока есть единичный сигнал на выходах регистра сдвига 11. Единичный сигнал с выхода триггера обеспечивает работу группы элементов И 22. Как только единичный сигнал с группы выходов регистра 18 поступает на тот элемент И группы элементов И 22, на другом входе которого присутствует единичный сигнал с одного из прямых выходов регистра 25, единичный сигнал с выхода этого элемента И прекращает циклический сдвиг содержимого регистра 18 по группе входов 36, единичный сигнал с данного элемента И группы элементов И 22 поступает на соответствующий вход группы входов обнуления по синхроимпульсу при этом данный разряд обнуляется по окончании распределения данной задачи по синхроимпульсу. Кроме того, единичный сигнал с этого элемента И группы элементов И 22 поступает на элемент ИЛИ 15, с выхода элемента ИЛИ 15 на вход элемента НЕ 1, с выхода которого нулевой сигнал закрывает элемент И 13 до тех пор, пока есть единичный сигнал с данного элемента И группы элементов И 22, а следовательно, пока присутствует код номера задачи на входах блоков элементов И 19 после ее распределения.

По разрешающему сигналу с соответствующего элемента И группы элементов И 22 открывается один из блоков группы блоков элементов И 21, код номера с отказавшей задачи через этот блок поступает на группу элементов ИЛИ 17 с группы выходов соответствующего регистра группы регистров 20, с выходов группы элементов ИЛИ 17 код номера IQ этой задачи поступает на входы блоков элементов И 19 и происходит распределение задачи по процессорам, как и при работе без отказавших процессоров. Как только код номера задачи 15 распределен, на выходах 37 регистра сдвига 11 появляются нулевые сигналы, при этом с выхода элемента ИЛИ 12 нулевой сигнал поступает на элементы НЕ 9 и И 5. Нулевой перепад с выхо- 20 да элемента И 5 поступает на вход синхронизации регистра 25. По нулевому перепаду обнуляется тот разряд, в котором находится единичный сигнал с выхода элемента И группы элементов 25 И 22. Одновременно единичный сигнал с элемента НЕ 9 поступает на элемент И 13. Как только код номера задачи исчезает с выходов группы элементов ИЛИ 17, с выхода элемента И 13 запи- 30 сывается очередной единичный сигнал в регистр 1Т сдвига через элемент ИЛИ 7. Нулевые сигналы с выходов элементов VI группы элементов И 22 разрешают циклический сдвиг единичного 5 сигнала в регистре 18 поиска. Если в регистре 25 записаны единичные сигналы, то обработка задач отказавших процессоров протекает аналогично описанному.40

В случае распределения последней задачи отказавших процессоров после синхроимпульса с выхода элемента И 5 на прямых выходах регистра 25 оказываются все нулевые сигналы, элемент И 8 открывается, так как на него поступил единичный сигнал с выхода элемента НЕ 9 и все единичные сигналы с группы инверсных выходов регистра 25, при этом единичный сигнал с выхода элемента И 8 обнуляет триггер k и разрешает запись на регистр 1 очередной заявки. В это время нулевой сигнал с выхода элемента ИЛИ 16 поступает на элемент И 13 быстрее, чем единичный сигнал с элемента НЕ И эа счет 5 различной глубины прохождения сигнала, что предотвращает запись единичного сигнала с выхода элемента И 13 через

элемент ИЛИ 7 в младший разряд регистра 11 сдвига.

Нулевой сигнал с выхода элемента ИЛИ 16 прекращает циклический сдвиг содержимого регистра 18 и подает запрещающий нулевой сигнал на элемент И 6. Устройство переходит в режим распределения входного потока заявок по процессорам.

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

Сигналы отказа поступают по группе входов 29 и обнуляют соответствующие разряды регистра 2й через элементы группы элементов ИЛИ 26, чтобы задача не распределилась на отказавшие процессоры. Одновременно эти поступившие сигналы отказов поступают на один из входов элементов И группы элементов И 28. Но в регистрах группы 20 регистров отказавших процессоров информации не записано (она обнулена предшествовавшим отказу сигналом готовности с процессоров), и на выходах соответствующих элементов ИЛИ группы элементов ИЛИ 27 присутствуют нулевые сигналы, которые запрещают запись сигналов отказа на регистр 25, чтобы устройство не работало вхолостую. В процессе работы процессоры могут восстанавливать свою работоспособность, при этом сигналы готовности по группе входов 35 записываются в регистр 2k и обнуляют содержимое соответствующих регистров группы регистров 20, подготавливая их к приему новой задачи .

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

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

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

ГРУППЫ, ВЫХОДЫ КОТОРЫХ ЯВЛЯЮТСЯ ГРУП-

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

15

0

5

,

|Q

о5

5

0

5

0

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

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

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

ы.

т

31

т

SO. т

Н1

Slf

Фм.г

V

Ј

-

Редактор Л.Пчолинская

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

Техрел М.Ходанич Корректор О.Кравцова

аказ 8101/5

Тираж 668

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

Ј

r

4

i

Подписное