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

Изобретение относится к вычислительной технике и может быть использонано н качестве диспетчера для выбора заданий на решенИе в системе обработки данных.Целью изобретения является расширение класса решаемых задач за счет возможности выбора заданий по рангам в зависимости от значений критериальных функций с учетом ограниченного ресурса.На фиг,1 представлена структурная схема устройства для распределения заданий; на фиг,2 - структурная схема блока выбора максимального кода; на фиг.З - структурная схема блока приоритетов.Устройство содержит матрицу 1 топологии орграфа из пп триггеров 2, группу элементов ИЛИ-НЕ 3, группу элементов И 4, группу регистров 5, группу элементов И 6, блок 7 выбора максимального кода, блока 8 приоритетов, группу элементов И 1 О, счетчик 11 рангов, группу триггеров 12, элемент задержки 13 элементы ИЛИ 14, элемент ИЛИ 15, элемент НЕ 16, элемент НЕ 16, элемент ИЛИ 7, счетчик 18 ресурсов, вход 19 устройства и группу выходон 20 устройства.Блок 7 выбора максимального кода включает группу элементов ИЛИ-НЕ 21 2 2, где ш - число разрядов в кодах, группу ячеек 22, 22..,22 анализа разрядов, каждая ячейка состоит из узлов 23 ,2311 23 т поразрядного переноса, в состав каждого из которых входят элементы ИПИ 24 и И 25.Блок 8 приоритетов включает элементы НЕ 26,26 и элементы И 27 27, где и - максимальное число заданий.Блок 7 выбора максимального кода предназначен для выдачи позиционного номера максимального кода, блок 8 приоритетов - для выдачи унитарного номера с наименьшим позиционным но" мерам кода.Устройство для распределения заданий работает следующим образом.В исходном состоянии нсе триггеры, регистры и счетчики находятся в нулевом состоянии. Первоначально через вход 19 в счетчик 18 заносится количество свободных ресурсов, а в матрицу 1 - информация О топологии орграфа. При этом триггеры 2; (,==,и), которые являются формирователями дуг, устанавливаются в единичное состояние, если есть информационная связь из х-й вершины в 1-ю вер шину, Соответствующий триггер 2,определяется пересечением -й строкии 3-го столбца. На регистры 5 с помощью управляющей программы в результате определения характеристик графа Ои выбора критериальной функции списочного расписания заносятся значения критериальной функции каждой вершины, После занесения исходной информации на выходах элементов ИЛИ-НЕ3 в стобцах, соответствующих начальным заданиям графа, появляются единичные сигналы, так как начальныезадания не содержат входящих дуг итриггеры 2 н этом столбце находятсяв нулевом состоянии. Высокие потенциалы с ныходов элементов ИЛИ-НЕ 3поступают на входы соответстнуюшихгрупп элементов И 6. С выходов соот"нетствующих регистров 5 значения 25функций через группу элементов И 6поступают на блок 7, н которомнавходы элементов ИЛИ 24 и И 25 узлов23 , 23 23поступают и кодов, каждый из которых представленразрядами, с выходов элементов И 6.В первый момент анализируются старшие разряды всех кодов. Если хотябы один из старших разрядов кодовранен единице, на выходе элемента 35 ИЛИ-НЕ 21 появляется низкий потенциал (код О); который соответствуетсигналу запрета при анализе остальных разрядов кодов, старшие разрядыкоторых равны нулю.Эти сигналы формируются на выходах элементов ИЛИ 24 и поступают навходы элементов И 25. Те коды, старшие разряды которых равны 1, проходят через элементы И 25 ячейки 22 45ъЕсли старшие разряды всех чисел равны О, на выходе элемента ИЛИ-НЕ 21,формируется "1", благодаря чему обеспечивается разрешение на прохождение остальных разрядов всех кодов 50 через элементы ячейки 22. Аналогичным образом анализируются вторые постаршенстну разряды всех кодов ит,д., в результате чего на выходахузлов 23 23,23формирует ся позиционный код номера максимального кода, на выходе блока 7 устанавливается позиционный номер или номера (и случае двух или более равныхмаксимальных значений), которые поступают на вход блока 8.Блок приоритетов работает следующим образом.На вход блока приоритетов посту пает двоичный код, Причем д-тая единица двоичного кода ( - младший разряд кода, значение которого равно единице) поступает на вход элемента И 271, (если =1, то сигнал сразу поступает на выход блока 8). Низкие потенциалы с (д)-го разряда двоичного кода поступают на соответствующие входы элементов НЕ 26,26;, .Следовательно, с выходов последних высокие потенциалы поступают на входы элемента И 27 . На выходе последнего, устанавливается высокий потенциал. Кроме того, высокий потенциал 1.-го разряда с входа блока 8 поступает на 40 вход элемента НЕ 26, низкий потенциал с выхода которого поступает на входы элементов И 271+127 . На выходе блока 8 устанавливается позиционный код номера приоритетного задания. Рассмотрим работу блока 8 на примереНа вход блока поступает двоичный код с выхода блока 7, равный 1011, ,О. Младший разряд кода равен еди нице, следовательно, высокий потенциал поступает на выход блока 8 и вход элемента НЕ 26,. На выходе последнего появляется низкий потенциал, который поступает на входы элементов З 5 И 27 27 Следовательно, на выходах элементов И 27 появляются низкие потенциалы. На выходе блока 8 устанавливается позиционный код 100, ,О. На 1-м выходе блока 8 появля ется унитарный код задания, имеющего максимальное значение критериальной функции иэ числа готовых заданий к назначению. В результате х-й триггер 12 устанавливается в единичное сос тояние. Так как высокий потенциал поступает с -го выхода блока 8 на д-й вход элемента ИЛИ 14, то с выхода последнего высокий потенциал поступает на счетный вход счетчика 18 50 и уменьшает его содержимое на единицу. При занесении количества ресурсов двоичный код ресурса с входа 19 поступает на входы элемента ИЛИ 17. В результате с выхода последнего вы сокий потенциал поступает на счетный вход счетчика 11. Следовательно, содержимое счетчика становится равным единице. Высокий потенциал с выходаэлемента ИЛИ 14 поступает на входэлемента 13 задержки, время задержкикоторого равно времени установкисчетчика 18 в нулевое состояние. Свыхода элемента 13 высокий потенциалпоступает на управляющие входы группы элементов И, На выходе элементаИ 10 устанавливается высокий потенциал, который поступает на регистр5 и устанавливает его в нулевое состояние. В результате исключения значения критериальной функции д-го задания на выходе блока 7 устанавливается позиционный номер следующегозадания. Далее процесс выбора заданий первого ранга повторяется до,тех пор, пока не будет распределенвесь ресурс. При окончании ресурсана входы элемента ИЛИ 15 с выходовсчетчика 18 поступают низкие потенциалы. Низкий потенциал с выхода элемента ИЛИ 15 поступает на входы элементов И 10, и процесс распределениязаданий приостанавливается. Одновременно низкий потенциал с выхода элемента ИЛИ 15 поступает на вход эле"мента НЕ 16. Высокий потенциал с выхода последнего поступает на управляющие входы элементов И 9. На выходе 1-х элементов И 9 появляются высокие потенциалы Ц - распределенныезадания), которые поступают на входыэлементов И 4, на вторые входы которых поступает двоичный код, равныйединице, с выхода счетчика 11. На регистрах 5 фиксируется код равныйединице. Одновременно высокие потенциалы с выходов элементов И 9 поступают на 1-тые строки матрицы 1 триггеров 2 и устанавливают их в нулевоесостояние, На выходы 20 устройства свыходов элементов И 9 выдаютсякодыраспределенных заданий. С поступлением очередного количества ресурсовна вход 19 на выходе элемента ИЛИ 17устанавливается высокий потенциал,который поступает на триггеры 12 иустанавливает их в нулевое состояние.Одновременно высокий потенциал с вы-,хода элемента ИЛИ 17 поступает насчетный вход счетчика 11 и увеличивает его содержимое на единицу. Далеепроцесс распределения заданий по рангам в зависимости от значений функций вершин орграфа с учетом ограниченного ресурса повторяется аналогично. Процесс распределения заданийзаканчивается при обнулении всехтриггеров 2 матриц 1. В результатена группе регистров 5 содержатся номера рангов распределяемых заданий,Формула изобретения 20 Устройство для распределения за" даний, содержащее матрицу топологии 10 орграфа из и ф и триггеров, первую группу из п элементов И, вторую группу из и элементов И, первый и второй элементы ИЛИ, элемент НЕ, счетчик ресурсов, счетчик рангов, группу из 15 и триггеров, выход каждого -го элемента И первой группы (где =1,2, ,и) подключен к входам установки в "О" триггеров д-ой строки матрицы топологии орграфа, входы установки в "1" триггеров матрицы формирования топологии орграфа являются первой группой информационных входов устройства, группа установочных входов счетчика ресурсов является второй группой информационных входов устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения класса решаемых задач за счет воэможности выбора заданий по рангам, в него 30 введены группа из и элементов ИЛИ-НЕ третья группа из и элементов И, четвертая группа из и элементов И,группа из и регистров, блок выбора максимального кода, блок приоритетов, З 5 третий элемент ИЛИ, элемент задерж" ки, выход каждого -го триггера каждого 1-го столбца матрицы формирования топологии орграфа 1 где 1 щ 1,2 и) подключен к -му входу .-го эле мента ИЛИ-НЕ группы, выход каждого из элементов ИЛИ-НЕ группы подключен к первому входу одноименного элемента И второй группы, выход каждого 3.-го элемента И второй группы подключен к х-му входу группы информационных входов блока выбора максимального кода, группа выходов которого подключена к группе входов блока приоритетов, каждый -ый выход группы выходов блока приоритетов подключен к-му входу третьего элемента ИЛИ, выход которого подключен к счетному входу счетчика ресурсов ик входу элемента задержки, каждый выход группы информационных выходовсчетчика ресурсов подключен к одноименному входу первого элемента ИЛИ,выход которого подключен к первымвходам элементов И третьей группы,вторые входы которых объединены иподключены к выходу элемента задержки, третий вход каждого -го элемента И третьей группы объединен с первым входом -го элемента И первойгруппы и подключен к выходу д-го триггера группы, вход установки в "1"которого подключен к -му выходугруппы выходов блокаприоритетов,входы установки в "О" всех триггеровгруппы объединены со счетным входомсчетчика рангов и подключены к выходу второго элемента ИЛИ, каждый -йвход которого объединен с "м входомгруппы установочных входов счетчикаресурсбв, выход первого элемента ИЛИподключен к входу элемента НЕ, выходкоторого подключен к вторым входамэлементов И первой группы, выходыкоторых являются группой информационных выходов устройства, выход каждого -го элемента И первой группыподключен к первому входу -го элемента И четвертой группы, вторыевходы всех элементов И четвертой группы объединены и подключены к выходусчетчика рангов, выход каждого -гоэлемента И четвертой группы подключен к информационному входу -го ре-.гистра группы, выход которого подключен к второму входу -го элемента И второй группы, вход установки в"О" каждого д-го регистра группы подключен к выходу -го элемента И третьей группы.. ЯУ-у Арф блана Ю мемеду д Елок Фиг. ЯСоставитель Т.СапуноваРедактор О.Юрковецкая Техред М.Ходанич Корректор М.Пожо аказ 65 роиэводственно-полиграфическое предприятие,г.ужгород,ул.Проект 63/42 Тираж 671 ВНИИПИ Государственного по делам изобретений 113035, Москва, Ж, РПодписнокомитета СССРи открытийушская наб., д.4/5