Устройство циклического приоритета Советский патент 1992 года по МПК G06F9/46 

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

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

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

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

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

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

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

Проведем оценку быстродействия устройства.

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

Тср.1- tcp.3 + tcp.K

(1)

где tcp.a - время поиска запроса; tcp.K - время поиска канала. Если регистр запроса содержит п разрядов, а запросы могут фиксироваться в любом из его разрядов, то время поиска запроса может быть вычислено, как среднее время

tcp.3

1мин.З + tiytaicc.3

Где , Т.макс..

Отсюда

п +1

2

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

ср,э

ti-и

(2)

. 1мин.к Ь twaxc.K

tcp.K--К--

где tMi/tH.

1маКС..

Отсюда

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

. т п + к + 2(л

1ср.1 2 ги W

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

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

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

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

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

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

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

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

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

ИЛИ первой группы (, 2(n-y+1); )1,

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

Сравнение . с прототипом показывает, что предлагаемое устройство отличается применением двух регистров, двух fруйп элементов ИЛИ, трех элементов И и их связей с другими элементами схемы устройства... „ ,.

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

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

Устройство содержит регистры 1-4 группы 5-8 элементов И, группы 9, 10 Элементов ИЛИ, триггер ,11, элементы И 12-15, тактовый вход 16 устройства, выходы 17 разрешения обслуживания устройства, выходы 18 идентификации устройства, запросные

входы 19 устройства и входы 20 готовности каналов устройства.

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

Исходное состояние устройства харак0 теризуется тем, что регистры .1-4 и триггеры 11 установлены О (на чертеже не показано).

Запросы от абонентов и сигналы готовности каналов устанавливают в единичные

5 состояния соответствующие разряды регистров 1 и 2 соответственно.

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

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

0 регистра 3 обеспечивается поиск запроса в соответствии с циклической дисциплиной обслуживания.

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

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

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

5 канала обслуживания. Схема выбора канала обслуживания идентична, но сигнал, сфор- мирсзанный на одном из выходов 18 идентификации устройства устанавливает триггер 1-1 в нулевое состояние, разрешая опрос в третьем такте схемы выбора очередной заявки на обслуживание. Пусть к этому моменту времени пришел запрос от 1-го абонента. В качестве очередной будет выбрана заявка от четвертого абонента, так как на соответствующий вход первого элемента поступает нулевой сигнал с нулевого выхода первого разряда. При этом сигналы установки в 1 поступает через соответствующие элементы ИЛИ 9 группы на 1, 2, 3 и 4-е разряды регистра 3. В пятом такте выбирается n-ый абонент на обслуживание, и все разряды регистра 3 устанавливаются в единичные состояния, что свидетельствует об окончании цикла обслуживания. В очередном 6-м такте при опросе схемы выбора канала обслуживания тактовый импульс с выхода элемента И 13 через элемент И 14, открытый с единичных выходов регистра 3,

устанавливает последний в нулевое состояние. По 7-му тактовому сигналу начнется

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

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

Проведем сопоставительный анализ прототипа и предложенного устройства по быстродействию. Выигрыш в быстродействии можно оценить по выражению

W

Тср.1 Тср.2

(5)

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

Тср.2 2 trn

(6)

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

W

п +к +2

(7)

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

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

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

Устройство циклического приоритета, содержащее дпп регистра, четыре группы

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

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

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

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

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

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

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

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

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

т