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

 

Изобретение относится к вычислительной технике и может быть использовано при организации пакетной обработки в ЭВМ, а также в устройствах , предназначенных для решения задач в специализированных процессорах . Цель изобретения - сокращение аппаратных затрат. Устройство содержит генератор тактовых импульсов , злементы И, 1ШИ, НЕ, счетчики , триггеры, узлы приоритета, состоящие из группы злементов НЕ и группы злементов И. Устройство ранжирует задачи в пакете с учетом известных времен ввода, решения и вывода результатов каждой задачи. 1 ил,.

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

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

РЕСПУБЛИН ив SUoD (50 4 С 06 Р 9/46

А1

ОПИСАНИЕ ИЗОБРЕТЕНИЯ к втоескочм свидвтяЛьСтву

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3884803/24-24 (22) 15.04.85 (46) 07.03.87. Бюл. У 9 (72) В.А.Титов, Е.Г.Иельников, А,Ф.Чудаев и В.П.Спичак (53) 68).325(088.8) (56) Авторское свидетельство СССР

У 966697, кл. G 06 F 9/46, 1982.

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

У 1065856, кл. G 06 F 9/46, 1984, (54) УСТРОЙСТВО ДЛЯ PACHPEgEJIEHHH

ЗАДАНИЙ (57) Изобретение относится к вычислительной технике и может быть использовано при организации пакетной обработки в ЭВМ, а также в устройствах, предназначенных для решения задач в специализированных процессорах. Цель изобретения - сокращение аппаратных затрат. Устройство содержит генератор тактовых импульсов, элементы И, ИЛИ, НЕ, счетчики, триггеры, узлы приоритета, состоящие нэ группы элементов НЕ и группы элементов И. Устройство ранжирует задачи в пакете с учетом известных времен ввода, решения и вывода результатов каждой задачи, 1 ил.

1 1295395 2

Изобретение относится к вичислительной технике и может быть использовано при организации пакетной обработки в ЭВМ, а также в устройствах предназначенных для решения задач в специализированных процессорах °

Цель изобретения — сокращение аппаратних затрат.

На чертеже приведена структурная схема устройства для распределения заданий.

Устройство содержит генератор 1 тактовых импульсов, элемент И 2, элементи И 3„...3 „, нычитающие счетчики 4«...4, дифференцирующие цепочЬ ки 5„° ° ° 5 „ýëåìåíòû ИЛИ 6„,...б „, элементы И 7« ° .,7 „, триггеры 8„; „.

8, элементы И 9, ...9„, элементы

2и

IIËÈ 10< ...10, узлы 11, и lf приоритета, вычитающий счетчик 12,элементы HE 13 и 13, суммирующие счетчики 14 и 15s триггер 16, выходы 1721, входы 22 и 23, Каждий узел 11 приоритета содержит элементы НЕ 24 . ...24„, и элементы И 25 ...25„.

Устройство работает следующим образом, В исходном состоянии все триггеры и счетчики находятся н нулевом состоянии. На счетчики 4«...4„„ за носятся коды, соответствующие первой фазе задач (установочные входы счетчиков не показаны). На счетчики

4 ...4 „ заносятся коды, соответстну21 ющие второй фазе задач, а на вичита.ющий счетчик 12 — код, соответствую1 щий числу (n+1), где n " количество задач н пакете.

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

Обозначим А; — время реализации

i-й задачи на первой фазе, В; — время реализации i-й задачи на второй фазе. После подачи высокого потенциала на вход 22 элемента И 2 так-. товые импульсы начинают поступать на входы вычитающих счетчиков 4„ ° ..4 „ через соответствующие элементы И

3«...3 „„

