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

 

Союз Советских

Социалистических

Республик

О П И С А H N Е 1»1SSS402

И ОБРЕТЕНИЯ к АВторскому свидитильству (61) Дополнительное к авт. свид-ву— (22) Заявлено 18.04.75 (21) 2126102/24 с присоединением заявки № (51) М. Кл.

G 06 F 9/18

Гасударственный иамитет

Совета Мииистров СССР ов делам изобретеиий и открытий (23) Приоритет (43) Опубликовано 25.04.77. Бюллетень № 15 (53) УДК 681.322(088.8) (45) Дата опубликования описания 28.06.77 (72) Авторы изобретения

Ю. Н. Головко и И. А. Петухов (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ОЧЕРЕДНОСТИ

ВЫПОЛНЕНИЯ ЗАДАНИЙ

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

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

Недостатком этих устройств является необходимость предварительного назначения приоритетов заданиям.

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

Целью изобретения является расширение

5 функциональных возможностей устройства.

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

10 блока регистров соединены с информационными входами блока маскирования, управляюший вход которого соединен с первым выходом коммутатора, выходы блока маскирования соединены с информационными входами ассоциативного эа.

1б помина юще го блока, и нфо рма пион ные выходы ассоциативного запоминающего блока соединены с входами блока приоритетов, 11cpBI>IH выход которого соединен с установочным входом блока изменения ассоциативного поиска н первым входом

20 коммутатора, второй вход которого является входом устройства, вторая группа выходов блока приоритстов соединена с управляющими входами коммутатора и блока маскирования, третья группа выходов блока прноритегов является выходами

25 у строй ства - пе 1рв ый, второй н третий выходы

3 коммутатора соединены с управляющими входам11 блока изменеllия ассо!п1атив11ОГО IIGHoKa. 11 ыходы которого соединены с управляющими входами ассоциативного за1томина ющего блока, На. чертеже приведе«а схема устройства для определения очередности выполнения заданий. устройство содержит ассоциативный запоминающий блок 1, репяюгций задачу выборки наибольших или наименьших значений параметров, блок регистров 2, служащий для хранения параметров заданий, блок изменения ассоциативного поиска 3, предназначенный для выработки сигнала изменения характера ассоциативного поиска (по максимуму или Ilo минимуму), блок максироваиия

4, служащий для "наложения маски" на параметры выделенных зада1вш при переходе к анализу параметров заданий на очередном шаге, блок приоритетов 5, вырабатывающий сигнал номера наиболее приоритетного задания или сигналы на переход к анализу очередной группы параметров заданий, коммутатор 6, представляющий собой сдвигающий регистр.

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

Каждому параметру ставится в соответствие критерий его учета К, принимающий значения * 0" HJIH

"1", причем значение "1" соответствует случаю, когда необходимо отдать предпочтение большему

11 по абсолютной величине зна 1е1ию параметра, а 0 наоборот, меньшему. Наиболее IlpHupH e HaFI работа определяется последовательно в несколько шагов. На первом шаге осуществляется анализ в соответствии со значением критерия учета «о первому параметру из набора. Если на первом шаге однозначно не определен наибольший или наименьший параметр, осуществляется переход ко второму цигу, в котором производится анализ в соответствии со значением критерия учета по второму параметру из набора, но уже не всех работ, а только выделенных па нервом шаге, и т.д. до однозначного выбора параметра одной иэ работ. В случае, если не получен однозначный ответ после анализа всего набора параметров предпочтение отдается работе с наименьшим номером.

Работа предлагаемого устройсгва осушествляется следующим образом.

Предположим, что в очереди находится четыре работы, подлежащие выполце1ию. Каждая работа характеризуется тремя параметрами, причем по первому параметру предпочте1ше надо отдавать наименьшему (т.е. К1=0), по второму параметру— наибольшему (К, =1), по третьему параметру— наименьшему (К;-„О) .

Примем следующие значения параметров по каждой работе:

1 работа -- РI =3, Р1 =4, Рз=З;

2 -"- — Р, =4, Рт =5, Рз =6;

3 -"- — Р, =3, Р2 =4, Рз =8;

4 — "— — Р, =3, Р2 =3, Рз=9При анализе по первому параметру набора предпочтение будет отдано 1, 3 и 4-й работам, как работам с наименьшими параметрами, при анализе

10 на 2-м шаге из 1, 3 и 4-й работ будут выбраны 1 и 3 работы, как работы с наибольшими параметрами, а на третьем шаге из 1 и 3-й работы будет отобрана

1-я, как имеющая меньший параметр.

В исходном состоянии в блоке регистров 2

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

31 При поступлении на вход устройства сигнала о наличии очереди с первого выхода коммутатора поступают сигналы на управляющие входы блока регистров 2, блока изменения ассоциативного поиска 3, блока маскирования 4. При поступлении

25 сигнала на управляющий вход блока регистров с выходов его íà входы блока маскирования посылаются первые параметры заданий, а затем все параметры пересылаются с выходов блока маскирования на информационные входы ассо30 циативного запоминающего блока, так как при поступлении сигнала на управляющий вход блока маскирования открыты все его входы. В блоке изменения ассоциативного поиска при поступлении сигнала на управляющий вход с первого выхода

35 коммутатора 6 вырабатывается сигнал характера ассоциативного поиска (110 максимуму или минимуму), который поступает на управляющие входы ассоциативного запоминающего блока. В ассоциативном запоминающем блоке 1 величины

40 параметров сравниваются и отобранные по максимуму или минимуму с информационных выходов ассоциативпо10 запоминающего блока посылаются

lIH FIxojIbI блока приоритетов. В слу гае однозначного выбора параметра на соответствую1цем выходе

45 устройства появится OHI IIHII номера выбранного задания.

В случае не одно э1гач нос ги вы бра нного параметра (11есколько первых параметров заданий совпадают Ilo величине) на выходах устройства

50 сигнала «е появи1ся, а сигнал с первого выхода блока приоритетов 5 поступит на установочный вход блока изменения ассоциативного поиска 3 и на пе рв ый вход коммута гора 6. При поступлении сигнала на вход коммутатора, представляющего

М арбой сдвигающий ре ги стр, на первом выходе коммутатора будет "0", а на втором выходе — "1".

Сигнал на устаиово!IIoM входе блока измененИя ассоциативного поиска 3 предназначен для обеспечения сравнения кзитериев учета параметров за60 даний, обеспечивая вьпгачу сигнала на изменения

i1 102 ассоциативного поиска с выходов блока изменения ассоциативного поиска 3 на управляющие входы ассоциативного запоминающего блока 1. При несовпадении критериев >ета параметров задании, при переходе к анализу очередной группы параметров (постуилен»ю сигналов с выхода коммутатора 6), сигнал со второго выхода коммутатора поступает также на управляющий вход блока регистров 2, обеспечивая выдачу на информационные входы блока маскирования 4 второй группы параметров заданий.

С выходов блока маскирования 4 на информационные входы ассоциативного запоминающего блока 1 поступят параметры только тех заданий, которые вьщелены на предыдущем шаге, так как на управляющие входы блока маскирования поступают сигналы только с тех выходов блока приоритетов 5, которые на предыдущем шаге находились в состоянии "1". В ассоциативном запоминающем блоке сравниваются параметры заданий и выделенные в соответствии с критериями учета параметры посылаются в блок приоритетов, в случае однозначного выбора на одном из выходов устройства появится си> нал номера выбранного задания. В противном случае сигналы с выходов второй группы блока приоритетов поступают на управляющие входы соответственно коммутатора 6 и блока маскирования 4, а с выхода блока приоритетов 5 на установочный вход блока изменения ассоциативного поиска 3, сигнал с выхода коммутатора поступает на управляющие входы блока регистров и блока изменения ассоциа гивного поиска 3 и процесс анализа повторяется ewe раз до тех пор, пока нс будет произведен однозначный выбор номера задания.

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

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

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

llpHopHI|:ToB, блок маскирования, блок изменения ассоциативного поиска, причем выходы блока регистров соединены с информаш онными входами блока маскирования, управляющий вход которого щ соединен с первым выходом коммут:>тора, вьгходы блока маскирования соединены с информационными входами ассоциативного запоминающего блока, информационные выходы ассоциативного запоминающего блока соещгнены с входами блока приоритетов, первый выход которого соединен с установочным входом блока изменения ассоциативного поиска и первым входом коммугатора, второй вход которого является входом устройства, вторая гру>ша выходов блока нрноригетов соеди30 непа с управляющими входами коммугагора и блока маскирования, >ретья > руина выходов блока приоригетов являе гся выход гмн ус>ройства первый второй и >ретнй»ь>хо ll,l коммутатора

1 соединены с управляклцнми входамн блока измеМ пения ассоциа гивного гн>иска, выходы ко го1>ого соединены с унравлянлними вхо»ами ассоциативного заноминаклцего б:п>к;>.

Рспактор Е. Гончар

Закаа 459/23 ави гс((н !!. Крмловз

Тскрс;< Н. Бабурка Коррсктоо И. Гоксич

Тираж 1!! Я Цойнисн< с !!!!ИИПИ осунырствснного комичсза ("овсовы Микис(рои СГТ р поясным иаобрсгсний и oTKpL(Ièé

113035, Москвы. Ж-35, ауигскыи наб..п. 4 5 (Фнвиыл ППП "Пычснр . г. Уж(оров. у н Проскгныа. 4