Устройство для распределения заданий Советский патент 1986 года по МПК G06F15/173 

гчэ сл

О5 4; Изобретение относится к вычислительной технике и может быть использовано в качестве диспетчера для выбора заданий на решение в системе обработки данных. Целью изобретения является расширение класса решаемых задач за счет возможности выбора заданий по рангам в зависимости от значений критериальных функций с учетом ограниченного ресурса. На фиг.I представлена структурная схема устройства для распределения заданий; на фиг.2 - структурная схема блока выбора максимального кода; на фиг.З - структурная схема блока приоритетов. Устройстве содержит матрицу 1 топологии орграфа из njan триггеров 2, группу элементов ИЛИ-НЕ 3, группу элементов И 4, группу регистров 5, группу элементов И 6, блок 7 выбора максимального кода, блока 8 приоритетов, группу элементов И 10, счетчик 11 рангов, группу триггеров 12, элемент задержки 13, элементы ИЛИ 14 элемент ИЛИ 15, элемент НЕ 16, элемент НЕ 16, элемент ИЛИ 17, счетчик 18 ресурсов, вход 19 устройства и группу выходов 20 устройства. Блок 7 выбора максимального кода включает группу элементов ИЛИ-НЕ 91 21 1 .,..,., где m - число раз ,i рядов в кодах, группу ячеек 22 , 22 ,...,22 анализа разрядов, каждая ячейка состоит из узлов ,23, ,. 23гг,т поразрядного переноса, в состав каждого из которых входят элементы ИЛИ 24 и И 25. Блок 8 приоритетов включает элементы НЕ 26 ,..., 26 и элементы И 27 ,. . . ,27f, где п - максимальное число заданий. Блок 7 выбора максимального кода предназначен для выдачи позиционного номера максимального кода, блок 8 приоритетов - для выдачи унитарного номера с наименьшим позиционным номером кода. Устройство для распределения заданий работает следующим образом. В исходном состоянии все триггеры регистры и счетчики находятся в нуле вом состоянии. Первоначально через вход 19 в счет.чик 18 заносится количество свободных ресурсов, а в матрицу 1 - информация о топологии ортрафа. При этом триггеры 2,-j (i,j 42 15п), которые являются формирователями, дуг, устанавливаются в единич- ное состояние, если есть информационная связь из i-й вершины в j-ю вершину. Соответствующий триггер 2 jj определяется пересечением i-й строки И j-ro столбца. На регистры 5 с помощью управляющей программы в результате определения характеристик графа и выбора критериальной функции списочного расписания заносятся значения критериальной функции каждой вершины. После занесения исходной информации на выходах элементов ИЛИ-НЕ 3 в стобцах, соответствующих начальным заданиям графа, появляются единичные сигналы, так как начальные задания не содержат входящих дуг и триггеры 2 в этом столбце находятся в нулевом состоянии. Высокие потенциалы с выходов элементов ИЛИ-НЕ 3 поступают на входы соответствующих групп элементов И 6. С выходов соответствующих регистров 5 значения функций через группу элементов И 6 поступают на блок 7, в которомна входы элементов ИЛИ 24 и И 25 узлов 23, 23, ...,231, поступают п кодов, каждый из которых представлен разрядами, с выходов элементов И 6. В первый момент анализируются старшие разряды всех кодов. Если хотя бы один из старших разрядов кодов равен единице, на выходе элемента 2 If появляется низкий потенциал (код 0) , который соответствует сигналу за.прета при анализе остальных разрядов кодов, старшие разряды которых равны нулю. Эти сигналы формируются на выходах элементов ИЛИ 24 и поступают на входы элементов И 25. Те коды, старшие разряды которых равны 1, проходят через элементы И 25 ячейки 22. Если старшие разряды всех чисел равкы о, на выходе элемента ИЛИ-НЕ 21 формируется 1, благодаря чему обеспечивается разрешение на прохождение остальных разрядов всех кодов через элементы ячейки 22. Аналогичньтм образом анализируются вторые по старшенству разряды всех кодов и т.д., в результате чего на выходах узлов 23, , 232, ,. .. ,23f формируется позиционный код номера максимального кода, на выходе блока 7 устанавливается позиционный номер или номера (в случае двух или более равных 31 максимальных значений), которые поступают на вход блока 8. Блок приоритетов работает следующим образом. На вход блока приоритетов поступает двоичный код. Причем i-тая единица двоичного кода (i - младший раз ряд кода, значение которого равно единице) поступает на вход элемента И 27j , (если , то сигнал сразу по ступает на выход блока 8). Низкие по тенциалы с (i-1-)-го разряда двоичного кода поступают на соответствующие входы элементов НЕ 26 , ... ,26 ,, .Сле довательно, с выходов последних высокие потенциалы поступают на входы элемента И 27 . На выходе последнего устанавливается высокий потенциал. Кроме того, высокий потенциал i-ro разряда с входа блока 8 поступает на вход элемента НЕ 26, низкий потенциал с выхода которого поступает на входы элементов И 27;. ,...,27. На выходе блока 8 устанавливается позиционный код номера приоритетного задания. Рассмотрим работу блока 8 на примере. На вход блока поступает двоичный код с выхода блока 7, равный 1011, ...,0. Младший разряд кода равен еди-30

