Устройство циклического приоритета

 

Изобретение относится к вычислительной технике и может быть использовано в вычислительных системах, ориентированных на обработку запросов с циклической дисциплиной обслуживания. Цель изобретения - повышение быстродействия за счет исключения непроизводительных затрат времени на поиск запросов и свободных каналов. Новым в устройстве является использование регистров 3, 4, двух групп элементов ИЛИ 9, 10, трех элементов И 12, 14, 15, Устройство обеспечивает выбор очередной заявки на обслуживание и свободного канала за два такта независимо от их номеров . 1 ил.

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

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)5 G 06 F 9/46

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

flO ИЗОБРЕТЕНИЯМ И ОТКР6!ТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТ8У

1 (21) 4825763/24 (22) 15,05.90 . (46) 29.02.92.6юл. М 8 (72) А,Х.Ганитулин; В.Г.Попов и М.В.Михайлов (53) 681.325 (088.8) (56) Авторское свидетельство СССР

N. 1126960, кл. G 06 F 9/46, 1983.

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

N- 1418713, кл. G 06 F 9/46, 1988. (54) УСТРОЙСТВО ЦИКЛИЧЕСКОГО ПРИ.ОРИТЕТА (57) Изобретение относится к вычислительИзобретение относится к вычислительной технике и может быть использовано в вычислительных системах, ориентированных на обработку потока запросов с цикли-. ческой дисциплиной обслуживания.

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

Недостатком данного устройства является низкое быстродействие.

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

