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

 

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

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

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

РЕСПУБЛИК

Ai (19) (И) (5)) 4 G 06 F 9 46

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

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

ПО ИЗОБРЕТЕНИЯМ И OTHPbfTHRM

ПРИ П.(НТ СССР

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4270427/24-24 (22) 02.04.87 (46) 23.01.89. Вюл. 9 3 (72) А.И. Иванов и С.М.,Терешко (53) 681.325 (088.8) (56) Авторское свидетельство СССР

Ф 629538, кл. С 06 F 9/00, 1978.

Авторское свидетельство СССР

У 913377, кл. G 06 F 9/00, 1980 ° (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

ЗАДАНИЙ ПРОЦЕССОРАМ (57) Изобретение относится к области вычислительной техники и автоматики и может быть использовано при построении многопроцессорных вычислитель,ных систем. Цель изобретения — расширение функциональных возможностей за счет распределения заданной процессором с учетом обеспечения приоритетной обработки входящих заданий.

Устройство содержит регистр готовности процессоров, два блока управления, регистр номера задания, регистр приоритета задания; регистр адреса записи приоритета задания, блок папяти приоритетов заданий, блок памяти упорядоченных приоритетов заданий, блок памяти номеров заданий, узел сортировки информации, дешифратор, шифратор, две схемы сравнения> эле-. менты И, ИЛИ задержки. В устройстве обеспечивается решение в вычислительном комплексе заданий с высоким прио- Ж ритетом в условиях отсутствия свободных процессоров ° 1 ил.

1453406

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

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

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

Устройство содержит группу сигнальных входов 1 устройства, группу входов 2 приоритета задания устройст-15 ва, группу входов 3 номера задания устройства, запросный вход 4 устройства, регистр 5 готовности процессоров, регистр 6 приоритета задания, регистр 7 номера задания, регистр 8 20 адреса записи приоритета задания, блок 9 памяти приоритетов заданий, блок 10 памяти упорядоченных приори" тетов заданий, блок 1 l памяти номеров заданий, узел 12 сортировки ин- 25 формации, блоки 13 и 14 управления, дешифратор 15, шифратор 16, группы

1?-20 элементов И, блоки элементов И

21 и 22, группы элементов ИЛИ 23, элементы ИЛИ 24-27, схемы 28 и 29 сравнения, элементы И 30 и 31, гене" ратор 32 импульсов, триггер 33, элементы 34-36 задержки, блок 37 элементов задержки, сигнальный выход 38 устройства. -Блок 13 содержит генератор 39 импульсов, триггер 401 элемент

И 41» счетчик 42, элемент ИЛИ 43, дешифратор 44, вход 45, вход 46, выход 47, выходы 48. Блок 14 выполнен аналогично блоку 13 и имеет вы4О ходы 49 и 50 и входы 51 и 52.

Узел 12 сортировки информации представляет собой. устройство, осуществляющее сортировку приоритетов заданий, хранящихся в блоке 9 памя45 ти. Запись этой информации в блок 10 памяти происходит по следующему принципу: в первую ячейку записывается номер процессора, выполняющего задание с наименьшим приоритетом, и значение этого приоритета, В последующие ячейки записывается аналогичная информация в порядке возрастания приоритета выполняемого задания. Узел

12 выполнен по известной схеме. В этом случае блок 9 памяти должен быть реализован в виде К-разрядных регистров, выходы каждого из которых непосредственно соединены с соответствующими входами узла 12.

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

По входам 1 по мере выполнения принятых в обработку сигналов заданий поступают сигналы готовности про цессоров и записываются в соответствующие разряды регистра 5. В случае наличия запроса на выполнение задания код готовности процессоров через соответствующие элементы И первой группы 17 подается на входы элемента ИЛИ 24, при этом с инверсного вы" хода элемента ИЛИ 24 снимается единичный сигнал в том случае, если все процессоры заняты выполнением заданий. В противном случае единичный сигнал формируется на прямом выходе элемента HJIH 24.

Единичный сигнал с прямого выхода элемента ИЛИ 24 поступает на вход

45 блока 13 и переводит триггер 40 в единичное состояние. Тем самым разрешается прохождение тактовых импульсов с выхода генератора 39 через элемент И 41 на вход счетчика 42, находящегося в исходном состоянии в нуле. С выхода дешифратора 44 снимается код, причем единица форин руется лишь на одном из выходов дешифратора 44 в зависимости от сос-. тояния счетчика 42. Сигналы с выходов дешифратора 44 поступают на вход элементов И группы 18, на вторые входы которых поступают сигналы готовности процессоров с выходов группы 17 элементов И.

При совпадении сигнала готовности процессора с номером цикла просмотра (определяемого содержимым счетчика 42) сигналом совпадения, проходящим через соответствующий элемент

ИПИ 23 группы, производится считывание содержимого ячейки блока 11 памяти, в которой записаны номера заданий, которые могут выполняться .в данном процессоре. Эта информация поступает на первые входы схемы 28 сравнения, на вторые входы которой поступает номер входящего задания.

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

46 блока 13 управления и сбрасывает

06 з

145,34 триггер 40 в нулевое состояние, тем самым запрещая прохождение тактовых импульсов и обнуляя счетчик 42. Цикл поиска свободного процессора, способного выполнить входящее задание, закончен .

По единичному сигналу с выхода схемы 28 сравнения разрешается прохождение сигнала готовности процессо" 10 ра с выхода группы элементов KIH 23.

Тем самым единичный сигнал с выхода выбранного элемента И группы 19 разрешает прохождение номера входящего задания через группу 20 элементов И 15 и выдачу его в соответствующий процессор.

Одновременно код с выхода группы

19 элементов И поступает на вход шифратора 16, где преобразуется в двоич- 2р ный код номера выбранного процессора, что соотве тствует адресу ячейки памяти блока 9, для записи приоритета принятого в обработку задания. Значениее приоритета по ступ ае т на запись 25 в блок 9 памяти через блок элементов

И 21 при наличии единичного сигнала с выхода элемента ИЛИ 25. В рассматриваемом случае единичный сигнал на .выходе элемента ИЛИ 25 инициирован З0 единицей с прямого выхода элемента

ИЛИ 24.

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

В случае, если очередной процес". сор занят, устройство по очередному импульсу генератора 39 производит 4б анализ готовности следующего процессора.

Когда все процессоры просмотрены и задание не выдано ни одному из них, по очередному импульсу генерато- 5О ра 39 с последнего выхода 47 дешифратора единичный сигнал поступает на вход элемента ИЛИ 27, затем через элемент 34 задержки — на вход блока

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

Сигнал с выхода элемента ИЛИ 2? устанавливает в единичное состояние триггер 33. Тем самым разрешается прохождение тактовых импульсов с ге" нератора 32 через элемент И 3 1 на первый вход узла 12 сортировки информации. Входы регистров узла 12 сортировки непосредственно соединены с выходами каждой ячейки памяти блока 9 памяти. Таким образом, перед на.

1 чалом сортировки в регистрах узла 12 записана информация аналогичная ин1 формации, хранящейся в соответствующих ячейках блока 9. По первому импульсу генератора 32 производится анализ информации, записанной в первом ре гис тре узла 1 2, и о пределяе тся адрес записи этой информации в блок 10 памяти. По этому же импульсу генератора 32, задержанному на элементе 36 задержки, производится счи" тывание информации с выхода узла 12 и запись проанализированной информа ции в блок 10 в соответствии с определенным адресоМ.

После того. кск узел 12 сортиров" ки отработает, -: блок 10 памяти будет записан отсортированный массив информации, хранившийся в блоке 9.

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

В последующих ячейках памяти блока

10 информация записана в порядке возрастания приоритетов.

Элемент 35 рассчитывается, исходя из требования наличия единичного сигнала на выходе триггера 33 на время выдачи генератором 32 необходимого количества импульсов. Затем триггер 33 устанавливается в нуль.

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

В первом цикле просмотра с выхода

50 блока 14 управления (с выходов дешифратора) снимается код, содержащий единицу в первом разряде. По этому сигналу производится считывание информации из первой ячейки памяти блока 10 и сравнение считанной

1453406 информации о приоритете задания„имеющего наименьшее значение, с приоритетом входящего задания. Схема 29 сравнения производит сравнение этих кодов, и если приоритет входящего задания меньше значения приоритета,, считанного из блока 10, то по единичному сигналу, снимаемому с инверсного выхода схемы 29 сравнения через "-ле- 1О мент ИЛИ 26, выдается сигнал отказа устройства от выполнения входящего задания на выход 38.

В противном случае единичный сигнал с прямого выхода схемы 29 сравне- 16 ния разрешает прохождение информации о номере процессора, занятого обсчетом наименее приоритетного задания, через группу элементов И 22 на вход дешифратора 15, где осуществляется 2р преобразование кода номера процессора в код, содержащий единицу в соответствующем разряде. Далее этот код поступает на вторые входы элементов ИЛИ

23. Затем осуществляется анализ воз" 25 можности решения входящего задания на этом процессоре. В случае положительного исхода такой проверки единичный сигнал с выхода схемы 28 сравнения поступает на вход 52 и останав- Зп ливает работу блока 14 управления„

Одновременно разрешается выдача номера задания на выбранный процессор и производится запись в соответствующую R l H Ó блока 9 rl>» Tя приоритета принятого в обработку задания. При этом производится стирание приоритета задания, решаемого выбранным процессором до этого.

В случае, если входящее задание не 40 может быть выполнено на выбранном процессоре, блок управления осущест вляет считывание следующей ячейки памяти блока 10 и далее процесс повторяется по описанной схеме. 45

По сигналу с последнего выхода блока 14 управления производится сброс блока 14 управления аналогично блоку 13 и с выхода 49 снимается сигнал, который выдается .через эле- Вп мент HJIH 26 как сигнал отказа устройства от выполнения задания.

Запуск блока 14 управления может осуществляться и по единичному сигналу с выхода элемента И 30, формируе».мому при наличии запроса в случае, если свободных процессоров нет (единичный сигнал с инверсного выхода элемента ИЛИ 24).

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

Устройст "o для распределения заданий процессорам, содержащее три элемента ИЛИ,триггер, регистр готовности процессоров, группа информационных входов которого соединена с группой сигнальных входов устройства, первую и вторую группы элементов И, группу элементов ИЛИ,, первый блок управле-. ния, первую схему сравнения, регистр номера задания, первый блок управления содержит элемент И, триггер и генератор импульсов, причем выход триггера блока управления соединен с первым входом элемента И блока управления, второй вход которого соеди-. нен с выходом генератор=- импульсов блока управления, каждый выход ре" гистра готовности процессоров соединен с первым входом сднокменного элемента И первой группы, о т л к ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей эа счет распре,целенкя заданий процессором с учетом обеспечения приоритетной обработки входящих заданий,. оно соде ржи т регистр приор ите та за,цания, регистр адреса =.àïèñhl приоритета задания, блок памяти приоритетов заданий блок памяти упорядоченных приоритетов "-aäÿíèé. блек п.=.-,мяти номеров =,àöàíèé, узел сор-.. кровки информа.цкк, второй блок управдел:. я„ дешифратор, шифратор., третью, .е..— вертую, пятую группы элементов И два блока элементов И, четверть11 ::. элемент ИЛИ, вторую схему сравнения, первый и вто, ой элементы И,. генератор импульсов, трк элемента задержки. первый блок управления допслнктеэ."=-. но содержит элемент ИЛИ, счетчик и дешифратор. а второй блок управле †.-ия содержит генератор . пульсов, эле-. мент И, триггер, сче;- кк, деп:куратор H элемент AIM, rlpp fl ì 1 —,упп-:. формационных входов регистра приоритета задания является гр-тпой входов приоритета задания устройства, вторые входы элементов И первой группы соединены с запросным входом устрокства, выходы элементов И первой группы соединены с входами первого элемента ИЛИ к с первыми входами одноименных элементов И второй группы, вторые входы которых соединень1 с выходами дешифратора первого блока правления, кроме последнего выхода„ прямой выход первого элемента ИЛИ1453406 8 соединен с единичным входом триггера первого блока управления и с первым входом второго элемента ИЛИ, инверсный выход первого элемента ИЛИ соединен с первым входом первого элемента И, второй вход которого подключен к запросному входу устройства, выход первого элемента И соединен с первым входом третьего элемента ИЛИ, второй вход которого соединен с последним выходом дешифрато" ра первого блока управления, выход третьего элемента ИЛИ соединен с вхо" дом первого элемента задержки и с единичным входом триггера, выход которого соединен с первым входом второго элемента И и с входом второго элемента задержки, выход которого соединен с входом сброса триггера, второй вход второго элемента И соединен с выходом генератора импульсов, выход второго элемента И соединен с тактовым входом узла сортировки информации и с входом третьего элемен— та задержки, выход которого соединен с входом считывания узла сортировки информации, информационный вход которого соединен с выходом блока памяти приоритетов заданий, а информацион;ный и адресный выходы узла сортировки информации соединены соответственно с информационным и адресным входами блока памяти упорядоченных приоритетов заданий, во втором блоке управления выход генератора импульсов соединен с первьм входом элемента И, второй вход и выход которого соединены соответственно с выходом триггера и со счетным входом счетчика, выходы которого соединены с входами дешифратора второго блока управления, выход элемента ИЛИ второго блока управления соединен с входами сброса счетчика и триггера второго блока управления, входы считывания блока па мяти упорядоченных приоритетов заданий соединены с выходами дешифратора второго блока управления, кроме последнего выхода дешифратора, еди" ничный вход триггера второго блока управления соединен с выходом первого элемента задержки, первые входы элементов ИЛИ первого и второго блоков управления соединены с выходом первой схемы сравнения, первая группа входов которой соединена с выходами блока памяти номеров .заданий, адресные входы которого соединены с выходами

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

1О соответствующими выходами дешифратора, вход которого соединен с выходом первого блока элементов И, управляющий вход которого соединен с прямьи выходом второй схемы сравнения, инверсный выход которой соединен с первым входом четвертого элемента

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

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

Тех ред Л. Олийнык

Корректор М. Самборская

Редактор Н. Тупица

Заказ 7286/46 Тираж 667 Подписное

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

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

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

1453406 10 блока управ-. ройства, сигнальный выход которого

И четвертой соединен с выходом четвертого элеменвыходов уст- та ИЛИ.