Устройство для обслуживания запросов в порядке поступления

 

УСТРОЙСТВО ДЛЯ ОБСЛУЖИВАНИЯ ЗАПРОСОВ В ПОРЯДКЕ ПОСТУПЛЕНИЯ, содержащее счетчик адресов на запис выход которого соединен с первым входом первого блока элементов И, отличающееся тем, что, с целью сокращения объема оборудования и расширения области применения а устройство введены три схемы сравнения , три блока элементов И, два блока элементов задержки, шесть элементов И, три элемента ИЛИ, элемент НЕ, блок элементов ИЛИ, триггер, регистры начального и конечного адреса, счетчик адресов на считывание, первый вход которого соединен с первым входом счетчика адресов на запись, с входами регистров начального и конечного адресов и с первым входом установочной шины устройства, второй вход счетчика адресов на считывание соединен с выходом второго блока элементов И, а выход счетчика адресов на считывание соединен с первыми входами первой и второй схем сравнения и с первым входом третьего блока элементов И, второй вход которого соединен с входом первого блока элементов задержки и с выходом первого элемента ИЛИ, первый вход которого соединен с выходом первого эле мента И, а второй вход соединен с выходом второго элемента И, первый вход которого соединен с первым щходом третьего элемента И и с выходом элемента НЕ, вход которого соединен .с первыми входами первого, четвертого , пятого и шестого элементов И и с выходом второй схемы сравнения, второй вход которой соединен с выходом счетчика адресов на запись и с первым входом третьей схемы срав- . нения, второй вход которойсоединен с выходом регистра конечного адреса § и с вторым входом первой схемы сравнения , выход которой соединен с первым входом второго б/юка Э1«ментов И, второй вход которого соединен с i выходом регистра начального адреса и с первым входом четвертого блока элементов И, второй вход которого соединен с выходом третьей схемы сравнения, а выход соединен с вторым входом счетчика адресов на . запись, третий вход которого соеди 00 | нен с первым выходом второго блока элементов задержки, второй выход которого соединен с третьим входом со четвертого блока элементов И, а третий выход второго блока элементов задержки соединен с вторым входом шестого элемента И, выход которого соединен с первым входом триггера, первый выход которого соедийен с вторым входом первого элемента И, а второй выход соединен с вторым входом пятого элементна И, третий вход которого соединен с вторым входом .третьего элемента И и с первым вхо

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

СВЗ

РЕСПУБЛИН

GllHGAHHE ИЗОБРЕТЕ

К ABTOPGHOMY СВИДЕТЕЛЬСТБУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTHA (21) 3341743/18-24 (22) 05.10.81 (46) 30.03.83 Бюл. М 12 (72) В.И. Семенова и С.А. Подопригора (53) 681. 325 (088. 8) (56) 1. Мультипроцессорные системы и параллельные вычисления. Под ред.

Ф.Г. Энслоу. И. "Мир", 1976, с. 215.

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

N 650078, кл."G 06 F 9/46, 1979 (прототип). (54) (57) УСТРОЙСТВО ДЛЯ ОБСЛУЖИВАНИЯ ЗАПРОСОВ В ПОРЯДКЕ ПОСТУПЛЕНИЯ, содержащее счетчик адресов на запись выход которого соединен с первым входом первого блока элементов И, о т л и ч а ю щ е е с я тем, что, с целью сокращения объема оборудования и расширения области применения в устройство введены три схемы сравне ния, три блока элементов И, два блока элементов задержки, шесть элементов

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

„Я0„„1 00874 элементов задержки и с выходом пер" вого элемента ИЛИ, первый вход которого соединен с выходом первого эле" мента И, а второй вход соединен с выходом второго элемента И, первый вход которого соединен с первым вхо" дом третьего элемента И и с выходом ,элемента НЕ, вход которого соединен .с первыми входами первого, четвертого, пятого и шестого элементов И и с выходом второй схемы сравнения, второй вход которой соединен с выходом. счетчика адресов на запись и с первым входом третьей схемы срав" . нения, второй вход которой соединен с выходом регистра конечного адреса и с вторым входом первой схемы срав- ® нения, выход которбй соединен с пер- вым входом второго блока элементов

И, второй вход которого соединен с выходом регистра начального адреса и с первым входом четвертого блока Я элементов И, второй вход которого соединен с .выходом третьей схемы ® сравнения, а выход соединен с вторым входом счетчика адресов на . запись, третий вход которого соеди-, нен с первым выходом второго блока © элементов задержки, второй выход « 4 которого соединен с третьим входом Фв четвертого блока элементов И, а тре. тий выход второго блока элементов задержки соединен с вторым входом шестого элемента И, выход которого соединен с первым входом триггера, -,фь первый выход которого соедийен с вторым входом первого элемента И, a второй выход соединен с вторым входом пятого элемента И, третий вход которого соединен с вторым входом ,третьего элемента И и с первым вхо1008743 дом шины обращения устройства, вто рой вход которой соединен с вторым входом второго и с третьим входом первого элементов И,. прй этом первый выход первого блока элементов. задержки соединен с первым входом счетчика адресов на считывание, второй выход соединен с третьим вхоI дом второго блока элементов И, а третий выход первого блока элементов задержки соединен с вторым входом четвертого элемента И, выход которого соединен с .первым входом второго элемента ИЛИ, второй вход которого соединен с вторым входом установоч-

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

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

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

И а выход соединен с входом второго блока элементов задержки и с вторым входом первого блока элементов И, при этом выходы первого и третьего блоков элементов И соединены с пер-. вым и вторым входами блока элементов

