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

Од

сь

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

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

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

Устройство, (фиг 1 и 2) содержит группы 1 и 2 элементов И, блок 3 регистров , элементы ИЛИ 4 и 5 , элемен1Ъ1 И 6 и 7, группь 8 и 9 элементов И, элементы ИЛИ 10 и 115 триггеры 12 регистра готовности процессоров 5 группы 1 3 и1 4 блоков элементов И, группы 15 и 16 элементов ИЛИ, элемент ИЛИ, 17, триггер 18з элемент ШШ 19, элемент И 20, выхо,цы 21 элементов И 8, блок 22 регистров, группы выходов 23 и 24 блока 22, группы входов 25 блока 22, группу входов 26 разрешения считывания блока 22J группу выходов 27 блока 22J группу сумматоров 28, элемент И 29, триггер 30, элемент 31 задержки, блок 32 выделения максимума, вход 33 блокировки работы блока 32, 34 блока 32, вход 35 разрешения работы блока 32, выходы 36 блока 32, группу элементов И 37, элемент ИЛИ 38, группу входов 39 заданий устройства, группы выходов 40 устройства, группу сигнальных входов 41 устройства и тактовый вход устройства.

Блок 32 выделения максимума (фиг. 3) содержит узлы 42 анализа, входы 43-46 узлов 42, выходы 47-50 узлов 42, элементы НЕ 51, элементы ИЛИ 52, элементы ИЛИ-НЕ 53 и элементы НЕ 54.

Узел 42 (фиГе 4) состоит из элементов И 55 и 56, а также элементов ИЛИ 57 и 58,

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

В исходном состоянии роцессоры свободны, что соответствует единичным сигналом на входах 41, триггеры 12 находятся в единичном состоянии, блоки 3 и 22 регистров свободны, триггеры 18 и 30 находятся в нулевом состоянии. С прямых выходов триггеров 12 единичные сигналы поступают на входы элемента ИЛИ 4. С его инверсного выхода нулевой сигнал поQ ступает на второй вход элемента

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

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

0 ИЛИ 5, а элементы И 1 закрыты нулевым сигналом с прямого выхода элемента ШШ 5. Так как триггеры 12 регистра готовности находится в

единичном состоянии, то элемента

5 1-114 открыть, а элементы И 1 3 закрыты.

На входы 39 поступают задания. Поступающее на входы 39 устройства задание, пройдя элементы И. 2, ИЛИ 16 и И 14, поступает на первую группу

0 выходов 40 устройства, на первый процессор. Одновременно через элемент ИЛИ 15 первый триггер 12 устанавливается в нулевое состояние, открываются элементы И 13 первого блока и за-

г крываются элементы И 14. Таким образом, подготавливается поступление очередного задания в следующий процессор. На первом входе 41 устройства появляется нулевой сигнал.

,. Второе задание, поступающее на входы 39 устройства, пройдя элементы И 2, ИЛИ 16, И 13 и И 14, поступает во второй процессор через вторую группу выходов 40 устройства, и одновременно устанавливает второй триггер 12 через второй элемент ИЛИ 15 в нулевое состояние. При этом подготавливается поступление очередного задания в следующий процессор путем открывания элементов И 13 и закрывания

элементов И 14, а на втором входе 41 устройства появляется нулевой сигнал и т.д.

После выполнения задания процессор устанавливает соответствующий

