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

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

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

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

Устройство содержит первую группу информационньк входов 1 устройства, вторую группу информационных входов 2 устройству, группу регистров. 3 хранения, группу элементов И 4, коммутатор 5, группу информационных входов 6 коммутатора 5, группу входов 7 коммутатора 5, первую группу выходов 8 коммутатора 5, вторую группу выходов 9 коммутатора 5, элемент ИЛИ-НЕ 10, элемент ИЛИ 11, регистр 12 готовности процессоров, блок элементов И 13,группы информационных выходов 14 устройства, группу сигнальных входов 15 устройства.

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

В исходном состоянии информация о задачах на группах информационных входов 1 и 2 устройства отсутствует Регистры 3 хранения группы обнулены на входах 6 и выходах 8 и 9 коммутатора действунуг нулевые сигналы.Поскольку и выходах 8 коммутатора 5 нулевая информация, то нулевые сигналы действуют на управляющих входах блоков элементов и 13 и на группе входов сброса регистра 12 готовности процессоров. Так как все процессоры свободны, то регистр 12 готовности процессоров заполнен нулями и на группе его выходов, следовательно, на входах элемента ИЛИ 11 и на гру пе входов 7 коммутатора 5 действуют единичные сигналы. Единичньй сигнал с выхода элемента ИЛИ 11 поступает на второй вход последнего элемента И 4, на первом входе которого, а та же на первых входах остальных элеметов И 4, действует единичный сигнал с выхода элемента ИЛИ-НЕ 10, так как на всех его входах действуют нулевые сигналы.

Единичный сигнал с выхода последнего элемента И 4 поступает на упраляющий вход последнего регистра 3

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

Программа Планировщик операционной системы (ЭПП ОС) строит упорядоченный по приоритетам список задач и вьщает информацию о задачах на первую и вторую группу информационных входов 1 и 2 устройства,причем на пер вую группу выдается номер задачи, а на вторую - количество потребных дгда ее решения процессоров в позиционном коде. Так как на управляющих входах регистров 3 хранения действуют единичные сигналы с выходов соответствующих элементов И, то информация о задачах последовательно переписьгоается с регистра на регистр. Первая задача, поступающая в устройство для распределения, записывается в последний регистр 3 хранения, предпоследняя - в первьй регистр хранения, а последняя остается на первой и второй группах информационных входов 1 и 2 устройства.

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

Код номера задачи с первой группы выходов регистра хранения поступает ,на группы информационных входов каждого блока элементов И 13, которые находятся в закрытом состоянии. По-3зиционный код количества потребных для решения задачи процессоров с второй группы выходов последнего регистра 3 хранения подается на группу информационных входов 6 коммутатора 5. Так как для решения задачи всегда требуется минимум один процессор, то на выходе младшего разряда последнего регистра 3 хранения и, следовательно, на входе 6 коммутатора 5 при поступлении на распределение любой задачи всегда будет единичньй сигнал, который поступает на второй вход элемента И 15, на первом входе которого действует единичный сигнал с выхода элемента И 4, единичный сигнал с вы хода элемента И 15 подается на вход формирователя 16. Единичньй сигнал с выхода .формирователя 16 поступает на последний вход элемента ИЛИ-НЕ 10. На выходе элемента КЛИ-НЕ 10 устанавливается нулевой сигнал, который подается на первые входы всех элементов И 4, закрывая их. Нулевые сигналы с выхо дов элементов И 4 поступают на упра ляющие входы соответствующих регист ров 3 хранения, блокируя дальнейший сдвиг информации по регистрам. Одновременно нулевой сигнал с выхода элемента ИЛИ-НЕ 10 подается на упра ляющий вход регистра 12 готовности процессоров, с выхода которого инфор мация о наличии свободных процессоров, вьщаваемая в позиционном коде, поступает на группу входов 7 коммутатора 5 и на входы элемента ИЛИ 11 Единичные сигналы с выходов 8 коммутатора 5 поступают на управляющий вход соответствующего блока элементов И 13 и на информационные входы триггеров регистра 12 готовности процессоров, соответствующих назначенным на решение задачи процессорам Блоки элементов И 13, соответствующие назначенным на решение задачи процессорам, открываются и код номера задачи с первой группы выходов последнего регистра 3 хранения поступает в назначенные процессоры, которые начинают решение задачи. По окончании цикла распределения единичньй сигнал с выхода формирователя 16 снимается и, если требования задачи полностью удовлетворены, т.е. нет единичных сигналов на выходах 9 коммутатора 5, на выходе 91 .4 элемента ИЛИ-НЕ 10 появляется единичньй сигнал, который подается на С-входы триггеров регистра 12 готовности процессоров и на первые входы элементов И 4. По фронту этого сигнала триггеры, на информационных входах которых действуют единичные сигналы, соответствующие назначенным для решения задачи процессорам, устанавливаются в единичное Состояние, единичные сигналы с инверсных выходов этих триггеров и, следовательно, с соответствующих входов элемента ИЛИ 11,.снимаются. Если в . процессе распределения окажутся назначенными все процессоры, то на выходе элемента ИЛИ 11 устанавливается нулевой сигнал, которьй блокирует поступление новых задач на распределение до момента освобождения хотя бы одного процессора. Таким образом после окончания цикла распределения на всех входах последнего элемента И 4 действуют единичные сигналы. Единичный сигнал с выхода элемента И 4 поступает на управляющий вход последнего регистра 3 хранения, осуществляя сброс информации, и одновременно подается на второй вход предпоследнего элемента И 4, на первом входе которого действует единич- ньй сигнал с выхода элемента ИЛИ-НЕ 10. Единичный сигнал с выхода элемента И 4 поступает на управляющий вход предпоследнего регистра 3, осуществляя перепись его содержимого в последний регистр 3 хранения, и на второй вход предьщущего элемента И 4, единичный, сигнал с выхода которого разрешает перепись информации предпоследнего регистра 3 хранения, выполняя описанные действия, и т.д. Таким образом, реализуются операции сдвига информации о задачах по регистрам хранения и поступления на распределение очередной задачи. Следовательно,необходимьм и достаточным условием дпя поступления на распределение новой задачи является окончание цикла распределения и наличие хотя бы одного процессора, т.е. наличие единичных сигналов на обоих входах последнего элемента И А. Если по окончании времени гщкла распределения формируемым формфователем 16 задача не полностью распреелена по процессорам, о чем свидетельствует наличие единичных сигналов

