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

ю

05 4

СО

Изобретение относится к вычислительной технике.

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

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

Устройство содержит распределитель 1 импульсов, вход 2 сброса, распределителя 1, вход 3 запуска устройства, вход 4 останова распределителя 1, первый выход 5, третий выход 6 и второй выход 7 распределителя , элемент И 8, элемент И 9, элемент 10 задержки, элемент ИЛИ П, элемент ИЛИ 12, элемент ИЛИ 13, одновибратор 14, триггер 15 режима, элемент ИЛИ 16, элемент И 17, группу элементов И 18, элемЪнт 19 задержки, дешифратор 20 режима, второй одновибратор 21, элемент И 22, коммутатор 23, первый 24 и второй 25 управляющие входы коммутатора 23, первый 26 и второй 27 информационные входы коммутатора 23, первый 28 и второй 29 информационные выходы коммутатора 23, группу 30 регистров хранения, блок элементов И 3I, блок элементов И 32, регистр 33 сдвига, вход 34 сдвига, вход 35 сброса, информационный вход 36 и группу входов 37 сброса разрядов регистра 33 сдвига,.группу элементов И 38, регистр 39 распределения, группу элементов И 40, группу 41 информационных входов устройства, регистр 42 готовности--процессоров, буферный регистр 43, выходы 44 кода количества процессоров и выходы 45 кода номера задачи буферного регистра 43, элемент 46 задержки, группу элементов ИЛИ 47, группу элементов И 48, регистр 49 готовности, группу одновибраторов 50 первые элементы ИЛИ 51 и 52, элемент И 53, выходы 54 элементов И 40.

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

Исходное состояние устройства ха,растеризуется тем, что все его элементы памяти установлены в состояние О не показано) . После этого в регистр готовности процессоров 42 по входам 4 поступают сигналы готовности от свободных процессоров.

Формирование очереди заявок в регистрах 30 осуществляется после прит ведения устройства в рабочее состояни

по сигналу Пуск, поступающему на вход 3.

С выхода элемента ИЛИ 13 снимается нулевой сигнал, так как регистр 33 находится в состоянии О. При этом в открытом состоянии находятся элементы И 22 и 8, а на выходе элемента ИЛИ 12 присутствует единичный сигнал. Этим сигналом открываются элементы И185И31 иИ32, а через элементы ИЛИ 47 - элементы И 48.

Одновременно с сигналом Пуск на вход 26 устройства поступает заявка. Под воздействием управляющего сигнала Запись с выхода элемента И 22 код кол1Г4ества процессоров с выхода 28 и код номера записи с выхда 29 коммутатора 23 записываются в первый регистр 30. Формирование управляющего сигнала Запись и тактовых сигналов, обеспечивающих запонение регистров 30 поступающими заявками с входа 26, производится следукхцим образом.

Так как последний регистр 30 группы при первоначальном формировании очереди заявок находится в состоянии О, то единичными сигналами с инверсных выходов разрядов кода номера задачи через элементы И 53 и ИЛИ 52 последний элемент И 18 группы открыт, и сигнал с выхода 7 распределителя 1 через этот элемент и элемент 19 задержки поступает на первый вход первого элемента И 18 и через элемент И 22 - на второй управлягадий вход 25 коммутатора 23 в качестве сигнала Запись,, Сигналом с выхода первого элемента И IB, поступающим на тактовый вход первого регистра 30, заявк записывается в этот регистр тактовыми сигналами с выходов последующих элементов И 18, начиная с второго, прежнее содержимое каждого предыдущего регистра 18 переписывается в последу сщий, образуя тем самым передвижение заявок в группе регистров 30. По каждому очередному тактовому сигнгшу Запись в регистрах 30 формируется очередь заявок, реализуя дисциплину обслуживания по алгоритму Первым пришел - первым обслужен.

После заполнения последнего регистра 30 на выходе элемента И 5 единичный сигнал снимается. Если на данный момент в регистре 42 го31

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

При наличии хотя бы одного сигнала готовности в регистре 42 в очередном такте первая поступившая заявка выбирается на обслуживание из последнего регистра 30 через открытые элементы И 31 в регистр 33 сдвига по входу 36. Одновременно код количества процессоров через элементы ИЗ и код номера задачи через элементы И 32 передаются в буферный регистр 43 по тактовому сигналу через элемент 46 задержки. Наличие элемента 19 задержки в цепи управления записью в регистры 30 группы позволяет обеспечить завершение записи в регистры 33 и 43 до того, как изменяется состояние очереди (осуществляется сдвиг заявок в очереди)