триггер 12 в единичное состояние единичным сигналом, поступающим на соответствуюн(ий вход 41 устройства. Очередное задание поступает на один

5

из свободных начиная с первого процессоров через соответствующую группу выход1ов 40 устройства.

Так как блок 22 регистров свободен , то с его г рушты выходов 23 нулевые сигналы поступают на входы элемента ИЛИ 19. Нулевой сигнал с его прямого выхода поступает, элемента ИЛИ 5, .на третий вход элемента И 29, закрывая его и блокируя поступление тактовых сигналов через него на триггер 30 и запрещая, таким образом, работу блока 32 выделения максимума при свободном блоке 22 регистров.

, Если все процессоры заняты, что соответствует нулевым сигналам на входах элемента ИЛИ 4, то единичный сигнал с инверсного выхода элемента ИЛИ 4 поступает на второй вход элемента- ИЛИ 5, первый вход элемента ИЛИ 11, третий вход элемента И 20, третьи входы элементов И 8 и через элемент ИЛИ 38 на нулевой вход триггера 30, который своим нулевым сигналом с прямого выхода блокирует работу блока 32. При том на инверсном

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

Одновременно через элемент ИЛИ 17 триггер 18 устанавлг-геается в единичное состояние, блокируя при этом нулевым сигналом с инверсного выхода прохождение тактовых сигналов через элемент И 20,

Так как на выходах блока 3 присутствует нулевой сигнал, то на прямом выходе элемента ИЛИ 10 имеется единичный сигнал, который поступает на третьи выходы элементов ИЛИ 5 и И 7. Поступление этого единичного сигнала на третий вход элемента ИЛИ 5 обеспечивает поступление очередных заданий в блок 3 регистров, если в нем находится уже хотя бы одно задание.

С выхода элемента ИЛИ 11 единичный сигнал поступает на второй вход элемента И 7, разрешая при этом про- холодение через него тактовых сигналов на тактовый вход блока 3 регистров и на вторые входы элементов И 8.

0

5

0

5

0

5

5

0

По sTUjv тактовым сигнал;1М проходит считывание поступающих заданий нз блока 3 через открытые элементы И 8 в блок 22. После считывания в блок 22 всгх заданшЧ на выходах блока появится ну:тевой сигнал. На вьпЧ вход элемента И 6 поступает единичный сигнал с инверсного выхода элeмe cтa ИЛИ 10, открьшая элемент И- 6 для прохождения тактовых сигналов. Поступивший тактовьп сигнал устанавливает через элемент И 6 в нулевое состояние триггер 18. Единичный сигнал поступает на первьп вход элемента И 20 с инверсного выхода триггера 18 и разрешает прохождение тактовых сигналов через элемент И 20. Разряды 1 ш каждого регистра блока предназначены для хранения кода номера задания, разряды (т + 1) - к предназначены для хранения кода признака приоритета данного задания, а разряды (к + 1) (к + + п) используются для хранения результата суммирования (состояния соответствующего сумматора 28).

Так как после записи поступивших заданий в блок 22 на определенных выходах групп выходов 23 блока 22 имеется ненулевой сигнал, то на прямом выходе элемента ИЛИ 19 присутствует единичный сигнал, который поступает на первый вход элемента ИЛИ 5, образом нулевым сигналом с инверсного выхода элемента ИЛИ 5 блокируется прохождение поступающих на , входы 39 устройства новых заданий через элементы И 2 на освобождающиеся процессоры. С инверсного выхода элемента ИШ1 19 нулевой сигнал поступает на второй вход элемента ИЛИ 11.

Каждому регистру блока 22 поставлен в соответствие свой сумматор 28. На входы каждого сумматора подаются значения разрядов признака приоритета с соответствующих выходов 23 блока 22 и значения разрядов результи- р- тощей суммы ( которая до начала суммирования равна нулю) с соответствующих выходов 24 блока 22, которые являются слагаемыми для соответствующего с т матора 2В.

По поступившему тактовому сигналу на вход открытого элемента И 20 и далее на тактовые входы сумматоров производится с ммирование этих слагаемых на соответствующих сумматорах 28 и запись результата суммирования

с выходов этих сумматоров в разряды соответствующих регистров блока 22 через соответствующие этим сумматорам 25 блока 22. По следующему тактовому сигналу операция суммирования повторяется и т.д. Таким образом обеспечивается аппроксимированное линейное увеличение значений признаков .приоритета поступивших заданий в зависимости от времени пребывания заданий в блоке 22 (количества тактов суммирования) и от начальной величины признака приоритета. Таким образом обеспечивается дисциплина обслуживания с динамическим приоритетом. Новые (увеличивающиеся) значения признаков приоритета хранятся в разрядах соответствующих регистров блока 22.

Если на вхо,ЕЦз1 39 устройства посту- пает новое задание, то оно записывается через открытые элементы И 1 в блок 3, при этом единичным сигналом с выхода ИЛИ 17 триггер 18 устанавливается в единичное состояние. Этот триг гер в свою очередь, нулевьм сигналом с инверсного выхода закрьшает элемент И 20 и прекращает дальнейшее поступление тактовых сигналов через Элемент И 20 на тактовые входы сумматоров (а следовательно, приостанавливается процесс суммирования) до тех пор, пока поступившее новое задание не nepentmieTCH из блока 3 в блок 22 в соответствии с опи- санньпч алгоритмом и пока триггер 18 не установится в нулевое состояние. При этом единичным сигналом с инверсного выхода триггера-18 возобновляется поступление тактовых сигналов через элемент И 20 на тактовые входы сумматоров. После этого процесс .суммирования возобновляется.

Как только освобождается один из процессоров (или несколько процессоров), что соответствует наличию единичного сигнала на соответствующем входе 41 устройства, а следовательно, наличию единичного сигнала на прямом выходе соответствующего триггера 12 и наличию единичного сигнала на прямом выходе элемента ИЛИ 4, то нулевым сигналом с инверсного выхода элемента ИЛИ 4 запираются элементы И 8, а также через элемент ИЛИ 11 (на другом входе которого также нулевой сигнал с ин -рсного выхода элемента ИЛИ 19 при наличии

заданий в блоке 22) запирается эле- мент И 7. Таким образом прекращается поступление тактовых сигналов на тактовый вход блока 3, а следовательно, прекращается и запись поступающих заданий из блока 3 в блок 22. Этим же нулевым сигналом с инверсного выхода элемента ИЛИ 4 также за-

пирается и элемент И 20, прекращается поступление тактовых сигналов через элемент И 20 на тактовые входы сумматоров 28, и, следовательно, операции суммирования на сумматорах 28 не выполняются. ЕДИНИЧНЬЕЙ сигнал с |ррямого выхода элемента ИЛИ 4 поступа- ёт на первый вход элемента И 29, на тре - тий вход которого поступает единичный сигнал с прямого выхода элемента ИЛИ 19. При этом пришедший тактовый сигнал через элемент И 29 поступает на единичный вход триггера 30, устанавливая его в единичное состояние, С прямого выхода триггера 30 на блок 32 поступает единичный сигнал, а с инверсного выхода триггера 30 на блок 32- нулевой сигнал. Эти сигналы обеспечивают работу блока 32 выделения максимума.

На входы блока 32. поступают значе-, ния соответствующих (каждой группе входов) результирующих сумм с соответствующих выходов 24 блока 22,

Блок 3 состоит из узлов 42, на которые подаются признаки результирующих сумм заданий обрабатываемого массива так, что каждый признак результата суммирования занимает одну строку матрицы (старшие разряды слева) .

Для поиска максимума используется известный алгоритм поразрядного сравнения всех признаков, который состоит в следующем.

На первом шаге просматривается содержимое запоминающих элементов левого (первого) столбца, т.е. старшие разряды всех регистров блока 22. Если все разряды содержат нули, то на след пощем шаге просматриваются

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

Выделенное на последнем шаге под- множестти строк (в частном случае

одна строка) содержит максимальные признаки.

Описанный алгоритм с помощью двумерной итеративной сети размером 4х х4 реализуется следующим образом, Допустим, что на соответствующие входы 34 блока 32 поступают сигна:та 1,1,0,0 которые, в свою очередь, поступают на входы 43 соответствуюгцих узлов 42 первой строки матрицы. На входы 43 узлов 42 второй строки мат- ршда поступают соответственно сигналы 1,1,0,1 с входом 34 блока 32 на входы 43 узлов 42 третьей строки матрицы сигналы 1,1,0,1 с входов 34 блока 32,на 43 узлов 42 четвертой строки матршда - сигналы 0,1,0, 1 с входов 34,

В исходном состоянии на вход 35 блока 32 и далее на входы 46 первого столбца матрицы подается сигнал О (с прямого выхода триггера 30), который поступает на входы элементов И 56 и 55 каждого из узлов 42 первого столбца, закрывает .эти элементы и блокирует работу всего блока, так как на выходах элементов И 55 и 56 имеется нулевой сигнал, а следовательно, на выходах элементов ИЛИ 58 также нулевой сигнал, который поступает на соответствующие входы 46 следзтощих ячеек 42 каждой из строк. На вход 33 блока 32 и далее на входы 44 узлов 42 первой строки подается сигнал 1 с инверсного выхода триггера ЗО

Сигнал 1 с прямого выхода триггера 30 появляется в том случае, если свободен хотя бы один процессор, т.е. с прямого выхода элемента ИЛИ 4 единичный сигнал поступает на первый вход элемента И 29, если в блоке 22 хранится хотя бы одно задание, т.е. ненулевой сигнал с прямого выхода элемента ИЛИ 19 поступает на третий вход элемента И 29, обеспечивая прохождение тактовых сигналов через элемент И 29 на единичный вход триггера 30, на прямом выходе которого появляется сигнал 1,

Анализ признаков, поданных на входы 34 блока 32 происходит следующим образом.

На вход 34 блока 32, а следовательно, и на вход 43, узла 42 подается единичный сигнал, который поступает на вход элемента И 56, на

второй вход которого поступает сигнал i с выхода 43( узла 42 . На выходе элемента И 56 будет единичкьй сигнал, который поступает на вход элемента ИЛИ 58, а с его выхода - на выход 47j. узла 42. и далее на вход 46,2 с-н- дующего узла 42 первой строки. Таким образом, данная строка выделяется для дальнейшего просмотра на следующем шаге.

Единичный сигнал с выхода элемента И 56 узла 42, поступает также на

5 вход элемента HJBl 57, на второй вход которого поступает сигнал О, посту- пртшш на вход 44,, узла 42, , Таким образоь, единичный сигнал с выхода этого элемента ИШ 57 поступает на

0 вход элемента ШМ 57 узла 42 и

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

5 ячейки первого столбца. Этот единич- Hbtfi сигнал поступает на вход элемента НЕ 54, , и нулевой сигнал с его выхода поступает на входы 45 узлов 42 первого столбца. Таким образом,

0 этот нулевой сигнал поступает на вход элементов И 55 каждого из узлов 42 первого столбца и закрьшает эти эле- ме и ты.

С выхода элемейтов И 55 нулевой сигнал поступает на первые входи соответствующих элементов ИЛИ 58 узлов 42 первого столбца и не влияет на выходные сигналы узлов.

Следовательно, при наличии на вход дах 43 узлов 42 первого столбца хотя бы одной единицы сигналы на выходах элементов ИЛИ 58, а следовательно, и на выходах 47 соответствующих узлов 42 первого столбца зависят от сигнаг лов, поданных на входы 43-соответствующих узлов 42 первого столбца. Если на вход 43 узла 42 подана единица, то на выходе 47 узла присутствует единичный сигнал, если на входе 43 - нулевой сигнал, на выходе 47 - также нулевой сигнал.

Для узлов 42 других столбцов выходной сигнал зависит, помимо сигналов на их входах 43, также и от сигналов поданных на входы 46 этих уз- лов с соответств тощих выходов 47 узлов 42 предыд т11,его столбца и характеризующих результаты анализа узлов соответствующих строк предыдущих

0

столбцов (для старших разрядов соответствующих строк).

Таким образом, на выходе 47 узла 42, имеется единичный сигнал; на

it

выходе 472 f узла 42,2,- единичный сиг нал; на выходе 47, узла 42 j, - единичный сигнал, а на выходе 47 узла 42, - нулевой сигнал, причем это нулевой сигнал постулает на вход узла , закрывает элемен1Ъ1 И 55 и 56 этого узла, вызывая появление нулевого сигнала на его выходе 47. Далее этот нулевой сигнал поступает на вход узла 42 j и т.д. Таким образом, этот нулевой сигнал, закрывает все последующие узлы 42 данной строки и исключает данную строку из дальнейшего анализа.

На входы 43 оставшихся (не исклю- ченных из анализа) узлов 42 второго столбца поданы все единицы,следовательно, на выходах 47 узлов 42, 5 -11 42j имеются едиличнряе сигналы

На входы 43 узлов 42 третьего столбца поданы все нулевые сигнал1 ц следовательно, элементы узлов третьего столбца И 56, на вторые входы которых поступают эти нулевые сигналы с входа 43 соответствующих узлов оказываются закрытг ми, на выходах элементов И 56 присутствует нулевой сигнал, которьш поступает на первьй вход соответствующих элементов ИЛИ 57 Таким образом, нулевой сигнал, поданный на вход 44,, узла 42„ первой

t3

строки, проходит без изменения через столбец по вертикали (через элементы ИЛИ 57 ячеек третьего столбца) и с выхода .поступает на элемент Iffi 54- , а с его выхода единичньш сигнал) подается на первые входы элементов И 55 узлов третьего столбца (элементы И 56 всех узлов третьего столбца закрыты). На вторые входы элементов И 55 узлов третьего столбца подаются соответствующие сигналы с выходов узлов соответствующих стро предзыдущего столбца.

Таким образом, при наличии на всех входах 43 узлов 42 строк (не исключенных из анализа) данного столбца нулевых сигналов, сигнал на выходе узлов столбца соответствует сигналу на входе 46 этих узлов, а следовательно, соответствует сигналу на втором входе элемек i И 55 соответствующего узла данного столбца.

С

- тQ 15

7 20

25

30

35

з гбк

у

40

45

50

55

0

На выходах 47 узлов 42, , 42, 42j3 присутствуют единичные сиг налы.

Поскольку на входах 43 узлов 42 последнего столбца (не исключенных из анализа) есть единичные, сигналы, то сигналы на выходах узлов .42 последнего столбца зависят от сигналов на входах элементов И 56 соответствующих узлов.

Таким образом, в результате просмотра матрицы на выходах 50 и 50, второй и третьей строк, появляются единичные сигналы, свидетельствующие о наличии в них максимального числа. На выходах 50. и 50 первой и четвертой строк имеются нулевые сигналы.

Далее сигналы с выходов 50 матрицы поступают на элементь: НЕ 51, ИЛИ 52 и ИЛИ-НЕ 53.

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

Каждому регистру блока 22 (входу 26) соответствует свой выход 36 блока 32. На выделенном выходе 36 блока 32, соответствующем регистру блока 22, в котором хранится максимальное значение результирующей , появляется единичный сигнал, который поступает на вход соответствующего элемента И 37, На второй вход этого элемента поступает сигнал, задержанный в элементе 31 на время, необходимое для окончания переходных процессов в блоке 32 при выделении максимального числа,

С выхода соответствующего элемента И 37 единичньм сигнал поступает на соответствующий вход 26 блока 22 и обеспечивает считывание задания из выбранного регистра, которое через элементы ИЛИ 16 поступает на один из освободившихся процессоров (начиная с первого), при этом выбранный ре- . гистр обнуляется и на соответствующих выходах 23, 27 и 24 присутствуют нулевые значения,

Единичньп сигнал с выхода соответствующего элемента И 37 поступает на соответствующий вход элемента ИЛИ 38, с выхода которого единичньй сигнал поступает на нулевой вход триггера 30, которьш при этом устанавливается в нулевое состояние и блокирует работу блока 32,

По след тощему тактовому сигналу (если Р меется единичный сигнал на

прямом выходе элемента ИЛИ

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

Если при этом на входы 39 уг.трой- ства поступшот новые задания, то они записываются в блок 3, устанавливая триггер 18 через элемент ИЛИ 17 в единичное состояние.

Если все задания из блока 22 выбраны, что соответствует нулевым сиг- яНалам на его выходах, то на инверсном выходе элемента ИЛИ 19 имеется единичный сигнал, который поступает через элемент ИЛИ 11 на элемент И 7, разрешая прохождение тактового сигнала через него и поступление этого тактового сигнала на тактовый вход блока 3. Этот же единичный сигнал с инверсного выхода элемента ИЛИ 19 по.ступает на вторые входы элементов И 9, на первые входы которых поступает единичный сигнал с прямого выхода элемента ИЛИ 4, По тактовому сигналу прошедшему через элемент И 7 на тактовый вход блока 3, задание из блока 3 через открытые элементы И 9 и элементы ШШ 16 и т.д. подается на освободившийся процессор.

Если имеются еще освободившиеся процессоры (есть единичный сигнал на прямом выходе элемента ИЛИ 4), то по следующему тактовому сигналу из блока 3 через элементы И 9 и ИЛИ 16 выдается очередное задание на освободившийся процессор.

Если все задания из блока 3 также выданы в освободившиеся процессоры, но при этом еще остаются свободные процессоры, то на выходах блока 3 имеются нулевые сигналы, которые поступают на входы элемента ИЛИ 10. Нулевой сигнал с его прямого выхода поступает на третий вход элемента ИЛИ 5. На первый и второй входы элемента ИЛИ 5 поступают соответственно нулевой сигнал с прямого выхода элемента ИЛИ 19 и нулевой сигнал с инверсного выхода элемента ИЛИ 4. Тогда нулевой сигнал с прямого выхода элеме} та I-UTll 5 закрывает элементы И 13 а единичньм сигнал с инверсного выхода элемента ИЛИ 5 открывает элементы И 2, обеспеч1геая поступление

,

10

15

20

25

яа;мни}1 через элеметъ И 2 и lUlM 16

