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

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении многопроцессорных вычислительных систем5Цель изобретения " расширение функциональных возможностей за счет распределения заданий процессорам с учетом обеспечения приоритетной обработки входящих заданий.На чертеже приведена структурная схема устройства.Устройство содержит группу сигнальных входов 1 устройства, группу входов 2 приоритета задания устройства, группу входов 3 номера задания устройства, запросный вход 4 устройства, регистр 5 готовности процессоров, регистр 6 приоритета задания, регистр 7 номера задания, регистр 8 20 адреса записи приоритета задания, блок 9 памяти приоритетов заданий, блок 10 памяти упорядоченных приори" тетов заданий, блок 11 памяти номеров заданий, узел 12 сортировки ин формации, блоки 13 и 14 управления, дешифратор 15, шифратор 16, группы 1-20 элементов И, блоки элементов И 21 и 22, группы элементов ИЛИ 23, элементы ИЛИ 24-27, схемы 28 и 29 сравнения, элементы И 30 и 31, гене" ратор 32 импульсов, триггер 33, элементы 34-36 задержки, блок 37 элементов задержки, сигнальный выход 38 устройства. Блок 13 содержит генератор 39 импульсов, триггер 40 элемент35 И 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 снимается единичный сигнал в том случае, есливсе процессоры заняты выполнениемзаданий. В противном случае единичный сигнал формируется на прямом выходе элемента ИЛИ 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ра с выхода группы элементов ИПИ 23.Тем самым единичный сигнал с выходавыбранного элемента И группы 19 разрешает прохождение номера входящегозадания через группу 20 элементов И 15и выдачу его в соответствующий процессор.Одновременно код с выхода группы19 элементов И поступает на вход шифратора 16, где преобразуется в двоич ный код номера выбранного процессора, что соответствует адресу ячейкипамяти блока 9, для записи приоритетапринятого в обработку задания. Значение приоритета поступает на запись 25в блок 9 памяти через блок элементовИ 21 при наличии единичного сигналас выхода элемента ИЛИ 25, В рассматриваемом случае единичный сигнал навыходе элемента ИЛИ 25 инициирован 30единицей с прямого выхода элементаИЛИ 24.При наличии нулевого сигнала с выхода схемы 28 сравнения сброс триггера 40 не производится и по очередному импульсу генератора 39 производится проверка готовности следующего процессора, В случае его готовности производится сравнение номе-,ров заданий, которые могут выполняться данным процессором, с номером входящего задания.В случае, если очередной процес".сор занят, устройство по очередномуимпульсу генератора 39 производит 4 банализ готовности следующего процессора.Когда все процессоры просмотреныи задание не выдано ни одному изних, по очередному импульсу генерато- бора 39 с последнего выхода 47 дешифратора единичный сигнал поступает навход элемента ИЛИ 27, затем черезэлемент 34 задержки - на вход блока14 управления, который работает аналогично блоку 13 управления, Этим начинается процесс просмотра занятыхпроцессоров с целью определения техиз них, которые выполняют задания с меньшим приоритетом, чем входящее задание.Сигнал с выхода элемента ИЛИ 27 устанавливает в единичное состояние триггер 33. Тем самым разрешается прохождение тактовых импульсов с ге" нератора 32 через элемент И 3 1 на первый вход узла 12 сортировки информации. Входы регистров узла 12 сортировки непосредственно соединены с выходами каждой ячейки памяти блока 9 памяти. Таким образом, перед на.1чалом сортировки в регистрах узла 12 записана информация аналогичная информации, хранящейся в соответствующих ячейках блока 9. По первому импульсу генератора 32 производится анализ информации, записанной в первом регистре узла 12, и определяется адрес записи этой информации в блок 10 памяти. По этому же импульсу генератора 32, задержанному на элементе 36 задержки, производится счи" тывание информации с выхода узла 12 и запись проанализированной информа-; ции в блок 10 в соответствии с определенным адресоМ.После того. кск узел 12 сортиров" ки отработает, . блок 10 памяти будет записан отсортированный массив информации, хранившийся в блоке 9. При этом в первой ячейке блока 10 будет записан номер процессора, выполняющего задание с наименьшим приоритетом, и номер этого приоритета, В последующих ячейках памяти блока 10 информация записана в порядке возрастания приоритетов.Элемент 35 рассчитывается, исходя из требования наличия единичного сигнала на выходе триггера 33 на время выдачи генератором 32 необходимого количества импульсов, Затем триггер 33 устанавливается в нуль. Сигнал запуска блока 14 управления поступает с выхода элемента ИЛИ 27 через элемент 34, который предназначен для задержки распространения сигнала на время сортировки информации.В первом цикле просмотра с выхода 50 блока 14 управления (с выходов дешифратора) снимается код, содержащий единицу в первом разряде. По этому сигналу производится считывание информации из первой ячейки памяти блока 10 и сравнение считанной406 5 1453информации о приоритете заданияимеющего наименьшее значение, с приоритетом входящего задания, Схема 29сравнения производит сравнение этих5кодов, и если приоритет входящего задания меньше значения приоритетасчитанного из блока 10, то па единичному сигналу, снимаемому с инверсноговыхода схемы 29 сравнения через элемент ИЛИ 26, выдается сигнал отказаустройства от выполнения входящегозадания на выход 38,В противном случае единичный сигнал с прямого выхода схемы 29 сравне бния разрешает прохождение информациио номере процессора, занятого обсчетом наименее приоритетного задания,через группу элементов И 22 на входдешифратора 15, где осуществляется 20преобразование кода номера процессорав код, содержащий единицу в соответствующем разряде. Далее этот код поступает на вторые входы элементов ИЛИ23. Затем осуществляется анализ воз" 25можности решения входящего заданияна этом процессоре. В случае положительного исхода такой проверки единичный сигнал с выхода схемы 28 сравнения поступает на вход 52 и останав- ЗОливает работу блока 14 управленияОдновременно разрешается выдача номера задания на выбранный процессор ипроизводится запись в соответствующую ячейку блока 9 памяти приоритета35принятого в обработку задания. Приэтом производится стирание приоритета задания, решаемого выбранным процессором до этого. В случае, если входящее задание не 40 может быть выполнено на выбранном процессоре, блок управления осущест вляет считывание следующей ячейки памяти блока 10 и далее процесс повторяется по описанной схеме. 45По сигналу с последнего выхода блока 14 управления производится сброс блока 14 управления аналогич" но блоку 13 и с выхода 49 снимается сигнал, который выдается, через эле- ВО мент ИЛИ 26 как сигнал отказа устройства от выполнения зацания.Запуск блока 14 управления может осуществляться и по единичному сигналу с выхода элемента И 30, формируе . мому при наличии запроса в случае, если свободных процессоров нет (единичный сигнал с инверсного выхода элемента ИЛИ 24). Формула изобретенияустройства для распределения заданий процессорам, содержащее три элемента ИЛИ,триггер, регистр готовности процессоров,группа информационных входов которого соединена с группой сигнальных входов устройства, первую и вторую группы элементов И, группу элементов ИЛИ первый блок управления, первую схему сравнения, регистр номера задания, первый блок управления содержит элемент И, триггер и генератор импульсов, причем выход триггера блока управления соединен с первым входом элемента И блока управления, второй вход которого соединен с выходам генератор- импульсов блока управления, каждый выход ре" гистра готовности процессоров соединен с первым входам одноименного элемента И первой группы, а т л; ч а ю щ е е с я тем, чта, с целью гасширения функциональных возможностей за счет распре,целения заданий процессором с учетом обеспечения приоритетной обработки входящих заданий оно содержит регистр приаритата за,цания, регистр адреса записи приоритета задания, блок памяти приоритетов заданий, блок памяти упорядоченных приоритетов заданий, блок и,-. ,мяти номеров заданий, узел сортировки информации, второй блок управления дешифратор, шифратор третью, ч,"; - вертую пя тую групп 1", элемент ав И два блока элементов И, четверты 1.элемент ИЛИ, вторую схему сравнения, первый и вт., ой элементы И,. генератор импульсов, три элемента задержки, первый блок управления дапалнитег.ь" но содержит элемент ИЛИ, счетчик и дешифратор. а второй блок управления содержит генератор мпульсав элемент И, триггер, сче мк, деп:ииратар и элемент ИЛИ, причем г-,упт.- информационных входов рег 1 стра приоритата задания является гр выпай входаприоритета задания устройства, вторые входы элементов И первой группы соединены с запросным входам устроиства, выходы элементов И первой группы соединены с входами первого элемента ИЛИ и с первыми входами одноименных элементов И второй группы, вторые входы ксторых соединены с выходами дешифратара первого блока управления, кроме последнего выхода прямой выход первого элемента ИЛИ .соединен с единичным входом триггера первого блока управления и с первым входом второго элемента ИЛИ, инверсный выход первого элемента ИЛИсоединен с первым входом первого.элемента И, второй вход которогоподключен к запросному входу устройства, выход первого элемента И соединен с первым входом третьего элемента ИЛИ, второй вход которого соединен с последним выходом дешифрато"ра первого блока управления, выходтретьего элемента ИЛИ соединен с вхо"дом первого элемента задержки и сединичным входом триггера, выход которого соединен с первым входом второго элемента И и с входом второгоэлемента задержки, выход которогосоединен с входом сброса триггера,второй вход второго элемента И соединен с выходом генератора импульсов,выход второго элемента И соединен стактовым входом узла сортировки информации и с входом третьего элемен -та задержки, выход которого соединенс входом считывания узла сортировкиинформации, информационный вход которого соединен с выходом блока памятиприоритетов заданий, а информацион,ный и адресный выходы узла сортировки информации соединены соответственно с информационным и адресным входами блока памяти упорядоченных приоритетов заданий, во втором блоке управления выход генератора импульсовсоединен с первьм входом элемента И,второй вход и выход которого соединены соответственно с выходом триггера и со счетным входом счетчика, выходы которого соединены с входамидешифратора второго блока управления,выход элемента ИЛИ второго блока управления соединен с входами сбросасчетчика и триггера второго блока управления, входы считывания блока памяти упорядоченных приоритетов заданий соединены с выходами дешифратора второго блока управления, кромепоследнего выхода дешифратора, еди"ничный вход триггера второго блокауправления соединен с выходом первогоэлемента задержки, первые входы элементов ИЛИ первого и второго блоковуправления соединены с выходом первойсхемы сравнения, первая группа входовкоторой соединена с выходами блокапамяти номеров заданий, адресные входы которого соединены с выходами элементов ИЛИ группы и с первыми входами элементов И третьей группы,вторые входы которых соединены с выходом первой схемы сравнения перУвые входы элементов ИЛИ группы соединены с выходами одноименных элементов И второй группы, вторые входы элементов ИЛИ группы соединены с 1 О соответствующими выходами дешифратора, вход которого соединен с выходом первого блока элементов И, управляющий вход которого соединен с прямьи выходом второй схемы сравнения, 15 инверсный выход которой соединен спервым входом четвертого элементаИПИ, второй вход которого соединен споследним выходом дешифратора второго блока управления, выходы блока па О мяти упорядоченных приоритетов заданий соединены с первой групной входов второй схемы сравнения и черезблок элементов задержки с инюрмационными входами первого блока элемен тов И, информационные входы блока па"мяти приоритетов соединены с выходами второго блока элементов И, управляющий вход которого соединен с выходом второго элемента ИЛИ, инфорЗо мационные входы второго блока элементов И соединены с выходами регистра приоритета задания и второйгруппой входов второй схемы сравнения, прямой выход которой соединенс вторым входом второго элемента ИЛИ,адресные входы блока памяти приоритетов соединены,с выходами регистраадреса записи приоритета задания,входы которого соединены с выходами о шифратора, входы которого соединеныс выходами элементов И третьей группы и с первыми входами одноименныхэлементов И четвертой группы, вторыевходы которых соединены с одноименны ми выходами регистра номера заданияи с второй группой входов первой схемы сравнения, группа входов регистра номера задания является группой входов номера задания устройства, последние выходы дешифраторов первого и второго блоков управления соединены с вторыми входами элементовИЛИ своих блоков управления, выход элемента ИЛИ каждого блока управления соединен с входом сброса счетчи" ка своего блока управления и с входом сброса триггера своего блока управления, счетный вход счетчика каждого блока управления соединен с выСоставитель М. Кудряшеедактор Н, Тупица Тех ред Л. Олийнык мборская оррект аказ 7286/46 Тираж 667 ПодписноеНИИПИ Государственного комитета по изобретениям и открытиям при ГКН113035, Москва, Ж, Раушская наб д. 4/5 Ужгород, ул. Проектная, 4 Производственно-полиграфическое предприяти ходом элемента И своего ления, выходы элементов группы являн 1 тся группой 1453406 1 Облока управ- ройства, сигнальный выход которого И четвертой соединен с выходом четвертого элеменвыходов уст- та ИЛИ,