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

ОПИСАНИЕИЗОВРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскияСоциалистическихРеспублик рн 959083(22) Заявлено 191280 (21)3234017/18-24 ИЧМ.Кл. С 06 Г 9/46 с присоединением заявки Йо Государственный комитет СССР по делам изобретений и открытийДата опубликования описания 150982 ы НИЙ(54) устРойст ПЕРЕДЕЛЕНИЯ Недляется оптимал решаемы нимума ста нев ьно эаЦель изобретения - расширение области применения устройства.Поставленная цель достигается тем, что устройство для распределения заданий., включающее группу схем сравне-. ния, первую, вторую группы блоков элементов И, первую, вторую группы ре-, гистров, причем первый выход каждого регистра первой группы соединен с первым входом соответствующего блока эле- ментов И первой группы, содержит третью, четвертую и пятую группы блоков элементов И, элемент И, три узла поиска максимального кода три группы элементов НЕ, группу элементов ИЛИ,; третью группу регистров и две группй элементов И-НЕ, причем второй выход каждого 1 го регистра (1.1 п) первой группы соединен с первым входом 1-го блока элементов И второй группьтт второй вход которого соединен с 1-мвыходом первого узла. поиска макси ного кода и с первым входом 1-го ка элементов И третьей группы, вт мальблоорой Изобретение относится к областн.вычислительной техники и,может быть, использовано в разработках аппаратного диспетчера при органиэации пакетной обработки в ЦВМ, а также в устройствах, предназначенных для ре, шения задач теории расписаний в спе" циализированных процессорах.10Известно устройство для распредЕ- ления заданий, содержащее матрицу ячеек памяти, блок анализа строк содержащий приемный регистр, узел опроса, регистр назначений, шифратФ, блок анализа столбов, содержащий приемный регистр, узел опроса, ре-: гистр назначений, шифратор, регистр, генератор, счетчик назначений, схему сравнения триггеры, элементы ИЛИ,.И и НЕ 1).Недостатком данного устройства является сложность и низкое быстро" действие при решении пакета задач в ЦВМ.Наиболее близким к предлагаемому 25 является устройство для распределе.ния заданий, содержащее по.числу заданий в пакете первую и вторую группы регистров, первую и вторую группу вентилей, группу схем сравнения 1 23. 30 тком данного устройства озможность осуществлени го распределения пакета задач в ЦВМ по критерию ммарного времени их реал35 вход которого соединен с выходом 1-го регистра второй группы, второй выход которого соединен с первым входом 1-го блока элементов И третьей группы, второй вход которого соединен с выходом 1-го элемента НЕ первой 5 группы и с первым входом 1-го элемента И-НЕ первой группы, вйход которого соединен с управляющими входамих регистров первой и второй групп выход каждого 1-го блока элементов И 1 О второй и третьей группы соединен соответственно с первым и вторым входами 1-й схемы сравнения группы, выход которой через 1-й элемент НЕ второй группы соединен с первым входом 1-го элемента И-НЕ второй группы и с входом 1-го элемента НЕ первой группы, второй вход каждого 1-го элемента И-НЕ второй группы соединен с 1-м выходом второго узла поиска максимальногг кода, входы которого соединены .соответственно со вторыми входами схем сравнения группы, выходы 1-х элементов И-НЕ второй группы соединейы со вторыми входами 1-х элементов И-НЕ первой группы и с первыми входами элементов ИЛИ группы, выходы которых являются информационными выходами устройства, вход считывания устройства соединен со вторыми входами каждого 1-го блока элементов И пер вой группы, выходы которых соединены с 1-ми входами первого узла поиска максимального кода, выход которого соединен с входами элемента И, выход которого соединен с первыми входами блоков элементов И пятой группы, вторые входы которых соединены с выходами соответствующих регистров третьей группы, первый, второй входы каждого 1-го регистра третьей 40 группы соединены соответственно с выходом 1-го блока элементов И чет" вертой группы и с 1-м выходом третьего узла поиска максимального кода, второй вход кажцого 1-го элемента ИЛИ группы через 1-й элемент. НЕ третьей группы соединен с 1-м выходом третьего узла поиска максимального кода, третий вход каждого блока элементов И пятой группы соединен с тактовым входом устройства, выход каждого -го блока элементов И пятой группы соединен с 1 -м входом третьего узла поиска максимального кода.На фиг. 1 представлена структурная схема устройства, на фиг. 2 - структурная схема узла поиска максимального кода.Схема устройства содержит узел 1. поиска максимального кода, группы блоков 2 элементов И, группы региат ров 3, .4,группы блоков 5 элементов И, группу блоков 6 элементов И,группу схем 7 сравнения, группу элементов НЕ 8, узел 9 поиска максимального кода, группы элементов И-НЕ 10, 11,группу элементов НЕ 12, группу элементов И 13, группу регистров 14, элемент И 15, группу блоков 16 элементов И, узел 17 поиска максимальногокода, группу элементов НЕ 18, группуэлементов ИЛИ 19, вход 20 считывания устройства, тактовый вход 21 устройства, информационные выходы 22устройства.Узел 1 содержит группу элементовИЛИ-НЕ 23, группы 24 элементов И-ИЛИ25, содержащие элементы ИЛИ 26 и элементы И 27 (на фиг. 2 обозначенывыходы 28 и входы 29),Схемы сравнения 7, входящие в устройстуо, выполнены аналогично узлампоиска максимального кода, но на двегруппы входов,Сущность изобретения состоит втом, что устройство располагает задания в пакете в соответствии с временем ввода и суммой времени решениязадачи и времени вывода в соответствии с алгоритмом Джонсона,Устройство работает следующим образом.В исходном состоянии на группурегистров 3 заносятся коды, пропорциональные времени ввода решаемых задач.На группу регистров 4 заносятсякоды, пропорциональные сумме временирешения задачи и вывода результатов.решения. После занесения инФормациина регистры первой группы 3 подаетсяуправляющий сигнал по шине 20 на входпервой группы блоков элементов 4 иустройство начинает свою работу повыбору очередной задачи из пакета.На узел 1 подаются коды с инверсных выходов регистров 3; т.е. информация на узел 1 подается в обратномкоде, поэтому в узле 1 выбираетсяминимальное число из кодов, занесенных в регистры 3 (выбирается одинили несколько кодов, если имеютсясреди них равные),Если минимальный код один, то сузла 1 на соответствующийблок элементов И 5 и 6 поступает высокий потенциал, благодаря чему коды с прямых выходов регистров 3 и 4 черезблоки 5 и 6 поступают на соответствующую схему сравнения 7, где происходит сравнение кодов времени вводаи решение одной задачи.Если. время решения оказалось больше времени "ввода, то на выходе схемы7 - низкий потенциал, который поступает на элемент НЕ 8, где инвертиру-.ется, и высокий потенциал поступаетна соответствующий элемент И-НЕ 10.Одновременно код с регистра 4 подается на узел 9. Иэ поступивших кодоввыбирается максимальный, а так как1поступил только один код, то он явля.ется максимальным и высокий потенциал с выхода узла 9 поступает на элемент И-НЕ 10.На выходе элемента И-НЕ 10 появляется низкий потенциал, что указавает на позиционный номер очередного выбранного задания. Такое же состояние на выходе элемента ИЛИ 19, Далее нызкий потенциал с элемента И-НЕ 10 поступает на вход соответствующего элемента И-НЕ 11.С выхода элемента НЕ 8 высокий потенциал поступает на элемент НЕ 12, с выхода которого низкий потенциал поступает на вход соответствующего элемента И-НЕ 11, что соответствует записи в регистры 3 и 4 единичного кода.Если максимальных кодов несколько, то с выхода узла 1 на соответствую" щие блоки элементов И 5 и 6 поступают высокие потенциалы. Пусть, например, высокий потенциал поступает на вентили 51, 6 к , 5 к Нк 5 км6+ (к = 1,2, ) . С регистров Зх4 к 3 к 4 к+4 к+ информация поступает соответственно на схемы сравнения 7 к-71 С 7 к, где происходят сравнения двух кодов.Пусть код времени ввода в регистре Зк,- больше кода времени решения в регистре 4.Тогда высокий потенциал поступает на вход элемента НЕ 8 , выход которого подключен ко входу элемента НЕ 12 к. Если на схему 9 поступают три кода с блоков 6 к , 6 к, бк+, то из них выбирается максимальный. Допустим, что код, поступивший с выхода 6 к, минимален. Тогда элемент 11переводит регистры 3и 4 кв единичное состояние. На первый вход элемента ИЛИ 19 к 1 поступает высокий потенциал, таким образом, на выходе устройства на (к)-м эле" менте высокий потенциал, а для указания выбора задания в пакете служит . низкий.Пусть кода, пропорциональные времени ввода, занесенные в регистры 3, 3 , меньше кодов, пропорцио" нальнйх времени решения, занесенным соответственно в регистры 4 к и 4, а код,занесенный в регистр 4 к,меньше кода, занесенного в регистр 4 к.. Тогда информация поступает на входы схем 7, 7 к+ . Низкие потенциалы выходов схем 7 к и 7 ки поступа"ют, соответственно на вход элемента ЙЕ 8 к . и 8 ц+, где инвертируются и далее подаются на входы элементов 10 к и 10 х+1. Одновременно на вход схемы 9 поступают коды с блоков бкю бк, бк. все изменения, происшедшие с кодом к-го номера,описаны, но на узел 9 (к)-Й код поступает одновременно с к-м и (к)-м кодами. Узел 9 выбирает максималь" ный код с номером к+1 и высокий потенциал с выхода схемы 9 поступает на второй вход элемента 10 к. Таким образом, низкий потенциал, которыйпоявляется на выходе 10 к , указывает на позиционный номер очередноговыбранного задания, так как на выходе элемента 22 к+ устройства будет такой же сигнал. Одновременно низкийпотенциал с выхода элемента 10, переводит регистры 3+ и 4 в единич" ное состояние. Одновременно с выхода узла 9 на элемент И-НЕ 10 поступает низкий 10 .потенциал, который образует на выхо де элемента 10 ц. высокий потенциал,поступающий на элемент ИЛИ 19. С выхода элемента 8 высокий потенциалподается на элемент НЕ 12 к, где инвертируется, информация, занесеннаяв регистры Зк и 4 , не.изменяется,15 а на выходе 22 - высокий потенциал,Одновременно, перед переведением,регистров 3 и 4 кв единичное сос 20 тояние, высоким уровнем потенциала,поступающего с выхода элемента НЕ 12 1, открывае"гся блок 13 ки информация с регистра 4заносится на регистр 14 . Затем блок 13зар 5 пирается.Если в рассмотренном случае окажется, что коды, занесенные в регистры 4 к и 4 +, равны,:то выбор очередного задания осуществляется в по" З 0 рядке поступления, Сначала выбирает"ся к-е задание и затем (к+1)"е заданиеПосле выбора очередного задания шаг выборки заканчивается. Для продолжения работы необходимо снова подать импульс на вход 20.Когда все задания в пакете пересмотрены и выбраны те, у которых время ввода меньше времени решения,первый цикл (цикл определения наибо. лее приоритетных для ЦВМ заданий)40 заканчивается. После первого цикла подается следующий сигнал по входу 20 и устройство снова переходит в рабочее состояние. На выходе узла 1 после прихода, 45 импульса на вход 20 образуются высокие потенциалы во всех .выходах, так как все коды, записанные в регистрах3 после первого цикла, максимальны(единичные кода). Открывается элемент 50 И 15, и высокий потенциал поступает на группы блоков 16 По приходу синхрониэирующего сиг",нала на вход 21 продолжается дальнейшая выборка очередных заданий.С выходов регистров 14 через блоки 16 информация поступает на узел17. Из всех кодов, пропорциональныхвремени решений, поступивших с реги,стров 14, выбирается максимальный, 6 ф и высокий потенциал поступает на вход соответствующего элемента НЕ 18,где инвертируется и определяет позиционный .номер очередного выбранногозадания, а на выходе 22 - низкий п тенциал.5 О Формула изобретения 15 20 Одновременно высокий потенциал свыхода узла 17 поступает на регистр14 и сбрасывает его в нулевые состояния. Низкие потенциалы с выходовузла 17 поступают на те регистры,которым они соответствуют, и оставляют их состояния без изменений. Схема переводится в рабочее состояние путем подачи нового синхронизирующего импульса по входу 21 и таким образом начинается следующий шаг"выборки.Если имеется несколько максимальных кодов, то выбор очередного задания пройзводится в порядке поступле ния. Устройство заканчивает свою работу после выбора всех заданий, присутствующих в пакете,Работу предлагаемого устройства рассмотрим на конкретном примере. .Пусть информацияо пакете решаемых задач задана следующей (с - время ввода, 1 - суммарное. время решения и вывода результата решения задачи):9 задачив пакете1 2 3 4 5 б 7 8И 3 3 4 6 7 3 4 43 5 2 2 3 7 2 2В исходном состоянии время с; занесено и хранится на регистрах 3, а время ф - на регистрах 4.После подачиуправляющего сигнала на вход 20 коды с инверсных выходов регистров 3 через открытые блоки 2. поступают на узел 1, где производится выбор заданий с номерами 1, 2 и 6. Одновременно коды с регистров 3 поступают на соответствующие блоки 5, но:проходят только 5., 5 а и 5 ь блоки.Коды с регистров 4 поступают на первые входы группы блоков б, на вторые входы которых поступают управляющие сигналы с соответствующих выходов узла 1. Только с выходов открытых блоков 5 и 61, 5 ч и б, 5 и бб кода поступают на схемы сравнения 71,7 и 74. соответственно, а нулевой сигнал появляЬтся на выходах схем 7 и 76.Одновременно через блоки 6, ба и бб коды срегистров 4, 4. и 4 поступают на узел 9, иа. б"мвыходе которогопоявляется высокий потенциал, который поступает на первый вход элемента 10 ь, поступает такыре высокий потенциал с выхода элемента НЕ 8. Поэтому на выходе элемента 22 б появляется низкий цотенциая, что свиде- . ,тельствует о назначении в первую очередь для реализации в ЦВИ б-й задачи, и так далее.В результате устройство для распределения заданий преобразует исходные данные последовательности заданий в следующие: Р задачив пакете 1 2 3 4 5 6 7 82 3 7 3 4 6 4 4 7 5 3 3 2 2 2 2Применение изобретения позволяет расширить область применения устройства за счет применения его там,где требуется оптимизировать пакеты заданий в соответствии с алгоритмом Джонсона. Усаройство для распределения заданий, содержащее группу схем сравнения, первую и вторую группы блоков элементов И, первую и вторую группы регистров, причем первый выход каждого регистра первой группы соединен с первым входом соответствующего блока элементов И первой группы, о т л и - ч а ю щ е е с я тем, что, с целью расширения области применения устройства, оно содержит третью, четвертуюи пятую группы блоков элементов И,элемент И, три узла поиска максимального кода, три группы элементов НЕ,группу элементов ИЛИ, третью группурегистров и две группы элементов ИВЕ, причем второй выход каждого 1-го(1 = 1,п) регистра первой группысоединен с первым входом 1-го блокаэлементов И второй группы, второйвход которого соединен с 1-м выходомпервого узла поиска максимальногокода и с первым входом 1 го блокаэлементов И третьей группы, второйвход которого соединен с выходом1-го регистра второй группы, второй 46 выход которого соединен с первым входом 1-го блока элементов И третьейгруппы, второй вход которого соединен с выходом 1-го элемента НЕ первой группы и с первым входом 1-го 45 элемента И-НЕ первой группы, выходкоторого соединен с управЛяющими входами 1-х регистров первой и второйгрупп, выход каждого 1-го блокаэлементов И второй и третьей групп 5 О соединен соответственно с первыми вторым входами 1-й схемы сравнениягруппы, выход которой через 1-й элемент. НЕ второй группы соединен с пер. выМ входом 1-го элемента И-НЕ второйгруппы и с входом 1-го элемента НЕ.первой группы, второй вход каждого1-го элемента И-НЕ второй группысоединен с 1-м выходом второго узлапоиска максимального кода, входыкоторого соединены соответственно совторыми входами схем сравнения группы, выходы 1-х элементов И-НЕ второй.группы соединены со вторыми входами.1-х элементов Й-НЕ первой группы ис первыми входами элементов ИЛИ груп пы, выходы которых являются информационными выходами устройства, вход считывания устройства соединен со вторыми входами каждого 1-го блока элементов И первой группы, выходы которых соединены с 1-ми входами первого узла поиска максимального кода, выход которого соединен с входами элемента И, выход которого соединен с первыми входами блоков элементов И пятой группы, вторые входы которых соединены с выходами соответствующих регистров третьей группы, первый,вто. рой входы каждого 1-го регистра третьей группы соединены соответственно с выходом 1-го блока элементов И четвертой группы и с 1-м выходом третьего узла поиска максимального кода, второй вход каждого 1-го элемента ИЛИ группы через 1-Й эле"мент НЕ третьей группы соединен с1-м выходом третьегоузла поиска максимального кода, третий вход каждогоблока элементов И пятой группы соедннен с тактовым входом устройства,выход каждого 1-го блока элемента Ипятой группы соединен с 1-м входомтретьего узла поиска максимальногокода.оИсточники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРР 696471, кл. 6 06 Г 15/20, 1979.2. Авторское свидетельство СССРР 339916, кл. 6 06 Г 9/46, 1972959083 г Составитель М.Кудряшоведактор О.Колесникова Техред 3.Палий Корректор А.Гриценк ПодписноеСССР Вака ет ыт б