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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИРЕСПУБЛИК 51)4 С 06 Р 9/4 ОСУДАРСТНЕННЫЙ НОМИТЕТ ССС О ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫ Е ИЗОБРЕТЕНИЯ ОП ТОРСКОМУ СВИДЕТЕЛВСТВУ(71) Институт технической ктики АН БССР(56) Авторское свидетельствВ 1111165, кл. С 06 Р 9/46,Авторское свидетельствопо заявке 1 Ф 3727173,кл. С 06 Р 9/46, 1984. бернеСССР984СР СПРЕДЕЛЕНИЯ носится к вычи тьатно мож апп товых к вь спределения оцессорной с для управле в реальном в ереениеройния - расшир ожностей уст(54) УСТРОЙСТВО ДЛЯ ЗАДАНИЙ ПРОЦЕССОРАМ (57) Изобретение.о лительной технике пользовано в качес диспетчера программ полнению, для их р процессорам многоп мы, предназначенно сложными объектами мени, Цель изобрет функциональных воз,801291983 А ства путем организации очередейзаданий с равными приоритетами. Вустройство, содержащее блок анализаприоритетов процессоров, блок анализа приоритетов заданий и схемусравнения, введена группа элементовИ, распределитель иммульсов и блокзапоминания заданий, основным узлом которого является модуль оперативной памяти, каждая страница которой содержит группу заданий с равными приоритетами, Блок анализа приоритетов заданий содержит два дешифратора, группу триггеров, группу элементов И и шифратор. Это блок выделяет наиболее приоритетное заданиепо групповому принципу. Положительный эффект достигается благодарясовместной работе блока запоминаниязаданий и блока анализа приоритетовзаданий, что позволяет производитьраспределение заданий не только всоответствии с их приоритетами, нои распределение равноприоритетныхзаданий согласно очередности ихпоступления в устройство. 2 ил.Изобретение относится к вычислительной технике и может быть использовано в качестве аппаратного диспетчера программ, готовых к выполнению, для их распределения по процессорам многопроцессорной вычислительной системы. предназначенной для управления сложными объектами в реальном времени.Цель изобретения - расширение функциональных возможностей устройства для распределения заданий процессорам путем организации очередей заданий с равными приоритетами и сокращение оборудования.15На фиг, 1 изображена структурнаясхема устройства;.на фиг . 2 - функциональная схема блока анализа приоритетов процессоров,Устройство (фиг. 1) содержит блок1 анализа приоритетов процессоров,схему 2 сравнения, группу элементовИ 3, блок 4 запоминания заданий,распределитель 5 импульсов, блок 625анализа приоритетов заданий, группузапросных входов 7 устройства, группу кодовых входов 8 устройства, группу выходов 9 прерывания устройства,группу информационных входов 10 устройства, вход 11 синхронизации устройства, группу выходов 12 номеразадания устройства. Блок 4 содержитрегистры 13 и 14, коммутатор 15, модули 16-18 памяти, счетчик 19 и схему 20 сравнения, буквами а-л обознчены выходы распределителя 5, буквой м - выход схемы 2.Блок 6 анализа приоритетов заданий содержит дешифраторы 21 и 22, 40группу триггеров 23, группу элементов И 24, шифратор 25,Блок 1 содержит каналы 26, в каждом канале (кроме последнего) - первую и вторую группы элементов ИЛИ-НЕ27 и 28, первую и вторую группы элементов ИЛИ 29 и 30. В последнем канале 26 содержится первая, вторая группы элементов ИЛИ-НЕ 27 и 28, группаэлементов ИЛИ 29, группа элементовИЛИ-НЕ 31.Устройство работает следующим образом.В системе постоянно имеется группа заданий, запуск которых (возбуждение готовности) производится посигналам, поступающим на входы системы с датчиков объекта управленияи от операторов, а также от ранее запущенных заданий (ведущих программных модулей) . В зависимости от взаимной срочности заданиям присвоены коды приоритетов. Задание, для которого возникла готовность к выполнению, передается на входы 10 устройства в виде кода имени и кода приоритета этого задания и заносится в модуль 16 памяти. Из всех заданий, находящихся в устройстве и ждущих предоставления им процессоров, блоки 4 и 6 выделяют задание с высшим приоритетом, Код приоритета этого задания поступает на вход схемы 2 сравнения.В системе имеется также группа процессоров, сигналы о состояния которых поступают на входы 7 устройства. Исправные процессоры характеризуются логическими нулями, неисправные - единицами. Процессоры выполняющие задания, присваивают себе коды приоритетов этих заданий, свободные процессоры характеризуются низшим приоритетом, не совпадающим с приоритетом ни одного из заданий, Коды приоритетов всех процессоров поступают на входы 8 устройства,Блок" 1 анализа приоритетов процессоров из числа исправных процессоров выделяется процессор с низшимприоритетом. Это характеризуетсяпоявлением логической единицы наодном из выходов блока 1, которыйпозиционно соответствует выделенному процессору. Код приоритета выделенного процессора поступает на другои вход схемы 2 сравнения, гдесравнивается с кодом приоритета выделенного задания,Если код приоритета выделенногонаиболее приоритетного задания,готового к выполнению, меньше или равен коду приоритета выделенного наименее приоритетного процессора,устройство не вырабатывает никаких сигналов до тех пор, пока в него непоступает более приоритетное заданиеили пока один из процессоров не закончит выполнение своего задания ине снизит свой код приоритета,При условии, что приоритет задания выше приоритета процессора, схема 2 сравнения вырабатывает сигнал,который поступает в распределитель5, с выхода которого единичный сигналпоступает на элементы И 3, в результате чего с одного из выходов9 на выделенный блоком 1 процессор с низшим приоритетом поступает сигнал прерывания. В это же время на выходах 12 устройства формируется код, состоящий из имени и кода 5 приоритета выделенного наиболее приоритетного задания.Процессор, получивший прерывание, принимает с выходов 12 новое задание, прекращает выполнение старого менее приоритетного задания (если он занят выполнением задания) и точку прерывания заносит в описатель прерванного задания, находящийся в системном модуле памяти. Имя прерванного задания и код его приоритета процессор передает на вход 10 устройства для распределения заданий, в результате чего это задание попадает в группу заданий, готовых 20 к выполнению и ждущих в устройстве предоставления им процессоров. Затем прерванный процессор присваивает себе приоритет принятого нового задания и приступает к его выполнению.Основным узлом блока 4 является модуль 16 оперативной памяти, предназначенный для хранения имен заданий, готовых к выполнению. Модуль 16 представляет единый узел, информационно-разделенныйна страницы, каждая из которых предназначена для хранения заданий только одного из приоритетных уровней. 35 При занесении новых заданий в устройство страницы модуля 16, соответствующие приоритетным уровням этих заданий, постепенно заполняют ся, а текущие адреса границ записи на эти страницы возрастают. Эти текущие адреса границ записи хранятся в модуле 17 памяти.Чтение заданий с какой-либо стра ницы модуля 16 происходит в порядке поступления этих заданий, т.е.цля заданий одного приоритетного уровня реализуется дисциплина обслуживания первым пришел - первым вы п шел. По мере чтения заданий с данной страницы адрес границы чтения постепенно возрастает. Текущие адреса границ чтения хранятся в модуле 18 памяти. 55Чем больше разность между границами чтения и записи, тем больше заданий с данным приоритетным уровнем хранятся на этой странице модуля 16. Равенство границ чтения и записи свидетельствует об отсутствии заданий с этим приоритетом, ждущих предоставления процессоров. Емкость одной страницы модуля 16 является достаточной, чтобы записать в нее все готовые к выполнению задания системы с одним приоритетом (страницы никогда не переполняются).Блок б анализа приоритетов заданий имеет группу триггеров 23, каждый из которых фиксирует наличие или отсутствие на соответствующей странице модуля 16 памяти заданий данного приоритетного уровня. Если несколько триггеров 23 находятся в единичном состоянии, это свидетельству- ет о наличии в устройстве такого же количества приоритетных групп заданий, ждущих предоставления им процессоров.С помощью элементов И 24 происхог дит позиционное выделение группы заданий с высшим приоритетом, Сформированный шифратором код приоритета используется для определения номера страницы модуля 16 памяти, на которой записана группа заданий с высшим приоритетом. Из этой группы извлекается и направляется на процессор задание, поступившее в устройство первым (раньше других заданий этой приоритетной группы).В режиме приема в устройство нового задания код, содержащий имя и код приоритета одного задания, поступает на выходы 10. Задание сопровождается синхропотенциалом,поступающим через вход 11 на вход синхронизации регистра 13. Передним фронтом синхропотенциала код регистрируется в регистре 13. Этот же синхропотенциал поступает с входа 11 на вход распределителя 5, который начинает вырабатывать серию импульсов, управляющих приемом нового задания. Потенциалом с выхода э. блока 5, поступающим на первый управляющий вход коммутатора 15, коммутатор переключается в состояние, в котором на его выход проходит код приоритета задания, поступающий с выхода регистра 13. Этот код приоритета задания поступает на первый адресный вход модуля 16 памяти, определяя номер его страницы, и на адресный вход модуля 17 памяти, определяя в нем адресячейки, в которой хранится текущее значение границы записи выбранной страницы модуля 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 устройства группы заданий, готовых к выполнению и имеющих разные 15 приоритеть 1, имена этих заданий ока -жутся записанными на различныестраницы модуля 16 памяти, которыесоответствуют кодам приоритетов поступивших заданий. Если среди посту пивших заданий присутствуют задания с равными приоритетами, они запишутся на одну страницу модуля 16,1Занесение хотя бы одного задания25 на какую-либо страницу модуля 16памяти сопровождается установкой вединичное состояние соответствующего триггера 23Поэтому после поступления в устройство группы заданий30 окажутс% в единичном состоянии тетриггеры 23, которые соответствуютне пустым страницам,Состояние триггеров 23 анализируется группой элементов И 24 так,чтопри наличии нескольких триггеров 23в единичном состоянии на вход шифратора 25 проходит только один единичный сигнал с самого верхнего по схеме, установленного в единицу триггера. Этот триггер соответствует заданию (заданиям) с высшим кодом приоритета из всех заданий, поступивших в устройство. Шифратор 25 вырабатывает двоичный код приоритетаэтого наиболее приоритетного задания. Этот код приоритета поступаетна вход схемы 2 сравнения, где сравнивается с кодом приоритета процессора с низшим приоритетом. При условии, что приоритет выделенного вблоке 6 задания с высшим приоритетомбольше приоритета процессора с низшим приоритетом, схема 2 сравнениявырабатывает единичный сигнал, который поступает на вход распределителя 5. Если устройство в данный момент времени свободно от приема новых заданий (отсутствует единичныйпотенциал на входе 11 устройства), 129198310 15 20 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 35 40 45 50 55 ния поступает на процессор с низшим приоритетом выделенный блоком 1 анализа приоритетов процессора. Этот процессор принимает код с выходов 12, содержащий имя и приоритет выделенного ему наиболее приоритетного задания,Одновременно с сигналом на выходе 3 распределителя .5 вырабатывается сигнал на его выходе е. Этим сигналом производится чтение границы записи из модуля 17 и сравнение ее с границей чтения этой же страницы в схеме 20 сравнения. Если эти границы равны, что свидетельствует о чтении последнего задания, находившегося на выбранной странице модуля 16, схема 20 сравнения вырабатывает импульс, который поступает на вход управления дешифратора 22. При этом один из триггеров 23, соответствую- щий коду приоритета, поступггвшему на вход дешифратора 22, сбрасывается в нулевое состояние. Формула изобретения Устройство для распределения заданий процессорам, содержащее блок анализа приоритетов процессоров, группа запросных и группа кодовых входов которого подключены соответственно к группе запросных и группе кодовых входов устройства, блок анализа приоритетов заданий и схему сравнения, первая группа входа которой соединена с первой группой выходов блока анализа приоритетов процессоров, о тл и ч а ю щ е е с я тем, что, с це,пью расширения функциональных воэможностей путем организации очередей заданий с равными приоритетами,оно содержит группу элементов И, распределитель импульсов и блок запоминания заданий, содержащий два регистра, коммутатор, три модуля памяти, счетчик и схему сравнения, блок анализа приоритетов заданий содержит два дешифратора, группу триггеров, группу элементов И и шифратор, гричем -й выход второй группы выходов блока анализа приоритетов процессоров (д= 1,2 ш, где ш - число процессоров) подключен к первому входу 1-го элемента И первой группы, выход которого является 1-м выходом группы выходов прерывания устройства, группа информацион9 12 91983 ных входов первого регистра блока запоминания заданий подключена к группе информационных входов устройства, вход синхронизации перво- . го регистра блока запоминания заданий подключен к входу синхронизации устройства и к входу синхронизации распределителя импульсов, первая группа выходов первого регистра блока запоминания заданий подключена к первой группе информационных входов коммутатора, вторая группа выходов первого регистра блока запоминания заданий подключена к входу данных первого модуля памяти, первый адресный вход которого соединен с адресными входами второго и третьего модулей памяти, с группами входов первого и второго дешифраторов, с выходом коммутатора и с первой группой информационных входов второго регистра блока запоми- нания заданий, второй адресный вход первого модуля памяти соединен с входами данных второго и третьего модулей памяти, с группой выходов счетчика и с первой группой входов схемы сравнения блока запоминания заданий, выходы первого модуля памяти соединены с второй группой информационных входов второго регистра, выходы которого являются группой выходов номера задания устройства, выходы второго и третьего модулей памяти объединены и подключены к группе информационных входов счетчика и к второй группе входов схемы сравнения блока запоминания заданий, выход которой соединен с управляющим входом первого дешифратора, 3-й выход которого (3 = 1, 2, , и, где и - число, приоритетных уровней заданий) подключен к нулевому входу 1-го триггера группы, 1-й выход второго дешифратора соединен с единичным входом 3-го триггера группы, единичный выход первого триггера группы подключен к первому входу шифратора, единичный выход К-го триггера 1 Огруппы (К = 2, 3) связан с первым входом (К)-го элемента И группы блока анализа приоритетов заданий, нулевой выход (К)-го триггера груп пы соединен с К-ми входами Б-х(БК) элементов И группы блока анализа приоритетов заданий, выход (К)-го элемента И группы подключен к К-му входы шифратора, группа 10 выходов которого соединена с второй группой информационных входов коммутатора и второй группой входов схемы сравнения, выход которой соединен с входом запуска распределителя импульсов, первый выход которого подключен к первому управляющему входу коммутатора, второй выход распределителя импульсов" подключен к входу управления чтением третьего модуля памяти,третий выход распределителя импульсов подключен к входу управления чтением первого модуля памяти и к 25входу синхронизации второго регистра блока запоминания заданий,четвертый выход распределителя импульсов подключен к суммирующему входу счетчика, пятый выход распределителя импульсов подключен к вхо - 30ду управления схемы сравнения блока запоминания заданий, к входу управления записью третьего модуля памяти и к вторым входам элементов И группы, шестой выход распределите ля импульсов подключен к входу управления чтением второго модуля памяти, седьмой выход распределителя импульсов подключен к входу управления записью счетика, восьмой выход 40распределителя импульсов подключен к второму управляющему входу коммутатора, девятый выход распределителя импульсов соединен с управляющим входом второго дешифратора, десятый 45выход распределителя импульсов подключен к входу управления записью первого модуля памяти, одиннадцатый выход распределителя импульсов подключен к входу управления записью 50 второго модуля памяти.129983 Составитель М.Кудряшеактор Н,Рогулич ТехредИ.Попович орр екмар ое ССР роизводственно-полиграфическое предприятие, г. Ужгород, у ектная 272/48 ТиражВНИИПИ Государпо делам изо1133035, Москва 73 Подписн венного комитета Сетений и открытийЖ, Раушская наб.,