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

 

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

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

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

РЕСПУБЛИК (51)4 С 06 Р 9 46

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

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

ОПИСАНИЕ ИЗОБРЕТЕНИЯ/ -, К ABTOPCHQMV СВОДЕТЕПЬСТВУ уд ., (21) 4186165/24-24 (22) 23. 01. 87 (46) 30.07.88. Вюл. Ф 28 (72) В.Н.Дроник и A.È.Êoâàëåâñêèé (53) 681.325 (088.8) (56) Авторское свидетельство СССР

Н 866560ь кл G 06 F 9/46, 1981.

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

У 1111165, кл. С 06 F 9/46, 1983, про то тип. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

ЗАДАНИЙ ПРОЦЕССОРАМ (57) Изобретение относится к вычислительной технике и может быть использовано для распределения задач аппаратным путем в многопроцессорных системах. Цель изобретения — расширение функциональных возможностей за счет организации обслуживания заявок с динамическим приоритетом и учета важности заданий и времени их ожида.ния в очереди на обслуживание в мультипроцессорной или многомашинной системе. Устройство содержит блоки реги„„SU„„>4>З6ЗО А1 стров, блок выделения максимума, регистр готовности процессоров, сумматоры, триггеры, элементы И, ИЛИ.

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

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

И 14 открыты, а элементы И 13 закрыты.

На входы 39 поступают задания.

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

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

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

41 устройства появляется нулевой сигнал и т.д.

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

Очередное задание поступает на один

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

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

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

Устройство, (фиг 1 и 2) содержит группы 1 и 2 элементов И, блок 3 регистров, элементы ИЛИ 4 и 5, элементы

И 6 и 7, группы 8 и 9 элементов И, элементы ИЛИ 10 и 11, триггеры 12 регистра готовности процессоров, группы 13 и14 блоков элементов И, группы 15 и 16 элементов ИЛИ, элемент ИЛИ, 17, триггер

18, элемент ИЛИ 19, элемент И 20, выходы 21 элементов И 8. блок 22 30 регистров, группы выходов 23 и 24 блока 22, группы входов 25 бпока 22, группу входов 26 разрешения считывания блока 22, группу выходов 27 блока 22, группу сумматоров 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, С его инверсного выхода нулевой сигнал поступает на второй вход элемента

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

Элементы И 2 открыты единичным сигналом с инверсного выхода элемента

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

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

Так как блок 22 регистров свободен, то с его группы выходов 23 нуле5 вые сигналы поступают на входа» элемента ИЛИ 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 имеется еди. 45 ничный сигнал, который поступает на третьи выходы элементов ИЛИ 5 и И 7.

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

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

По этим тактовым сиг»»а»»ям проходит считывл»»»е поступающих заданий из блока 3 через открытые элементы

И 8 в блок 22, После счить»вания в блок 22 всех заданий на выходах блока появится нулевой сигнал. На первьп» вход элемента И 6 поступает единичный сигнал с инверсного выхода элемента ИЛИ 10 открывая элемент

И 6 для прохождения тактовых сигналов. Поступивший тактовый сигнал устанавливает через элемент И б в нулевое состояние триггер 18. Единичный сигнал поступает на первый вход элемента И 20 с инверсного выхода триггера 18 и разрешает прохождение тактовых сигналов через элемент И 20. Разряды 1 — m каждого регистра блока предназначены для хранения кода номера задания, разряды (m + 1) — к предназначены для хранения кода признака приоритета данного задания, а разряды (к + 1) (к +

+ n) используются для хранения результата суммирования (состояния соответствующе го сумматора 28) .

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

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

Каждому регистру блока 22 поставлен в соответствие свой сумматор 28.

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

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

28 и запись результата суммирования

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

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

Если на входы 39 устройства поступает новое задание, то оно записывается через открытые элементы И 1 в блок

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

При этом единичным сигналом с инверсного выхода триггера 18 возобновляется поступление тактовых сигналов через элемент И 20 на тактовые входы сумматоров. После этого процесс, суммирования возобновляется.

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

ИЛИ 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.

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

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

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

Описанный алгоритм с помощью дву— мерной итеративной сети размером 4х х4 реализуется следующим образом.

Допустим, что на соответствующие входы 34 блока 32 поступают сигналы

1,1,0,0 которые, в свою очередь, поступают на входы 43 соответствую}цих узлов 42 пе рвой строки матрицы. Н а входы 43 узлов 4? второй строки матрицы поступают соответственно сигналы 1,1,0,1 с входом 34 блока 32 на входы 43 узлов 42 третьей строки мат-15 рицы сигналы 1,1,0,1 с входов 34 блока 32,на входы 43 узлов 42 четвертой строки матрицы — сигналы 0,1,0, 1 с входов 34.

