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

(Л

С

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

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

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

Устройство содержит (см. чертеж) груп- у первых регистров 1i...1n, блоки элемен- ов И 2i...2n, первые элементы задержки 1,..3п, триггеры 4i,..4n, вторые регистры 1...5П, сумматоры накапливающего типа

6i...6n, блоки элементов И 7i..,7n, дешифраторы 8i...8n, элементы И 9i...9n, элемент И 10, элементы НЕ 11i...11n-i, элементы И 122...12П, элементы ИЛИ 13, элемент задержки 14, блок элементов ИЛИ 15, выходы 16 и 17, входы 18 и 19.

В исходном состоянии все триггера А, регистры 1i, 5i и сумматоры накапливающего типа 6j (I 1,п) находятся в нулевом состо- янии. По входу 19 последовательно в i устройство заносятся на регистры 1i номера заданий (задач или программ), а на сумматоры 6i - веса заданий. В качестве веса задания может быть взято, например, время реализации данной задачи. На триггер 4i заносится код единицы, свидетельствующий о необходимости решения i-ой задачи. На регистр 5i заносится код приращения, характеризующий степень важности задасосо

00

О

.10

15

и, которая пропорциональна коду прираения.

Таким образом в начале работы устройтва при реализации полного пакета задач все триггеры 4| находятся в единичном со- стояими. Дешифраторы 8 при наличии поло- ж ительного кода и отличного от пуля на сумматор© 6) обеспечивают появление на споем пыходе нулевого сигнала, а при нуле- вом или отрицательном коде на сумматоре 6j дешифратор 8i обеспечивает выработку единичного сигнала, который подается на первый вход элемента И 9|. Таким образом после занесения исходной информации на выходах элементов И 9i будут нулевые сигналы, следовательно, на прямом выходе элемента ИЛИ 13 (выход 16 устройства) будет нулевой сигнал, а на инверсном выходе элемента ИЛИ 13 будет единичный сигнал, который подается на управляющий вход 20 элемента И 10.

Работа устройства начинается после подачи последовательности тактовых импульсов ко входу 18 на вход элемента И 10. С выхода элемента И 10 тактовые импульсы далее поступают на управляющие входы блоков элементов И 7| ( 1,п), после чего обратный код с выхода регистра 5i поступает через блок элементов И 7i па вход сумматора . накапливающего типа GI (к информационному входу блока элементов И 7i подсоединен инверсный выход регистра 5i). На сумматорах накапливающего типа 6i (I Тп) происходит сложение двух кодов, первым из которых является код, хранящийся на сумматоре 6i, а второй код снимается с инверсного выхода регистра 5i и через открытый блок элементов И 7i поступает на второй вход сумматора 6i. Синхронизация работы сумматоров 6i осуществляется сиг- 40 налом с выхода элемента задержки 14, который задерживает прохождение тактового сигнала на время передачи кода с выхода регистра 5i через блок элементов И 7i.

Накопление соответствующих приращений на сумматорах 6i происходит до тех пор, пока хотя бы на одном из них не окажется код, равный нулю или меньше нуля, после чего на выходе соответствующего дешифратора 8j 0 ° Tin) появится единичный 50 сигнал, который далее поступает на первый вход элемента И 9j, на второй вход которого поступает единичный сигнал с выхода соответствующего триггера .Единичный сиг- нэл с выхода элемента И 9j поступает далее 55 на входы схемы приоритета, которая собрана ка элементах НЕ 11i...11n-i и элементах И 122...12П. Эта схема обеспечивает появление единичного сигнала только на одном из своих выходов после поступления несколь25

30

35

45

0

5

0

0

0 55

5

0

5

5

ких единичных сигналов на ее вход. При появлении единичного сигнала на выходе элемента И 12j (| « 2,п) или на выходе элемента И 9i на выходе 16 устройства (на прямом пыходе элемента ИЛИ 13) появляется единичный сигнал, свидетельствующий о выборе устройством номера очередной наиболее приоритетной задачи. Кроме того, низкий потенциал с инверсного выхода элемента ИЛИ 13 запрещает прохождение тактовых импульсов через элемент И 10.

Одновременно с появлением единичного сигнала на j-ом входе элемента ИЛИ 13 единичный сигнал поступает также на входы соответствующих элементов задержки 3j и входы блока элементов И 2J, в результате чего код номера задачи с выхода регистра 1j поступает через блок элементов ИЛИ 15 на выход 17 устройства (сигнал на выходе 16 устройства свидетельствует о выборе одной из задач пакета набора). Элемент задержки 3j обеспечивает задержку сигнала на время передачи кода номера наиболее приоритетной задачи на выход 17 устройства.

По истечении некоторого времени на выходе элемента задержки 3j появляется единичный сигнал, который сбрасывает триггер 4j в нулевое состояние. С появлением нулевого сигнала на выходе триггера 4j и на первом входе соответствующего блока элементов И 7j запрещается передача кода приращения с обратного выхода регистра 5j на вход сумматора 6j. Одновременно нулевой сигнал с выхода триггера 4j запрещает подачу единичного сигнала с выхода элемента И 9 на вход схемы приоритета, в результате, тактовые импульсы вновь будут поступать по входу 18 через открытый элемент J4J 0 на открытые блоки элементов И 7i(i 1,n, I j) и с помощью элемента задержки 14 обеспечивать работу сумматоров накапливающего типа 6i. Работа устройства далее продолжается аналогичным образом.

После выбора j-ой задачи на решение в ЭВМ операционная система может на место j-ой задачи дополнить очередь решаемых задзч.

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

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

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

Элемент И, первый вход которого является тактовым входом устройства, группа входов номера заданий которого соединена с ин- юрмационными входами соответствующих «егистров первой группы, выходы которых оединены с первыми входами соответству- ощих блоков элементов И группы, выходы которых соединены с соответствующими ходами блока элементов ИЛИ группы, руппа выходов которого является группой выходов устройства, группа входов признака адания которого соединена с единичными зходами соответствующих триггеров груп- 1Ы, нулевые входы которых соединены с зыходами соответствующих элементов задержки группы, инверсный выход элемента /1ЛИ соединен со вторым входом элемента /I выходы триггеров группы соединены с первыми входами соответствующих элементов И первой группы, выход К-ro элемен- га И первой группы (К 1, М-1, М - число одновременно обслуживаемых задании) соединен с входом К-ro элемента НЕ группы, выход которого соединен с К-ми входами элементов И второй группы с К-ro по (М-1)-и, выход (К-И)-го элемента И первой группы соединен с (К-Н )-м входом-Кто элемента И второй группы, выход которого соединен с входом (К-И)-го элемента задержки группы и вторым входом (К+1)-го блока элементов И (группы, а также с соответствующим входом

0 1Ь 30

5

20

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