Если А„<В;, i=1...n(, то в первую очередь обнуляется счетчик 4; и на. выходе элемента ИЛИ 6„ появляется низкий потенциал..При изменении полярности сигнала на выходе элемента ИЛИ 6„ с высокого уровня на низкий на выходе дифференцирующей цепочки 5; появляется импульсный сиг5

Ю

55 триггера 8,, после чего триггер 8; устанавливается н нуленое состояние. Следовательно, на i-м выходе узла Iff устанавливается низкий по„тенциал, в результате на вход элеHan 1(o I 0pblH x стаяавливаеT T I l. f p

8 а епННп «0 cîñòîÿíèå.

Так как счетчик 4,, находится в нулевом состоянии, то на выходе элемента ИЛИ 6 устанавливается низкий

1 потенциал, который отключает счетчики 4„ и 4, от генератора 1 через элементы И 3„ и 3; соответственно. При обнулении счетчика 4; значение (В;—

А;) на счетчике 4 далее не изменяется, так как на одном из входов элементов 3<, и 3 постоянно низкий потенциал с выхода элемента ИЛИ 6; ° Аналбгичное происходит, если первым обнуляется счетчик 4,. С выхода триггера 8, высокий потенциал поступает на i-й вход узла 11; приоритета, который обеспечивает выработку высокого потенциала только на одном из его и выходов. С выхода узла 11, приоритета снимается позиционный код номера очередной выполняемой задачи, которую необходимо ставить в начало очереди. В случае одновременного обнуления нескольких счетчиков

4, и появления высоких потенциалов

« на нескольких входах узла 11 приоритета позиционный код видается поочередно, начиная с наименьшего номера, Кроме того, с i-го выхода узла Ilf приоритета высокий потенциал поступает íà i-й вход элемента

ИЛИ 1О, а далее — на вход счетчика

14, с выхода которого снимается двоичный код номера задачи в очереди.

Одновременно с выхода элемента ИЛИ

l0f высокий потенциал поступает на вход элемента HE 13,, с выхода которого низкий потенциал поступает на вход элемента И 2, после чего прекращается прохождение тактовых импульсов через элемент И 2. После выдачи кода номера задачи с выхо-: да 17 и номера этой задачи в очереди с выхода 18 операционная система ЗВМ выдает сигнал приема номера задачи к обработке на вход 23, который далее поступает на вход элементов И 7«...7 „. Так как на второй вход элемента If 7, (д =1...п) поступает высокий потенциал с i-го выхода узла 11, на выходе элемента И

7 устанавливается высокий потенци11 ал, который поступает на второй вход

3 1 мента И 2 через элементы ИЛИ 10 и НЕ 13, поступает высокий потенциал, и тактовые импульсы снова начинают поступать на входы счетчиков

4,,4 . С выхода счетчика 14 снима-

Ы ется номер задачи только при выпол- нении условия А; В, а задачи в очереди располагаются в порядке возрастания А;, начиная с первого, Если А;=В, то счетчики 41 и 4; обнуляются одновременно и триггери

8 и 8 устанавливаются в единичное

11 г, состояние. Низкий потенциал с выхода элемента ИЛИ 6, поступает на первый вход элемента И 9;, на Вто» ром входе которого высокий потенциал с выхода триггера 8, a pe21 зультате на выходе элемейта И 9; низкий потенциал, следовательно, сигнал на узел 11 приоритета не поступает. С выхода триггера 8 высокий потенциал поступает на i-й вход узла 11,. Далее процесс постановки i-й задачи в очередь повторяется аналогичным образом, как и при условии А;сЬ;.

Если А; В, то счетчик 4 обнуляется раньие, чем счетчик 4 . В этом

1» случае триггер 8 устанавливается в

21 единичное состояние.

Высокий потенциал с выхода триггера 8 поступает на вход элемента ! И 9 ; на второй вход которого поступает высокий потенциал с выхода элемента ИЛИ 6, . Так как счетчик

4„ еще не обнулился, то на выходе элемента И 9 устанавливается высо- кий потенциал, который поступает на

i-й вход узла ll . С выхода 20 узла

11 приоритета снимается код номера задачи, которую необходимо ставить в конец очереди. Кроме того, с выхода узла llг код поступает на входы элемента ИЛИ 10, с выхода которого высокий потенциал поступает на вход элемента НЕ 13,г. Низкий потенциал с выхода элемента.НЕ 13 постуг пает на вход элемента И 2 и запрещает подачу тактовых импульсов с генератора 1, Кроме того, с выхода элемента ИЛИ 10< высокий потенциал через элемент .. ИЛИ 1Оэ поступает на вход счетчика 15, который производит подсчет числа распределенных за" дач. Одновременно с выхода элемента

ИЛИ 10 высокий потенциал поступает на вход вычитающего счетчика 12, с выходов 19 которого снимается номер задачи в очереди. Содержимое

295395 4

10,переполнения устанавливает триггер

3О!

16 в единичное состояние. В резуль1

;тате на выходе 21 появляется сигнал окончания работы устройства, а с инверсного выхода триггера 16 низкий потенциал поступает на вход элемента И 2, запрещая поступлению на входы счетчиков 4„...4г„тактовых импульсов, На этом устройство заканчивает свою работу.

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

Устройство для распределения за40 даний, содержащее генератор тактовых импульсов,элемент И, пять групп Ns и (n " число заданий) элементов И, две группы из и триггеров, две группы йз п элементов ИЛИ, первый счетчик, шестую и седьмую группы из (п-1) элементов R,âûõîä генератора тактовых импульсов соединен с первым входом элемента И, выход которого соединен с первыми входами элементов И первой и второй групп, выходы

i-x (i=1...n) элементов И третьей и четвертой группы соединены с соответствующими входами сброса -х триггеров первой и второй групп соответственно, о т л и ч а ю m ее с я тем, что, с целью сокращения аппаратных затрат, оно содержит две счетчика 12 уменьшается всегда на

"1" и в порядке поступления сигналов) с выхода элемента ИЛИ 10 задачи устанавливаются с конца очереди в порядке увеличения Р;, начиная с

n-ro.

Если А;=А или В;=В; i j=l п,i4„, то на узел ll или ll соответственно поступают одновременно несколько сигналов высокого уровня.

Элемент ИЛИ 10, или 10 выдает высокий потенциал на вход элемента ИЕ

13 или НЕ 13г,с выхода которого на элемент И 2 поступает низкий потенциал и запрещает подачу тактовых импульсов с выхода генератора I на счетчики 4„...4 „ до тех пор, пока все задачи не установятся в очередь.

Когда на всех выходах узлов ll или

112 низкие потенциалы, на входы элемента И 2 с выходов элементов НЕ 13 или НЕ 13 поступают высокие потен2 циалы, а тактовые импульсы с выхода генератора 1 начинают поетупать на счетчик 4„,.;4

Й ° .2н

Устройство заканчивает работу, когда счетчик 15 с коэф4ициентом пересчета и переполняется и сигнал

1295395 группы из и дифференцирующих цепочек, две группы из и счетчиков, вто рой и третий счетчик и три элемента ИЛИ, два элемента НЕ, триггер, две группы из (и-I) элементов НЕ, причем единичный вход триггера соединен с выходом переполнения первого счетчика, первый выход триггера соединен с вторым входом элемента

И, третий вход которого является входом запуска устройства, второй выход триггера является выходом конца работы устройства, выходы i"õ элементов И первой и второй групп. соединены с информационными входами

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

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

i-.õ дифференцирующих цепочек первой

И второй групп соединены с соответствующими входами установки триггеров первой и второй групп соответственно, выход i-го триггера второй группы соединен с вторым входом

i-го элемента И пятой группы, вход подтверждения устроиства соединен с первыми входами элементов И третьей и четвертой групп, четвертый вход элемента И соединен с выходом первого элемента HF. пятый вход элемента И соединен с выходом второго элемента НЕ, выход первого элемента ИЛИ соединен с входом первого элемента

НЕ, счетным входом второго счетчика и первым входом второго элемента

ИЛИ, выход третьего элемента ИЛИ соединен с входом второго элемента

НЕ, счетным входом третьего счетчика и вторым входом второго элемента ИЛИ, выход второго элемента ИЛИ соединен

|со счетным входом первого счетчика, выход первого триггера первой группы соединен с входом первого элемента НЕ первой группы, вторым входом первого элемента И третьей группы и первым входом первого элемента HJIH выход m-ro (m=2...(n-l)) триггера первой группы соединен с входом m-го элемента НЕ первой группы и входом

К-го (К=l...(n-2)) элемента H mecтой группы, выход последнего триггера первой группы соединен с входом последнего элемента И шестой группы, выход j-ro (I=l...n-l) элемента

НЕ первой группы соединен с (j+1) входами с j-го по (n-1)-й элемент

И шестой группы, выход j-го элемента И шестой группы соединен с вторым входом S-го (S=2...n) элемента

И третьей .группы и с S-м входом первого элемента ИЛИ, выходы элементов И шестой группы и выход первого триггера первой группы являются первым выходом кода номера задачи устройства, выход первого элемента

И пятой группы соединен с входом первого элемента НЕ второй группы и первым входом третьего элемента

ИЛИ, выход m-го элемента И пятой группы соединен с входом m-ro элемента НЕ второй группы и входом К-ro элемента И седьмой группы, выход последнего элемента И пятой группы соединен с входом последнего элемента И седьмой группы, выход j-го эле" мента НЕ второй группы соединен с (j+I)-ми входами с j-го по (n-I)-й элемент И седьмой группы, выход j-го элемента И седьмой группы соединен с. вторым входом S-го элемента И четвертой группы и с S-м входом третьего элемента ИЛИ, выходы элементов И седьмой группы и выход первого элемента И пятой группы являются вторым входом кода номера задачи устройства, выходы второго счетчика являются первым выходом номера задачи в очереди устройства, выходы третьего н счетчика являются вторым выходом номера задачи в очереди устройства.

1 ? 95395

Составитель Г.Пономарева

Редактор И.П1улла ТехредЛ.Сердокова Корректор В Бутяга

Заказ 618/55 Тираж 673 Подписное

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

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

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