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

сооз соаетснихсоциАлисти 1 еснихРЕСПУБЛИК А 4,СО 6 Р 9 46 ЫИ НОМИТЕТ СССР ТЕНИЙ И ОТКРЫТИ 4 ГОСУДАРСТНЕННПО ДЕЛАМ ИЗ БРЕТЕНИ ИСАНИ СВИДЕТЕЛЬСТВУ К АЬТОРСК( 71) Институт технической кибернетики АН БССР(56) Авторское свидетельство СССР В 1001101, кл. С 06 Р 9/46, 1983.Авторское свидетельство СССР Р 1005055, кл. С 06 Р 9/46, 1983. (54) УСТРОЙСТВО ДЛЯ ПРИОРИТЕТНОГО РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ ПРОЦЕССОРАМ (57) Изобретение относится к вычисли. тельной технике и моает быть использовано в многопроцессорных ЭВМ для аппаратурной реализации функций операционной системы по днспетчированиюзаданий, готовых к выполнению. Цельизобретения - расширение областиприменения за счет учета как приоритетных заданий, так и приоритетов процессоров. Устройство содержит элементы ИЛИ, схему сравнения, две группы блоков анализа приоритетов и переключатель. Поставленная цель достигается благодаря учету приоритетовкак заданий, так и процессоров, реализация абсолютной и относительнойдисциплины обслуживания и возмозщости работы при совпадении несколькихкодов приоритетов. 1 ил.И зебре тс ие относится к вычислительной гехиике и может быть исполь.ловлно н устройствах приоритетногоуирдвлеиия распределением заданий процессорлм многопроцессорных вычис лительных систем.Цел., изобретения - расширение области применения устройства за счет учетл клк приоритетов заданий, так и риоритетов проессоров.1 ОВ основу устройства положен следующий принцип распределения заданий ио процессорам, В многопроцессорной вычислительной системе имеется множество злдлний (программ) с приорите тами. Возможно совпадение приоритетов иекотсрьх зддаиий, Задания, готовые к выпотнешю, выставляют в устройство распределения запросы на обслуживание, которые являются требования ми о предоставлении вычислительных ресурсов (процессоров) . В системе имеется также группа процессоров. Процессорам, выполняющим задания, установлены приоритеты этих заданий, Свободные процессоры имеют наименьший приоритет, не совпадаюший с приоритетом ни одного из заданий, Всепр опес с оры, и с ключ ля н еи сир авные, выставляют в устройство распределения запросы нд предоставление заданий. Устройство распределения заданий процессорам определяет задание с35 высшим приоритетом из множества заданий, готовых к вьптолнецию, и выделяет процессор с низшим приорите том, В случде рдботы многопроцессор - ной сигтемь в режиме с абсолютной40 приоритетной дисциплиной в устройстве происходит сравнение приоритета найдеиного задания с приоритетом выделенного процессора. Если приоритет здддиия выше приоритета процес- ф 5 сора, то он ; ригтупает к выполнению этого ладлиия независимо от того, был ли этот процессор свободным или выполнял менее приоритетное задание, Прерванное ллдлние поступает в группу заданий, готовых к выполнению. Если приоритет задания оказался ниже приоритета процессора, то устройство рлсп гдслечия не разрешает прерывание процессора, 55В глу ле рлбс ть системь с относитеьой пио 1)итетиой дисциплиной нллн;чеипс :ылленного наиболее при -оритетного задания происходит толькосвободный процессор.Нд чертеже изображенд функциональная схема устройства,Устройство содержит блоки 1 анализа приоритетов первой Й второйгрупп, кодовые входы 2 устройства,запросные входы 3 устройства, группысинальных выходов 4 устройства,вход 5 логического нуля устройства,элементы ИЛИ 6 группы, первую группу кодовых выходов 7 устройства,переключатель 8, схему 9 сравнения,выход 10 прерывания усройств. Каждый блок 1 содержит группу регистров 11, каналы 12 и 13. Каждый канал 12 и 13 содержит входь и выходыи 15, элементы ИЛИ-НЕ 16, ИЛИ 17,ИЛИ-НЕ 1 й, ИЛИ 19 (кроме последнегоканала), Последний канал 13 в каждом блоке 1, кроме того, содержитэлемент ИЛИ 20 и группу элементовИЛИ-НЕ 21. Устройство содержиттакже группу кодовых выходов 22,вход 23 логической единицы устройства,Устройство работает следующим образом.На входы 2, подключеннье к блокам 1, соединенным с выходами 7 подаются коды приоритетов заданий.1 опускаются совпадающие коды. Задания, готовые к выполнению, выставляют запросы на облуживание на входы 3. Блоки 1 этой группы из всех заданий, выставивших запросы, выявляют задание с минимальным (высшим) кодом приоритета. При этом возбуждается один из выходов 4 того бло" ка 1, в канале которого находится это задание. а высший (минимальный) код приоритета выбранного задания окажется на выходах 7, В случае, если нл входах 2 одного блока 1 имеется несколько совпадающих высших кодов приоритетов, то возбуждается выход 4 только того канала, номер которого в этом модуле наименьший, Если совпадающие высшие коды приоритетов имеются на входах 2 нескольких блоков 1, то возбуждается выход 4 только того блока 1, номер которого наь. меньший. При этом на выходе элемента ИЛИ 20 этого блока 1 вырабатывается единичный сигнал, который через элвменты ИЛИ 6 поступает на соответствую шие входы 5 во вге последующие блокиэтой группы и запрещает этимблокам выработку сигналов нд вьходах 4,Таким образом, первая группа блоков 1 выявляется иэ всех заданий,выставивших запросы, единственное 5задание с высшим приоритетом. Позиционный адрес этого задания (начальный адрес программы) будет на одномиз выходов 4 модулей 1 этой группы,а код приоритета - на группе выходов 7,На входы 2 второй группы блоков1, подключенных к выходам 22, поступают инверсные коды приоритетовпроцессоров. Эта группа блокон 1,работая аналогично описанной вышепервой группе, выявляет один канал,на вход 2 которого поступил минимальный код приоритета, Поскольку на входы 2 второй группы блоков были поданы иннерсные коды приоритетон процессоров, то будет возбужден одиниэ выходов 4, который указывает напроцессор с максимальным (ниэшим)кодом приоритета, При этом на ныходах 22 будет инверсный код приоритета выявленного процессора.В случае абсолютной приоритетной дисциплины обслуживания заданий переключатель 8 установлен н положение, изображенное на чертеже. Тогда на первую группу входов схемы 9 поступает код приоритета задания с выходов 7. На вторую группу нходов схемы 9 поступает код с выходов 22, 35При коде с выходов 22, большем кода с выходов 7, соответстнующем условию, когда приоритет выянленного задания превышает приоритет задания, выполняемого выделенным про цессором, схема 9 вырабатывает сигнал на выход 1 О, разрешающий прерывание этого процессора с целью перенаэначенья его на новое, более приоритетное задание. Прерываемый про цессор традиционным способом заносит в описатель прерванного задания его состояние и устанавливает запрос на продолжение выполнения этого задания на соответствующем входе 3 пер вой группы блоков 1. Процессор, получивший новое задание, присваивает себе его приоритет к выполнению этого задания, а запрос на входе 3 первой группы блоков 1, соответствующем заданию, получившему назначение на процессор, снимается, Устройство начинает новый цикл работы. При условии, коглд приоритет вьявленного первой группой блоковзадания не превышдс т приоритета процессора, выявленного группой блоков1, прерываний процессоров и назначений эаданий не происходитдотех пор, пока ве появится запросзадания с более высоким приоритетомили один из процессоров не освободит ся,В случае относительной приоритетной дисциплины обслуживания заданийна первую группу входов схемы 9 спереключателя 8 поступает код 1,.1 О.При этом сигнал на выходе 1 О вырабатывается только в том случае когда1будет выявлен свободный процессорс кодом приоритета 1)1, т.е. назначение выявленного наиболее приоритетного задания происходит толькона свободный процессор,Блокработает следующим образом.Коды приоритетов запросов на обслуживание поступают н регистры 11и фиксируются н них. Высшему приори.тету соответствует минимальный код.Блок 1 работоспособен при подаче врегистры 11 произвольного наборакодов приоритетов. Допустимо совпадение кодов приоритетов. На входы3 поступают запросы абонентов (наличие запроса соответствует логическому нулю).Первый канал 12 анализирует состояние запросов на входах 3 (14) иназначения старших разрядов регистров 11При отсутствии запроса вкаком-либо канале логическая единица с входа 14 этого канала независи"мо от значения старшего разряда всоответствующем регистре 11 устанавливает в единицу выходной сигнал эле.мента ИЛИ 9 и независимо от значения следующего разряда этого регистра устанавливает в единицу выходнойсигнал следующего кандла 12 и т.д.В итоге, при отсутствии запроса единичный сигнал с хода 4, пройдя через все элементы ИЛИ 19 и ИЛИ-НЕ 21данного канала, вырабатывает нулевойсигнал на выходе 4 данного блока 1( отсутствие необходимости обслуживания). При н дли чин э ап рос ов и д н ходд х 4 имеются логические нули, ие влияющие нд прохождение сигналов с рдзрядиых входов 15 через немецм 16-19.;ч в . " т а р цц х р а з р я до вц трв 11 приходят ца выходы эле - мцэн ИИ 17 псрвог канала 12. Выхо всех з:ем нтов ИЛИ 17 соедии ець оиц Г дру им и под ключ Рцы к 5 ятветствующ му выходуруппы выходв 7 ( ) . Т,кое соединение вьгходов логических элементов известно под цаэваццем монтажной логики и реализует логическую операцию И на 1 О соответствукчпем выходе группы 7, единица будет только в том случае, когда ца входы всех элементов ИЛИ 17 поступают логические единицы. Описашую схеу из элементов ИЛИ 17 и 15 мотажной логики И можно назвать схемй и. я вьпеления минимального значеция цз ацлиэуемых одноименных разрядв реги.тров 1. Действительно,ца любом выходе группы 7 (22) логичекая единица будет при условии наличия едиццц го всех соответствующихразрядах регистров 11, а логическийнуль - ри условии наличия хотя быодного нуля в этих разрядах. 25"формированный таким образом сиг-,нал с выхода группы 7 поступает вэлементы ИЛИ-НЕ 18, в которых логиче кн суммируется с инверсными зна -чецчямц тарших разрядов соответсвую- З 0щих реистров 11, поступивших с выхдов элементов 1 ПИ-НЕ 16,Если значения цализируемых старших разрядов совпадант (все единицыили ве цулц), то о этим разрядамеще невозможно сделать вывод о номе -ре канала, которьй среди каналов,вытавинппх запросы, имеет в соответствующем регистре 11 минимальный код .В этом случае необходимо ца выходахпервого канала 12 в блоках 1, кудапос тупизн запросы, выработать ло ические нули, которые, поступив назапросные входы 1 следующего канала 2, соответствуют запросам наанализ следующего разряда кодов ириритетов. .1 то реализуется таким образом. Ирглположим, что во всехстарих разрядах регистров 11 логические единць. Тогда ца первом вы 50ходе группы 7 также логическая единица, котораяри прохождении черезэлемцты 8 и 19 обеспечивает требуемые огические нули на всех вы, х 1 гвсех старцх разрядахр цгг в 1 оичс кце нули, то: :р х ждепия через эл емецть6, 18 и 19 об спс чивакт цявление требуемых логических нулей на всех выходах канала 12.В случае, когда в старших разрядах регистров 11 имеются разные значения, то регистры, в которых пнализируемые разряды содержат едиицы, це являются регистрами с высшим (минимальным) приоритетом. На вьходах канала, содержащего эти регистры, необходимо выработать логические единицы, которые аннулируют запросы на запросных выходах 14этих каналов всех следуюшх логических каналов 12.В остальных каналах, анапизированные разряды которых содержат нули, должен быть произведен анализ следующих разрядов. На выходах этих каналов 12 необходимо выработать логические нули, соответствующие запросам на входах следующего канала, Это реализуется таким образом. При несовпадении значений анализируемьх разрядов в регистрах 11 ца соответствующем выходе 7 (22) будет логический нуль. При этом на выходах элементов 19 будут логические сигналы, совпадающие со значениями анализируемых разрядов регистров 11, что и требовалось получить.Благодаря наличию элементов ИЛИНЕ 21 последнего канала 13 ца соответствующем выходе 4 вырабатывается логическая единица, если в одноимец. цом регистре 11 цаходится минимальный (высший) код приоритета канала среди всех каналов, выставивпвх запросы на входах 3. Дополнительные связи между элементами ИЛИ-НЕ 21 канала 3 исключают возможность появления логических единиц одновременно на двух или более выходах 4. При наличии минимальных кодов приоригетов в нескольких регистрах 11 логическая единица вьграбатывается на выходе 4, порядковый номер которого соответствует минимальному номеру канала, в который поступил запрос,Появление логической единицы налюбом из выходов 4 предыдущего блока 1 формирует единицу на выходе элемента ИЛИ 21, которая запрещает выработку сигналов ца выходах 4 последующих блоков 1, в котрых могут находиться коды приоритетов, равные выделеьцому в прельдушем блоке, 125277Формула изобретения Устройство для приоритетного распределения заданий процессорам, содержащее две группы элементов ИЛИ, 5 первую группу блоков анализа приоритетов, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения устройства за счет учета как приоритетов заданий, так и приоритетов процессоров, устройство содержит вторую группу блоков анализа приоритетов, схему сравнения и переключатель, причем каждый блок анализа приоритетов группы содержит группу регистров приоритета и каналы, каждый из которых, кроме последнего, содержит две группы элементов ИЛИ и дне группы элементов ИЛИ-НЕ, а последний капал - три 20 группы элементов ИЛИ-НЕ, группу элементов ИЛИ и элемент ИЛИ, причем в каждом блоке анализа приоритетов группа входов каждого регистра приоритета группы соединена с соответствующей группой кодовых входов устройства, первые входы элементов ИЛИ первой и второй групп и элементов ИЛИ-ЫЕ первой группы первого канала соединены с соответствующими запрос ными входами устройства, К -й выход М-го регистра группы каждого блока анализа приоритета (1, М = 1, 2,.О, где и - число заданий) соединен в 1 -и канале с вторыми входами З 5 М-х элементов ИЛИ-НЕ и ИЛИ первых групп, выходы элементов ИЛИ первой группы С -го канала ( С = 1, 2,., и ) соединены с первыми входами элементов ИЛИ-НЕ второй группы своего ка нала, объединены по схеме монтажного И и соединены с С м выходом соответстнующей группы кодовых выходов устройства, выходы элементов ИЛИ-НЕ первой группы каждого канала 45 каждого блока анализа приоритетов соединены с вторыми входами одноименных элементов ИЛИ-НЕ второй группы своего канала в каждом блоке анализа приоритетов выходы лемев ИЛИ 50 второй группы каждого канала, кроме последнего, соединены с вторыми входами одноименных элементов ИЛИ и ИЛИ-НЕ первых групп и с первыми входами одноименных элементов ИЛИ и ИЛИ-НЕ перных Групп и с первыми входами одноименных элементов ИЛИ второй группыследуннцего канала, в последнем канале каждого блока анализа приоритетов вторые входы элементов ИЛИ и ИЛИ-НЕ первых групп и первые входы племен ов ИЛИ - НЕ третьей группы соединены с выходами одноименных элементов Ю 1 И второй группы предпоследнего кацапа, в последних каналах всех блоков анализа приоритетов вторые входы элементов ИЛИ-НЕ третьей группы соединены с выходами одноименных элементов ИЛИ-НЕ второй группы, и каждом блоке анализа приоритетов выход каждого элемента ИЛИЕ третьей группы соединен с соответствуюшим входом следуюпях элементов ИЛИ-НЕ третьей группы своего канала, выходы элементов ИЛИ-НЕ третьей группы последнего канала каждого блока анализа приоритетов являются выходами соответсвующей группы сигнальных выходов устройства и соединены с входами элемента ИЛИ своего канала, выход элемента ИЛИ последнего канала каждого блока анализа приоритетов сое:,ц нен с соотнетснующими входами вснк элементов ИЛИ соответственно первой и второй группы, выход каждою о элемента ИЛИ группы соединен с соответствующими входами элементов 1 ц 1 И-НЕ третьей группы последнего капала каждого блока анализа приори гетов, кроме первого, соответствую. щие входы элементов ШП 1-11 Е третьей группы последнего канала первого блока анализа приоритетов соединены с входом логического нуля устройст" на, первая группа кодовых выходов устройства через нормально замкнутые контакты переключателя соединена с первой группой входов схемы сравнения, вторая группа входов которой соединена с второй группой кодовых выходов устройства, выход схемы сравнения является выходом прерывания устройства, нормально разомкнутые контакты переключателя, кроме последнего контакта, соединены с вхо дом логической единицы устройства, последний нормально разомкнутый контакт переключателя соединен с входом логического нуля устройства.1252777Составитель М.Кудряшов Редактор В.Петраш Техред В.Кадар Корректор Т.Колб Заказ 4621 /49 Тираж 671 Подписное ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Рауюская наб ., д. 4/5Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4