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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУ БЛИН

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

Г10 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) 1095181 (21) 3824273/24-24 (22) 17.12.84 (46) 15.10.86. Бюл; Р 38 (72) А;Х.Ганитулин и В.Г.Попов (53) 681.325 (088.8) (56) Авторское свидетельство СССР.

Р 1095181, кл. G 06 Р 9/46, 1984. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

ЗАДАНИЙ ПРОЦЕССОРАИ (57) Изобретение относится к вычислительной технике и является усовершенствованием устройства IIO авт. св.11- 1095181. Цель изобретения— повышение быстродействия. Устройство для распределения заданий процессорам содержит распределитель им„„SU„„1264173 А 2 (51) 4 С 06 F 9/46 пульсов, элементы И,ИЛИ, элементы задержки, два одновибратора, триггер режима, дешифратор режима, коммутатор, групву регистров хранения, ре-. гистр сдвига, регистр распределения, регистр готовности процессоров, буферный регистр. В устройстве одновременно с реализацией функции формирования очереди и отслеживания ее состояния производится отслеживание состояния процессоров. Перевод процессора из состояния "Свободен" в состояние "Занят" может произойти в результате выполнения функции

"Выделение .процессоров задаче", а освобождение лроцессара может про-изойти. в любое время работы устройства. ил.

1264173

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

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

Устройство содержит распределитель 1 импульсов, вход 2 сброса, !

О распределителя 1, вход 3 з апуск а устройства, вход 4 останова распределителя 1, первый выход 5 третий выход 6 и второй выход 7 распределителя 1, элемент И 8, элемент И 9, !

5 элемент 10 задержки, элемент ИЛИ 11, элемент ИЛИ 12, элемент ИЛИ 13, одновибратор 14, триггер 15 режима, :элемент ИЛИ 16, элемент И 17, группу элементов И 18, элемент 19 задержки, дешифратор 20 режима, второй одновибратор 21, элемент И 22, коммутатор 23, первый 24 и второй

25 управляющие входы коммутатора 23, первый 26 и второй 27 информацион25 ные входы коммутатора 23, первый 28 и второй 29 информационные выходы коммутатора 23, группу 30 регистров хранения, блок элементов И 31, блок элементов И 32, регистр 33 сдвига, вход 34 сдвига, вход 35 сброса, информационный вход 36 и группу входов

37 сброса разрядов регистра 33 сдвига,.группу элементов И 38, регистр

39 распределения, группу элементов 35

И 40, группу 41 информационных входов устройства, регистр 42 готовности"процессоров, буферный регистр 43, выходы 44 кода количества процессоров и выходы 45 кода номера задачи 40 буферного регистра 43, элемент 46 задержки, группу элементов ИЛИ 47, группу элементов И 48, регистр 49 готовности, группу одновибраторов 50, первые элементы ИЛИ 5! и 52, элемент 45

И 53, выходы 54 элементов И 40.

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

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

"0 (не показано) . После этого в регистр готовности процессоров 42 по входам 41 поступают сигналы готовности от свободных процессоров. 55

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

С выхода элемента ИЛИ 13 снимается нулевой сигнал, так как регистр

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

Одновременно с сигналом Пуски на вход 26 устройства поступает заявка. Под воздействием управляющего сигнала Запись" с выхода элемента

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

Так как последний регистр 30 группы при первоначальном формировании очереди заявок находится в состоянии "0, то единичными сигналами с инверсных выходов разрядов кода номера задачи через элементы

И 53 и ИЛИ 52 последний элемент

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

После заполнения последнего регистра 30 на выходе элемента И 51 едииичный сигнал снимается. Если на данный момент в регистре 42 го1264 тавности проце соров не зафиксиронаны сигналы от свободных процессо— ров, то на выходе элемента ИЛИ 51 присутствует нулевой сигнал, которым через элемент ИЛИ 52 последний элемент И 18 закрывается, запрещая прохождение тактовых сигналов.

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

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

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

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

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