Одновременно с реализацией функции формирования очереди и отслеживания ее состояния в устройстве осуществляется отслеживание состояния процессоров. Сигналы готовносди из регистра 42 через открытые элементы И 48 единичным сигналом с выхода элемента ИЛИ 13 через элементы ИЛИ 12 и 47 передаются в соответствующие разделы регистра 49 готовности.

Особенностью функции отслеживания состояния процессоров является то, что перевод процессора из состояния Свободен в состояние Занят может произойти в результате выполнения функции Вьщеление процессоров задаче, а освобождение процессора может произойти в любое время работы устройства. Поэтому содержимое регистра 49 должно отражать состояние процессоров к моменту выполнения функции Вьщеление процессоров задаче.

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

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

гистров 33, 42 и 49 одинакова и соответствует числу процессоров вычислительной системы. В регистре 49 зафиксирован позиционный код состояния процессоров, в регистре 43 - ко1тая заявки, выбранной на обслуживание, в регистрах 30 - очередь заяво на решение задач.

Далее устройство реализует функцию Распределение процессоров выбранной задаче.

В зависимости от количества требуемых процессоров для регаения задачи устройство работает в одном из двух режимов: Обслуживание заявок в порядке ..поступления или Обслуживание заявок по круговому циклическому алгоритму. Установка режима производится триггером 15 режима единичным сигналом с выхода дешифратора 20 режима, настроенного на определенный код требуемого числа про цессоров. Таким образом, переключение устройства в один из этих режимов производится самой заявкой, принятой в регистр 33.

Суть работы устройства в указанных режимах состоит в следукщем.

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

Работа устройства в режиме Обслуживание заявок в порядке поступления состоит в следующем.

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

5

закрывается элемент И 22 и запрещается запись заявок с входа 26 устройства в регистры 30. Однопременно снимается единичный сигнал с выхода элемента ИЛИ 12, чем закрываются элементы И 18 групны и запрещается прохождение сигнала записи через эт элементы. Кроме того, затсрываются элементы И 31 и 32, запрещая тем самым выбор заявок на обслуживание из последнего регистра 30. Через элеметы И.ПИ 47 закрываются элементы И 48, В регистре 49 зафиксированы состояния процессоров на момент их распределения. В этом режиме срабатывает дешифратор 20, устанавливающий в состояние 1 триггер 15 режима. Пр .этом через элементы ИЛИ 16 и 47 элементы И 48 вновь открываются, обеспечивая отслеживание состояния процессоров. Кроме того, е;.1;иничным сигналом с выхода триггера 15 открываются элементы И 40, а по входу 2 распределителя 1 разрешается прохождение сигнагюв сдвига с выхода 5 распределителя 1 на вход 34 регистра 33. Под воздействием сигнала сдвига в регистре 33 осуществляется циклический сдвиг кода количества процессоров с целью поиска свободных процессоров и назначения их задаче.

Процесс выделения процессоров задаче выполняется следующим образом.

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

Единичными сигналами с выходов элементов И 38 устанавливаются в единичное состояние, соответствующее выделяемым процессорам, разряды регистра 39, с выходов которого через открытые элементы И 40 переводятся процессоры в регистре 42 в состояние Занят. Выходными сигналами разрядов регистра 39 запускаются соответствующие одновибраторы 50, устанавливающие в состояние О соответствующие разряды регистров 33 и 49.

73 6

Одновременно сигнал выбора процесора и код номера задачи с выходов 45 регистра 43 через открьгтые элементы И 40 сигналами с выхода разрядов регистра 39 передаются на выходы 51 устройства.

Процесс поиска свободных процессоров путем циклического сдвига содержимого регистра 33 производится до тех пор, пока задаче не будут ВЬ делены все требуем1ле процессоры. Завершается этот процесс в том случае, когда в регистре 33 нее разряды установлены в О. По этому состоянию сигналом с выхода элемента ИЛИ 13 запускается одновибратор 14, устанавливакядий в состояние О тригер 15, а через элемент ИЛИ II и одновибратор 3 - регистр 39. При этом в регистре 49 продолжается отслеживание состояния процессоров, так как единичньм сигналом с выхода элемента И.ПИ 2 через элементы Ш1И 47 на входах элементов И 48 поддерживается единичный уровень сигнала. По нулевом сигналу с выхода элемента ИЛИ 13 разрешается продвижение заявок в очереди, если в регистре 42 готовности процессоров имеется хотя бы одрш свободный процессор. В противном случае устройство переходит в режим ожидания освобождения процессоров о

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

