Устройство для динамического распределения памяти Советский патент 1986 года по МПК G11C8/16 

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

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

На фиг. 1 изображена структурная схема устройства для динa шчecкoгo распределения памяти; на фиг. 2 г древовидная структура памясти по методу взвешенных близнецов; на фиг. 3 - типовая ветвь дерева ; на фиг. 4 - структурная схема эле- мента памяти; на фиг, 5 - структурная схема ячейки памяти Нс1копйтеля.

Устройство содержит блок 1 управления, формирователь 2 упр)авляющих сигналов, накопитель 3, шифратор 4, формирователь 5 сигналов ошибки, пре образователь 6 кодов и дешифратор 7. Устройство имеет входы 8-11 с первого по третий и первьш 12 и второй 13

выходы ,

Накопитель 3 состоит (фиг. 4) из элементов памяти, каждый из которых содерлсит триггер 14, элементы И 15т2 элементы №1И 24-26 и имеет входы 27 42 и выходы 43-46. Пять элементов 47 51 памяти образуют ячейку памяти накопителя 3 (фиг. 5), входы которой подключены к шинам 52 и 53, а выходы - к шине 54. Элементы 47-49 находятся на уровнях h, h+1 и h+2, эле менты 50 и 51 - на уровне h+4. Величина h принимает значения О, 2, 4, 6, ..., п-4, где п - четное число.

Вся распределяемая память объема

Z слов представляется в виде древоридной структуры взвешенных близнецов. При этом память разделяется

.- Г т oM-i n

на блоки объема 2 , 3-2 , 2 , Зх

Jo -ioV -KTi

2 ,...,2 двоичньк слов. Все блоки памяти одного размера представ ляются статическим регистром (не показан) . Следовательно, регистров столько, сколько существует различны размеров (уровней) памяти. На каждом уровне h, ,n, начиная с верхнего нутгевого, количество триггеров К , в регистре определяется по рекуррентной (})ормуле

5

Q

5

5

1, если ,3;

Ку..( ,, если h - нечетное;

К| К( h четное; О, если KK-3+K t(i , если .

(Совокупность регистров составляет накопитель 3, который, таким образом, отображает структуру распределяемой в виде дерева. Единичное состояние некоторого триггера регистра з ровня означает, что соответствую- ЕЦ-ш блок памяти занят и не может быть распределен; нулевое состояние триггера с;видетельствует о незанятости блока памяти.

На фиг. 2 приведена древовидная структура памяти по методу взвеше;- - близнецов для 11 уровней (h-0,10). Нетрудно заметить, что двоичное дерево этого метода состоит только из типовых ветвей (фиг. 3), что позволяет гсостроить накопитель 3 из одинаковых ячеек памяти (фиг. 5).

Е ассмотрим работу устройства в двух режимах.

1. Выполнение команды Запрос (выдача адреса свободного блока памяти).

В этом на вход 8 устройства поступает команда Запрос, а на вход; 11 - сигнал Объем, представляю- щ1-1й двоичный код количества запрашиваемых слов памяти. По команде Запрос блок 1 вьщает на первый вход фop rиpoвaтeля 2 серию управляющих сигналов. На второй вход формирователя: 2 поступает сигнал с выхода преобразователя 6, который определяет номер уровня, а следовательно, я номер регистра накопителя 3, где долл;ен производиться поиск свободного блорса памяти. С выхода формирователя 2 на первый вход накопителя 3 поступают управляющие сигналы, которые обеспечивают выполнение следующих операций:

поиск первого свободного блока памяти, (а значит, первого триггера, находящегося в состоянии О) на запрашиваемом уровне;

отметка выбранного блока (установка триггера в 1);

отметка двоичного

ч 1 п

дерева , т.е. предков

установка в 1 всех предков и потомков выбранного блока (триггера).

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

хода 12 шифратора 4 снимается адрес свободного блока памяти.

Если на запрашиваемом уровне свободных блоков памяти нет, формирователь 5 вьфабатывает сигнал Ошибка, который снимается с выхода 13 устройства .

II. Выполнение команды Возврат (освобождение блока памяти).

В этом режиме на вход 9 устройства поступает команда Возврат, на вход 10 - начальный адрес бсвобождае- мой памяти, на вход 11 - двоичный код количества освобождаемых слов памяти.

Преобразователь 6, как и в первом режиме, вырабатывает сигнал, определяющий уровень, на котором происходит освобождение блока памяти. Дешифратор 7 выдает управляюш;ие сигналы на те триггеры накопителя 3, которые соответствуют блокам памяти, имеющим начальный адрес, равный адресу, поступившему на вход 10 устройства (блоки памяти различных уровней могут иметь одинаковые начальные адреса, но ни на одном уровне нет двух блоков с одинаковыми адресами). По сигналам с выхода формирователя 2 и дешифратора 7 определяется освобождаемый блок, памяти. Триггер, соответствующий этому блоку, устанавливается в состоя ние О. Затем производится отметка двоичного дерева в накопителе 3: обнуляются все триггеры - потомки и те триггеры - предки, у которых свободны и вторые потомки.

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

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

30314

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

5 управляющих сигналов и третьим входом формирователя сигналов ошибки.

2. Устройство по п. 1, о т л и- чающееся тем, что каждая

0 ячейка памяти накопител-я содержит элементы памяти с первого по пятьй, причем первые информационные входы второго и пятого элементов памяти подключены к первому информационному

5 выходу первого элемента памяти, второй информационный вход которого подключен к информационному выходу второго элемента памяти.и первым информационным входам третьего и четвертоQ го элементов памяти, третий информационный вход первого элемента памяти соединен с информационным выходом пятого элемента памяти, второй и третий информационные входы второго элемента памяти подключены соответственно к информационным выходам третьего и четвертого элементов памяти, вход приоритета пятого элемента памяти соединен с выходом приоритета четвертого элемента памяти, первый информационный вход первого элемента памяти, управляюи 1е входы элементов памяти, входы приоритета элементов памяти, кроме пятого, вторые и третьи информационные входы третьего, четвертого и пятого элементов памяти являются входами ячейки памяти, выходами которой являются информационные выходы элементов памяти, кроме второго, адресные выходы элементов памяти и выходы приоритета элементов памяти, кроме четвертого.

5

0

5

0

УроВем Размер в/юяа паия/пи Ог

J-f

/п-г

юг

Изобретение относится к вычислительной технике и может быть использовано в ЭВМ, интерпретирующих программу, записанную на языке высокого уровня, для организации нсстранично/7. адрес го обмена между оперативной и внешней памятью, а также для аппаратной реализации динамического распределения памяти в вычислительных системах. Цель изобретения - расширение области применения устройства Устройство содержит блок 1 управления, формирователи управляющих сигналов 2 и сигналов ошибки 5, накопитель 3, шифратор 4, преобразователь 6 кодовой де- шифтор 7. Устройство реализует метод взвешенных близнецов, при этом накопитель 3 отображает структуру распределяемой памяти в виде дерева. Устройство работает в двух режимах: режиме поиска свободного блока памяти и в режиме освобождения блока памяти. 1 з.п. ф-лы, 5 ил. с е tsd 4iaN о; фиг. /

fi-l(t}-3;h-) Уробемб

/7-8 /1-8 фиг.З

фиг. 5

Составитель В.Рудаков Редактор В.Петраш Техред М.Моргентал Корректор р.Синицкая

-- - -- - - ™.«„,,ц

Заказ 3711/52 Тираж 543 Подписное ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д.. 4/5

Производственно-полиграфическое предприятие, г.Ужгород, ул.Проектная, 4