Устройство для распределения заданий Советский патент 1987 года по МПК G06F9/54 

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

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

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

Устройство содержит генератор i тактовых импульсов, элемент И 2, элементы И 3„.,.32 вычитающие счетчики ,,„, дифференцир5гющие цепочки 5„ ... 5 элементы ИЛИ 6,... в, элементы И 7,, ... 7,, триггеры 8, -. „ . 8 , элементы И 9, ,. . элементы ИЛИ 0 ... 1 Од, узлы 11, и 11, приоритета, вычитающий счетчик 12,элементы НЕ 13 и 132 суммирующие счетчики 14 и 15, триггер 16, выходы 17- 21, входы 22 и 23. Каждый узел 11 приоритета содержит элементы НЕ 2Д,. ...24 и элементы И 25... 25 ,.

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

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

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

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

Если А.В|, ..,nj, то в пернал, который устаиарливает тримч. р Sjj в единичное сос .тояние.

Так как счетчик 4,; находится в нулевом состоянии, то на выходе эле мента ИЛИ 6с устанавливается низки потенциал, который отключает счетчи ки 4,; и от генератора 1 через эл

менты И и

Ю

is

20

25

3;j; соответственно.

При

обнулении счетчика - значение (В;- AJ) на счетчике 42,-далее не изменяе ся, так как на одном из входов элементов 3,; и постоянно низкий пот циал с выхода элемента ИЛИ . Ана логичное происходит, если первым об нуляется счетчик 42,.. С выхода триггера 8j, высокий потенциал поступает на i-й вход узла 1 1, приоритета, который обеспечивает выработку высокого потенциала только на одном из его п выходов. С выхода узла II, приоритета снимается позиционный код номера очередной выполняемой за дачи, которую необходимо ставить в начало очереди. В случае одновремен ного обнуления нескольких счетчиков 4, и появления высоких потенциалов на нескольких входах узла l приоритета позиционный код вьщается поочередно, начиная с наименьшего

30 номера. Кроме того, с i-ro выхода узла 11, приоритета высокий потенциал поступает на i-й вход элемент ИЛИ 10, а далее - на вход счетчика 14, с выхода которого снимается дв

35 ичный код номера задачи в очереди. Одновременно с выхода элемента ИЛИ 10 высокий потенциал поступает на вход элемента НЕ 13,, с выхода кот рого НИЗК.ИЙ потенциал поступает на

40 вход элемента И 2, после чего прекращается прохождение тактовых импульсов через элемент И 2. После вьщачи кода номера задачи с выхо да 17 и номера этой задачи в очере45 ди с выхода 18 операционная система ЭВМ выдает сигнал приема номера задачи к обработке на вход 23, кото рый далее поступает на вход элементов И 7j, . . . 7. Так как на второй

50 вход элеЪ1ента И 7, (...n) поступает высокий потенциал с i-ro выхода узла 11, на выходе элемента И 7,1 устанавливается высокий потенциал, который поступает на второй вхо