В исходном состоянии на вход 35 блока 32 и далее на входы 46 первого столбца матрицы подается сигнал

"0" (с прямого выхода триггера 30), который поступает на входы элементов

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

На вход ЗЗ блока 32 и далее на входы 44 узлов 42 первой строки подается сигнал "1" с инверсного выхода триггера 30, Сигнал "1" с прямого выхода триггера 30 появляется в том случае, 40 если свободен хотя бы один процессор, т.е. с прямого выхода элемента

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

50 которого появляется сигнал "1".

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

На вход 34 блока 32 а следова11

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

«торой вход которого поступает сиг}}ял "1" с выхода 43 узла 42 . На

11 и выходе элемента И 56 будет единичный сигнал, который поступает на вход элемента ИЛИ 58, а с его выхода— на выход 4?, узла 42 и далее на вход 461 следующего узла 42 первой строки. Таким образом, данная строка выделяется для дальнейше го просмотра на следую}цем шаге.

Единичный сигнал с выхода элемента И 56 узла 421, поступает также на вход элемента KIII 57, на второй вход которого поступает сигнал "0", поступивший на вход 44,„узла 42, . Таким образом, единичный сигнал с выхода этого элемента ИЛИ 57 поступает на вход элемен та KIH 57 узла 42 } и далее этот сигнал точно также проходит весь столбец по вертикали через элементы ИЛИ 57 ячеек этого столбца и появляется на выходе 48 последней ячейки первого столбца. Этот единичный сигнал поступает íà Вход элемента HF. 54,, и нулевой сигнал с его выхода поступает на входы 45 узлов

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

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

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

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

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

Таким образом, ня выходе 47„узла 42„имеется единичный сигнал; на выходе 47 узла 42 — единичный сиг2! 2! нал; на выходе 47, узла 42 з! — единичный сигнал, а на выходе 47<1 узла 42 — нулевой сигнал, причем этот нулевой сигнал поступает на вход

46 y2 узла 42 2, закрывает элементы

И 55 H 56 этого узла, вызывая появление нулевого сигнала на его выходе

47. Далее этот нулевой сигнал поступает на вход 46 узла 42 1 и т.д.

Таким образом, этот нулевой сигнал, закрывает все последующие узлы 42 данной строки и исключает данную строку из дальнейшего анализа.

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

42 32 имеются единичные сигналы

Й я входы 43 узлов 42 третьего столбца поданы в се нулевые сигна,гп>, следовательно, элемен ты узлов тре тьего столбца И 56, на вторые входы ко то рых по ступают э ти нулевые сиги а.г|ы с входа 43 соответствующих узлов., 30 оказываются закрыть!ми, на выходах элемен то в И 5 6 присутс тв уе т нулевой сигнал, который поступает на первый вход соответствующих элементов И|И 57.

Таким о бразом, нулевой сигнал, подан- 35 ный на вход 44 узла 42 первой строки, проходит без изменения через столбец по вертикали (через элементы ИЛИ 57 ячеек третьего столбца) и с выхода 48 поступает на элемент 40

ИЕ 54» а с его выхода единичный сигнал) подается на первые входы эле, ментов И 55 узлов третьего столбца (элементы И 56 всех узлов третьего столбца закрыты). На вторые входь! д5 элементов И 55 узлов гретьего столбца подаются соответствующие сигналы с выходов узлов соответствующих строк предыдуще ro столбца.

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

НЯ выходах 47 узлов 42 4?

42 присутствуют единичные сигналы.

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

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

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

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

Каждому регистру блока 22 (входу

26) соответствует свой выход 36 блока 32. На выделенном выходе 36 блока

32, соответствующем регистру блока

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

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

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

30, который при этом устанавливается в нулевое состояние и блокирует работу блока 32.

По следую|цемg Tяк ° Овому сигналу (p сли имее тся с;!! гн !! !!!ь!й си Гнал ня

1413630 прямом выходе элемента ИЛИ 4, свиде-.— тельствующий о наличии освободившихся процессоров) процесс поиска максималь«ого значения результирующей суммы в блоке 32 повторяется и происхо5 дит выдача следующего выбранного задания из блока 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 посту«ают соответствен- 50 но нулевой сигнал с прямого выхода элемента ИЛИ 19 и нулевой сигнал с инверсного выхода элемента ИЛИ 4.

Тогда нулевой сигнал с прямого выхо— да элемента ИЛ1 5 закрывает элементы 55

И 1, а единичный сигнал с и»версного выхода элемен та ИЛИ 5 открыв ае т элементы И 2, обеспечивая поступление зада»ий через э..кме»ты И 2 и ИЛИ 16 и т.ii »епс средстве»«î на свободные