нице, следовательно, высокий потенциал поступает на выход блока 8 и вход элемента НЕ 26|. На выходе последнего появляется низкий потенциал, который поступает на входы элементов И 27- ,...,27. Следовательно, на выходах элементов И 27 появляются низкие потенциалы. На выходе блока 8 устанавливается позиционный код 100, ...,0. На i-M выходе блока 8 появляется унитарный код задания, имеющего максимальное значение критериальной функции из числа готовых заданий к назначению. В результате i-й триггер 12 устанавливается в единичное соетояние. Так как высокий потенциал поступает с i-ro выхода блока 8 на i-й вход элемента ИЛИ 14, то с выхода последнего высокий потенциал поступает на счетный вход счетчика 18 и уменьшает его содержимое на единицу. При занесении количества ресурсов двоичный код ресурса с входа 19 поступает на входы элемента ИЛИ 17. В результате с выхода последнего высокий потенциал поступает на счетный вход счетчика 11. Следовательно, содержимое счетчика становится равным

де J-X элементов И 9j появляются высокие потенциалы (j распределенные задания), которые поступают на входы элементов И 4j, на вторые входы которых поступает двоичный код, равный единице, с выхода счетчика 11. На регистрах 5 фиксируется код равный единице. Одновременно высокие потенциалы с выходов элементов И 9j поступают на j-тые строки матрицы 1 триггеров 2 и устанавливают их в нулевое состояние. На выходы 20 устройства с выходов элементов И 9 выдаются коды распределенных заданий. С поступлением очередного количества ресурсов на вход 19 на выходе элемента ИЛИ I7 устанавливается высокий потенциал, который поступает на триггеры 12 и устанавливает их в нулевое состояние. Одновременно высокий потенциал с вы-, хода элемента ИЛИ 17 поступает на счетный вход счетчика 11 и увеличивает его содержимое на единицу. Далее процесс распределения заданий по рангам в зависимости от значений функций вершин орграфа с учетом ограниченного ресурса повторяется аналогично. Процесс распределения заданий 4 единице. Высокий потенциал с выхода элемента ИЛИ 14 поступает на вход элемента 13 задержки, время задержки которого равно времени установки счетчика 18 в нулевое состояние. С выхода элемента 13 высокий потенциал поступает на управляющие входы группы элементов И. На выходе элемента И 10 устанавливается высокийпотенциал, который поступает на регистр 5(. и устанавливает его в нулевое состояние. В результате исключения значения критериальной функции i-ro задания на выходе блока 7 устанавливается позиционньм номер следующего задания. Далее процесс выбора заданий первого ранга повторяется до. тех пор, пока не будет распределен весь ресурс. При окончании ресурса на входы элемента ИЛИ -15 с выходов счетчика 18 поступают низкие потенциалы. Низкий потенциал с выхода элемента ИЛИ 15 поступает на входы элементов И 10, и процесс распределения заданий приостанавливается. Одновременно низкий потенциал с выхода элемента ИЛИ 15 поступает на вход элемента НЕ 16. Высокий потенциал с выхода последнего поступает на управляющие входы элементов И 9. На выхозаканчивается при обнулении всех триггеров 2 матриц 1. В результате на группе регистров 5 содержатся номера рангов распределяемых заданий.

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

Устройство для распределения заданий, содержащее матрицу топологии орграфа из п п триггеров, первую группу из п элемелтов И, вторую группу из п элементов И, первый и второй элементы ИЛИ, элемент НЕ, счетчик ресурсов, счетчик рангов, группу из п триггеров, выход каждого i-ro эле«тента И первой группы (где ,2, ...,п) подключен к входам установки в О триггеров i-ой строки матрицы топологии орграфа, входы установки в 1 триггеров матрицы формирования топологии орграфа являются nep-f вой группой информационных входов устройства, группа установочных входов счетчика ресурсов является второй группой информационных входов устройства, отличающееся тем, что, с целью расширения класса решаемых задач за счет возможности выбора заданий по рангам, в него введены группа из п элементов ИЛИ-НЕ третья группа из п элементов И, четвертая группа из п элементов И,группа из п регистров, блок выбора максимального кода, блок приоритетов, третий элемент ИЛИ, элемент задержки, выход каждого i-ro триггера каждого j-ro столбца матрицы формирования топологии орграфа (где j I ,2,..., п) подключен к i-му входу j-ro элемента ШШ-НЕ группы, выход каждого из элементов ИЛИ-НЕ группы подключен к первому входу одноименного элемента И второй группы, выход каждого i-ro элемента И второй группы подключен к 1-му входу группы информационных входов блока выбора максимального кода, группа выходов которого подключена к группе входов блока приоритетов, каждый i-ый выход группы выходов блока приоритетов подключен к i-му входу третьего элемента ИЛИ, выход которого подключен к счет- ному входу счетчика ресурсов и к входу элемента задержки, каждый выход группы информационных выходов

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

подключены к выходу элемента задержки, третий вход каждого i-ro элемента И третьей группы объединен с первым входом i-ro элемента И первой группы и подключен к выходу i-ro триггера группы, вход установки в 1 которого подключен к i-му выходу группы выходов блока приоритетов,входы установки в О всех триггеров группы объединены со счетным входом

счетчика рангов и подключены к выходу второго элемента ИЛИ, каждый i-й вход которого объединен с i-м входом группы установочных входов счетчика ресурсбв, выход первого элемента ИЛИ

подключен к входу элемента НЕ, выход которого подключен к вторым входам элементов И первой группы, выходы которых являются группой информационных выходов устройства, гйыход каждого i-ro элемента И первой группы подключен к первому входу i-ro элемента И че.твертой группы, вторые входы всех элементов И четвертой группы объединены и подключены к выходу

счетчика рангов, выход каждого i-ro элемента И четвертой группы подключен к информационному входу i-ro per гистра группы, выход которого подключен к второму входу i-ro элемента И второй группы, вход установки в О каждого-i-ro регистра группы подключен к выходу i-ro элемента И третьей группы.

2Jfn

ft . //лг 0lff.f

J Sjfoffi/ Sjiof a 8

1275464

/t-ff 8

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

Гг5

У1 ®L0 Ш

S r r -J:r-3--:Jfe -

III

11

f Jwfг r

11 (Ж1Ш11 I ш

LJ-J --...-.- prz J.:--,. r -nr J

lifel Й Ш1

I Tu

ZILI

J( злемем/пу Jf6

фиг. 2

/л

ii

m

Jj

II I

ff-f

-Л

1Й Й (л

Э

23агп

/( злеме///п /fS/,

к блоку tif