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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИК

«I% «И) A t

«504 G 06 F 9 46

°

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

К A STOPCKOhIY СВИДЕТЕЛЬСТВУ

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

ГЮ ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPbITPM (21) 3727173/24-24 (22) 06 ° 04. 84 (46) 23.08.86. Бюл. Р 31 (71) Институт технической кибернетики АН БССР (72) М.М.Маханек и А.Г.Ярусов (53) 681.325 (088.8) (56) Авторское свидетельство СССР

Р 1001101, кл. С 06 F 9/46, 1983.

Авторское свидетельство СССР

Р 1005055, кл. С 06 Р 9/46, 1983. (54) УСТРОЙСТВО ДЛЯ ПРИОРИТЕТНОГО

РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ ПРОЦЕССОРАМ (57) Изобретение относится к вычисли тельной технике и моиет быть использовано в многопроцессорных ЭВМ для аппаратурной реализации функций операционной системы по днспетчированию заданий, готовых к выполнению. Цель изобретения - расширение области применения за счет учета как приоритетных заданий, так и приоритетов процессоров. Устройство содержит элементы ИЛИ, схему сравнения, две группы блоков анализа приоритетов и переключатель. Поставленная цель достигается благодаря учету приоритетов как заданий, так и процессоров, реализация абсолютной и относительной дисциплины обслуживания и возмо кности работы при совпадении нескольких кодов приоритетов. 1 ил.

1252777

Иэ«1 р.т>11ие относится к вычислител1,llcI» гехнике и может быть использов>зно н устройствах приоритетного процес с оры, исключая неисправные, выставляют в устройство распределения запросы на предоставление заданий.

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

35 высшим приоритетом из множества за— даний, готовых к вь1полнению, и выделяет процессор с низшим приорите»том. В случ11е работы многопроцессор— ной системы в режиме с абсолютной

40 приоритетной дисциплиной в устройстве происходит сравнение приоритета найденног«:задания с приоритетом выделенного процес<.ора. Если приоритет задания выше приоритета процес— сора, то он приступает к выполнению этого задания независимо от того, был ли этот процессор свободным или вып nJIII>IJ м cll ее приоритетное задание.

Прерванное задание поступает в группу заданий, готовых к выполнению.

Если приоритет задания оказался ниже приоритета процессора, то устройство расп! «дслечия не разрешает прерывание пр>зцессора, 55

В глу зе 1111б1ть1 системь1 с относит е11 1 11 «й 11 > и «!>и т е т н «Й f C IJH 11 JI HH O Il

11>1зн;1 1еиис 1>ыд>лени«го наиболее приуправления распределением заданий процессорам многопроцессорных вычис- 5 лительных систем.

Цсл1> изобретения — расширение области применения устройства за счет учета как при«ритеT«B заданий, так и 11риоритетов про1>ессоров.

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

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

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

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

ИЛИ-НЕ 21. Устройство содержит также группу кодовых выходов 22, вход 23 логической единицы устройства.

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

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

Допускаются совпадающие коды. Задания, готовые к выполнению, выставляют запросы 1 на облуживание на входы 3. Блоки 1 этой группы из всех заданий, выставивших запросы, выявляют задание с минимальным (высшим) кодом приоритета. При этом возбуждается один из выходов 4 того бло" ка 1, в канале которого находится это задание. а высший (минимальный) код приоритета выбранного задания окажется на выходах 7. В случае, если на входах 2 одного блока 1 имеется несколько совпадающих высших кодов приоритетов, то возбуждается выход

4 только того канала, номер которого в этом модуле наименьший, Если совпадающие высшие коды приоритетов имеются на входах 2 нескольких блоков 1, то возбуждается выход 4 только того блока 1, номер которого на1 меньший. При этом на выходе элемента

ИЛИ 20 этого блока 1 вырабатывается единичный сигнал, который через элементы ИЛИ 6 поступает на соответствую. щие входы 5 во все последующие блоки этой группы и запрещает этим

1 „ ) 2 7 7 7 блокам выработку сигналов на выходах 4.

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

На входы 2 второй группы блоков

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

В случае абсолютной приоритетной дисциплины обслуживания заданий переключатель 8 установлен н положение, изображенное на чертеже. Тогда на первую группу входов схемы 9 поступает код приоритета задания с выходов 7. На вторую группу нходов схемы 9 поступает код с выходов 22, При коде с выходов 22, большем кода с выходов 7, соответстнующем условию, когда приоритет выянленного задания превышает приоритет задания, выполняемого выделенным про- 40 цессором, схема 9 вырабатывает сигнал на выход 10 разрешающий прерывание этого процессора с целью перенаэначенья его на новое, более приоритетное задание. Прерываемый процессор традиционным способом заносит в описатель прерванного задания его состояние и устанавливает запрос на продолжение выполнения этого задания на соответствующем входе 3 пер- N вой группы блоков 1. Процессор, получивший новое задание, присваивает себе его приоритет к выполнению этого задания, а запрос на входе 3 первой группы блоков 1, соответствующем заданию, получившему назначение на процессор, снимается ° Устройство начинает новый цикл работы.

