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

j;

СП

00 4

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

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

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

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

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

непосредственно соединены с соответ- ствуюпдими входами узла 12.

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

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

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

При совпадении сигнала готовности процессора с номером цикла просмотра (определяемого содержимым счетчика 42) сигналом совпадения, проходящим через соответствующий элемент ИЛИ 23 группы, производится считывание содержимого ячейки блока 11 памяти, в которой записаны номера заданий, которые могут выполняться в данном процессоре. Эта информация поступает на первые входы схемы 28 сравнения, на вторые входы которой поступает номер входящего задания. В случае, если номер входящего задания совпадает с одним из номеров списка заданий, которые согут решаться в процессоре, на выходе схемы 28 сравнения формируется единичный сигнал, который поступает на вход 46 блока 13 управления и сбрасывает

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

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

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

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

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

Когда все процессоры просмотрены и задание не вьщано ни одному из них. По очередному импульсу генератора 39 с последнего выхода 47 дешифра- тора единичный сигнал поступает на вход элемента ШМ 27, затем через элемент 34 задержки - на вход блока

14 управления, который работает ана- gg дешифратора) снимается код, содержа- логично блоку 13 управления. Этим на- щий единицу в первом разряде. По

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

,

0

о

меньшим приоритетом, чем входящее задание .

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

5 записана информация аналогичная информации, хранящейся в соответствующих ячейках блока 9. По первому импульсу генератора 32 производится анализ информации, записанной в первом регистре узла 12, и определяется ;1дрес записи этой информации в блок 10 памяти.. По этому же импульсу генератора 32, задержанному на элементе 36 задержки, производится счи5 ывание информации с выхода узла 12 ; и запись проанализированной информа-t ции в блок 10 в соответствии с определенным адресо|4.: После того. Kaic узел 12 сортиров0 ки отработает, Б блок 10 памяти будет записан отсортированный массив информации, хранившийся в блоке 9. При этом в первой ячейке блока 10 будет записан номер процессора, выполняющего задание с наименьшим приоритетом, и номер этого приоритета. В последующих ячейках памяти блока 10 информация записана в порядке возрастания приоритетов.

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

5

5

50

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