„„. Ж„, 1716516 А1 ной технике и может быть использовано в вычислительных системах, ориентированных на обработку запросов с циклической дисциплиной обслуживания. Цель изобре- тения — повышение быстродействия за счет искл ючения непроизводительных затрат времени на поиск запросов и свободных каналов. Новым в устройстве является использование регистров 3, 4, двух групп элементов ИЛИ 9,.10, трех элементов И 12, 14, 15, Устройство обеспечивает выбор очередной заявки нз обслуживание и свободного канала за два такта независимо от их номеров, 1 ил. нены с выходами элементов И первой группы, первый и второй входы каждого элемен( та И первой группы подключены к

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

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

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

Данное устройство обеспечивает выдачу кода запроса в свободный канал путем последовательного опроса регистра запроса посредством регистра сдвига,. а затем при обнаружении запроса — поиск свободного канала.

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

Время работы устройства можно определить по соотношению

Тср.1= 1ср.з + асср.к - (") где tcp.з — время поиска запроса; .

tcp.K — время поиска канала..

Если регистр запроса содержит и разрядов, а запросы могут фиксироваться в любом из его разрядов, то время поиска запроса может быть вычислено, как среднее время тмин.3 + tMSKc.Ç

tcp.з= ю

ГдЕ 1мин. =тги;

tMBKc.ç=ПСги.

Отсюда

n+1

tcp.з=

2 тги (2)

Аналогичным образом время поиска канала представляет собой соотношение мин;к + 1макс.к

1ср.к= Ф

5 где 1мин.к=1ги, 1макс.к Юги.

Отсюда к+1 асср.к=, тги.

2 (3) 10

Подставив выражения (2) и (3) в (1), получим и + к + 2 (4)

Из выражения (4) видно, что время передачи запроса на обслуживание зависит

20 как от числа запросов, так и от количества каналов.

Целью изобретения является повышение быстродействия за счет исключения непроизводительных затрат времени на поиск

25 запросов и свободных каналов.

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

35 регистров; единичные выходы которых соединены с первыми прямыми входами одноименных элементов И первой и второй групп соответственно, выходы которых подключены к первым входам одноименных

40 элементов И соответственно третьей и четвертой групп, выходы которых являются соответственно запросными выходами и выходами идентификации каналов устройства и соединены с нулевыми входами соот45 ветствующих разрядов первого и второго регистров соответственно, выходы первых элементов ИЛИ первой и второй группы подключены соответственно к единичному и нулевому входам триггера, единичный вы50 ход которого соединен с первым входом первого элемента И, второй вход которого подключен к тактовому входу .устройства. введены третий и четвертый регистры, по и-2 элемента ИЛИ в первую и вторую груп55 пы, второй, третий и четвертый элементы И, причем нулевой выход i-ro разряда третьего регистра (i=1, 2, ..., и) подключен к второму входу l-го элемента И первой группы, выход которого соединен с Нч инверсными входами (i+1)-ro

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

1-го элемента И второй группы, выход которого соединен с I-ми инверсными входами (i+1)-ro и последующих элементов И второй группы, единичные выходы третьего регйстра подключены к соответствующим входам третьего элемента И,. выход которого соединен с входом сброса третьего регистра, единичные выходы четвертого регистра соединены с соответствующими входами четвертого элемента И, выход которого подключен к входу сброса четвертого регйстра, выходы элементов ИЛИ первой групййподключены к единичным входам одноименнйх разрядов третьего регистра, выходы элементов ИЛИ второй группы прдключены к единичным входам одноименййх- разрядов четвертого регистра, j-й вход у- ro элемента

ИЛИ первой группы (j=i, 2...„(n — у+1); y=1, 2, ..., n — 1) подключен к выходу (j+ у-1)-го элемента И третьей группы, выход п-.ãî элемента И которой соединен с единичным входом и-го разряда третьего регистра, j-й вход у-го элемента ИЛИ второй группы подключен к выходу О+ у-1)-го элемента И третьей группы, выход и-го элемента И которой соединен с единичным входом п-го разряда третьего регистра, j-й вход y-ro элемента

ИЛИ второй группы подключен к выходу (j+

+ у-1)-го элемента И четвертой группы, выход и-го элемента И которой соединен с единичным входом п-го разряда четвертого регистра, нулевой выход триггера подключен к первому входу второго элемента И, второй вход которого соединен с тактовым входом устройства. выход второго элемента

И подключен к (и+1)-му входу третьего элемента И и вторым входом элементов И третьей группы, выход первого элемента И подключен к (п+1)-му входу четвертого элемента И и вторым входом элементов И четвертой группы, Сравнение . с прототипом показывает, что предлагаемое устройство отличается применением двух регистров, двух групп элементов ИЛИ, трех элементов И и их"связей с другими элементами схемы устройства.

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

На чертеже п ри в еде н а структурная схема устройства.

Устройство содержит регистры 1- 4, группы 5-8 элементов И, группы 9, 10 Элез5

55 ментов ИЛИ, триггер 11, элементы И 12-15, тактовый вход 16 устройства, выходы 17 разрешения обслуживания устройства, выходы

18 идентификации устройства, запросные входы 19 устройства и входы 20 готовности каналов устройства.

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

Исходное состояние устройства характеризуется тем, что регистры 1 — 4 и триггеры

11 установлены "0" (на чертеже не показано).

Запросы от абонентов и сигналы готовности каналов устанавливают в единичные состояния соответствующие разряды регистров 1 и 2 соответственно, Первый тактовый. импульс через открытый единичным сигналом с нулевого выхода триггера 11, элемент И 12 поступает на элементы И 7 группы для опроса схемы выбора запроса от абонентов на обслуживание. Непосредственно схема выбора выполнена на элементах И 5 группы по приоритетной схеме. За счет подключения выхода каждого элемента И 5 группы к инверсным входам всех последующих из нескольких запросов большим приоритетом обладает запрос от абонента с меньшим номером. Подключением входов элементов И 5 к нулевым выходам регистра 3 обеспечивается поиск запроса в соответствии с циклической дисциплиной обслуживания.

Рассмотрим работы схемы выбора на примере, Пусть в единичное состояние установлены разряды 2, 4 и п-й регистра 1. Учитывая, что с нулевых выходов регистра 3 на соответствующие входы элементов И 5 группы поступает разрешающие сигналы, единичный сигнал формируется на выходе второго элемента И 5 группы, запрещая формирование единичных сигналов на выходах всех последующих элементов И 5 группы, включая 4-й и п-й. Таким образом, тактовый импульс проходит через 2-й элемент И 7 группы на выход 172 разрешения обслуживания устройства, осуществляя выбор второго абонента. Этим сигналом дополнительно в устройстве переключается в

"0" второй разряд регистра 1, через первый и второй элементы ИЛИ 9 группы устанавливаются в единицу соответствующие разряды регистра 3 и триггер 11, разрешая прохо;кдение второго тактового импульса через элемент И 13 на опрос схемы выбора качала обслуживания. Схема выбора канала обслуживания идентична, но сигнал, сформированный на одном из выходов 18 идентификации устройства устанавливает триггер 11 в нулевое состояние, разрешая опрос в третьем такте схемы выбора очеред1716516

W = " (5)

Тср.2

50 и +к+2

55 ной заявки на обслуживание, Пусть к этому моменту времени пришел запрос от 1-ro абонента. В качестве очередной будет выбрана заявка от четвертого абонента, так как на соответствующий вход первого элемента поступает нулевой сигнал с нулевого выхода первого разряда. При этом сигналы установки в "1" поступает через соответствующие элементы ИЛИ 9 группы на 1, 2, 3 и

4-е разряды регистра 3. В пятом такте выбирается п-ый абонент на обслуживание, и все разряды регистра 3 устанавливаются в единичные состояния, что свидетельствует об окончании цикла обслуживания. В очередном 6-м такте при опросе схемы выбора канала обслуживания тактовый импульс с выхода элемента И 13 через элемент И 14, открытый с единичных выходов регистра 3, „устанавливает последний в нулевое состояние. По 7-му тактовому сигналу начнется

-новый цикл обслуживания абонентов. Схема выбора каналов обслуживания в дальнейшем работает аналогично рассмотренному выше.

Таким образом, при наличии заявок и готовых каналов выбор заявка и канала осуществляется за два такта и не зависит от числа абонентов и каналов.

Проведем сопоставительный анализ прототипа и предложенного устройства по быстродействию. Выигрыш в быстродействии можно оценить по выражению где Тср.1 рассчитывается по выражению (4).

Время выбора в предложенном устройстве

Тср.2 = 2 1ги . (6) Подставив выражения (4) и (6) в выражение (5), получим

Из выражения (7) видно, что выигрыш в быстродействии обеспечивают при любом соотношении числа каналов и запросов (за исключением, когда n=k=1).

Таким образом, предложенное устройство в сравнении с прототипом обладает существенным преимуществом, заключающимся в повышении быстродействия.

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

Устройство I. 11Kлического приоритета, содержащее дв» регистра, четыре группы

25 элементов И, первый элемент И, триггер, первый элемент ИЛИ первой группы и первый элемент ИЛИ второй группы, причем запросные входы и входы готовности каналов устройства подключены к единичным входам соответственно первого и второго регистров, единичные выходы которых соединены с первыми прямыми входами одноименных элементов И первой и второй групп соответственно, выходы которых подключены к первым входам одноименных элементов И соответственно третьей и четвертой групп, выходы которых являются соответственно запросными выходамй и выходами идентификации каналов устройства и соединены с нулевыми входами соответствующих разрядов первого и второго регистров соответственно, выходы первых элементов ИЛИ первой и второй групп подключены соответственно к единичному и нулевому входам триггеров, единичный выход которого соединен с первым входом первого элемента И; второй вход которого подключен к тактовому входу устройства, о тлича ющееся тем,что,сцельюповышения быстродействия за счет исключения непроизводительных затрат времени на поиск запросов и свободных каналов, в него введены третий и четвертый регистры., по и-2 (где и — число запросов) элементов ИЛИ в первую и вторую группу, второй, третий и четвертый элементы И, причем нулевой выход i-го разряда третьего регистра (l=1, 2, ..., n) подключен к второму прямому входу i-го элемента И первой группы, выход которого, кроме и-го элемента И, соединен с i-ми инверсными входами (i+1)-ãî и последующих элементов И первой группы, нулевой выход

j-го ()=1,..., m) разряда четвертого регистра подключен к второму прямому входу i-го элемента И второй группы, выход которого (кроме m ro элемента И, где m — число каналов) соединен с j-ми инверсными входами (j+1)-ro и последующих элементов И второй группы, единичные выходы третьего регистра подключены к соответствующим входам второго элемента И, выход которого соединен с входом сброса третьего регистра, единичные выходы четвертого регистра соединены с соответствующими входами третьего элемента И, выход которого подключен к входу сброса четвертого регистра, выходы к — х (k=2, ..., и) элементов ИЛИ первой группы подключены к единичным входам одноименных разрядовтретьего регистра, выходы

