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

СООЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИРЕСПУ БЛИН 12641) 4 С 06 Р 9/46 ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ ОБРЕТЕНИЯЕЛЬСТВУ ПИСАН К АВТОРСКОМ.Г.Поп юл; в линиВ88.8)свидетельствоС 06 Р 9/46,СССР,984. ычиссоверройст- процес- им ТРОЙСТВО ДЛЯ РАСПРЕДПРОИЕССОРАИобретение относитсяой технике и являетсванием устройства по95181. Цель изобретеие быстродействия. Ураспределения заданийодержит распределител(57) Илительшенствсв.9 1повьппенво длясорам с пульсов, элементы И,ИЛИ, элементызадержки, два одновибратора, триггеррежима, дешифратор режима, коммутатор, групау регистров хранения, ре-,гистр сдвига, регистр распределения,регистр готовности процессоров, буферный регистр. В устройстве одновременно с реализацией функции формирования очереди и отслеживания еесостояния производится отслеживаниесостояния процессоров. Перевод процессора из состояния "Свободен" всостояние "Занят" может произойтив результате выполнения функции"Выделение .процессоров задаче", аосвобождение эроцессара может произойти в любое время работы устройства,ил.Изобретение относится к вычислительной технике.Цель изобретения - повышениебыстродействия за счет снижения непроизводительных затрат времени прираспределении процессоров,На чертеже приведена структурнаясхема предлагаемого устройства.Устройство содержит распределитель 1 импульсов, вход 2 сброса,Ораспределителя 1, вход 3 запускаустройства, вход 4 останова распределителя 1, первый выход 5, третийвыход 6 и второй выход 7 распределителя 1, элемент И 8, элемент И 9,5элемент 1 О задержки, элемент ИЛИ 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.Устройство работает следующим образом.Исходное состояние устройства характеризуется тем, что все его элементы памяти установлены в состояние"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 в очередном такте первая поступившая за явка выбирается на обслуживание извпоследнего регистра 30 через открытые элементы И 31 в регистр 33 сдвига по входу 36. Одновременно код количества процессоров через эле менты И 31 и код номера задачи через элементы И 32 передаются в буферный регистр 43 по тактовому сигналу. через элемент 46 задержки. Наличие элемента 19 задержки в цепи управле ния записью в регистры 30 группы позволяет обеспечить завершение записи в регистры 33 и 43 до того, как изменяется состояние очереди (осуществляется сдвиг заявок в очереди) . 25Одновременно с реализацией функции формирования очереди и отслеживания ее состояния в устройстве осуществляется отслежИвание состояния процессоров. Сигналы готовнос ти из регистра 42 через открытые элементы И 48 единичным сигналом с выхода элемента ИЛИ 13 через элементы ИЛИ 12 и 47 передаются в соответствующие разделы регистра 49 готовности.Особенностью функции отслеживания состояния процессоров является то, что перевод процессора из состояния Свободен в состояние Занят мо, жет произойти в результате выполнения функции "Выделение процессоров задаче", а освобождение процессора может произойти в любое время работы устройства. Поэтому содержимое 45 регистра 49 должно отражать состояние процессоров к моменту выполнения функции "Выделение процессоров задаче цТаким образом, к моменту начала 50 распределения процессоров устройство характеризуется следующим состоянием.В регистре 33 записан позиционный код количества процессоров, не обходимых для решения задачи, причем он записан в смежных разрядах, начиная с младшего. Разрядность ре 173 4гистров 33, 42 и 49 одинакова и соответствует числу процессоров вычислительной системы. В регистре 49 зафиксирован позиционный код состояния процессоров, в регистре 43 - копия заявки, выбранной на обслуживание, в регистрах 30 - очередь заявок на рещение задач.Далее устройство реализует функцию "Распределение процессоров выбраиной задаче".В зависимости от количества требуемых процессоров для решения задачи устройство работает в одном из двух режимов; "Обслуживание заявок в порядке .поступления" или "Обслуживание заявок по круговому циклическому алгоритму . Установка режима производится триггером 15 режима единичным сигналом с выхода дешифратора 20 режима, настроенного на определенныйекод требуемого числа про-, цессоров. Таким образом, переключение устройства в один из этих режимов производится самой заявкой, принятой в регистр 33.Суть работы устройства в указанных режимах состоит в следукицем.В первом режиме заявка, выбранная на обслуживание, остается в уст-.ройстве в течение времени поиска и выделения процессоров в требуемом количестве. В этом режиме задача может получить необходимое количество процессоров для решения без ожидания достаточного количества процессоров, если в регистре 49 готовности на момент установки этого режима фиксируются сигналы готовности процессоров и производится предварительное распределение этих процессоров задаче, По результатам этого распределения устройство реализует либо функцию "Выделение процессоров задаче", если попытка оказалась успешной, когда число требуемых процессоров не менее числа свободных, либо заявка возвращается в ко-. нец очереди для последующих попыток распределения, если число требуемых процессоров больше свободных.Работа устройства в режиме "Обслуживание заявок в порядке поступления" состоит в следующем.После записи кода количества процессоров в регистр 33 на выходе элемента ИЛИ 13 устанавливается единичный потенциал,По этому сигналу1264173 40 45 50 3закрывается элемент И 22 и запрещается запись заявок с входа 26 устройства в регистры 30. Одновременно снимается единичный сигнал с выхода элемента ИЛИ 12, чем закрываются элементы И 18 группы и запрещается прохождение сигнала записи через эти элементы. Кроме того, закрываются элементы И 31 и 32, запрещая тем самым выбор заявок на обслуживание из О последнего регистра 30. Через элементы ИЛИ 47 закрываются элементы И 48, В регистре 49 зафиксированы состояния процессоров на момент их распределения. В этом режиме срабатывает 5 дешифратор 20, устанавливающий в состояние "1" триггер 15 режима. При этом через элементы ИЛИ 16 и 47 элементы И 48 вновь открываются, обеспечивая отслеживание состояния 20 процессоров, Кроме того, единичным сигналом с выхода триггера 15 открываются элементы И 40, а по входу 2 распределителя 1 разрешается прохождение сигналов сдвига с выхода 5 25 распределителя 1 на вход 34 регистра 33. Под воздействием сигнала сдвига в регистре 33 осуществляется циклический сдвиг кода количества процессоров с целью поиска свобод- ЗО ных процессоров и назначения их задаче.Процесс выделения процессоров задаче выполняется следующим образом.35 На входы элементов И 38 поступают код количества процессоров с вы- хода регистра 33 и код состояния процессоров с выходов регистра 49. Появление единичного сигнала на выходах элементов И 38 свидетельствует о том, что соответствующии процессор свободен и может быть выделен задаче.Единичными сигналами с выхоцов элементов И 38 устанавливаются в единичное состояние, соответствующее выделяемым процессорам, разрядырегистра 39, с выходов которого через открытые элементы И 40 переводятся процессоры в регистре 42 всостояние Занят". Выходными сигналами разрядов регистра 39 запускаются соответствующие оцновибраторы50, устанавливающие в состояние "О"соответствующие разряды регистров33 и 49. Одновременно сигнал выбора процессора и код номера задачи с выходов45 регистра 43 через открытые элементы И 40 сигналами с выхода разрядов регистра 39 передаются на выходы 51 устройства,Процесс поиска свободных процессоров путем циклического сдвига содержимого регистра 33 производитсядо тех пор, пока задаче не будут выделены все требуемые процессоры.Завершается этот процесс в том случае, когда в регистре 33 все разряды установлены в О". По этому состоянию сигналом с выхода элементаИЛИ 13 запускается одновибратор 4,устанавливающий в состояние 0 триггер 15, а через элемент ИЛИ 11 и одновибратор 31 - регистр 39. Приэтом в регистре 49 продолжается от-слеживание состояния процессоров,так как единичным сигналом с выхода элемента И.И 12 через элементыИЛИ 47 на входах элементов И 48 поддерживается единичный уровень сигпала. По нулевому сигналу с выходаэлемента ИЛИ 3 разрешается продвижение заявок в очереди, если в регистре 42 готовности процессоровимеется хотя бы один свободный процессор, В противном случае устройство переходит в режим ожидания освобождения процессоров.Работа устройства в режиме "Обслуживание по круговому циклическому алгоритму" состоит в следующем.Если после завершения формирования очереди заявок в регистрах 30,в регистре 42 зафиксированы сигналы готовности процессоров, то очередным тактовым сигналом код числатребуемых процессоров передается врегистр 33, а копия заявки - в регистр 43 указанным образом.В этом режиме единичный сигналдешифратором 20 не формируется, итриггер 15 остается в нулевом состоянии. При этом на выходе элементов ИЛИ 47 снимается единичный сигнал, чем фиксируется код числа свободных процессоров в регистре 49.По единичному сигналу с выходаэлемента ИЛИ 13, поступающему навход 4 распределителя 1, и нулевому сигналу с выхода триггера 15,поступающему на вход 2 распределителя 1, на его выходе 6 появляетсясигнал, По этому сигналу открывают 7 12 б 41ся по первому входу элемент И 8, апо второму - элемент И 9.Сигналами с выхода 5 распределителя 1 осуществляется один циклсдвига кода регистра 33. При этом 5аналогично производится установкав "1" разрядов регистра 39, а в"0" - регистров 33 и 49. Так какэлементы И 40 закрыты, то выделениепроцессоров задаче не происходит, ОПо окончании цикла сдвига в регистре 39 фиксируется результат проведенного распределения процессоров.Если эа один цикл распределениявсенеобходимые процессоры задаче 15могут быть представлены, о чем свидетельствует нулевое состояние регистра сдвига 33, то элемент И 8 открывается нулевым сигналом с выходаэлемента ИЛИ 13. Единичным сигналом 20с выхода элемента И 8 через элементИЛИ 1 б открываются элементы И 40,разрешая однвоременное выделениепроцессоров как и в указанном режимеобслуживания заявок в порядке поступ ления,сохраняется единичный сигнал. Поэтому сигналом с выхода 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 задержки на время выделения процессоров единичный сигнал через элемент З 0 ИЛИ 1 и одновибратор 21 устанавливает в "О" .регистр 39. Булевым сигналом с выхода элемента ИЛИ 13 по входу. останова распределителя 1 запрещается дальнейшее поступление З 5 сигналов сдвига с выхода 5 распределителя 1 на вход 34 регистра 33.В дальнейшем работа устройства аналогична,Если после окончания цикла сдви га в регистре 33 остались единичные значения разрядов, что означает отсутствие требуемого числа процессоров, то на выходе элемента ИЛИ 13 Устройство для распределения заданий процессорам по авт. св. У 1095181, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, оно содержит пятый элемент И, пятый и шестой элементы ИЛИ, причем входы пятого элемента ИЛИ подключены к выходам разрядов регистра готовности процессоров, входы пятого элемента И соединены с инверсными выходами разрядов кода номера задачи последнего регистра хранения группы, выходы пятых элементов ИЛИ и И подключены к входам шестого элемента ИЛИ, выход которого соединен с третьим входом последнего элемента И второй группы.1264 73Составитель М.Кудряшев Редактор И.Касарда Техред В.Кадар Корректор А.Зимокосов Заказ 5563/49 Тираж 671 Подписное ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д.4/5 Производственно-полиграфическоепредприятие, г.ужгород, ул. Проектная, 4