Устройство для распределения памяти запоминающих устройств

 

О П И С А Н И Е 3IS 948

ИЗОБРЕТЕНИЯ

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

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

Республик

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

Зависимое от авт. свидетельства №

Заявлено 04.VIII.1969 (№ 1353427/18-24) с присоединением заявки №

Приоритет

Опублнковапо 28.Х.1971. Бюллетень ¹ 32

Дата опубликования описания 17.XII.1971

МПК G 06113/06

Комитет по делам изобретений и открытий при Совете Министров

СССР

УДК 681.327(088.8) Авторы изобретения

Э. И. Борисевич, Л. Ф. Симоненко и Ю. С. Смир С. Д1 ..

"-,,"" . " "«e er;

Г)у j )/

Заявитель

УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ПАМЯТИ

ЗАПОМИНАЮЩИХ УСТРОЙСТВ

Изобретение относится к. области вычислительной техники.

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

Недостатками известных устройств являются, во-первых, слишком большой объем памяти, требуемый для хранения списка, C =R 1ода/т, где Я вЂ” количество зон в ЗУ центра; во-вторых, невысокая надежность. Действительно, достаточно одного сбоя в любом из адресов связи, и список целиком или частично разрушается, а это означает потерю всех зон или части их для центра. Поскольку в центрах коммутации сообщений, как и в любых системах, работающих в реальном масштабе времени, особенно высоки требования к надежности, этот недостаток спискового устройства распределения становится весьма существенным, а возможность накапливания ошибок в таком устройстве при непрерывной работе центра практически исключает целесообразность его применения без многократного резервирования.

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

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

С = Я.

Разрядность ячейки ЗУ 1=2". Каждый элемент имеет свой кодовый адрес, определяе20 мый как код адреса ячейки и код порядкового номера элемента в ячейке. Кодовый адрес элемента, полученный таким образом, равен кодовому номеру зоны памяти центра.

Поиск свободной зоны осуществляют путем

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

30 свободных зон заносятся в один из двух ре318948 гистров, предназначенных для хранения кодов свободных зон, т. е. создается некоторый запас свободных зон. Для обеспечения возможности поиска и коррекции таблицы в автономном режиме таблица хранится в отдельном запоминающем устройстве из N ячеек, N = —.