на каком-либо выходе 9 коммутатора 5, на выходе элемента ЙЛИ-НЕ 10 будет нулевой сигнал, который подается на первый вход последнего элемента И 4, блокируя поступление на распределение следующей эадачи. Так как мультипроцессорная система загружается задачами различной временной степени трудности поочередно, то процессоры заканчивают решение задач динамично. После окончания решения какой-либо задачи процессор выставляет еднничньй сигнал готовности, которьй с группы входов 15 подается на cootвeтcтвyющий вход группы входов регистра 12 готовности процессоров. Единичный сигнал с выхода последнего поступает на вход 7 распределяющего блока 5 и на вход элемента ИЛИ 11, с выхода которого

он подается на второй вход последнего элемента И 4. Наличие единичного сигнала на входе 7 позволяет назначить освободившийся процессор на решение перераспределенной задачи.Назначение производится описанным образом. По окончании распределения всего списка заданий устройство возвращается в исходное состояние.

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

УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАЧ МЕЖДУ ПРОЦЕССОРАМИ, содержащее регистр готовности процессоров, элемент ИЛИ, п блоков элементов И, где п - число процессоров, группу элементов И, элемент И и группу регистров хранения, причем первая группа информационных входов первого регистра хранения группы является первой группой информационных входов устрой- . ства,вторая группа информационных входов первого регистра хранения группы является второй группой информационных входов устройства, управляющий вход каждого регистра хранения группы соединен с выходом соответствующего элемента И группы, первая и вторая группы вькодов каждого регистра хранения группы, кроме последнего, соединены соответственно с первой и второй группами информационных входов последующего регистра хранения группы, первая группа выходов последнего регистра хранения группы соединена с группой информационных входов каждого блока элементов И, группа выходов каждого блока элементов И подключена к.одноименной группе информационных выходов устройства, группа информационных входов регистра готовности процессоров соединена с группой сигнальных входов устройства,первые входы элементов И группы объеди-, нены между собой, отличающее с я тем, что, с целью повышения быстродействия устройства за счет организации параллельного распределения задач между процессорами, в него введены коммутатор, элемент ИЛИ-НЕ, формирователь импульсов, причем группа информационных входов коммутатора подключена к группе выходов последнего регистра хранения группы, группа управляющих входов коммутатора подключена к группе выходов регистра готовности процессоров и входам элемента ИЛИ, каждьй выход первой группы выходов коммутатора подключен к соответствующему входу группы обнуляющих входов регистра готовности процессо.ров и к. управляющему входу соответствующего блока элементов И, вторая группа выходов коммутатора подключена к входам элемента ШТИ-НЕ,. выход кото s| рого подключен к управляющему входу :о регистра готовности процессоров и первому входу последнего элемента И группы, второй вход которого подключен к выходу элемента ШШ, а выход - к первому входу элемента И, второй вход которого подключен к выходу младщего разряда последнего регистра хранения группы, а выход к входу формирователя импульсов, выход которого подключен к последнему входу элемента ИПИ-НЕ, выход каждого элемента И группы, начиная , с последнего, подключен к второьсу входу предьдущего элемента И группы.