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

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

Цел1 изобретения - расширение области применения устройства за счет учета как приоритетов заданий, так и приоритетов тфогессоров.

В основу устройства положен сле- дуюишй приинип распределения заданий по процессорам, В многопроцессорной вычислительной системе имеется множество заданий (программ) с приорите тами. ВОЗМ15ЖНО совпадение приоритето некоторых заданий. Задания, готовые к выполнению, выставляют в устройство распределения запросы на обслуживание, которые являются требования ми о предоставлении вычислительных ресурсов (процессоров). В системе имеется также группа процессоров. Процессорам, выполняюп1им задания, установлены приоритеты этих заданий, Свободные процессоры имеют наименьший приоритет, не совпадающий с при-т оритетом ни одного из заданий. Все процессоры, исключая неисправные, выставляют в устройство распределе ния запросы на предоставление заданий .

Устройство распределения заданий процессорам определяет задание с высшим приоритетом из множества заданий, готовых к выполнению, и выделяет процессор с низшим приорите - Tt jM. В работы многопрог;ессор- ной системы в режиме с абсолютной приоритетной дисциплиной в устройстве происходит сравнение приоритета найденного задания с приоритетом выделенного процессора. Если приоритет зада}1иЯ выше приоритета процессора, 1 о он приступает к вьшолнению э-1 ого задания независимо от того, был ли этот процессор свободным или выполнял менее приоритетное задание. Прерванное зпдание поступает в груп- ну заданий, г отовых к выполнению. Если приоритет задания оказался ниже приоритета процессора, то устройство гделечия не разрешает прерывание процессора.

В случае системы с относительной приоритетной дисциплиной н.чзн.чченис Рыдсленного наиболее при

10

5

- 5 в - 20

50 55

30

4S

оритетного задания происходит только i;. i свободный процессор.

На чертеже изображена функциональная схема устройства.

Устройство содержит блоки 1 анализа приоритетов первой W второй групп, кодовые входм 2 устройства, запросные входы 3 устройства, группы сигнальных выходов 4 устройства, вход 5 логического нуля устройства, элементы ИЛИ 6 группы, первую группу кодовых выходов 7 устройства, переключатель 8, схему 9 сравнения, выход 10 прерьгеания устройств. Каждый блок 1 содержит группу регистров 11, каналы 12 и 13. Каждый канал 12 и 13 содержит входь и выходы )А и 15, элементы ИЛИ-НЕ 16, ИЛИ 17, Ш1И-НЕ 18, ИЛИ 19 (кроме последнего канала). Последний канал 13 в каждом блоке 1, кроме того, содержит элемент ИЛИ 20 и группу элементов ИЛИ-НЕ 21, Устройство содержит также группу кодовых выходов 22, вмод 23 логической единицы устройства .

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

На входы 2, подключенные к блокам 1, соединенным с выходами 7 подаются коды приоритетов заданий. Допускаются совпадающие коды. Задания, готовые к выполнению, выставляют запросы на облужнвание на

входы 3. Блоки 1 зтой группы из всех заданий, выставивших запросы,

выявляют задание с минимальным (выс- вшм) кодом приоритета. При этом возбуждается один из выходов 4 того блока 1 , в канале которого находится это задание, а высший (минимальный) код приоритета выбранного задания окажется на выходах 7, В случае, если на входах 2 одного блока Г имеется несколько совпадающих высших кодов приоритетов, то возбуждается выход А только того канала, номер которого в этом модуле наименьший. Если совпадаюпие высшие коды приоритетов имеются на входах 2 нескольких блоков 1, то возбуждается выход А только того блока 1, номер которого наименьший. При этом на выходе элемента ИЛИ 20 этого блока 1 вырабатывается единичный сигнал, который через элементы ИЛИ 6 поступает на соответствующие входы 5 во все последующие блоки

этои группы и запрещает этим

блокам пыработку сигиллон на выходах 4.