Если после завершения формирования очереди заявок в регистрах 30, в регистре 42 зафиксированы сигналь готовности процессоров, то очередным тактовым сигналом код числа требуемых процессоров передается в регистр 33, а копия заявки - в регистр 43 указанным образом.

В этом режиме единичный сигнал дешифратором 20 не формируется, и триггер 15 остается в нулевом состоянии. При этом на выходе элементов ИЛИ 47 снимается единичный сигнал, чем фиксируется код числа свободных процессоров в регистре 49.

По единичному сигналу с выхода элемента ИЛИ 13, пocтyпaющe fy на вход 4 распределителя 1, и нулевому сигналу с выхода триггера 15, поступающему на вход 2 распределителя 1, на его выходе 6 появляется сигнал. По этому сигналу открывают7ся по первому входу элемент И 8, а по второму - элемент И 9. Сигналами с выхода 5 распределителя 1 -осуществляется один цикл сдвига кода регистра 33. При этом аналогично производится установка в разрядов регистра 39, а в О - регистров 33 и 49. Так как злементы И 40 закрыты, то выделение процессоров задаче не происходит. По окончании цикла сдвига в регист ре 39 фиксируется результат проведенного распределения процессоров. Если за один цикл распределения все необходимые процессоры задаче могут быть представлены, о чем свидетельствует нулевое состояние регистра сдвига 33, то элемент И 8 от крьшается нулевым сигналом с выхода элемента ИЛИ 13. Единичным сигналом с выхода элемента И 8 через элемент ИЛИ 16 открываются элементы И 40, разрешая однвоременное вьщеление процессоров как и в указанном режим обслуживания заявок в порядке посту ления.

Задержанный на элементе 10 задержки на время выделения процессоров единичный сигнал через элемент ИЛИ 11 и одновибратор 21 устанавливает в О регистр 39. Нулевым сигналом с выхода элемента ИЛИ 13 по входу останова распределителя 1 запрещается дальнейшее поступление сигналов сдвига с выхода 5 распределителя 1 на вход 34 регистра 33. В дальнейшем работа устройства аналогична.

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

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

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

группы, выходы пятых элементов ИЛИ и И подключены к входам шестого элемента ИЛИ, выход которого соединен с третьим входом последнего эле |ента И второй группы. 38 сохраняется единичный сигнал. Поэтому сигналом с выхода 6 распределителя 1 через открытый элемент И 9 на выходе элемента И 17 форт ируется единичный сигнал Запись, поступающий на первый управляющ вход 24 коммутатора 23. Кроме того, единичным сигналом с выходов элементов И 9 и ИЛИ 12 открьшаются элементы И 18, 31 и 32, разрешая прохождение тактового сигнала с выхода 7 распределителя. Одновременно единичным сигналом с выхода элемента И 9 уста навливается в О регистр 33, через элемент ИЛИ 11 и одновибратор 21 регистр 39. После этого копия заявки из регистра 43 по входу 27 по сигналу записи с входа 24 залисьгаается в первый регистр 30, т.е. в конец очереди, остальные заявки перемещаются по регистрам 30, а очередная заявка принимается на обслуживание в регистры 33 и 43. В дальнейшем работа устройства аналогична. Формула изобретения

4Г

Изобретение относится к вычислительной технике и является усовершенствованием устройства по авт. св.№ 1095181. Цель изобретения повьшение быстродействия. Устройство для распределения заданий процессорам содержит распределитель импульсов, элементы И,ИЛИ, элементы задержки, два одновибратора, триггер режима, дешифратор режима, коммутатор, группу регистров хранения, ре-, гистр сдвига, регистр распределения, регистр готовности процессоров, буферный р егистр. В устройстве одно- . временно с реализацией функции формирования очереди и отслеживания ее состояния производится отслеживание состояния процессоров. Перевод процессора из состояния Свободен в состояние Занят может произойти в результате вьтолнения фзгнкции Вьщеление -процессоров задаче, а I освобождение процессара может произойти- в любое время работы устрой(Л ства. 1 ил.