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

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

Цель изобретения - повышение быстродействия за счет сокращения времени на пересчет весов фаз выполняемых задач,

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

Устройство содержит (фиг.1) генератор тактовых импульсов 1, элемент И2, элементы И3ц...32п, где п - число задач в пакете, блок элементов И 4, элемент ИЛИ 5, блок элементов И 6, блок выдачи результатов 7, вычитающие счетчики 8ii...8an. элементы ИЛИ 9ц...92п. элемент И 10ц...102п. триггеры 11 ц...112п. дифференцирующие цепочки 12ii...122n. элементы H13i...13n, блоки 14i и

142 приоритета, вход 15, выходы 16,17i. , 18, входы 19, 20ii...20in, 202i...202nБлок 7 (фиг.2) содержит элементы ИЛИ 211 и 212, два формирователя импульсов 221 и 222, элемент ИЛИ23, блоки элементов И 24i и 242, блок элементов ИЛИ 25, элемент ИЛИ 26, счетчики 27, 28, триггер 29, счетчик 30., элемент И 31, блок элементов ИЛИ 32, блок элементов И 33, входы 34ц...34 2п. выход 35.

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

В исходном состоянии все триггеры 11 и 29, счетчики 8, 27, 28, 30 находятся в нулевом состоянии (входы установки в нуль на фиг.1 и фиг.2 не показаны). На счетчики 8n,..8in заносятся коды, соответствующие первой фазе работ (задач), по входам 20ii...20in. На счетчики 821...82п заносятся коды, соответствующие второй фазе работ (задач), по входам 2021,..202п. На вычитающий счетчик 27 блока 7 заносится код. соот00Сл) СА OD XI W

ветствующий числу (n-Н), где п- количество задач в пакете (входы занесения кода на счетчик 27 на рисунке не показана).

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

Введены следующие обозначения;

AI - время реализации i-ой задачи на ее первой фазе;

BI - время реализации i-ой задачи.на ее второй фазе,С выходов вычитающих счетчиков 8ii...82n коды поступают на блок элементов И 4 (число элементов И 4 в блоке равно числу разрядности счетчиков 8), где одноименные разряды кодов первых и вторых фаз задач проверяются на одновременное наличие в них единиц. чС выхода блока И4 на вход элемента ИЛИ 5 поступают сигналы, соответствующие, единице (если все одноименные разряды имеют 1) и нулю,(есл хотя бы один из них имеет О).

При наличии на входе элемента ИЛИ 5 хотя бы одной единицы с инверсного выхода элемента. ИЛИ 5 снимается нулевой сигнал, который поступает на вход элемента И2, запрещая подачу через .соответствующие, элементы И 3 тактовых импульсов на вычитающие счетчики 8ц.,,82п. Одновременно с выхода Элемента ИЛИ 5 единичный сигнал поступает на входы блока элемента И б, куда также поступают сигналы с выхода блока элементов. И 4. С выхода блока элементов И6 сигналы поступают на -входы сброса в нуль разрядов вычитающих счетчиков 811 ...82п (как первых, так и вторых фаз), обнуляя одноименные разряды счетчиков, содержащие единицы.

С выхода счетчиков 8 коды фаз поступают на блок элементов И 4, с выхода которого теперь снимается нулевой сигнал (так как в одноименных разрядах кодов обеих фаз те-, перь. нет всех единиц), который поступает на вход элемента ИЛИ 5 и с его инверсного выхода единичный сигнал поступает на вход элемента И 2, разрешая при наличии пускового единичного сигнала на входе 15 элемента И 2 поступление тактовых импульсов на входы вычитающих счетчиков 8ц...82п через,соответствующие элементы И 3.

Если AI Bi (i 1, п), то в первую очередь обнуляется счетчик 8м и на выходе элемента ИЛИ 9И появляется нулевой сигнал.

При изменении уровня сигнала на выходе элемента ИЛИ 9ц с единичного уровня на нулевой на выходе дифференцирующей цепочки 12ц появляется импульсный сигнал, который устанавливает триггер 11ii в единичное состояние.

Так как счетчик 8ц находится в нулевом

состоянии, то на выходе элемента ИЛИ 9ц

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

закрывает элементы И Зц и 321. и запрещает

прохождение на счетчики 8ц и 8 счетных.

импульсов с генератора 1. При обнулении

счетчика 8ii значение (Bi-AI) на счетчике 8я

ранее не изменяется, так как на одном из

выходов элементов И Зц и 321 будет постоянно находиться нулевой сигнал с выхода элемента ИЛИ 9ц. С выхода триггера 11ц единичный сигнал поступает на вход узла 14т, который обеспечивает выработку единичного сиг.нала только на одном из своих

выходов. Структура блока 14i (142) полностью совпадает ср структурой аналогичного блока в прототипе..

: С выхода блока 14i снимается позици- онный код номера очередной выполняемой

задачи, которую необходимо ставить в нача-: ло очереди, В случае одновременного обнуления нескольких счетчиков 81|и появление единичных сигналов на нескольких входах узлЈ 14i позиционный код выдается поочередно, начиная с наименьшего номера. Кроме того с i-rp выхода блока 141 единичный сигнал поступает на i-й вход элемента ИЛИ 211 блока 7 (фиг.2) и с его прямого выхода - на вход счетчика 30, с выхода которого снимается двоичный код номера задачи в оче- .реди-, который через открытые элементы И 31 (открытый сигналом с выхода формирователя импульсов 221) и через блок элементов ИЛИ 32 поступает на выход 17i устройства.

А позиционный код данной задачи в наборе

. выдается через открытый блок элементов И

24 и блок элементов ИЛИ 25 на выход

устройства. Одновременно с инверсного

выхода элемента ИЛИ 2ti нулевой сигнал