Такое размещение таблицы позволяет выбрать ЗУ с достаточно высоким быстродействием и высокой надежностью, так как практически R (<1024, 1 = 8 — 16, N 128 †. В случае меньших R таблица может быть реализована на триггерных элементах.

На чертеже приведена структурная схема предлагаемого устройства распределения памяти. Перед началом работы все элементы запоминающего устройства 1 устанавливают в состояние «1», что соответствует незанятости всех зон памяти; счетчик зон 2, регистр обмена 8, регистры свободных зон 4, 5, регистр освободившихся зон б устанавливают в исходное состояние, соответствующее хр анению пустого слова.

Счетчик зон 2 предназначен для формирования адреса ячейки в ЗУ и номера разряда в ячейке и представляет собой обычный триггерный счетчик, состоящий из двух частей: счетчика младших разрядов емкостью 1 и счетчика старших разрядов емкостью N.

Счетчики младших и старших разрядов имеют разделньые счетные входы 7 и 8. Содержимое младших разрядов может быть передано на дешифратор 9, а содержимое старших разрядов — на регистр 10 адреса ЗУ.

В качестве запоминающего устройства может быть применено любое ЗУ (2D, 3D, 1

2 — D на различных элементах), обеспечиваг ющее требуемые технические параметры.

Содержимое ячеек ЗУ 1:переписывается через регистр 11 числа в регистр 8 обмена, который предназначен для приема слова, хранения на время анализа его изменений и последующей передачи в регистр числа.

Регистр обмена содержит 1 триггеров, регистр освободившихся зон б — Р триггеров (P = 1одф) и разбит на две части: младшие разряды на К триггерах (К = 1ор1) и старшие разряды на М триггерах (М = 1о@У).

Содержимое старших разрядов может быть передано на регистр 10 адреса ЗУ, содержимое младших разрядов — на дешифратор 9.

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

Регистры 4, 5 свободных зон предназначены для приема из счетчика зон кодовых номеров найденных свободных зон, хранения их

4 до востребования процессором и выдачу. Количество регистров свободных зон выбирают исходя из соотношения частоты запросов зон процессором и быстродействия устройства распределения таким образом, чтобы снизить время ожидания до заданного, Регистры свободных зон представляют собой обычные регистры на P триггерах каждый; параллельной работой этих регистров управляет распределитель 12, который обеспечивает занесение кода свободной зоны из счетчика свободных зон только в один свободный регистр, если регистры свободны, и выдачу кода в процессор только из одного занятого регистра, если регистры заполнены. Узел управления 18 представляет собой группу триггеров и логических схем и предназначен для формирования управляющих сигналов для работы устройства в режиме поиска свободной зоны и в режиме приема освободившейся зоны. Схема совпадения 14 предназначена для анализа отдельных разрядов регистраа обмена.

В режиме поиска устройство работает следующим обр азом.

В группу старших разрядов счетчика 2 зон добавляется «+ 1», и их содержимое записывается в регистр 10 адреса ЗУ. По этому адресу в ЗУ 1 считывается слово, а слово из регистра ll числа ЗУ 1 передается в регистр

8 обмена. Обратный код слова с триггерного регистра 8 обмена засылается на схему совпадения 15, и если прочитанное слово было пустым (т. е. во всех 1 разрядах слова был записан «О», что соответствует занятости соответствующих зон), то в группу старших разрядов счетчика 2 зон добавляется «+ 1» и осуществляется чтение слова из ЗУ 1 по вновь сформированному адресу. Если прочитанное слово не было пустым, то добавляется «+ 1» в группу младших разрядов счетчика зон. Полученный код поступает на дешифратор 9, и схема совпадения 14 анализирует содержимое 1-го разряда слова. Если в

1-м разряде записан «О» (что соответствует занятости зоны), то в группу младших разрядов добавляется «+ 1», и анализируется следующий разряд.

Если в анализируемом разряде содержится «1» (что соответствует незанятости зоны), то в этом разряде триггер перебрасывается в состояние «0», содержимое счетчика 2 зон засылается в регистр 4 или 5, добавляется

«+ 1» в группу младших разрядов счетчика

2 зон, и аналогичным образом осуществляется ан ал из следующего р азр яда.

По окончании анализа всех l разрядов или по заполнении регистров 4 и 5 кодами свободных зон измененное слово засылается из регистра 8 обмена в регистр 11 числа ЗУ 1 по адресу в старших разрядах счетчика 2 зон, добавляется «+1» в группу старших разрядов счетчика зон, считывается слово по этому адресу, и весь процесс повторяется. Поиск свободной зоны осуществляется в автоном318948 ном режиме до тех пор, пока регистры 4, 5 свободных зон не будут заполнены, после чего измененное слово отсылается в регистр

11 числа ЗУ 1, и при обращении к последующей ячейке ЗУ 1 анализируется ее содержимое. Найденная свободная зона не фиксируется, а слово не изменяется и засылается обратно в ЗУ 1.

Если из процессора поступает сигнал «Выдать», то в случае наличия кода в регистрах

4, 5 свободных зон осуществляется выдача кода в процессор из одного регистра, этот регистр устанавливается в исходное состояние, и код найденной затем свободной зоны записывается в этот регистр. Если к моменту поступления сигнала «Выдать» ни в одном из регистров 4, 5 свободных зон нет кода, то осуществляется поиск свободной зоны, как указывалось выше.

Если в процессе поиска свободной зоны из процессора поступает сигнал «Принять», то заканчивается анализ очередного разряда, производятся операции по изменению слова (в случае необходимости) и его засылке в

ЗУ 1, как описано выше, после чего устройство распределения переходит в режим приема освободившейся зоны.

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

По сигналу процессора «Принять» в регистр б освободившихся зон заносится из процессора код освободившейся зоны. Содержимое старших разрядов регистра б освободившихся зон засылается в регистр 10 адреса

ЗУ 1, считывается соответствующая ячейка, и содержимое ее передается в регистр 8 обмена. Содержимое младших разрядов регистра б освободившихся зон передается на дешифратор 9, возбуждается соответствующий выход дешифратора и в соответствующем разряде слова, размещенного в регистре 8 обмена, вместо «О» записывается «1». Измененное слово засылается обратно в ЗУ 1 по адресу старших разрядов регистра 6 освободившихся зон, затем регистр 6 устанавливается в исходное состояние, в группу старших разрядов счетчика добавляется «+ 1», и устройство переходит в режим поиска свободной зоны.

Как следует из описания, предлагаемое усгройство распределения памяти требует для своей реализации минимального объема памяти, поскольку каждой зоне ставится в соответствие только один запоминающий элемент. Это позволяет использовать в памяти элементы повышенной надежности. Кроме того, принцип построения устройства обеспечивает высокую надежность распределения па10 мяти центра: сбой в одном разряде влечет за собой потерю только одной зоны, а не целой группы зон.

Требуемое быстродействие обеспечивается как за счет структуры устройства (увеличение

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

Предмет изобретения

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

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

30 зон и счетчика зон через первучо схему

«ИЛИ» подключены ко входам регистра адреса запоминающего устройства, выходы младших разрядов регистра освободившихся зон и счетчика зон через вторую схему «ИЛИ»

35 подсоединены ко входам дешифратора, выходы которого через вентили подключены к управляющим входам регистра обмена, информационные входы и выходы регистра обмена соединены соответственно с выходами и вхо40 дами регистра числа запоминающего устройства и со входами первой и второй схем совпадения, выход первой схемы совпадения подключен к счетному входу старших разрядов счетчика зон, а выход второй схемы сов45 падения — к счетному входу младших разрядов счетчика зон, выходы счетчика зон через вентили подсоединены ко входам регистров свободных зон.

318948 онято

Составитель А. А. Плащнн

Редактор И. А. Орлова Техред 3. Н. Тараненкб Корректор В. И. Жолудева

Заказ 3542/17 Изд. № 1497 Тираж 473 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

Москва, 7К-35, Раушская нзб., д. 4/5

Типография, пр, Сапунова, 2