и т.д. непосредственно на свободные процессоры. Единичный сигнал с инверсного выхода элемента ШОТ 10 открывает элемент И 6 и по тактовому сигналу, поступающему на него, триггер 18 устанавливается в нулевое состояние,

Ecjni из бдюка 22 все задания не считываются и не остается свободных процессоров (единичный сигнал на ин- Е ерсном выходе элемента 1ШИ 4, от крываилцш элемен1Ъ1 И 8), то задания, накопленные в блоке 3 за время вы-.. дачи заданш из блока 22 в освободившиеся процессоры, по тактовым сигналам, поступающим через открытый элемент М 7 на блок 3, переписываются в блок 22. При этом нулевой сигнал с прямого выхода элемента ИЛИ 4 закрывает элементы И 9 (закрывается выход заданий через элементы И 9, lUlVi 16 на занятые процессоры) и элемент И 29 (закрывается доступ тактовых сигналов через элемент И 29 на триггер 30, находящийся в нулевом состоянии после окончания выдачи выделенных сигналов считывания с выходов блока 35, т.е. не вырабатываются сигналы 1 с прямого выхода триггера 30 и О с его инверсного выхода, необходимые для работы блока 32). После освобождения блока 3, что соответствует нулевым сигналам на его выходах и на входах элемента ИЛИ 10, единичным сигналом с инверсного выхода элемента ИЛИ 10, поступающим на вход элемента И 6, разрешается прохождение тактового сигнала через элемент И 6 на нулевой вход триггера 18. Единичный сигнал с его инверсного выхода поступает на первый вход элемента И 20, на третий вход которого подается также единичный сигнал с инверсного выхода элемента lUll-i 4. Таким образом, разрешается прохождение тактовых сигналов через элемент И 20 на тактовые входы сумматоров 28 и по ним осуществляет- 50 ся выполнение операцш суммирования с содержшым блока 22.

