УСТРОЙСТВО для РАСПРЕДЕЛЕНИЯ ПАМЯТИ ЗАПОМИНАЮЩИХ УСТРОЙСТВ Советский патент 1971 года по МПК G06F12/00 

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

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

Недостатками известных устройств являются, во-первых, слишком большой объем памяти, требуемый для хранения списка,

C ..log2,

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

ошибок в таком устройстве при непрерывной работе центра практически исключает целесообразность его применения без многократного резервирования.

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

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

С У.

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

последовательного перебора ячеек и разрядов в ячейке. Кодовый адрес элемента незанятой зоны заносится в регистр, причем в целях повышения быстродействия поиск происходит непрерывно, а найденные кодовые адреса гистров, предназначенных для хранения кодов свободных зон, т. е. создается некоторый запас свободных зон. Для обеспечения возможности поиска и коррекции таблицы в автономном режиме таблица хранится в отдель- 5 ном запоминающем устройстве из Л ячеек, Такое размещение таблицы позволяет вы- 10 брать ЗУ с достаточно высоким быстродействием и высокой надежностью, так как практически 1024, / 8-16, Л 128-64. В случае меньших R таблица может быть реализована на триггерных элементах. На чертеже приведена структурная схема предлагаемого устройства распределения памяти. Перед началом работы все элементы запоминающего устройства 1 устанавливают в состояние «1, что соответствует незанято- 20 сти всех зон памяти; счетчик зон 2, регистр обмена 3, регистры свободных зон 4, 5, регистр освободившихся зон 6 устанавливают в исходное состояние, соответствующее хранению пустого слова. Счетчик зон 2 предназначен для формирования адреса ячейки в ЗУ и номера разряда в ячейке и представляет собой обычный триггерный счетчик, состоящий из двух частей: .счетчика младших разрядов емкостью i 30 и счетчика старших разрядов емкостью N. Счетчики младших и старших разрядов имеют разделньые счетные входы 7 и 5. Содержимое младщих разрядов может быть передано на дешифратор 9, а содержимое стар- 35 ших разрядов - на регистр 10 адреса ЗУ. В качестве запоминающего устройства может быть применено любое ЗУ (2Д 3, 2- D на различных элементах), обеспечивающее требуемые технические параметры. Содержимое ячеек ЗУ 1 переписывается через регистр // числа в регистр 3 обмена, который предназначен для приема слова, хранения на время анализа его изменений и45 последующей передачи в регистр числа. Регистр обмена содержит / триггеров, регистр освободившихся зон 6 - Р триггеров (Р - QgzR И разбит на две части: младшие разряды на К триггерах (Д logs/) и стар-50 шие разряды на М триггерах (М logsA). Содержимое старших разрядов может быть передано на регистр 10 адреса ЗУ, содержимое младщих разрядов - на дешифратор 9. Дешифратор 9 представляет собой группу55 схем совпадения с К. входами, имеет 1 выходов и предназначен для преобразования кода, поступающего из счетчика 2 зон или регистра 6 освободивщихся зон, в позиционный сигнал на одной из / шин, чем осущест-60 вляет селектирование одного из / разрядов регистра 2 обмена, его анализ и коррекцию. 15 25 40 до востребования процессором и выдачу. Количество регистров свободных зон выбирают исходя из соотношения частоты запросов зон процессором и быстродействия устройства распределения таким образом, чтобы снизить время ожидания до заданного. Регистры свободных зон представляют собой обычные регистры на Р триггерах каждый; параллельной работой этих регистров управляет распределитель 12, который обеспечивает занесение кода свободной зоны из счетчика свободных зон только в один свободный регистр, если регистры свободны, и выдачу кода в процессор только из одного занятого регистра, если регистры заполнены. Узел управления 13 представляет собой группу триггеров и логических схем и предназначен для формирования управляющих сигналов для работы устройства в режиме поиска свободной зоны и в режиме приема освободившейся зоны. Схема совпадения 14 предназначена для анализа отдельных разрядов регистра обмена. В режиме поиска устройство работает следующим образом. В группу старших разрядов счетчика 2 зон добавляется «+ 1, и их содержимое записывается в регистр 10 адреса ЗУ. По этому адресу в ЗУ 1 считывается слово, а слово из регистра 11 числа ЗУ / передается в регистр 3 обмена. Обратный код слова с триггерного регистра 3 обмена засылается на схемусонпадения 15, и если прочитанное слово было пустым (т. е. во всех / разрядах слова был записан «О, что соответствует занятости соответствующих зон), то в группу старших разрядов счетчика 2 зон добавляется «+ 1 и осуществляется чтение слова из ЗУ 1 по вновь сформированному адресу. Если прочитанное слово не было пустым, то добавляется «+ Ь в группу младших разрядов счетчика зон. Полученный код поступает на дешифратор 9, и схема совпадения 14 анализирует содержимое 1-го разряда слова. Если в 1-м разряде записан «О (что соответствует занятости зоны), то в группу младщих разрядов добавляется «+ 1, и анализируется следующий разряд. Если в анализируемом разряде содержится «1 (что соответствует незанятости зоны), то в этом разряде триггер перебрасывается в состояние «О, содержимое счетчика 2 зон засылается в регистр 4 или 5, добавляется «-|- 1 в группу младших разрядов счетчика 2 зон, и аналогичным образом осуществляется анализ следующего разряда. По окончании анализа всех / разрядов или по заполнении регистров 4 и 5 кодами свободных зон измененное слово засылается из регистра 3 обмена в регистр 11 числа ЗУ / по адресу в старших разрядах счетчика 2 зон, добавляется «-f- 1 в группу старших разряном режиме до тех пор, пока регистры 4, 5 свободных зон не будут заполнены, после чего измененное слово отсылается в регистр 11 числа ЗУ 1, и при обращении к последующей ячейке ЗУ 1 анализируется ее содержимое. Найденная свободная зона не фиксируется, а слово не изменяется и засылается обратно в ЗУ 1.

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

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

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

По сигналу процессора «Принять в регистр 6 освободивщихся зон заносится из процессора код освободившейся зоны. Содержимое старших разрядов регистра 6 освободившихся зон засылается в регистр 10 адреса ЗУ 1, считывается соответствующая ячейка, и содержимое ее передается в регистр 3 обмена. Содержимое младших разрядов регистра 6 освободивщихся зон передается на дешифратор 9, возбуждается соответствующий выход дещифратора и в соответствующем разряде слова, размещенного в регистре 3 обмена, вместо «О записывается «1. Измененное слово засылается обратно в ЗУ / по адресу старщих разрядов регистра 6 освободившихся зон, затем регистр 6 устанавливается в исходное состояние, в группу старщих разрядов счетчика добавляется «-|-1, и устройство переходит в режим поиска свободной зоны.

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

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

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

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

20

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

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

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

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

Hod cdoSoi/wiJ зона/

i.

Tw разр. Mfipozp.

(/МП ijrlpa8лeнuя

I III

I I I

. Принять

.Мать