Далее устройство реализует функцию "Распределение процессоров Bb(6раиной задаче".

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

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

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

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

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

1264173

45

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

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

На входы элементов И 38 поступают код количества процессоров с вы- хода регистра 33 и код состояния процессорон с выходов регистра 49.

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

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

50, устанавливающие в состояние "О" соответствующие разряды регистров

33 и 49.

Одновременно сигнал выбора процес— сора и код номера зала«и с выходов

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

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

Завершается этот процесс н том случае, когда н регистре 33 нсе разряды установлены н 0". По этому состоянию сигналом с выхода элемента

ИЛИ 13 запускается одновибратор !4, устанавливающий н состояние Ои триггер !5, а через элемент ИЛИ 11 и одновибратор 3! — регистр 39. При этом в регистре 49 продолжается от- слеживание состояния процессорон, так как единичным сигналом с выхода элемента И. !И !2 через элементы

И!!И 47 на входах элементов И 48 поддерживается единичный уровень сигпала. По нулевому сигналу с выхода элемента KIH IЗ разрешается продвижение заявок в очереди, если в регистре 42 готовности процессоров имеется хотя бы один свободный процессор. В противном случае устройство переходит н режим ожидания освобождения процессоров.

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

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

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

По единичному сигналу с выхода элемента ИЛИ 13, поступающему на вход 4 распределителя l, и нулевому сигналу с выхода триггера 15, поступающему на вход 2 распределителя на его выходе 6 появляется сигнал. По этому сигналу открывают7 12б41 ся по первому входу элемент И 8, а по второму — элемент И 9.

Сигналами с выхода 5 распределителя 1 осуществляется один цикл сдвига кода регистра 33. При этом 5 аналогично производится установка в "1" разрядов регистра 39, а в

"0" — регистров 33 и 49. Так как элементы И 40 закрыты, то выделение процессоров задаче не происходит.

По окончании цикла сдвига в регистре 39 фиксируется результат проведенного распределения процессоров.

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

ИЛИ 1б открываются элементы И 40, разрешая однвоременное выделение процессоров как и в указанном режиме обслуживания заявок в порядке поступ-25 ления, сохраняется единичный сигнал. Поэтому сигналом с выхода 6 распределителя 1 через открытый элемент И 9 на выходе элемента И 17 формируется единичный сигнал "Запись", поступающий на первый управляющйй вход 24 коммутатора 23. Кроме того, единичным сигналом с выходов элементов

И 9 и ИЛИ 12 открываются элементы

И 18, 31 и 32, разрешая прохождение тактового сигнала с выхода 7 распределителя. Одновременно единичным сигналом с выхода элемента И 9 устанавливается в "0" регистр 33, через элемент ИЛИ 11 и одновибратор 2! регистр 39. После этого копия заявки из регистра 43 по входу 27 по сигналу записи с входа 24 записывается в первый регистр 30, т.е. в конец очереди, остальные заявки перемещаются по регистрам 30, а очередная заявка принимается на обслуживание в регистры 33 и 43. В дальнейшем работа устройства аналогична.

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

Задержанный на элементе 10 задержки на время выделения процессоров единичный сигнал через элемен

ИЛИ 11 и одновибратор 21 устанавливает в "О" .регистр 39. Нулевым сигналом с выхзда элемента ИЛИ 13 по входу. останова распределителя 1 запрещается дальнейшее поступление 3g сигналов сдвига с выхода 5 распределителя 1 на вход 34 регистра 33.

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

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

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

Ф 1095181, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, оно содержит пятый элемент

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

1264173

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

Редактор И.Касарда Техред B.Кадар Корректор А.Зимокосов

Заказ 5563/49 Тираж 671 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035 Москва, Ж-35, Раушская наб., д.4/5

Производственно-полиграфическое предприятие, г.Ужгород, ул. Проектная, 4