l-х (l=2, ..., m) элементов ИЛИ второй группы гюдключены к единичным входам одноименных разрядов четвертого регистра, 8-й входу-го элемента ИЛИ первой группы ($=1,2, ..., (п10

1716516

Составитель А.Ганитулин

Техред M.Mîðãåíòàë КорректорЛ. Бескид

Редактор Н.Коляда

Заказ 613 Тираж Подписное

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

113035, Москва; Ж-35, Раушская наб„4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101

-у+ 1); у=1, 2, ..., и — Ц подключен к выходу($+ -1)-го элемента И третьей группы, выход и-го элемента И которой соединен с единичным входом и-го разряда третьего регистра

Ь-й вход q-ro (b=1... (m — q+1, q=1 ...m-1) эле- 5 мента ИЛИ второй группы подключен к выходу b+q-1-го элемента И четвертой группы, выход m-ro элемента И которой соединен с единичным входом m-го разряда четвертого регистра, нулевой выход триггера подклю- 1 чен к первому входу четвертого элемента И, второй вход которого соединен с тактовым входом устройства, выход четвертого элемента И подключен к{п1+1)-му входу третьего элемента И и вторым входам элементов

И третьей группы, выход первого элемекта

И подключен к (п+1)-му входу второго элемента И и к вторым входам элементов И четвертой группы.