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

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН (50 4 0 06 F 15 20 9/46

ГОСУДАРСТ8ЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ / " -:

Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ . / ,1 (21) 3919762/24-24 (22) 22.05.85 (46) 07,12.86. Бюл. У 45 (72) А.А.Есетов и А.А.Чупринов (53) 681.333(088.8) (56) Авторское свидетельство СССР

У 716043, кл. G 06 F 15/20, 1980.

Авторское свидетельство СССР

И 1013963, кл. G 06 F 15/20, 1983. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

ЗАДАНИЙ (57) Изобретение относится к вычислительной технике и может быть использовано в качестве диспетчерадля выбора заданий на решение в системе

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

НЕ ° 3 ил.

1275464

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

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

На фиг.1 представлена структур-. ная схема устройства дпя распределения заданий; на фиг,2 — структурная схема блока выбора максимального кода; на фиг.3 — структурная схема блока приоритетов.

Устройство содержит матрицу 1 топологии орграфа из пуп триггеров 2, группу элементов ИЛИ-НЕ 3, группу элементов И 4, группу регистров 5, группу элементов И 6, блок 7 выбора максимального кода, блока 8 приоритетов, группу элементов И 1О, счетчик 11 рангов, группу триггеров 12, элемент задержки 13 элементы ИЛИ 14, элемент ИЛИ 15, элемент НЕ 16, элемент НЕ 16, элемент ИЛИ 17 счетчик

18 ресурсов, вход 19 устройства и группу выходон 20 устройства.

Блок 7 выбора максимального кода включает группу элементов ИЛИ-НЕ

21,, 21,...,2!„„, где m — число разрядов в кодах, группу ячеек 22„, 22 . ° .,22 анализа разрядов, каждая ячейка состоит из узлов 23„,23,, 11

23nrn поразрядного переноса, в состав каждого из которых входят элементы

ИПИ 24 и И 25.

Блок 8 приоритетов включает элементы НЕ 26,,...,26„ и элементы

И 27,...,27„, где n — максимальное число заданий.

Блок 7 выбора максимального кода предназначен для выдачи позиционного номера максимального кода, блок 8 приоритетов — для выдачи унитарного номера с наименьшим позиционным но" мерам кода.

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

В исходном состоянии нсе триггеры, регистры и счетчики находятся в нулевом состоянии. Первоначально через вход 19 н счетчик IB заносится количество свободных ресурсов, а в матрицу 1 — информация о топологии орграфа. При этом триггеры 2;„ (i,j=

=1,и), которые являются формирователями дуг, устанавливаются в единичное состояние, если есть информационная связь из i-й вершины в j-ю вершину. Соответствующий триггер 2;„ определяется пересечением i-й строки .и j-го столбца. На регистры 5 с помощью управляющей программы в результате определения характеристик графа

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

3 в стобцах, соответствующих начальным заданиям графа, появляются единичные сигналы, так как начальные задания не содержат входящих дуг и триггеры 2 н этом столбце находятся в нулевом состоянии. Высокие потенциалы с ныходов элементов ИЛИ-НЕ 3 поступают на входы соответствующих групп элементов И 6. С выходов соответствующих регистров 5 значения

25 функций через группу элементов И 6 поступают на блок 7, н котором на входы элементов ИЛИ 24 и И 25 узлов

23„, 23 ...,,23 „ поступают и кодов, каждый из которых представлен разрядами, с выходов элементов И 6.

В первый момент анализируются старшие разряды всех кодов. Если хотя бы один из старших разрядов кодов ранен единице, на выходе элемента

35 ИЛИ-НЕ 21„„ появляется низкий потенциал (код 0); который соответствует сигналу запрета при анализе остальных разрядов кодов, старшие разряды которых равны нулю.

Эти сигналы формируются на выходах элементов ИЛИ 24 и поступают на входы элементов И 25. Те коды, старшие разряды которых равны 1, проходят через элементы И 25 ячейки 22

45 Если старшие разряды всех чисел равны О, на выходе элемента ИЛИ-НЕ 21,„ формируется "1", благодаря чему обеспечивается разрешение на прохождение остальных разрядов всех кодов

50 через элементы ячейки 22„„. Аналогичным образом анализируются вторые по старшенству разряды всех кодов и т.д., в результате чего на выходах узлов 23„,, 23<, 23 „ формирует55 ся позиционный код номера максимального кода, на выходе блока 7 устанавливается позиционный номер или номера (и случае двух или более равных

1275464 максимальных значений), которые поступают на вход блока 8.

Блок приоритетов работает следующим образом.

На вход блока приоритетов поступает двоичный код. Причем i-тая единица двоичного кода (i — младший разряд кода, значение которого равно единице) поступает на вход элемента

И 271, (если i=1, то сигнал сразу по-10 ступает на выход блока 8). Низкие потенциалы с (i-1)-ro разряда двоичного кода поступают на соответствующие входы элементов НЕ 26,,...,26;, .Следовательно, с выходов последних высокие потенциалы поступают на входы элемента И 27„.. На выходе последнего, устанавливается высокий потенциал.

Кроме того, высокий потенциал i-ro разряда с входа блока 8 поступает на вход элемента НЕ 26, низкий потенциал с выхода которого поступает на входы элементов И 27;,,...,27„ . На выходе блока 8 устанавливается позиционный код номера приоритетного задания. Рассмотрим работу блока 8 на примере °

На вход блока поступает двоичный код с выхода блока 7, равный 1011, ...,О. Младший разряд кода равен еди- 30 нице, следовательно, высокий потенциал поступает на выход блока 8 и вход элемента НЕ 26,. На выходе последнего появляется низкий потенциал, который поступает на входы элементов 3

И 27,...,27,„. Следовательно, на выходах элементов И 27 появляются низкие потенциалы. На выходе блока 8 устанавливается позиционный код 100, ...,О. Ha i-м выходе блока 8 появля- 40 ется унитарный код задания, имеющего максимальное значение критериальной функции иэ числа готовых заданий к назначению. В результате i-й триггер

12 устанавливается в единичное сос- 45 тояние. Так как высокий потенциал поступает с i-го выхода блока 8 на

i-й вход элемента ИЛИ 14, то с выхода последнего высокий потенциал поступает на счетный вход счетчика 18 50 и уменьшает его содержимое на единицу. При занесении количества ресурсов двоичный код ресурса с входа

19 поступает на входы элемента ИЛИ 17.

В результате с выхода последнего вы- 55 сокий потенциал поступает на счетный вход счетчика ll. Следовательно, содержимое счетчика становится равным единице. Высокий потенциал с выхода элемента ИЛИ 14 поступает на вход элемента 13 задержки, время задержки которого равно времени установки счетчика 18 в нулевое состояние. С выхода элемента 13 высокий потенциал поступает на управляющие входы группы элементов И. На выходе элемента

И 10 устанавливается высокий потенциал, который поступает на регистр

5<, и устанавливает его в нулевое состояние. B результате исключения значения критериальной функции i-го задания на выходе блока 7 устанавливается позиционный номер следующего задания. Далее процесс выбора заданий первого ранга повторяется до, тех пор, пока не будет распределен весь ресурс. При окончании ресурса на входы элемента ИЛИ 15 с выходов счетчика 18 поступают низкие потенциалы. Низкий потенциал с выхода элемента ИЛИ 15 поступает на входы элементов И 10, и процесс распределения заданий приостанавливается. Одновременно низкий потенциал с выхода элемента ИЛИ 15 поступает на вход эле" мента НЕ 16. Высокий потенциал с выхода последнего поступает на управляющие входы элементов И 9. На выходе j-х элементов И 9„ появляются высокие потенциалы (j — распределенные задания), которые поступают на входы элементов И 4„, на вторые входы которых поступает двоичный код, равный единице, с выхода счетчика 11. На регистрах 5 фиксируется код равный единице. Одновременно высокие потенциалы с выходов элементов И 9„. поступают на j òûå строки матрицы 1 триггеров 2 и устанавливают их в нулевое состояние. На выходы 20 устройства с выходов элементов И 9 выдаются коды распределенных заданий. С поступлением очередного количества ресурсов на вход 19 на выходе элемента ИЛИ 17 устанавливается высокий потенциал, который поступает на триггеры 12 и устанавливает их в нулевое состояние.

Одновременно высокий потенциал с вы-, хода элемента ИЛИ 17 поступает на счетный вход счетчика 11 и увеличивает его содержимое на единицу. Далее процесс распределения заданий по рангам в зависимости от значений функций вершин орграфа с учетом ограниченного ресурса повторяется аналогично. Процесс распределения заданий

1275464 заканчивается при обнулении всех триггеров 2 матриц I. В результате на группе регистров 5 содержатся номера рангов распределяемых заданий.

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

Устройство для распределения заданий, содержащее матрицу топологии 1О орграфа из и ф и триггеров, первую группу из п элементов И, вторую группу из и элементов И, первый и второй элементы ИЛИ, элемент НЕ, счетчик ресурсов, счетчик рангов, группу из 15 и триггеров, выход каждого i-ro элемента И первой группы (где i=1,2, ...,n) подключен к входам установки в "0" триггеров i-ой строки матрицы топологии орграфа, входы установки в "1" триггеров матрицы формирования топологии орграфа являются пер-1 вой группой информационных входов устройства, группа установочных входов счетчика ресурсов является второй группой информационных входов устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения класса решаемых задач за счет воэможности выбора заданий по рангам, в него 30 введены группа из и элементов ИЛИ-НЕ третья группа из Il элементов И, четвертая группа из и элементов И,группа из и регистров, блок выбора максимального кода, блок приоритетов, третий элемент ИЛИ, элемент задержки, выход каждого i-ro триггера каждого j-го столбца матрицы формирования топологии орграфа (где j 1,2,..., n) подключен к i-му входу .j-ro эле- 40 мента ИЛИ-НЕ группы, выход каждого из элементов ИЛИ-НЕ группы подключен к первому входу одноименного элемента И второй группы, выход каждого

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

i-му входу третьего элемента ИЛИ, выход которого подключен к счетному входу счетчика ресурсов и к входу элемента задержки, каждый выход группы информационных выходов счетчика ресурсов подключен к одноименному входу первого элемента ИЛИ, выход которого подключен к первым входам элементов И третьей группы, вторые входы которых объединены и подключены к выходу элемента задержки, третий вход каждого i-ro элемента И третьей группы объединен с первым входом i-го элемента И первой группы и подключен к выходу i-го триггера группы, вход установки в "1" которого подключен к i-му выходу группы выходов блока приоритетов,входы установки в "0" всех триггеров группы объединены со счетным входом счетчика рангов и подключены к выходу второго элемента ИЛИ, каждый i-й вход которого объединен с i-м входом группы установочных входов счетчика ресурсбв, выход первого элемента ИЛИ подключен к входу элемента HE выход которого подключен к вторым входам элементов И первой группы, выходы которых являются группой информационных выходов устройства, выход каждого i-ro элемента И первой группы подключен к первому входу i-ro элемента И четвертой группы, вторые входы всех элементов И четвертой группы объединены и подключены к выходу счетчика рангов, выход каждого 3.-го элемента И четвертой группы подключен к информационному входу i-ro ре-. гистра группы, выход которого подключен к второму входу i-го элемента И второй группы, вход установки в

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

1275464

1275464

Я 1-чу Аоф блана Ю

Ая-му &аду йлола 8

A snemrwmy 4

4 Елок

Я anr e mp

4 Фюоку 7

Фиг. Л

Составитель Т.Сапунова

Редактор О.Юрковецкая Техред М.Ходанич Корректор M.Ïoæî

Заказ 6563/42 Тираж 671 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д.4/5

Производственно-полиграфическое предприятие,г.ужгород,ул.Проектная,4