В первом цикле просмотра с выхода 50 блока 14 управления (с выходов

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

из них, которые выполняют задания с

мяти блока 10 и сравнение считанной

1453406

i-шформации о приоритете задания, име- Формула ющего наименьшее значение, с приоритетом входящего задания. Схема 29 сравнения производит сравнение этих кодов, и если приоритет входящег о задания меньше значения приоритета,, считанного из блока 10, то по единичному сигнапу, снимаемому с инверсного выхода схемы 29 сравнения через элемент ШШ 26, выдается сигнал отказа устройства от выполнения входящего задания на выход 38.

В противном случае единичньй сигизобретения5 стройство для распределения заданий процессорам,содержащее три элемен- 5 та ИЛИ,триггер,регистр готовности процессоров, группа информационных входов которого соединена с группой сигнальных входов устройства, первую и вторую группы элементов И, группу 10 элементов ИЛИ, первый блок управления, первую сравнения, регистр номера задания, первый блок управления содержит элемент И, три-гер и

нал с прямого вьпсода схемы 29 ср;в не- ,5 тоигг ер ГбГ ния разрешает прохождение информации ервьГвхоло Р с

о номере процессора, занятого обсче- ° ° элемента И блока уп

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

23, Затем осуществляется анализ воз- 25 за СЧРТ ..

можности решения входящего заданияпессопом г Г

на этом процессоре. В случае положи-ритетной о5п Г «°тельного исхода такой проверки еди-оно гоГ входящих заданий,

ничньш сигнал с выхода схемь 28 срав- цания . Риоритета за- нения поступает на вход 52 и останав- зо тета °- ливает работу блока 14 управления,.тон за п йг ™ ириориге-.

одновременно разрешается номе- .

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

ра задания на выбранньш процессор и производится запись в соответствуюмяти номеров заданий, узел сорт-иооё.У. ячейку блока 9 памяти-приор;;;та ,, принятого в Обработку задания. Привертун,, пя;ую группы ;РМ™ И

этом производится стирание приорите- два блокя -, м°

та задания, решаемого выбранньн. про- элемент ОТИ вертый.

цессором до этогоэлемент ИЛИ, вторую схему сравнения,

первьи и второй элементы И., rehepaВ случае, если входящее задание не 40 тор импульсов, три элемента -чапеш-кч может быть выполнено на выбранномпервый блок управления дополните --

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

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

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

но содержит элемент ИЛИ, счетчик и дешифратор, а второй блок управления содержит генератор з- пульсов, эле- 45 мент И, триггер, счетчик, дегпифра- тор и элемент ИПИ., причем групп ; информационных входов регистра приоритета задания является группой входер приоритета задан1.1Я устройства, вто- 50 Рые входы эламентоз И т.:ервой гр;дтпы соединены с запросным входом устройства, выходы элементов И первой группы соединены с входами первого эле™ .мента ИЛИ и с первьпуи входами одно- 55 именных элементов И второй группы, вторые входы которьк соединены с выходами дешифратора первого блока уп- равления кроме последнего выхода,, прямой выход первого элемента ИЛИ ° ° элемента И блока уп

за СЧРТ ..

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

40 тор импульсов, три элемента -чапеш-кч первый блок управления дополните --

но содержит элемент ИЛИ, счетчик и дешифратор, а второй блок управления содержит генератор з- пульсов, эле- 45 мент И, триггер, счетчик, дегпифра- тор и элемент ИПИ., причем групп ; информационных входов регистра приоритета задания является группой входер приоритета задан1.1Я устройства, вто- 0 Рые входы эламентоз И т.:ервой гр;дтпы соединены с запросным входом устройства, выходы элементов И первой группы соединены с входами первого эле™ .мента ИЛИ и с первьпуи входами одно- 5 именных элементов И второй группы, вторые входы которьк соединены с выходами дешифратора первого блока уп- равления кроме последнего выхода,, прямой выход первого элемента ИЛИ соединен с единичным входом триггера первого блока управления и с пер- вьм входом второго элемента ИЛИ, инверсный выход первого элемента ИЛИ соединен с первым входом первого элемента И, второй вход которого подключен к запросному входу устройства, выход первого элемента И соединен с первым входом третьего элемен- та ИЛИ, второй вход которого соединен с последним выходом дешифратора первого блока управления, выход третьего элемента ИЛИ соединен с входом первого элемента задержки и с единичным входом триггера, выход которого соединен с первым входом второго элемента И и с входом второго элемента задержки, выход которого соединен с входом сброса триггера, второй вход второго элемента И соединен с выходом генератора импульсов, выход второго элемента И соединен с тактовьм входом узла сортировки информации и с входом третьего элемен- та задержки, вькод которого соединен с входом считывания узла сортировки информации, инфор«1ационный вход которого соединен с выходом блока памяти приоритетов заданий, а информацион- ;ный и адресный выходы узла сортировки информации соединены соответственно с информационным и адресным входами блока памяти упорядоченных приоритетов заданий, во втором блоке уп- равления выход генератора импульсов соединен с первьм входом элемента И, второй вход и выход которого соединены соответственно с выходом триггера и со счетным входом счетчика, вы- ходы которого соединены с входами дешифратора второго блока управления, выход элемента ИЛИ второго блока управления соединен с входами сброса счетчика и триггера второго блока уп- равления, входы считывания блока пак мяти упорядоченных приоритетов заданий соединены с выходами дешифратора второго блока управления, кроме последнего выхода дешифратора, еди- ничный вход триггера второго блока управления соединен с выходом первого элемента задержки, первые входы элементов ИЛИ первого и второго блоков управления соединены с выходом первой схемы сравнения, первая группа входов которой соединена с выходами блока памяти номеров -заданий, адресные входы которого соединены с выходами

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

ходом элемента И своего блока управ-ройства,сигнальный выход которого

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