ИЛИ соответственно, выход которого соединен с адресной шиной устройства.

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

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

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

Все это ограничивает область использования устройства.

Цель изобретения - сокращение объемов оборудования и расширения области использования устройства.

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

ie

20

4О

3 . 10 блока элементов задержки, шесть эле- ментов И, три элемента ИЛИ, элемент

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

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

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

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

На чертеже изображено предлагае" мое устройство для обслуживания запросов в порядке поступления, Устройство содержит блок 1 адреса. ции записи, блок 2 адресации считывания, блок 3 граничных адресов, блок 4 управления адресацией, блок

5 элементов ИЛИ, адресную шину 6 на" копителя общего пользования, устано-. вочную шину 7, шину 8 обращения, причем блок 1 адресации записи состоит из счетчика 9 адресов на запись и блока 10 элементов И считывания показаний счетчиков блока, а блок 2 адресации считывания состоит из счет" чика 11 адресов на считывание и блока 12 элементов И считывания. Блок

3 граничных адресов содержит схемы

13 и 14 поразрядного сравнения, ре" гистры 15 и 16 конечного и начального адресов эоны накопителя, соответ" ственно, блоки 17 и 18 элементов И считывания начального и конечного адресов соответственно. Блок 4 управления адресацией содержит схему

19 поразрядного сравнения, триггер 20, блоки 21 и 22 элементов . задержки, элементы И 23 - 28, элементы ИЛИ 29 - 31, элемент НЕ 32.

5 1008

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

В исходном состоянии на счетчиках

9 и 11, также на регистре 16 записан начальный адрес назначенной к исполь. зованию зоны накопителя общего поль" зования, в регистр 15 - конечный адрес зоны накопителя, триггер 20 состояния зоны через элемент ИЛИ 31 установлен в нулевое состояние, озна- 1В чакщее, что в зоне нет невыполненных запросов. установка исходных состояний осуществляется по линиям устансвочной шины 7 в начале выполнения задачи. 15

При равенстве адресов считывания и записи, содержащихся в счетчиках

9 и И, запись возможна только при нулевом состоянии триггера 20, а считывание - при единичном. При неравен- 20 стве адресов разрешены как считывание, так и запись запросов в накопи" тель.

При появлении сигнала на линии ."Запись" шины 8(обращение на запись . запроса) с помощью элементов И 25 и

27 производится проверка состояния, триггера 20 и схемы 19 сравнения.

Если адрес записи запроса в зону накопителя, содержащийся в счетчике 9, совпадает с адресом-считывания запроса из очереди, содержащимся s счетчике 11, на выходе схемы 19 возникает

"1", а на выходе элемента HE 32"0". Если триггер 20 находится в

"нулевом" положении, то откроется эле. мент И 27, который через элемент.ИЛИ

29 запустит блок 21 элементов задержки и откроет блок 10 элементов И. В

40 результате код адреса записи, содержащийся в счетчике 9 поступит через блок 5 элементов ИЛИ на адресную шину 6 накопителя. При появлении сигнала на первом выходе блока 21 элемен4S тов задержки содержимое счетчика 9 увеличится на единицу. По истечении дополнительного времени задержки, достаточного для срабатывания счетчика 9, возникает сигнал на втором выходе блока 21 элементов задержки

50 и разрешит работу схемы 13 сравнения адреса записи с конечным адресом зоны, содержащимся в регистре 15.

Если вновь сформированный в счетчике

9 адрес записи равен конечному адресу зоны, откроется блок 17 элементов И и запишет в счетчик 9 начальный адрес зоны из регистра 16.

По истечении еще одной дополнительной задержки, достаточной для окончательного формирования адреса записи, с третьего выхода блока 21 элементов задержки на вход элемента И 23 поступит разрешающий сигнал. Если после окончания записи текущий адрес записи в счетчике,9 совпадет с адресом счи-тывания, содержащемся в счетчике 11, то это будет означать переполнение зоны. В этом случае элемент И 23 устанавливает триггер 20 в состояние

"1", в результате дальнейшая запись запрещается. Разрешение на запись появится теперь только после освобождения ячеек накопителя, т.е. пос" ле того, как будет произведено считывание. Если адреса записи и считывания не равны, то от элемента

НЕ 32 поступит "1" на вход элемента

И 25 и разрешит передачу очередного адреса в накопитель по шине 6. далее цикл повторяется.

При наличии. сигнала н4тение" по шине 8 схема работает аналогично.

C помощью элементов И 28 и 26 проверяется состояние триггера 20. Если адреса записи и считывания, содержащиеся в счетчиках 9 и 11, не совпада-ют, а триггер 20 находится в состоянии "1", -то сигнал с выхода элемента ИЛИ 30 разрешает вывод адреса считывания из счетчика 11 на шину 6.

Первый задержанный сигнал на выходе блока 22 элементов задержки увеличит содержимое счетчика 11 на единицу, после чего произойдет сравнение нового значения счетчика 11 с конечным адресом зоны, записанным в регистре 15 с помощью схемы 14 сравне.ния. В случае равенства в счетчик

11 через блок 18 элементов И будет записан начальный адрес зоны.

После дополнительной задержки на блоке 22 элементов задержки с помощью элемента И 24 проверяется сос-, тояние схемы 19 сравнения. В случае равенства адресов считывания и записи триггер 20 устанавливается в состояние "0", благодаря чему устройство приводится в состояние готовности к приему следующего сигнала "Запись" по шине 8.

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

ВНИИПИ Заказ 2340/60 Тираж 704 Подписное

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4