Если один или несколько процессоров освобождается (нулевой сигнал на инверсном выходе элемента ИЛИ-4), 55 то поступление тактовьЕХ сигналов на тактовые вхо;) сумматоров через элемент И 20 прекращается, процесс суммирования прекращается, новые посту30

35

40

45

пивших задания из блока 3 в блок 22 не поступают (вновь постушгвише задния накапливаются в блоке 3) и от- крывае гся элемент И 29, обеспечивая прохождение тактовых сигналов на единичный вход триггера 30 (установление его в единичное состояние). Таким образом обеспечивается работа блока 32, производящего выделение максимального значения, и выдача выбранных заданрш из блока 22 на освободившиеся процессоры

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

Устройство для распределения заданий процессорам, содержа1дее регистр готовности процессоров, первый элемент И, первый блок регистров, три группы элементов И, две группы элементов ItHH, три элемента ИЛИ, первую и вторую группы блоков элементов И, причем группа входов заданий устройства соединена с первыми входами элементов И первой и второй групп, выходы элементов И первой группы соединены с группой входов первого блока регистров, установочные входы регистра готовности процессоров подключены к соответствующим сигнальным входам устройства, управляющие Bxojflii блоков элементов И первой и второй групп соединены соответственно с инверсным и прямым выходами одноименных разрядов регистра готовности процессоров, группа выходов каждого блока элементов И первой группь соединена с группой входов следующего блока элементов И первой группь и группой входов следующего блока элементов И второй группы, группы выходов блоков элементов И второй группы соединены с группами входов одноименных элементов ИЛИ первой группы и группами информационных выходов устройства, выход каждого элемента ИЛИ первой группы соединен с нулевым входом одноименного разряда регистра готовности процессоров к прямым выходам которого подключены входы первого элемента ИЛИ, группа выходов первого блока регистров соединена с первыми входами элементов И третьей группы и выходами второго элемента ИЛИ; прямой выход кото рого соединен с первыми входами пер вого элемента И третьего элемента ИЛИ, второй вход первого элемента И

