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

 

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

Изобретение относится к вычислительной технике.

Задачей изобретения является расширение области применения устройства.

Структурная схема устройства представлена на чертеже.

Устройство содержит блок 1 управления, первый 2, второй 3 и третий 4 регистры сдвига, блок сумматоров 5, первый 6 и второй 7 элементы задержки, первый элемент И 8, элемент ИЛИ 9, первый блок элементов И 10, второй блок элементов И 11, блок 12 выделения минимального числа, первый 13, второй 14 и третий 15 формирователи импульсов, схему 16 сравнения, первый 17 и второй 18 триггеры, генератор 19 импульсов, второй 20 и третий 21 элементы И, группу регистров 22, группу 23 блоков элементов И, третий блок элементов И 24, блок 25 элементов ИЛИ, дешифратор 26, четыре входа 27-30 и выход 31.

Устройство работает следующим образом.

В исходном состоянии регистры 2, 3, 4, 22 обнулены. В i-м (i ) сумматоре-вычитателе блока 5 хранится код времени ожидания начала обслуживания в очереди к i-му процессору вычислительной системы. Устройство распределяет задания на те процессоры вычислительной системы, время ожидания начала обслуживания в очереди к которым является минимальным.

В работе устройство можно выделить два этапа.

На первом этапе производится выбор достаточного для обслуживания поступающего задания количества процессоров, время ожидания начала обслуживания в очереди к которым является минимальным. По входам 27 и 28 устройства соответственно в регистры 4 и 3 записываются код числа, необходимого для выполнения задания процессов, и код типа задания. По входам 30 в j-й (j где m число типов заданий) регистр 22 записывается код среднего времени обслуживания t_j заявки j-го типа. Код типа задания j из регистра 3 дешифруется дешифратором 26, и разрешается прохождение кода среднего времени обслуживания t_j заявки j-го типа из j-го регистра 22 на информационный вход всех блоков элементов И 24. Триггер 18 устанавливается в единичное состояние, и через элемент И 21 сигнал с генератора 19 импульсов поступает на запуск блока 12. Блок 12 обеспечивает выбор унитарного кода номера процессора вычислительной системы (например, код 00000100 соответствует третьему процессору восьмипроцессорной системы), код времени ожидания начала обслуживания в очереди к которому является минимальным (структурная схема и работа устройства для выбора экстремального числа приведены в авт. св. СССР N 752326, кл. G 06 F 7/02, 1980). На информационных выходах блока 12 хранится код номеров процессоров, время ожидания начала обслуживания к которым является минимальным, и записывается в регистр 2. Если код числа необходимых процессоров превышает код числа выбранных, то из числа невыбранных для распределения процессоров снова выбирается код номеров процессоров, время ожидания начала обслуживания в очереди к которым является минимальным. При этом число выбранных номеров процессоров увеличивается. Если код числа необходимых процессоров не превышает числа выбранных, то сигнал с выхода схемы 16 сравнения устанавливает триггер 17 в единичное состояние, а триггер 18 в нулевое. При этом запрещается работа блока 12. На этом первый этап работы устройства заканчивается.

На втором этапе производится распределение задания для обслуживания между выбранными процессорами вычислительной системы. Единичный уровень с единичного выхода триггера 17 разрешает прохождение импульсов с генератора 19 импульсов через элемент И 20 на входы элементов И 10. При этом на выходах некоторых элементов И 10 появляются сигналы, которые разрешают прохождение кода типа задания через соответствующие блоки элементов И группы 11 на соответствующие выходы 31 устройства. Номер выхода 31 определяется совпадением одноименных единичных разрядов в регистрах 2 и 4. С выходов элементов И 10 единичные сигналы поступают на обнуление соответствующих триггеров регистров 2 и 4 и на управляющие входы блоков элементов И 24. При этом разрешается запись кода среднего времени обслуживания t_j заявки j-го типа (из j-го регистра 22) в соответствующие сумматоры-вычитатели 5. На вычитающий вход i-го сумматора-вычитателя 5 по i-му входу 29 устройства поступает код t_j после обслуживания заявки j-го типа i-м процессором системы. Если при этом в регистре 4 остались триггеры в единичном состоянии, то задержанные элементом 6 задержки импульсы продвижения поступают с генератора 19 импульсов до тех пор, пока регистр 4 не будет полностью обнулен. При этом триггер 17 устанавливается в нулевое состояние и запрещает прохождение импульсов продвижения и работу элементов И 10, сигнал с выхода элемента И 8 обнуляет регистры 2 и 3. Это означает, что задание распределено среди процессоров, время ожидания начала обслуживания в очереди к которым является минимальным. На этом работа устройства заканчивается.

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

УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ В ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ, содержащее блок управления, три регистра сдвига, два элемента задержки, элемент И, элемент ИЛИ, первый блок элементов И, второй блок элементов И, блок выделения минимального числа, блок управления содержит три формирователя импульсов, схему сравнения, два элемента И, два триггера, генератор тактовых импульсов, вход числа процессоров устройства является информационным входом первого регистра сдвига, выход первого разряда которого является входом последнего разряда этого регистра, группа нулевых выходов первого регистра сдвига подключена к группе входов элемента И, выход которого соединен с входами обнуления второго и третьего регистров сдвига и входом первого формирователя импульсов, выход которого подключен к нулевому входу первого триггера, единичный выход которого соединен с первым входом первого элемента И блока управления, второй вход которого подключен к выходу генератора тактовых импульсов и первому входу второго элемента И, а выход к входу первого блока элементов И и входу первого элемента задержки, выход которого соединен с входом управления сдвигом первого регистра сдвига, группа единичных выходов которого подключена к первой группе входов первого блока элементов И и к группе входов элемента ИЛИ, выход которого соединен с входом второго формирователя импульсов, выход которого подключен к единичному входу второго триггера, единичный выход которого соединен с вторым входом второго элемента И блока управления, выход которого подключен к входу пуска блока выделения минимального числа и входу второго элемента задержки, выход которого соединен с входом управления сдвигом третьего регистра сдвига, информационный вход которого подключен к выходу блока выделения минимального числа и входу второго элемента задержки, выход которого соединен с входом управления сдвигом третьего регистра сдвига, информационный вход которого подключен к выходу блока выделения минимального числа, а группа нулевых выходов подключена к второй группе входов первого блока элементов И, к группе установочных входов блока выделения минимального числа и первой группе входов схемы сравнения, вторая группа входов которой соединена с группой единичных выходов первого регистра сдвига, а выход с входом третьего формирователя импульсов, выход которого подключен к нулевому входу второго триггера и единичному входу первого триггера, выход первого блока элементов И соединен с нулевыми входами первого и третьего регистров сдвига и первым входом второго блока элементов И, выход которого является выходом устройства, а второй вход подключен к выходу второго регистра сдвига, информационный вход которого является входом типа задания устройства, группа единичных выходов третьего регистра сдвига соединена с группой входов сброса блока выделения минимального числа, отличающееся тем, что в устройство введены группа регистров, блок сумматоров, третий блок элементов И, группа блоков элементов И, блок элементов ИЛИ и дешифратор, причем входы времени обслуживания группы входов устройства является информационными входами регистров группы, выходы которых подключены к первым входам блоков элементов И группы, вторые входы которых соединены с выходами дешифратора, а выходы с входами блока элементов ИЛИ, выход которого подключен к первому входу третьего блока элементов И, второй вход которого соединен с выходом первого блока элементов И, а выход с суммирующим входом блока сумматоров, выход которого подключен к информационному входу блока выделения минимального числа, а вычитающий вход блока сумматоров является входом времени ожидания начала обслуживания устройства, выход второго регистра сдвига соединен с входом дешифратора.

РИСУНКИ

Рисунок 1