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

 

Изобретение.относится к вычислительной технике и может быть использовано в качестве аппаратного диспетчера программ, готовых к выполнению , для ,их распределения по процессорам многопроцессорной системы , предназначенной для управления сложными объектами в реальном времени . Цель изобретения - расширение функциональных возможностей устройства путем организации очередей заданий с равными приоритетами. Б устройство, содержащее блок анализа приоритетов процессоров, блок анализа приоритетов заданий и скему сравнения, введена группа элементов И, распределитель иммульсов и блок запоминания заданий, основным узлом которого является модуль оперативной памяти, каждая страница которой содержит группу заданий с равными приоритетами. Блок анализа приоритетов заданий содержит два дешифратора , группу триггеров, группу элементов И и шифратор. Это блок .выделяет наиболее приоритетное задание по групповому принципу. Положительный эффект достигается благодаря совместной работе блока запоминания заданий и блока анализа приоритетов заданий, что позволяет производить распределение заданий не только в соответствии с их приоритетами, но и распределение равноприоритетных заданий согласно очередности их поступления в устройство. 2 ил. с в (Л to о 00 со

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

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

РЕСПУБЛИК

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3947570/24-24 (22) 14.08.85 (46) 23.02.87. Бюл; № 7 (71) Институт технической кибернетики АН БССР (72) А.Г.Ярусов, M.М.Маханек и В.Е.Чернявский (53) 681.325(088.8) (56) Авторское свидетельство СССР

¹ 1111165, кл. G 06 F 9/46, 1984.

Авторское свидетельство СССР по заявке № 3727173, кл. С 06 F 9/46, 1984. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

ЗАДАНИЙ ПРОЦЕССОРАМ (57) Изобретение. относится к вычислительной технике и может быть использовано в качестве аппаратного диспетчера программ, готовых к выполнению, для их распределения по процессорам многопроцессорной системы, предназначенной для управления сложными объектами в реальном времени. Цель изобретения — расширение функциональных возможностей устрой„„SU„„1291983 А 1 (51)4 G 06 F 9/46 ства путем организации очередей заданий с равными приоритетами. В устройство, содержащее блок анализа приоритетов процессоров, блок анализа приоритетов заданий и схему сравнения, введена группа элементов

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

1291983

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

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

На фиг. 1 изображена структурная схема устройства;.на фиг. 2 — функциональная схема блока анализа приоритетов процессоров.

Устройство (фиг. 1) содержит блок

1 анализа приоритетов процессоров, схему 2 сравнения, группу элементов

И 3, блок 4 запоминания заданий,распределитель 5 импульсов, блок 6

25 анализа приоритетов заданий, группу запросных входов 7 устройства, группу кодовых входов 8 устройства, группу выходов 9 прерывания устройства, группу информационных входов 10 устройства, вход 11 синхронизации устройства, группу выходов 12 номера задания устройства. Блок 4 содержит регистры 13 и 1 4, коммутатор 15, модули 16-18 памяти, счетчик 19 и схему 20 сравнения, буквами а-л обозн»- 35 чены выходы распределителя 5, буквой м — выход схемы 2.

Блок 6 анализа приоритетов заданий содержит дешифраторы 21 и 22, гр группу триггеров 23, группу элементов И 24, шифратор 25.

Блок 1 содержит каналы 26, в каждом канале (кроме последнего) — первую и вторую группы элементов ИЛИ-НЕ

27 и 28, первую и вторую группы элементов ИЛИ 29 и 30. В последнем канале 26 содержится первая, вторая группы элементов ИЛИ-НЕ 27 и 28, группа элементов ИЛИ 29, группа элементов

ИЛИ-НЕ 31.

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

В системе постоянно имеется группа заданий, запуск которых (возбуждение готовности) производится по сигналам, поступающим на входы системы с датчиков объекта управления и от операторов, а также от ранее запущенных заданий (ведущих программных модулей) . В зависимости от взаимной срочности заданиям присвоены коды приоритетов. Задание, для которого возникла готовность к выполнению, передается на входы IO устройства в виде кода имени и кода приоритета этого задания и заносится в модуль 16 памяти. Из всех заданий, находящихся в устройстве и ждущих предоставления им процессоров, блоки 4 и 6 выделяют задание с высшим приоритетом, Код приоритета этого задания поступает на вход схемы 2 сравнения.

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

Коды приоритетов всех процессоров поступают на входы 8 устройства.

Блок" 1 анализа приоритетов процессоров из числа исправных процес. соров выделяется процессор с низшим приоритетом. Это характеризуется появлением логической единицы на одном из выходов блока 1, который позиционно соответствует выделенному процессору. Код приоритета выделенного процессора поступает на другои вход схемы 2 сравнения, где сравнивается с кодом приоритета выделенного задания, Если код приоритета выделенного наиболее приоритетного задания,готового к выполнению, меньше или равен коду приоритета выделенного наименее приоритетного процессора,устройство не вырабатывает никаких сигналов до тех пор, пока в него не поступает более приоритетное задание или пока один из процессоров не закончит выполнение своего задания и не снизит свой код приоритета.

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

5, с выхода которого единичный сигнал поступает на элементы И 3, в результате чего с одного из выходов

1291983

9 на выделенный блоком 1 процессор с низшим приоритетом поступает сигнал прерывания. В это же время на выходах 12 устройства формируется код, состоящий из имени и кода 5 приоритета выделенного наиболее приоритетного задания.

Процессор, получивший прерывание, принимает с выходов 12 новое задание, прекращает выполнение старого менее приоритетного задания (если он занят выполнением задания) и точку прерывания заносит в описатель прерванного задания, находящийся в системном модуле памяти. Имя прерванного задания и код его приоритета процессор передает на вход 10 устройства для распределения зада ний, в результате чего это задание попадает в группу заданий, готовых 20 к выполнению и ждущих в устройстве предоставления им процессоров. 3атем прерванный процессор присваивает себе приоритет принятого нового задания и приступает к его выполнению.

Основным узлом блока 4 является модуль 16 оперативной памяти, предназначенный для хранения имен заданий, готовых к выполнению. Модуль 16 представляет единый узел, информационно-разделенный на страницы, каждая из которых предназначена для хранения заданий только одного из приоритетных уровней. 35

При занесении новых заданий в устройство страницы модуля 16, соответствующие приоритетным уровням этих заданий, постепенно заполняют- 4р ся, а текущие адреса границ записи на эти страницы возрастают. Эти текущие адреса границ записи хранятся в модуле 17 памяти.

Чтение заданий с какой-либо стра- 15 ницы модуля 16 происходит в порядке поступления этих заданий, т.е.

„цля заданий одного приоритетного уровня реализуется дисциплина обслу живания "первым пришел — первым вы шел . По мере чтения заданий с данI ной страницы адрес границы чтения постепенно возрастает. Текущие адреса границ чтения хранятся в модуле

18 памя ти . 55

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

Равенство границ чтения и записи свидетельствует об отсутствии заданий с этим приоритетом, ждущих предоставления процессоров. Емкость одной страницы модуля 16 является достаточной, чтобы записать в нее все готовые к выполнению задания системы с одним приоритетом (страницы никогда не переполняются).

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

С помощью элементов И 24 происходит позиционное выделение группы заданий с высшим приоритетом. Сформированный шифратором код приоритета используется для определения номера страницы модуля 16 памяти, на которой записана группа заданий с высшим приоритетом. Из этой груп— пы извлекается и направляется на процессор задание, поступившее в устройство первым (раньше других заданий этой приоритетной группы).

В режиме приема в устройство нового задания код, содержащий имя и код приоритета одного задания, поступает на выходы 10. Задание сопровождается синхропотенциалом,поступающим через вход 11 на вход синхронизации регистра 13. Передним фронтом синхропотенциала код регист— рируется в регистре 13. Этот же синхропотенциал поступает с входа 11 на вход распределителя 5, который начинает вырабатывать серию импульсов, управляющих приемом нового задания.

Потенциалом с выхода э- блока 5, поступающим на первый управляющий вход коммутатора 15, коммутатор пе— реключается в состояние, в котором на его выход проходит код приоритета задания, поступающий с выхода регистра 13. Этот код приоритета задания поступает на первый адресный вход модуля 16 памяти, определяя номер его страницы, и на адресный вход модуля

17 памяти, определяя в нем адрес

1291983 ячейки, в которой хранится текущее значение границы записи выбранной страницы модуля 16 памяти. Код приоритета задания с выхода коммутатора

15 поступает также на группу входов дешифратора 21.

Импульсом с выхода е распределителя 5 происходит чтение границы записи из модуля 17 памяти. Одновременно с этим вырабатывается импульс на выходе ж блока 5; который поступает на вход управления счетчика 19, в результате чего граница записи из модуля 17 заносится в счетчик 19, с выхода которого эта граница поступает на второй адресный вход модуля 16 памяти, определяя адрес ячейки для записи нового задания на страницу, определенную кодом приоритета этого задания. Одновременно с этим вырабатывается импульс на выходе и. распределителя 5. Этот импульс поступает на управляющий вход дешифратора

21, в результате чего устанавливается в единичное состояние один из триггеров 23, номер которого соответствует коду приоритета задания, который поступил на группу входов дешифратора 21. Единичное состояние этого триггера свидетельствует о наличии хотя бы одного задания с данным кодом приоритета на выбранной странице модуля 16 памяти.

Затем вырабатывается импульс на выходе к распределителя 5. Этот импульс поступает на вход управления записью модуля 16 памяти, в результате чего имя нового задания, поступившего с выхода регистра 13 на вход данных модуля 16, записывается на выбранную страницу в выбранную ячейку этого модуля памяти.

Затем вырабатывается импульс на выходе а распределителя 5. Этот импульс поступает на счетный вход счетчика 19, увеличивая на единицу значение границы записи задания с данным приоритетом. Счетчик 19 устроен так, что если его содержимое больше размера страницы модуля 16 памяти, благодаря наличию обратных связей содержимое счетчика становится равным единице и адреса ячеек на странице модуля 16 начинают возрастать вновь. Этим обеспечивается возможность занесения на данную страницу новых заданий.

Модифицированное в счетчике 19 текущее значение границы записи поступает на вход данных модуля 17 памяти.

Последним в этом режиме импульсом с выхода л распределителя 5 увеличенное на единицу значение границы записи записывается в ячейку модуля

17 памяти. В конце приема задания

10 в устройство синхропотенциал с вхо— да 11 снимается.

В результате поступления на входы

10 устройства группы заданий, готовых к выполнению и имеющих разные приоритеты, имена этих заданий окажутся записанными на различные страницы модуля 16 памяти, которые соответствуют кодам приоритетов поступивших заданий. Если среди посту20 пивших заданий присутствуют задания с равными приоритетами, они запишутся на одну страницу модуля 16.

Занесение хотя бы одного задания

25 на какую-либо страницу модуля 16 памяти сопровождается установкой в единичное состояние соответствующего триггера 23 ° Поэтому после поступления в устройство группы заданий

30 окажутс% в единичном состоянии те триггеры 23, которые соответствуют не пустым страницам.

Состояние триггеров 23 анализируется группой элементов И 24 так,что при наличии нескольких триггеров 23 в единичном состоянии на вход шифратора 25 проходит только один единичный сигнал с самого верхнего по схеме, установленного в единицу триггера. Этот триггер соответствует заданию (заданиям) с высшим кодом прио— ритета из всех заданий, поступивших в устройство. Шифратор 25 вырабатывает двоичный код приоритета этого наиболее приоритетного задания. Этот код приоритета поступает на вход схемы 2 сравнения, где сравнивается с кодом приоритета процессора с низшим приоритетом. При условии, что приоритет выделенного в блоке 6 задания с высшим приоритетом больше приоритета процессора с низшим приоритетом, схема 2 сравнения вырабатывает единичный сигнал, который поступает на вход распределителя 5. Если устройство в данный момент времени свободно от приема новых заданий (отсутствует единичный потенциал на входе 11 устройства), 1291983

25 распределитель 5 переключается в режим чтения (выдачи) задания.

В режиме чтения (выдачи) задания распределитель 5 вырабатывает единичный потенциал на выходе а. Этот потенциал поступает на второй управляющий вход коммутатора 15. Коммутатор переключается в состояние,в котором на его выход проходит код приоритета задания с выхода шифратора 25.

Код приоритета наиболее приоритетного задания с выхода коммутатора 15 поступает на первый адресный вход модуля 16 памяти, определяя страницу, соответствующую этому коду приоритета. Код приоритета с входа коммутатора 15 поступает также на адресные входы модулей 17 и 18 памяти и на входы дешифратора

22 и регистра 14.

Затем распределитель 5 вырабатывает импульс на выходе Г. Этот импульс поступает на вход управления чтением модуля 18 памяти, в результате чего текущее значение границы чтения выделенной страницы модуля 16 поступает на вход счетчика

19. Одновременно с этим вырабатывается импульс на выходе ж распределителя 5, в результате чего граница чтения из модуля 18 заносится в счетчик 19. С выхода счетчика

19 граница чтения поступает на второй адресный вход модуля 16 и на нижний по схеме кодовый вход схемы

20 сравнения.

Затем импульсом с выхода Ь распределителя 5 происходит чтение имени первого по очереди наиболее приоритетного задания с выбранной страницы модуля 16 памяти и занесение имени и кода приоритета этого задания в регистр 14.

Затем вырабатывается импульс на выходе распределителя 5; Этим импульсом в счетчике 19 значение границы чтения данной страницы увеличивается на единицу.

Затем импульсом с выхода 8 распределителя 5 модифицированное зна— чение границы чтения записывается в соответствующую этому коду приоритета ячейку модуля 18 памяти. Этим же импульсом открывается группа элементов И 3, в результате чего вырабатывается сигнал на одном из выходов

9, который в виде сигнала прерыва30

55 ния поступает на процессор с низшим приоритетом выделенный блоком

1 анализа приоритетов процессора.

Этот процессор принимает код с выходов 12, содержащий имя и приоритет выделенного ему наиболее приоритетного задания.

Одновременно с сигналом на выходе

3 распределителя .5 вырабатывается сигнал на его выходе е. Этим сигналом производится чтение границы записи из модуля 17 и сравнение ее с границей чтения этой же страницы в схеме 20 сравнения. Если эти границы равны, что свидетельствует о чтении последнего задания, находившегося на выбранной странице модуля 16, схема 20 сравнения вырабатывает импульс, который поступает на вход управления дешифратора 22. При этом один из триггеров 23, соответствую- щий коду приоритета, поступившему на вход дешифратора 22, сбрасывается в нулевое состояние.

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

Устройство для распределения заданий процессорам, содержащее блок анализа приоритетов процессоров, группа запросных и группа кодовых входов которого подключены соответственно к группе запросных и группе кодовых входов устройства, блок анализа приоритетов заданий и схему сравнения, первая группа входа которой соединена с первой группой выходов блока анализа приоритетов процессоров, о тл и ч а ю щ е е с я тем, что, с це,пью расширения функциональных воэможностей путем организации очередей заданий с равными приоритетами,оно содержит группу элементов И, распределитель импульсов и блок запоминания заданий, содержащий два регистра, коммутатор, три модуля па— мяти, счетчик и схему сравнения, блок анализа приоритетов заданий содержит два дешифратора, группу триггеров, группу элементов И и шифратор, гричем i-й выход второй группы выходов блока анализа приоритетов процессоров (i= 1,2,..., m, где m— число процессоров) подключен к первому входу i-го элемента И первой группы, выход которого является

i-м выходом группы выходов прерывания устройства, группа информацион9 12

91983 ных входов первого регистра блока запоминания заданий подключена к группе информационных входов устройства, вход синхронизации перво-го регистра блока запоминания заданий подключен к входу синхронизации устройства и к входу синхронизации распределителя импульсов, первая группа выходов первого регистра блока запоминания заданий подключена к первой группе информационных входов коммутатора, вторая группа выходов первого регистра блока запоминания заданий подключена к входу данных первого модуля памяти, первый адресный вход которого соединен с адресными входами второто и третьего модулей памяти, с группами входов первого и второго дешифраторов, с выходом коммутатора и с первой группой информационных входов второго регистра блока запоми- нания заданий, второй адресный вход первого модуля памяти соединен с входами данных второго и третьего модулей памяти, с группой выходов счетчика и с первой группой входов схемы сравнения блока запоминания заданий, выходы первого модуля памяти соединены с второй группой информационных входов второго регистра, выходы которого являются группой выходов номера задания устройства, выходы второго и третьего модулей памяти объединены и подключены к группе информационных входов счетчика и к второй группе входов схемы сравнения блока запоминания заданий, выход которой соединен с управляющим входом первого дешифратора, j-й выход которого (j = 1, 2,..., n, где n — число, приоритетных уровней заданий) подключен к нулевому входу j-го триггера группы, j-й выход второго дешифратора соединен с единичным входом j-ro триггера группы, еди— ничный выход первого триггера группы подключен к первому входу шифратора, единичный выход К-го триггера!

О группы (К = 2, 3,...,) связан с первым входом (К- 1)-го элемента И группы блока анализа приоритетов заданий, нулевой выход (К-1)-ro триггера группы соединен с К-ми входами S-x (S >К-1) элементов И группы блока анализа приоритетов заданий, выход (K- 1)-го элемента И группы подключен к К-му входы шифратора, группа

10 выходов которого соединена с второй группой информационных входов коммутатора и второй группой входов схемы сравнения, выход которой соединен с входом запуска распределителя импульсов, первый выход которого подключен к первому управляющему входу коммутатора, второй выход распределителя импульсов

" подключен к входу управления чте20 нием третьего модуля памяти,третий выход распределителя импульсов подключен к входу управления чтением первого модуля памяти и к

25 входу синхронизации второго регистра блока запоминания заданий,четвертый выход распределителя импульсов подключен к суммирующему входу счетчика, пятый выход распределителя импульсов псф ключен к вхо—

30 ду управления схемы сравнения блока запоминания заданий, к входу управления записью третьего модуля памяти и к вторым входам элементов

И группы, шестой выход распределите35 ля импульсов подключен к входу управления чтением второго модуля памяти, седьмой выход распределителя импульсов подключен к входу управления записью счетика, восьмой выход

40 распределителя импульсов подключен к второму управляющему входу коммутатора, девятый выход распределителя импульсов соединен с управляющим входом второго дешифратора, десятый

45 выход распределителя импульсов подключен к входу управления записью первого модуля памяти, одиннадцатый выход распределителя импульсов подключен к входу управления записью второго модуля памяти.

1291983 юг 1

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

Редактор Н.Рогулич ТехредИ.Попович Корректор С.Шекмар

Заказ 272/48 тираж 673 Подписное

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

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

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