При v(л< вии, когда приоритет выявленного первой группой блс кон I задания не превыша т приоритета процессора, выявленного группой блоков

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

При этом сигнал на выходе 10 вырабатывается только в том случае когда

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

Коды приоритетов запросов на обслуживание поступают н регистры l! и фиксируются н них. Высшему приоритету соответствует минимальный код.

Блок 1 работоспособен при подаче в регистры 11 произвольного набора кодов приоритетов. Допустимо совпадение кодов приоритетов. На входы

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

Первый канал 12 анализирует состояние запросов на входах 3 (14) и назначения старших разрядов регистров I I ° . При отсутствии запроса в каком-либо канале логическая единица с входа 14 этого канала независимо от значения старшего разряда в соответствующем регистре 11 устанавливает в единицу выходной сигнал элемента ИЛИ 19 и независимо от значения следующего разряда этого регистра устанавливает в единицу выходной сигнал следующего канала 1 2 и т.д.

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

При наличии запросов на входах ! 4 имеются логические нули, ие влияющие на прохождение сигналов с разI рядиых входов 5 через 1лемеи м 6-19.

12 з2777 ь

I(II>lo(х с T»Ðø>з

I и тр >з> 11 ирих< пят нл вьзходы эле— м II I <>н IIIIII 7 II(!>в(>Г(> к зззлл(з 2. Вь<—

v(>jill всех э<(ем< нтов ИЛИ 17 соединеиь(один с другим и подключены к 5

С (>(>1 и f Т Г ТР»(»П<(МУ ВЫХОДУ I P Ï ПЫ ВЫХО д< в 7 (2? Т,<кое соединение выходов л згических элементов известно иод илэвлгизем монтажной логики и реализует логическую операцию И на 10 соотвстствуY>III(M выходе группы 7, единица будет только в том случае, когда нл входы всех элементов ИЛИ

17 иоступлют логические единицы. Описанную схему из элементов ИЛИ 17 и 15 мснтлжнсй логики И можно назвать схем(й дчя вь.>зелен»я минимального знлчен»я »з лнллиэуемых одноименных разряд<>в регистров 1!. Действительно, ил лз<>бом выходе группы 7 (22) логи- 20 чекля ед»ница будет при условии наличия единиц г<(1 всех соответствующих рлззр>здлх регистров 11, л логический нуль — (зри условии нлличия хотя бы одногo> нуля в этих разрядах. 25

Гформировлнный таким образом сиг-, нал с выхода группы 7 поступает в элементы ИЛИ-НЕ 18, в которых логиче< к» сумм»руется с инверсными зна—

«eI«IEI«»«(1.EIpIlI»x рлэрядов соответсвую- 30 ш»х рез истров 11, поступивших с вых<>дов элемен I ov ИЛИ-НЕ 16.

Если э илч еи»я ли лл»эиру емых стлр—

DI»x разрядов соззплдлн>т (все единицы или в< е нули), то I>o этим разрядам еще ненозм(жно спел(зть вывод о номе— ре клнллл, который среди каналов, вы< тлвивппзх EIE!po<.bl, имеет в соответс TE>vH>IIlем регистре ! минимальный код .

В этом случае необходимо нл выходах первого клнала 12 в блоках 1, куда п<зступизш .запросы, выработать лот ические нули, которые, поступив на запросные входы 1 следующего канала !2, соответствуют запросам на лнллиэ следуюпзего разряда кодов ирисритетов. Зтo реализуется таким образом. Ирслположим, что во всех стлрп(»х разрядах регистров 11 логичес кие единш<ьз. Тогда на первом вы50 ходе группы 7 также логическая едиII»lIr которая з ри прохождении через элем< I<1bl l 8?? i 9 ??????????>ечивлет треГУЕ.П,(Е >I<>ГИЧЕСКИЕ НУЛИ НЛ ВСЕХ ВЫх»,(,зх E.л>(; ° I I I 2

1 с (з; всех сlap I1 лс(»чс< кис нули, то

> I(;I I I (ч (1. l>(Y <»I>jl(< <и>< ч c p p I эл ем е>з ты 6, 18 и 19 обс < Il(. Чивлют появление требуемых логических нулей на в< (x выходлх канала 12.

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

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

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

При наличии минимальных кодов приоритетов в нескольких регистрах 11 логичPñE<àÿ единица вьграбатывается нл выходе 4, порядковый номер которого соответствует минимальному номеру канала, в который поступил запрос, Появление логической единицы на любом из выходов 4 предыдущего блоxa I формирует единицу нл выходе элемента ИЛИ 20, которая запрещает выработку сигналов на выходах 4 пос<ледующих блоков 1, в кот >рых могут находиться коды приоритетов, равные выделеьпзому в иредыдуп!ем блоке.

1212?77

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

Устройство для приоритетного распределения заданий процессорам, содержащее две группы элементов ИЛИ, 5 первую группу блоков анализа приоритетов, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения устройства за счет учета как приоритетов заданий, так и приоритетов процессоров, устройство содержит вторую группу блоков анализа приоритетов, схему сравнения и переключатель, причем каждый блок анализа приоритетов группы содержит группу регистров приоритета и каналы, каждый из которых, кроме последнего, содержит две группы элементов ИЛИ и дне группы элементов

ИЛИ-HF., а последний капал — три 20 группы элементов ИЛИ-HF., группу элементов ИЛИ и элемент HJIH, причем в каждом блоке аггализа приоритетов группа входов каждого регистра приоритета группы соединена с соответствующей группой кодовых входов устройства, первые входы элементов ИЛИ первой H второй гppilii H элемсHTGB

ИЛИ-1Е первой группы первого канала соединены с соответствующими запрос- 30 ными входами устройства, K -й выход

М-го регистра группы каждого блока анализа приоритета (k M = 1, 2,...

О, где и — число заданий) соединен в М -и канале с вторыми входами З

M-х элементов ИЛИ-НЕ и HJIH первых групп, выходы элементов ИЛИ первой группы С -го канала (С = 1, 2, ° . °, h ) соединены с первыми входами элементов ИЛИ-HF. второй группы своего ка- 40 нала, объединены по схеме монтажного И и соединены с (. -.м выходом соответстнующей группы кодовых выходов устройства, выходы элементов

ИЛИ-HF, первой группы каждого канала 4s каждого блока анализа приоритетов соединены с вторыми входами одноименных элементов ИЛИ-HE вт арой rpy ппы своего канала в каждом блоке анализа приоритетов, выходы элементов ИЛИ gp второй группы каждого канала, кроме последнего, соединены с вторыми входами одноименных элементов ИЛИ и ИЛИ-НЕ первых групп и с первыми входами одноименных элементов ИЛИ и ИЛИ-НЕ первых групп и с первымгг входами одноименных элемевтоп ИЛИ второй группы сл едуннцсг. о канал а, в последнем канале каждого блока анализа приоритетов pторые входы элементов ИЛИ и

ИЛИ-HE первых групп и первые входы элеменг ов ИЛИ вЂ” НF. третьей группы соединены с выходами одноименных элементов И11И второй группы предпоследнегс канала, в последних каналах всех блоков анализа приоритетов вторые входы элементов ИЛИ-НЕ третьей групггы соединеггы с выходами одноименных элементов ИЛИ-HE второй группы, и каждом блоке аггализа приоритетов выход каждого элемента ИЛИ-+1Е третьей группы соединен с соответствующим входом следуюпях элементов

ИЛИ-НЕ третьей группы своего канала, выходы элементов ИЛИ-НЕ третьей группы последнего канала каждого блока анализа приоритетов являются выходами соответсвующей группы сигнальных выходов устройства и соединены с входами элемента ИЛИ своего канала выход элемента ИЛИ последнего канала каждого блока анализа приоритетов

c:оед нен с соответсвующими входами вс -к элемеггтов ИЛИ соответственно псpBoA ii Bj opoli группы, выход каждог о элемента ИЛИ группы соединен с с< ответствукппими входами элемеH топ 1г !И-НЕ тре1ьей группы последнего капала каждого блока анализа приори гетов, кроме первого, соответствуюпгие входы элементов ШП1-ffE третьей группы последнегo канала первого блока анализа приоритетов соединены с входом логического нуля устройст" ва, первая группа кодовых выходов устройства через нормально замкнутые контакты переключателя соединена с первой группой входов схемы сравнения, вторая группа входов которой соединена с второй группой кодовых выходов устройства, выход схемьг сравнения является выходом прерывания устройства, нормально разомкнутые контакты переключателя, кроме последнего контакта, соединены с вхо. дом логической единицы устройства, последний нормально разомкнутый контакт переключателя соединен с входом логического нуля устройства.

1252777

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

Редактор В.Петраш Техред B.Кадар Корректор Т.Колб

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

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

1 i 3035, Москва, Ж-35, Рауюская наб ., д. 4/5

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