0

5

0

5

0

соединен с тактоБыь входом устройства, второй вход и выход тре тьего элемента ИЛИ соединены соотБетственно с с инве зсным выходом первого элемента ИЛИ и с вторыми входами элементов И первой группы, выход первого элемента И соединен с тактовым входом первого блока регистров, шшерсный выход третьего элемента КГШ соединен с вторыми входами элементов И второй ppynnbF, выходы которых соединены с первыми входами элементов ИЛИ второй группы, вторые входы которых соединены с выходами элементов И третьей группы, выходы элементов ИЛИ второй группы соединены с группами входов первых блоков элементов И первой и второй групп, о т л и ч а ю щ е е- с я тем, что, с целью расширения функциональных возможностей за счет организации дисциплины обслуживания заявок с динамическим приоритетом и учета важности заданий и времени их ожидания в очереди на обслуживание в мультипроцессорной шш многомашинной системе, в него введены второй блок регистров, четвертая и пятая группы элементов И, группа сумматоров, второй, третий, четвертый, пятый, шестой и седьмой элементы И,

40

45

50

55

блок выделения максимума, элемент задержки, первый и второй триггеры, причем выходь первого блока регистров соединены с первыми входами эле- 35 ментов И четвертой группы, выходы которых подключены к первой группе входов второго блока регистров, тактовый вход устройства соединен с первыми входами jBTOpoго J третьего и четвертого элементов И, выходы элементов И первой группы соединены с входами четвертого элемента ИЛИ, выход которого подключен к единичному входу первого триггера, нулевой вход которого соединен с выходом второго элемента И, инверсный выход первого триггера подключен к второму входу четвертого элемента И, третий вход которого соединен с инверсным выходом первого элемента ИЛ1-1, вторыми входами элементов И четвертой группы, первым входом пятох о элемента Ш1И и первым входом шестого элемента ИЛИ, выход пятого элемента ИПИ соединен с треть;iM входом первого элемента И, выход первого элемента ШБ-1 соединен с вторыг и входами элементов И трсгг/.-.ей групти и вторым

входом третьего элемента И, пара групп выходов регистров второго блока регистров соединена с группами входов соответствуюгдих сумматоров группы, выходы которых подключены к соответствующим группам входов каждого регистра второго блока регистров, первые группы выходов каждой пары групп выходов регистров второго бло на ре гистров подключены к входам седьмого элемента ИЛИ, прямой выход которого соединен с третьим входом третьего элемента ИЛИ и третьим входом третьего элемента И, инверсный выход седьмого элемента ИЛИ соединен с третьими входами элементов И третьей группы и вторым входом пятого элемента ИЛИ, выход четвертого элемента И соединен с тактовыми входами сумматоров группы, вторые группы ВБ1ХОДОВ

каждой пары трупп выходов второго блока регистров соединены с группой

с

0

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

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

V/ W

W

фи.2

66

л у

fiW