вую очередь обнуляется счетчик 4 и на выходе элемента ИЛИ 6,; появляется низкий потенциал, -При изменении 55 триггера 8,, после чего триггер 8,; полярности сигнала на выходе элёмен- устанавливается в нулевое состоя- та ИЛИ 6,j с высокого уровня на низ- ние. Следовательно, на i-м выходе кий на выходе дифференцирующей цепочки 5,; появляется импульсный сигузла 11( устанавливается низкий по- тенциал, в результате на вход эленал, который устаиарливает тримч. р Sjj в единичное сос .тояние.

Так как счетчик 4,; находится в нулевом состоянии, то на выходе элемента ИЛИ 6с устанавливается низкий потенциал, который отключает счетчики 4,; и от генератора 1 через эле-менты И и

0

5

3;j; соответственно.

При

ч

обнулении счетчика - значение (В;- AJ) на счетчике 42,-далее не изменяется, так как на одном из входов элементов 3,; и постоянно низкий потенциал с выхода элемента ИЛИ . Аналогичное происходит, если первым обнуляется счетчик 42,.. С выхода триггера 8j, высокий потенциал поступает на i-й вход узла 1 1, приоритета, который обеспечивает выработку высокого потенциала только на одном из его п выходов. С выхода узла II, приоритета снимается позиционный код номера очередной выполняемой задачи, которую необходимо ставить в начало очереди. В случае одновременного обнуления нескольких счетчиков 4, и появления высоких потенциалов на нескольких входах узла l приоритета позиционный код вьщается поочередно, начиная с наименьшего

0 номера. Кроме того, с i-ro выхода узла 11, приоритета высокий потенциал поступает на i-й вход элемента ИЛИ 10, а далее - на вход счетчика 14, с выхода которого снимается дво5 ичный код номера задачи в очереди. Одновременно с выхода элемента ИЛИ 10 высокий потенциал поступает на вход элемента НЕ 13,, с выхода которого НИЗК.ИЙ потенциал поступает на

0 вход элемента И 2, после чего прекращается прохождение тактовых импульсов через элемент И 2. После вьщачи кода номера задачи с выхо-: да 17 и номера этой задачи в очере5 ди с выхода 18 операционная система ЭВМ выдает сигнал приема номера задачи к обработке на вход 23, который далее поступает на вход элементов И 7j, . . . 7. Так как на второй

0 вход элеЪ1ента И 7, (...n) поступает высокий потенциал с i-ro выхода узла 11, на выходе элемента И 7,1 устанавливается высокий потенциал, который поступает на второй вход

5 триггера 8,, после чего триггер 8,; устанавливается в нулевое состоя- ние. Следовательно, на i-м выходе

триггера 8,, после чего триггер 8,; устанавливается в нулевое состоя- ние. Следовательно, на i-м выходе

узла 11( устанавливается низкий по- тенциал, в результате на вход эле3

мента И 2 через элементы ИЛИ 10, и НЕ 13, поступает высокий потенциал, и тактовые импульсы снова начинают поступать на входы счетчиков ...4j. С выхода счетчика 14 снима ется номер задачи только при выполнении условия А, , а задачи в очереди располагаются в порядке возрастания А;, начиная с первого.

Если , то счетчики 4. и обнуляются одновременно и триггеры и 8j. устанавливаются в единичное состояние. Низкий потенциал с выхода элемента ИЛИ 6,; поступает на первый вход элемента И 9, , на втором входе которого высокий потенциал с выхода триггера 8-, t в результате на выходе элемента И 9; низкий потенциал, следовательно сигнал на узел И приоритета не поступает, С выхода триггера высокий потенциал поступает на i-й вход узла 11I. Далее процесс постановки i-й задачи в очередь повторяется аналогичным образом, как и при условии Aj tB J.

Если , то счетчик обнуляется раньие, чем счетчик 4, . В этом случае триггер 8, устанавливается в единичное состояние.

Высокий потенциал с выхода триггера 8j поступает на вход элемента И 9 , на второй вход которого поступает высокий потенциал с выхода элемента ИЛИ . Так как счетчик 4, еще не обнулился, то на выходе элемента И 9, устанавливается высокий потенциал, который поступает на i-й вход узла 11 . С выхода 20 узла П приоритета снимается код номера задачи, которую необходимо ставить в конец очереди. Кроме того, с выхода узла 1Ij код поступает на входы элемента ИЛИ 10, с выхода которого высокий потенциал поступает на вход элемента НЕ 13. Низкий потенциал с выхода элемента .НЕ 13 поступает на вход элемента И 2 и запрещает подачу тактовых импульсов с генератора I. Кроме того, с выхода элемента ИЛИ 10 высокий потенциал через элемент.. ИЛИ 10} поступает на вход счетчика 15, который производит подсчет числа распределенных задач. Одновременно с выхода элемента ШШ lOj высокий потенциал поступает на вход вычитающего счетчика 12, с выходов 19 которого снимается номер задачи в очереди. Содержимое

953954

счетчика 12 уменьшается всегда на I и в порядке поступления сигнало с выхода элемента ИШ 10 задачи устанавливаются с кошта очереди в

5 порядке увеличения RJ , начиная с п-го.

Если или ji,,.,, , то на узел II, тши 11 соответственно поступают одновременно

JO несколько сигналов высокого уровня. Элемент ИЛИ 10, или 10 выдает высокий потенциал на вход элемента НЕ 13 или НЕ 13-,с выхода которого на элемент И 2 поступает низкий потенiS циал и запрещает подачу тактовых импульсов с выхода генератора 1 на счетчики тех пор, пока все задачи не установятся в очередь. Когда на всех выходах узлов 11, или

0 IIj низкие потенциалы, на входы элемента И 2 с выходов элементов НЕ 13, или НЕ I3- поступают высокие потенциалы, а тактовые импульсы с выхода генератора 1 начинают поступать на

5 счетчик 4,,..,4,j.

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

30j 16 в единичное состояние, В резуль- тате на выходе 21 появляется сигнал окончания работы устройства, а с инверсного выхода триггера 16 низкий потен1щал поступает на вход злемен35 та и 2, запрещая поступлению на входы счетчиков 4„.,,4 тактовых импульсов. На этом устройство заканчивает свою работу.

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

Устройство для распределения за- ;даний, содержащее генератор тактовых импульсов,элемент И, пять групп из п (п - число заданий) элементов И,

45 две группы из п триггеров, две группы из п элементов ИЛИ, первый счетчик, шестую и седьмую группы из (п-1) элементов Невыход генератора тактовых импульсов соединен с первым

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

группы из п дифференцирующих цепочек, две группы из п счетчиков, вто рой и третий счетчик и три элемента ИЛИ, два элемента НЕ, триггер, две группы из (п-1) элементов НЕ, причем единичный вход триггера соединен с выходом переполнения первого счетчика, первый выход триггера соединен с вторым входом элемента И, третий вход которого является входом запуска устройства, второй выход триггера является выходом -конца работы устройства, выходы i-x элементов И первой и второй групп соединены с информационными входами i-x счетчиков первой и второй групп соответственно, выходы i-x счетчиков первой и второй групп соединены с соответствз тощими входами элементов ИЛИ первой и второй групп соответственно, выход i-ro элемента Или первой группы соединен с вто рыми входами i-x элементов И первой и второй групп, с входом i-диффе- ренцирЗ Чёй цепочки первой группы. Первым входом i-ro элемента И пятой группы, выход i-ro элемента ИЛИ второй группы соединен с третьими входами i-x элементов первый и второй групп, входом i-й дифференцирующей цепочки второй группы, выходы i-x дифференцирующих цепочек первой и второй групп соединены с соответствующими входами установки триггеров первой и второй групп соответственно, выход i-ro триггера второй группы соединен с вторым входом i-ro элемента И пятой группы, вход подтверждения устройства соединен с первыми входами элементов И третьей и четвертой групп, четвертый вход элемента И соединен с выходом первого элемента НЕ, пятый вход элемента И соединен с выходом второго элемента НЕ 5 выход первого элемента ИЛ соединен с входом первого элемента НЕ, счетным входом второго счетчика и первым входом второго элемента ИЛИ, выход третьего элемента ИЛИ соединен с входом второго элемента НЕ, счетным входом третьего счетчик и вторым входом второго элемента ИЛ

5

0

5

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

0

5

0

0

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