Таким образом, первая группа блоков 1 выявляется из всех заданий, выставивших запросы, единственное задание с высшим приоритетом. Позиционный адрес этого задания (начальный адрес nporpa fMbi) будет на одном из выходов 4 модулей 1 этой группы, а код приоритета - на группе выходов 7.

На входы 2 второй группы блоков I, подключенных к выходам 22, поступают инверсные коды приоритетов процессоров. Эта группа блоков I, работая аналогично описанной вьппе первой группе, выявляет один канал, на вход 2 которого поступил минималный код приоритета. Поскольку на входы 2 второй группы блоков были поданы инверсные коды приоритетов процессоров, то будет возбужден один из выходов Д, который укаэьгеает на процессор с максимальным (низшим) кодом приоритета. При этом на выходах 22 будет инверсный код приоритета выявленного процессора.

В случае абсолютной приоритетной дисциплины обслуживания заданий переключатель 8 установлен в положение, изображенное на чертеже. Тогда на первую группу входов схемы 9 поступает код приоритета задания с выходов 7. На вторую группу входов схемы 9 поступает код с выходов 22.

При коде с выходов 22, большем кода с выходов 7, соответствующем условию, когда приоритет выявленного задания превышает приоритет задания, выполняемого вьщепенньм процессором, схема 9 вьфабатьгеает сигнал на выход 10, разрешаю1Щ1Й прерывание этого процессора с целью переназначенья его на новое, более приоритетное задание. Прерываемый процессор традиционным способом заноси в описатель прерванного задания его состояние и устанавливает запрос на продолжение выполнения этого задания на соответствующем входе 3 первой группы блоков 1. Процессор, получивший новое задание, присваивает себе его приоритет к выполнению этого задания, а запрос на входе 3 первой группы блоков 1, соответствующем заданию, получившему назначение на процессор, гггимается, Устройство начинает новьгй цикл работы.

7774

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

В случае относительной приоритетной дисциплины обслуживания заданий на первую I pynny входов схемы 9 с переключателя 8 поступает код 1,.10.

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

Блок работает следующим образом .

Коды приоритетов запросов на обслуживание поступают в регистры J1 и фиксируются в них. Высшему приоритету соответствует минимальньш код. Блок I работоспособен при подаче в регистры I1 произвольного набора

кодов приоритетов. Допустимо совпадение кодов приоритетов. На входы 3 поступают запросы абонентов (наличие запроса соответствует логическому нулю).

Первый канал I2 анализирует состояние запросов на входах 3 (14) и назначения старших разрядов регистров 1I. При отсутствии запроса в каком-либо канале логическая единица с входа 14 этого канала независ - мо от значения старшего разряда а соответствующем регистре II устанавливает в единицу выходной сигнал элемента ИЛИ 19 и независимо от значе- ния следующего разряда этого регистра устанавливает в единицу выходной сигнал следующего канала 12 и т.д. В итоге, при отсутствии запроса единичный сигнал с хода 14, пройдя через все элементы ИЛИ 19 и ИЛИ-НЕ 21 данного канала, вырабатывает нулевой сигнал на выходе 4 данного блока 1 (отсутствие необходимости обслуживания) .

При наличии запросов пл входах

14 имеются логические нули, tie влияющие на прохождение сигналор с рлз- рядных входов 15 чоррз л мсяпм 16-)У.

