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

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

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

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

Устройство (фиг. 1) содержит блок 1 анализа приоритетов процессоров, схему 2 сравнения, группу элементов И 3, блок 4 запоминания заданий,распределитель 5 импульсов, блок 6 анализа приоритетов заданий, группу запросных входов 7 устройства,группу кодовых входов 8 устройства,группу выходов 9 прерывания устройства, группу информационных входов 10 устройства, вход 11 синхронизации устройства, группу выходов 12 iioMepa задания устройства. Блок 4 содержит регистры 13 и 14, коммутатор 15, модули 16-18 памяти, счетчик 19 и схему 20 сравнения, буквами а-л

обознл

чены.выходы распределителя 5, буквой м - выход схемы 2. I

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

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

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

В системе постоянно имеется группа заданий, запуск которых (возбуждение готовности) производится по сигналам, поступающим на входы системы с .датчиков объекта управления и от операторов, а также 0т ранее

5

0

5

0

5

0

5

0

5

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

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

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

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

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

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

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

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

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

фронтом синхропотенциала код регист рируется в регистре 13. Этот же син хропотенциап поступает с входа 11 на вход распределителя 5, который

Чтение заданий с какой-либо стра- 45 начинает вырабатывать серию импульницы модуля 16 происходит в поряд- .ке поступления этих заданий, т.е. для заданий одного приоритетного уровня реализуется дисциплина обслу- |Живания первым пришел - первым вы|шел. По мере чтения заданий с данI

НОИ страницы адрес границы чтения

постепенно возрастает. Текущие адреса границ чтения хранятся в модуле 18 памяти.

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

сов, управляющих приемом нового задания. I

Потенциалом с выхода блока 5,

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

55 Ра 13. Этот код приоритета задания поступает на первый адресный вход мо дуля 16 памяти, определяя номер ег страницы, и на адресньй вход модуля 17 памяти, определяя в нем адрес

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

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

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

В режиме приема в устройство нового задания код, содержащий имя и код приоритета одного задания, поступает на выходы Ю. Задание сопровождается синхропотенциалом,поступающим через вход 11 на вход син- хронизации регистра 13. Передним

фронтом синхропотенциала код регистрируется в регистре 13. Этот же син- хропотенциап поступает с входа 11 на вход распределителя 5, который

начинает вырабатывать серию импульсов, управляющих приемом нового задания. I

Потенциалом с выхода блока 5,

поступающим на первый управляющий вход коммутатора 15, коммутатор переключается в состояние, в котором на его выход проходит код приоритета задания, поступающий с выхода регистРа 13. Этот код приоритета задания поступает на первый адресный вход модуля 16 памяти, определяя номер его страницы, и на адресньй вход модуля 17 памяти, определяя в нем адрес

- 20

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

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

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

fO

2919836

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

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

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

- 15

30

35

40

I

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

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

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

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

0

5

0

I

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

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

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

5

0

5

7

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

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

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

Затем распределитель 5 вырабатывает импульс на выходе S, Этот импульс поступает на вход управления чтением модуля 18 памяти, в результате чего текущее значение границы чтения выделенной страницы модуля 16 поступает на вход счетчика 19. Одновременно с этим вьфабаты- вается импульс на выходе ж распределителя 5, в результате lero граница чтения из модуля 18 заносится в счетчик 19. С выхода счетчика 19 граница чтения поступает на вто

рой. адресный вход модуля 16 и на нижний по схеме кодовый вход схемы 20 сравнения.

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

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

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

5

0

5

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

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

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

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

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

310

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

ю

о/3

7

J6

11

W

20

1

2;

Z3

23

ГШ1

25

/75

2Z

пп

Л

П)7ПП

Фиа.2

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

Заказ 272/48 Тираж 673 Подписное ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. А/5

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

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