Устройство для распределения заданий процессорам
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК
ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) 21) 4406540/24 22) 08.04,88 46) 30.08.93. Бюл. N 32 72) В.А,Титов, В.П,Неверов В.Л.Гайдуков 56) Авторское свидетельство СССР 548859, кл. G 06 F 9/46, 1974. Авторское свидетельство СССР 1290322, кл, 6 06 F 9/46, 1985. 54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ АДАНИЙ ПРОЦЕССОРАМ 57) Изобретение относится к вычислитель-. ой технике и может быть использовано при рганизации вычислительного процесса по бработке пакета или потока задач с ограиченной очередью в многопроцессорной Изобретение относится к области выислительной техники и может быть испольовано при организации вычислительного роцесса по обработке пакета или потока адач с ограниченной очередью в многоп(оессорной вычислительной системе. Целью изобретения является расширеие функциональных возможностей за счет рганизации распределения задач с учетом зменения приоритетности задач в зависиости от времени ожидания обслуживания учетом функции штрафа). На чертеже представлена структурная ема устройства для распределения задаий процессорам, Устройство содержит (см. чертеж) групу первых регистров 11...1п, блоки элеменВ И 21 ..2n, ПЕРВЫЕ ЭЛЕМЕНТЫ ЗадЕржКИ 1„,3, триггеры 41„.4п, вторые регистры 1...5П, сумматоры накапливающего типа „„« Ы„„1837280 А1 вычислительной системе. Цель изобретения— расширение области применения устройства за счет организации распределения заданий с учетом изменения их приоритетов. Устройство для распределения заданий процессорам содержйт группу накапливающих сумматоров, группу дешифраторов, две группы блоков элементов И, две группы регистров, блок элементов ИЛИ, группу элементов задержки, группу триггеров, -две группы элементов И, группу элементов НЕ, элемент ИЛИ, элемент И. Устройство обеспечивает распределение задач исходного набора по процессорам вычислительной системы в соответствии с функцией штрафа за ожидание в очереди на решение. 1 ил. 61...6n, блоки элементов И 71...7n, дешифраторы 81...8n, элементы И 91...9>, элемент И 10, элементы НЕ 111...11п-1, элементы И 122...12n, элементы ИЛИ 13, элемент задержки 14, блок элементов ИЛИ 15, выходы 16 и 17, входы 18 и 19. В исходном состоянии все триггера 4ь регистры 1i, 5 и сумматоры накапливающего типа 6 (! = Т,п) находятся в нулевом состоянии. По входу 19 последовательно в устройство заносятся на регистры 1i номера заданий (задач или программ), а на сумматоры 6i — "веса" заданий. В качестве "веса задания" может быть взято, например, время реализации данной задачи. На триггер 4i заносится код единицы, свидетельствующий о необходимости решения i-ой задачи. На регистр 5i заносится код приращения, характеризующий степень важности зада1 1 ей IQQ (д 4 ! М leî 1О (> 1837286 чи, которая пропорциональна коду приращения, Таким образом в начале работы устройства при реализации полного пакета задач все триггеры 4i находятся в единичном состоянии. Дешифраторы 8 при наличии поло- ° жительного кода и отличного от нуля на сумматоре 61 обеспечивают появление на своем выходе нулевого сигнала, а при нуле. 80M или отрицательном коде на сумматоре 61 дешифратор 81 обеспечивает выработку единичного сигнала, который подается на первый вход элемента И 9ь Таким образом после занесения исходной информации на выходах элементов И 9i будут нулевые сигналы, следовательно, на прямом выходе элемента ИЛИ 13 (выход 16 устройства) бу-дет нулевой сигнал, а на инверсном выходе элемента ИЛИ 13 будет единичный сигнал, который подается на управляющий вход элемента И 10. Работа устройства начинается после подачи последовательности тактовых импульсов ко входу 18 на вход элемента И 10. С выхода элемента И 10 тактовые импульсы далее поступают на управляющие входы блоков элементов И 7i (1 = 1 n), после чего обратный код с выхода регистра 5i поступает через блок элементов И 7i на вход сумматора накапливающего типа 6 (к информационному входу блока элементов И 7i подсоединен инверсный выход регистра Ь). На сумматорах накапливающего типа 6 (1 = Т,п) происходит сложение двух кодов, первым из которых является код, хранящийся на сумматоре 6ь а второй код снимается с инверсного выхода регистра 5i и через открытый блок элементов И 7i поступает на второй вход сумматора бь Синхронизация работы сумматоров 6 осуществляется сигналом с выхода элемента задержки 14, который задерживает прохождение тактового сигнала на время передачи кода с выхода регистра 5 через блок элементов И 7ь Накопление соответствующих приращений иа сумматорах 6i происходит до тех пор, пока хотя бы на одном из них не окажется код, равный нулю или меньше нулл, после чего на выходе соответствующего ДЬшифрзтора 81 (I - 1,n) появится единичный сигнал, который далее поступает на первый .вход элемента И 91, на второй вход которого поступает единичный сигнал с выхода соответствующего триггера 41. Единичный сигнал с выхода элемента И 91 поступает далее на входы схемы приоритета, которая собрана на элементах НЕ 111...11 -> и элементах И 12р...12П. Эта схема обеспечивает появление единичного сигнала только на одном из своих выходов после поступления нескольких единичных сигналов на ее вход. При появлении единичного сигнала на выходе элемента И 121 g - 7,й) или на выходе элемента И 91 на выходе 16 устройства (на прямом выходе элемента ИЛИ 13) появляется единичный сигнал, свидетельствующий о выборе устройством номера очередной наиболее приоритетной задачи. Кроме того, низкий потенциал с инверсного выхода эле10 мента ИЛИ 13 запрещает прохождение тактовых импульсов через элемент И 10. Одновременно с появлением единичного сигнала на )-ом входе элемента ИЛИ 13 единичный сигнал поступает также на вхо15 ды соответствующих элементов задержки 31 и входы блока элементов И 2), в результате чего код номера задачи с выхода регистра 11 поступает через блок элементов ИЛИ 15 на выход 17 устройства (сигнал на выходе 16 20 устройства свидетельствует о выборе одной из задач пакета набора). Элемент задержки 31 обеспечивает задержку сигнала на время передачи кода номера наиболее приоритетной задачи на выход 17 устройства. По истечении некоторого времени на выходе элемента задержки 31 появляется единичный сигнал, который сбрасывает триггер 41 в нулевое состояние. С появлением нулевого сигнала на выходе триггера 41 и 30 на первом входе соответствующего блока элементов И 71 запрещается передача кода приращения с обратного выхода регистра 51 на вход сумматора 61. Одновременно нулевой сигнал с выхода триггера 41 запрещает 35 подачу единичного сигнала с выхода элемента И 91 на вход схемы приоритета, в результате, тактовые импульсы вновь будут поступать по входу 18 через открытый элемент И 10 на открытые блоки элементов И 40 7>(l =1,п,1 Nj) и с помощью элемента задержки 14 обеспечивать работу сумматоров накапливающего типа 6ь Работа устройства далее продолжается аналогичным образом, После выбора J-ой задачи на решение в 45 ЭВМ операционная система можетна место 1-ой задачи дополнить очередь решаемых задач. Таким образом, технико-экономической эффект от предложенного устройства— 50 обеспечивать распределение задач исходного набора по процессорам вычислительной системы в соответствии с функцией штрафа за ожидание в очереди на решение. Формула изобретения Устройство для распределения заданий процессорам, содержащее блок элементов ИЛИ, первую группу регистров, группу элементов задержки, группу триггеров, группу блоков элементов И, две группы элементов И, группу элементов НЕ, элемент ИЛИ и 1837286 лемент И, первый вход которого является актовым входом устройства, группа входов номера заданий которого соединена с инормационными входами соответствующих егистров первой группы, выходы которых оединены с первыми входами соответствуощих блоков элементов И группы, выходы оторых соединены с соответствующими ходами блока элементов ИЛИ группы, руппа выходов которого является группой ыходов устройства, группа входов признака аданйя которого соединена с единичными ходами соответствующих триггеров групы, нулевые входы которых соединены с ыходами соответствующих элементов заержки группы, инверсный выход элемента ЛИ соединен со вторым входом элемента, выходы триггеров группы соединены с ервыми входами соответствующих элелентов И первой группы, выход К-го элемена И первой группы (К = 1, M-1, M — число дновременно обслуживаемых заданий) содинен с входом К-го элемента HE группы, выход которого соединен с К-ми входами лементов И второй группы с К-го по (M-1)-й, выход (К+1)-го элемента И первой группы соединен с (К+1)-M входом К-го элемента И второй группы, выход которого соединен с входом (К+1)-го элемента задержки группы и вторым входом (К+1)-го блока элементов И .группы, а также с соответствующим входом,-элемента ИЛИ, выходпервого элемента И первой груйпы соединен с соответствующим входом элемента ИЛИ, входом первого элемента задержки группы и вторы входом 5 первого блока элементов И группы, о т л ич а ю щ е е с я тем, что, с целью расширения области применения устройства эа счет организации распределения заданий с учетом изменения их приоритетов, в него введены 10 группа накапливающих сумматоров, группа дешифраторов, вторая группа блоков элементов И, вторая группа регистров, входы которых соединены с группой входов веса задания устройства, rpynna входов приори15 тета задания которого соединена с первыми информационными входами соответствующих накапливающих сумматоров группы, выходы которых соединены с входами соответствующих дешифраторов, выходы кото20 рых соединены с вторыми входами соответствующих элементов И первой группы, выходы триггеров группы соединены с первыми входами соответствующих блоков элементов И второй группы, выходы которых 25 соединены с вторыми информационными входами соответствующих накапливающих сумматоров группы, синхровходов которых соединены с выходом элемента И, выходы регистров второй группы соединены с вторы30 ми входами соответствующих блоков элементов И второй группы.