;ч,1ч( нссх гтлрших р, пряд и итиг1р()я 11 приходят ил рыходь зле- или 17 iit pnoro канала 12. Выходы нгрх лем 11тс р Ш1И 17 гоеди- Heiitii С1/дач г другугм и подключены к

cooTnt TCTPVKirupMy пыходу 1 руппы выхо- Д(1В 7 (22). Такое соещ1ненне РЫХО- доп л пгческих элементов известно под л 1 аиием монтажной логики и ре;1личует логическую операцию И на соответствующем выходе г руппы 7, единица будет только в том случае, кот да на входы всех элементов ИЛИ 17 поступают логические единицы. Они санную схему из элементов ИЛИ 17 и монтажной логики И можно назвать схемой Ш1Я в.Iлeлeния минимального значения И1 аналиэуемьгх одноименных разрядов регистров II. Действительно, на любом выходе группы 7 (22) логи- чекан единица будет при условии наличия единиц ru: всех соответствуюишх раярядах регистров 11, а логический нуль - при условии наличия хотя бы .одного нуля в этих разрядах.

Сформированньт таким образом сиг- нал с выхода группы 7 поступает в элементы ИЛИ-НЕ 18, в которых логически суммируется с инверсными значениями гтарших разрядов соответсвую ВДНХ регистров 11, поступивших с выходов элементов И.ПИ-НЕ 16.

Кслн значения анализируемых старших разряд( совпадают (все единипи или Bcf нули) , то по этим разрядам еще невозможно сделать вьтод о номере канала, который среди каналов, выстапив1пих запросы, имеет в соответствующем регистре 11 минимальный код R этом случае необходимо на выходах первот о канала 12 в блоках 1 , куда П(.)ступш1и запросы, выработать логические нули, которые, поступив на запросные входы 1 следующего канала 12, С01ттветствуют запросам на анализ слеДуюшег-о разряда кодов приоритетов. Это реализуется таким образом. Предположим, что во всех старших разрядах регистров 11 логические единицы. Тогда на первом выходе группы 7 также логическая единица, которая при прохождении через элементы 18 и 19 обеспечивает тре- Гуемые логические нули на всех выХг:/1,1Х ;аи:-;ЛЛ 1 2 .

fV/ M nci. x старигих разрядах рс111гтр( п II ло1-ичегкие нули, то if.i II.чл1. I;P(v.r)) jtoinfH через элеменс

Ю 15 20 25

Q

Q

0

5

ты 16, 18 и 19 обеспечивают ноявле- fnuj требуемых лог ических 1гулей на всех выходах капала 12.

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

В остальных каналах, анализированные разряды которых содержат нули, должен быть произведен анализ следующих разрядов. На выходах этих каналов 12 необходимо вьфабо- тать логические нули, соответствующие запросам на входах следующего канала. Это реализуется таким образом. При несовпадении значений анализируемых разрядов в регистрах 11 на соответствующем выходе 7 (22) будет логический нуль. При этом на выходах элементов 19 будут логические сигналы, совпадающие со значениями анализируемых разрядов регистров II, что и требовалось получить.

Благодаря наличию элементов ИЛИ- iiF, 21 последнего канала 13 на соответствующем выходе Д вырабатывается логическая единица, если в одноименном регистре I1 находится минимальный (высший) код приоритета канала среди всех каналов, выставивщих запросы на входах 3. Дополнительные связи между элементами ИЛИ-НЕ 21 канала 13 исключают возможность появления логических единиц одновременно на двух или более выходах 4. При наличии минимальных кодов приоритетов в нескольких регистрах 11 логическая единица вьфабатывается на выходе 4, порядковый номер которого соответствует минимальному номеру канала, в который поступил запрос,

Появление логической единицы на любом из выходов 4 предыдущего блока 1 формирует единицу на выходе элемента ИЛИ 20, которая запрещает выработку сигналов на выходах 4 последующих блоков 1, в которых могут находиться ко/ды приоритетов, равные )ыделе}и1ому в 1федыдуп1ем блоке.

71252777

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

вы им сл на 5 то ИЛ эл ди ме He вс ры гр им 5 пы те тр ст ШБ 0 вы пы ан да ны 25 с вы ка со ле 30 пе ДО с то го 35 ор пш гру бл с в 40 ва

Устройство для приоритетного распределения заданий процессорам, содержащее две группы элементов ИЛИ, первую группу блоков анализа приоритетов, отличающееся тем, что, с целью расширения области применения устройства за счет учета как приоритетов заданий, так и приоритетов процессоров , устройство содержит вторую группу блоков анализа приоритетов, схему сравнения и переключатель, причем каждый блок анализа приоритетов группы содержит группу регистров приоритета и каналы, каждый из которых, кроме последнег о, содержит две группы элементов ИЛИ и две группы элементов ИЛИ-НЕ, а последний капал - три группы элементов ИПИ-НЕ, группу элементов ИЛИ и элемент ИПИ, причем в каждом блоке а)1ализа приоритетов группа входов каждого регистра приоритета группы соединена с соответствующей группой кодовых входов устройства, первые входы элементов ИЛИ первой и второй групп и эломснтов ИЛЯ-МЕ первой группы первого канала соединены с соответствующими запрос нь1ми входами устройства, К -и выход W-ro регистра группы каждого блока анапиза приоритета (К, М 1, 2,.,. (1, где п - число заданий) соединен в К -м канале с вторыми входами М-х элементов ИЛИ-НЕ и ИЛИ первых групп, выходы элементов ИЛИ первой группы С-го канала (С 1, 2,-i ,h соединены с первьп ш входами элементов ИЛИ-НЕ второй группы своего канала, объединены по схеме монтажного И и соединены с С м выходом соответствующей группы кодовых выходов устройства, выходы элементов ИЛИ-НЕ первой группы каждого канала каждого блока анализа приоритетов соединены с вторыми входами одноименных элементов ИЛИ-НЕ второй группы своего канала в каждом блоке анализа приоритетов, выходы элементов ИЛИ второй группы каждого канала, кроме последнего, соединены с вторыми входами одноименных элементов ИЛИ и ИЛ7И-НЕ первых групп и с первыми входами одноименных элементов ИЛИ и ИЛИЧ1Е пер8

0

вых групп и с первыми входам 1 одноименных элементол ИЛИ второй г руппы следующего канала, в гюследнсм канале каждого блока анализа приорите- 5 тов иторые входы элементов ИЛИ и ИЛИ-НР первых групп и первые входы элементов третьей группы соединены с выходами одноименных элементов ИЛИ второй группы предпослед- Hei o канапа, в последних каналах всех блоков анализа приоритетов вторые входы элементов ИЛИ-НЕ третьей группы соединены с выходами одноименных элементов ИЛИ-НЕ второй груп- 5 пы, в каждом блоке анализа приоритетов выход каждого элемента ИЛИ-НЕ третьей группы соединен с соответствующим входом следующих элементов ШБ1-Р1Е третьей группы своего канала, 0 выходы элементов ИЛИ-НЕ третьей группы последнего канала каждого блока анализа приоритетов являются выходами соответсвующей группы сигнальных выходон устройства и соединены 5 с входами элемента ИЛИ своего канала, выход элемента ИГТИ последнего канала каждого блока анализа приоритетов сорлпнен с соответсвуюшими входами лесу, элементов ИЛИ соответственно 0 перпой и второй группы, выход каж- ДО141 элемента ИЛИ группы соединен с спответствук1 Щ1ми входами элементов третьей группы последнего капала каждого блока анализа при- 5 оригетов, кроме первого, соответствую- пше входы элементов ШП ШЕ третьей группы последнего канала первого блока анализа приоритетов соединены с входом логического нуля устройст- 0 ва, первая группа кодовых выходов

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

-I

-hm;;1-r

Ri

Составитель М.Кудряшов Редактор В.Петраш Техред В.КадарКорректор Т.

Заказ Д621/49Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

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

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

Изобретение относится к вычисли тельной технике и может быть использовано в многопроцессорных ЭВМ для аппаратурной реализации функций операционной системы по диспетчироваиию заданий, готовых к выполнению. Цель изобретения - расширение области применения за счет учета как приоритетных заданий, так и приоритетов процессоров . Устройство содержит элементы ИЛИ, схему сравнения, две группы блоков анализа приоритетов и переключатель. Поставленная цель достигается благодаря учету приоритетов как заданий, так и процессоров, реализация абсолютной и относительной дисциплины обслуживания и возможности работы при совпадении нескольких кодов приоритетов. 1 ил. г сл