»роцес<оры. Еди»ичшж сигнал с инверс»ого выхода элемента ИЛИ 10 открывает элеме«т И 6 и Ilo тактовому сиг»алу, »оступающему на него, триггер 18 уста»авливается в нулевое состо я»ие.

Если из блока 22 все задания не считыв «ются и не ос тает ся свободных процессоров (единич»ый сиг«ал на инверсном выходе элемента ИЛИ 4, QT крывающий элементы И 8), то задания, »ако«ле»»ые в блоке 3 за время вы-. дачи зада»пй пз блока 22 в освободившиеся процессоры, по тактовым сигналам, поступающим через открытый эле-. мент П 7 »а блок 3, переписываются в блок 22. При этом нулевой сигнал с прямого выхода элемента ИЛИ 4 закрывает элементы И 9 (закрывается выход зада»ий через элементы И 9, ИЛИ 16 «а занятые процессоры) и элемент И 29 (закрывается доступ тактовых сигналов через элемент И 29 на триггер 30, находящийся в нулевом состоянии после окончания выдачи выделенных сигналов считывания с выходов блока 35, т.е. не вырабатываются сигналы "1" с прямого выхода триггера 30 и "0" с его инверсного выхода, необходимые для работы блока

32). После освобождения блока 3, что соответствует нулевым сигналам на его выходах и на входах элемента

ИЛИ 10, единичным сигналом с инверсного выхода элемента ИЛИ 10, поступающим на вход элемента И 6, разрешается прохождение тактового сигнала через элемент И 6 на нулевой вход триггера 18. Единичный сигнал с еro инверсного выхода поступает на первый вход элемента И 20, на третий вход которого подается также единичный сигнал с инверсного выхода элемента ИЛИ 4. Таким образом, разрешается прохождение тактовых сигналов через элемент И 20 на тактовые входы сумматоров 28 и по ним осуществляется выполнение операций суммирования с содержюьм блока 22.

Если один или несколько процессоров о сво бождае тся (нулевой сигнал на инверсном выходе элемента ИЛИ-4), то поступление тактовых сигналов на тактовые входьi сумматоров через элемент И 20 прекращается, процесс суммирон ан ия пре кращается, новые по сту1 4 l 3 () 3! ) пивших задания из блока 3 в блок 22 не поступают (внов» поступившие задания накапливаются в блоке 3) и открывается элемент И 29, обеспечивая прохождение тактовых сигналов на единичный вход триггера 30 {установление его в единичное ссстояние).

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

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

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

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

ИЛИ, второй вход перво о элемента И сое ливен с та к тош!и EB xo 10M ус трои с т ва, второй вход и выход трс тьего элемента ИЛИ соединены соответственно с с инверсным выходом перво1 элемента

ИЛИ и с вторыми входами элементов И первой группы, выход первого элемента И соединен с fdêòîâûì входом первого блока регистров, инверсный выход третьего элемента ИЛИ соединен с вторыми входами элементов И второй группы, выходы которых соединены с первыми входами элементов ИЛИ второй группы, вторые входы которых соединены с выходами элементов И третьей группы, выходы элементов ИЛИ второй группы соединены с группами входов первых блоков элементов И первой и второй групп, о т л и ч а ю щ е. ес я тем, что, с целью расширения функциональных возможностей за счет организации дисциплины обслуживания заявок с динамическим приоритетом и учета важности заданий и времени их ожидания в очереди на обслуживание в мультипроцессорной или многомашин— ной системе, в него введены второй блок регистров, четвертая и пятая группы элементов И, группа суммато— ров, второй, третий, четвертый, пятый, шестой и седьмой элементы И, блок выделения максимума, элемент задержки, первый и второй триггеры, причем выходы первого блока регистров соединены с первыми входами элементов И четвертой группы, выходы которых подключены к первой группе входов второго блока регистров, тактовый вход устройства соединен с первыми входами в торо го,, третье го и четвертого элементов И, выходы элементов И первой группы соединены с входами четвертого элемента HIM выход ко то ро го подключен к единичному входу первого триггера, нулевой вход которого соединен с выходом второго элемента И, инверсный выход первого триг re ра подключен к в то рому входу четвертого элемента И, третий вход которого соединен с инверсным выходом первого элемен та И. И, в то рыми входами элементов И четвертой группы, первым входом пятого элемента

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

ИЛИ, выход пятого элемента ИЛИ соединен с треть м Bxoäoë. первого элемента И, прям и выход первого элемента ИЛИ соединен с вторыми входами элементов И третей группы и вторым

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

ИЛИ второй группы.

141 3630!

413630

1413630

Составитель М.Кудряшов

Техред Л.Олийнык

Корректор Г. Решетник

Редактор Л. Пч елин с кая

Подписное

Аираж 704

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

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

Заказ 3787/52

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