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

(19) 6 Г 9/46 Ян 1 ЛЕНИЯ ислитель-, вано при цесса по ч с огра- ессорной ршвей 1 Оо Сд а- И, деш элем менты Инт задерыходы 16 М ОС 1 1 р, (Э ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕВЕДОМСТВО СССР(ГОСПАТЕНТ СССР) 21) 4406540/2422) 08.04,8846) 30.08.93. Бюл. Ит 3272) В.А,Титов, В.П,НеверовВ.Л.Гайдуков56) Авторское свидетельство ССС548859, кл. 6 06 Р 9/46, 1974.Авторское свидетельство ССС1290322, кл, 6 06 Р 9/46, 1985,54) УСТРОЙСТВО ДЛЯ РАСПРЕДАДАНИЙ ПРОЦЕССОРАМ57) Изобретение относится к вычой технике и может быть использорганизации вычислительного пробработке пакета или потока задаиченной очередью в многопроц Изобретение относится к области выислительной техники и может быть испольовано при организации вычислительного роцесса по обработке пакета или потока адач с ограниченной очередью в многопроессорной вычислительной системе.Целью изобретения является расширеие функциональных возможностей за счет рганизации распределения задач с учетом зменения приоритетности задач в зависиости от времени ожидания обслуживания учетом функции штрафа).На чертеже представлена структурная ема устройства для распределения задаий процессорам,Устройство содержит (см. чертеж) групу первых регистров 111 п, блоки элемен- В И 212 п, ПЕРВЫЕ ЭЛЕМЕНТЫ ЗадЕржКИ 1,3 п, триггеры 414 п, вторые регистры 15 п, СуММатсрЫ НаКаПЛИВаЮщЕГО тИПа вычислительной системе. Цель изобретения - расширение области применения устройства за счет организации распределения заданий с учетом изменения их приоритетов. Устройство для распределения заданий процессорам содержйт группу накапливающих сумматоров, группу дешифраторов, две группы блоков элементов И, две группы регистров, блок элементов ИЛИ, группу элементов задержки, группу триггеров, две группы элементов И, группу элементов НЕ, элемент ИЛИ, элемент И. Устройство обеспечивает распределение задач исходного набора по процессорам вычислительной системы в соответствии с функцией штрафа за ожидание в очереди на решение. 1 ил,616 п, блоки элементов И 717 п торы 818 п, элементы И 919 п, 10, элементы НЕ 11111 п, эл 122."12 п, элементы ИЛИ 13, элем жки 14, блок элементов ИЛИ 15, и 17, входы 18 и 19. В исходном состоянии все триггера 41, регистры 1, 5 и сумматоры накапливающего типа 6 ( =Т,п) находятся в нулевом состоянии, По входу 19 последовательно вустройство заносятся на регистры 1 номера заданий(задач или программ), а на сумматоры 61 - "веса" заданий. В качестве "веса задания" может быть взято, например, время реализации данной задачи. На триггер 41 заносится код единицы, свидетельствующий о необходимости решения 1-ой задачи.На регистр 5 заносится код приращения, характеризующий степень важности зада 1837286чи, которая пропорциональна коду приращения,Таким образом о начале работы устройства при реализации полного пакета задачвсе триггеры 4 находятся о единичном состоянии, Дешифрзторы 81 при наличии поло-жительного кода и отличного от нуля цасумматоре 61 обеспечивают появление насооем выходе нулевогосигнала, а при нуле. вом или отрицательном коде на сумматоре61 дешифратор 81 обеспечивает выработкуединичного сигнала, который подается напервый вход элемента И 9 ь Таким образомпосле занесения исходной информации навыходах элементов И 9 будут нулевые сигналы, следовательно, на прямом выходеэлемента ИЛИ 13 (выход 16 устройства) бу дет нулевой сигнал, а на инверсном выходеэлемента ИЛИ 13 будет единичный сигнал,который подается ца управляющий входэлемента И 10.Работа устройства начинается послеподачи последовательности тактовых импульсов ко входу 18 на вход элемента И 10.С выхода элемента И 10 тактовые импульсыдалее поступают ца управляющие входыблоков элементов И 71 (1 = 1,п), после чегообратный код с выхода регистра 5 поступает через блок элементов И 7 ца вход сумматора накапливающего типа 6 (кинформационному входу блока элементов ИЪ подсоединен инверсный выход регистра Ь).На сумматорах накапливающего типа6 1 = Тй) происходит сложение доух кодов,первым из которых является код, хранящийся цз сумматоре 6 ь а второй код снимаетсяс инверсного выхода регистра 5 и черезоткрытый блок элементов И 7 поступает навторой вход сумматора бь Синхронизацияработы сумматоров 6 осуществляется сигналом с выхода элемента задержки 14, который задерживает прохождение тактовогосигнала на время передачи кода с выходарегисра Ь через блок элементов И 7 ьНакопление соответствующих приращений цз сумматорах 61 происходит до техпор, пока хотя бы на одном из них не окажется код, равный нулю или меньше цулл,после чего на выходе соответствующего Фшифрзтора 81 Д " 1,п) появится единичныйсигнал, который далее поступает на первый.вход элемента И 91, ца второй вход которогопоступает единичный сигнал с выхода соответствующего триггера 41. Единичный сигцзя с выхода элемента И 91 поступает далеена входы схемы приоритета, которая собрана цз элементах НЕ 111".11 пи элементахИ 12212 п, Эта схема обеспечивает появление единичного сигнала только на одном изсвоих выходов после поступления нескольких единичных сигналоо на ее вход. При появлении единичного сигнала на выходе элемента И 121 Ц - 2,й) или на выходе элемента И 91 ца выходе 16 устройства (ца прямом оыходе элемента ИЛИ 13) появляется единичный сигнал, свидетельствующий о выборе устройством номера очередной наиболее приоритетной задачи. Кроме того, низкий потенциал с инверсного выхода эле;лента ИЛИ 13 запрещает прохождение тактовых импульсов через элемент И 10.Одновременно с появлением единичного сигнала ца )-ом входе элемента ИЛИ 13 единичный сигнал поступает также ца охо ды соотоетст вующих элементов задержки 31и входы блока элементов И 2, в результате чего код номера задачи с выхода регистра 11 поступает через блок элементов ИЛИ 15 на выход 17 устройства (сигнал на выходе 16 20 устройства свидетельствует о выборе однойиз задач пакета набора). Элемент задержки 31 обеспечивает задержку сигнала на время передачи кода номера наиболее приоритетной задачи на выход 17 устройства.25По истечении некоторого времени навыходе элемента задержки 31 появляется единичный сигнал, который сбрасывает триггер 41 в нулевое состояние. С появлением нулевого сигнала на выходе триггера 41 и 30 ца первом входе соответствующего блокаэлемецтоо И 71 запрещается передача кода приращения с обратного выхода регистра 51 ца вход сумматора 61. Одновременно нулевой сигнал с выхода триггера 41 запрещает 35 подачу единичного сигнала с выхода элемента И 91 ца вход схемы приоритета, в результате, тактооые импульсы онооь будут поступать по входу 18 через открытый злелент И 10 на открытые блоки элементов И 40 71= 1,п,1 Ф Я и с помощью элемента задержки 14 обеспечивать работу сулматоров накапливающего типа 6 ь Работа устройства далее продолжается аналогичным образом,После выбора 1-ой задачи на решение в 45 ЭВМ операционная система можетца место)-ой задачи дополнить очередь решаемыхзадач.Таким образом, технико-экономическойэффект от предложенного устройства - 50 обеспечивать распределение задач исходного набора по процессорам вычислительной системы в соответствии с функцией штрафа за ожидание в очереди ца решение.Формула изобретения 55 Устройство для распределения заданийпроцессорам, содержащее блок элементовИЛЙ, первую группу регистров, группу эле- ментов задержки, группу триггеров, группу блоков элементов И, две группы элементов И, группу элементов НЕ, элемент ИЛИ илемент И, первый вход которого являетсяактовым входом устройства, группа входов номера заданий которого соединена с инормационными входами соответствующих егистров первой группы, выходы которых оединены с первыми входами соответствуощих блоков элементов И группы, выходы оторых соединены с соответствующими ходами блока элементов ИЛИ группы, руппа выходов которого является группойыходов устройства, группа входов признака аданйя которого соединена с единичными ходами соответствующих триггеров групы, нулевые входы которых соединены с ыходами соответствующих элементов заержки группы, инверсный выход элемента ЛИ соединен со вторым входом элемента , выходы триггеров группы соединены с ервыми входами соответствующих элелентов И первой группы, выход К-го элемена И первой группы (К = 1, 1-1, М - число дновременно обслуживаемых заданий) содинен с входом К-го элемента НЕ группы, выход которого соединен с К-ми входамилементов И второй группы с К-го по (М)-й, выход (К+1)-го элемента И первой группы соединен с (К+1)-м входом К-го элемента И второй группы, выход которого соединен с входом (К+1)-го элемента задержки группы и вторым входом (К+1)-го блока элементов И группы, а также с соответствующим входом, элемента ИЛИ, выход первого элемента Ипервой груйпы соединен с соответствующим входом элемента ИЛИ, входом первого элемента задержки группы и вторывходом 5 первого блока элементов И группы, о т л ич а ю щ е е с я тем, что, с целью расширения области применения устройства эа счет организации распределения заданий с учетом изменения их приоритетов, в него введены 10 группанакапливающих сумматоров, группадешифраторов, вторая группа блоков элементов И, вторая группа регистров, входы которых соединены с группой входов веса задания устройства, группа входов приори тета задания которого соединена с первымиинформационными входами соответствующих накапливающих сумматоров группы, выходы которых соединены с входами соответствующих дешифраторое, выходы кото рых соединены с вторыми входамисоответствующих элементов И первой группы, выходы триггеров группы соединены с первыми входами соответсгвующих блоков элементов И второй группы, выходы которых 25 соединены с вторыми информационнымивходами соответствующих накапливающих сумматоров группы, синхровходов которых соединены с выходом элемента И, выходы регистров второй группы соединены с втооы ми входами соответствующих блоков элементов И второй группы.