поступает на выход 35 блока 7, а затем по- ступает на вход элемент И2, после чего .прекращается прохождение тактовых импульсов с выхода генератора через элементы И 2. Кроме того единичный сигнал с

выхода элемента 21.1 через элемент ИЛ И-26

поступает1 на выход 18 устройства, сеиде1тельствуя о наличии на выходе 17 кода номера задачи в.очереди. После выдачи

позиционного кода номера задачи по выхрду 172 и номера этой задачи в очереди по

выходу 17i операционная система ЭВМ выдает сигнал приема задачи к обработке на

вход 19, который далее поступает на первые

входы элементов И 10ц...102п. Так как на

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

триггер 11ц устанавливается в нулевое состояние.

Следовательно, на l-ом выходе блока 14i устанавливается нулевой сигнал, в результате на входе элемента И 2 через элементы ИЛИ 21i поступает единичный сигнал, и тактовые импульсы снова начинают поступать на счетные входы счетчиков 8Ц...82п.

С выхода счетчика 30 снимается код номера задачи только при выполнении условия AI BI, и тогда задачи в очереди располагаются в порядке возрастания AI, начиная с первой.

Если AI BI, то счетчики 8i и 82 обнуляются одновременно и триггеры 11ц и 1121 устанавливаются в единичное состояние.

Нулевой сигнал с выхода элемента ИЛИ 9ц поступает на первый вход элемента И 13i, на втором входе которого будет единичный сигнал с выхода триггера 1121. В результате на выходе элемента И 13i будет нулевой сигнал, следовательно, единичные сигналы на блок 142 приоритета не поступают. С выхода триггера 11 ц единичный сигнал поступает на 1-й вход блока 14i. Далее процесс постановки i-рй задачи в очередь повторяется аналогичным образом), как при условии AI Bj.

Если AI BI, то счетчик 821 обнуляется раньше, чем счетчик 8ц.. В этом случае триггер 1121 устанавливается в единичное состояние.

Единичный сигнал с выхода триггера 1121 поступает на первый вход элемента И13|, на второй вход которого поступает единичный сигнал с выхода элемента ИЛИ 9ц. Так как счетчик 8ц еще необнулился, то на выходе элемента И 13i устанавливается единичный сигнал, который поступает на 1-й вход блока 142. С выхода блока 142 снимается код номера задачи, которую необходимо ставить в конец очереди. Кроме того, с выхода блока 142 поступает на входы элемента ИЛИ 212, с инверсного выхода которого нулевой сигнал поступает по выходу 35 блока 7 на вход элемента И 2 и запрещает подачу тактовых импульсов с генератора 1. Кроме того, с прямого выхода ИЛИ 212 единичный сигнал запускает формирователь 222 и единичный сигнал через элемент ИЛИ 23з поступает на вход счетчика 28, который осуществляет подсчет числа распределенных задач. Одновременно с прямого выхода элемента ИЛИ 212 единичный сигнал поступает на вход вычитающего счетчика 27, с выходов которого снимается номер задачи в очереди. Содержимое счетчика 27 уменьшается всегда на единицу и в порядке поступления сигналов с прямого выхода

элемента ИЛИ 212 задачи устанавливаются с конца очереди в порядке увеличения Bt, начиная с п-го.

Если AI AJ или В| Bj (i, j 1, п. j 4), то 5 на входе блока 14i (или 142 соответственно) поступают одновременно несколько сигналов, на инверсном выходе элемента ИЛИ 211 (или 212) появляется нулевой сигнал, который поступает на вход элемента И 2, и 0 запрещает подачу тактовых импульсов с выхода генератора 1 на счетчики 8 до тех пор, пока все задачи одинаковой приоритетности не установятся в очередь. Если на всех выходах блоков 14i или 142 будут нулевые

5 сигналы, то на входы элемента И 2 с инверсных выходов элементов ИЛИ 211 (или 212) поступают единичные сигналы, и тактовые импульсы с выхода генератора 1 начинают поступать на счетчики 8.

0 Устройство заканчивает работу, когда счетчик 2 с коэффициентом пересчета п переполняется и сигнал переполнения устанавливает триггер 2 в единичное состояние. В результате на выходе 16 появляется сиг5 нал окончания работы устройства, а с инверсного выхода триггера 2 поступает нулевой сигнал на вход элемента И 2, запрещая поступление на входы счетчиков 8 тактовых импульсов. На этом устройство заканчивает

0 свою работу. Формирователи 221 и 222 имеют разное время задержки и выдачи импульса на своих выходах, что исключает одновременную выдачу информации на выходе 172 состояний счетчиков 27 и 30.

5

Формула изобретения 1.. Устройство для распределения заданий, содержащее генератор тактовых импульсов, элемент И, элемент ИЛИ, пять

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

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

2. Устройство по п,1, о т л и ч а ю щ е е- с я тем, что блок выдачи результата содержит триггер, три счетчика, четыре элемента ИЛИ, два блока элементов ИЛИ, три блока

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

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

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

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

элемента ИЛИ и второму входу первого блока элементов к входу второго блока элементов И, выход второго формирователя импульсов подсоединен к первому входу третьего блока элементов И, вторым входам

элемента И и четвертого элемента ИЛИ, выход четвертого элемента ИЛИ подсоединен к счетному входу третьего счетчика, выход которого подсоединен к единичному входу триггера, инверсные выходы триггера первого и третьего элементов ИЛИ через монтажное ИЛИ подсоединены к первому выходу блока, единичный выход триггера является четвертым выходом блока, группа входов второго блока элементов И подсоединена К первой группе входов блока, а выход к первому входу второго блока элементов ИЛИ, второй вход которого подсоединен к выходу третьего блока элементов И, группа входов которого является

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

ч

I

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

со

оо

Г)

со

со

$