Устройство для динамического распределения памяти

 

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

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

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

„„SU„„1243Î31 (51) 4 С 11 С 8/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н A BTOPCHOMY СВИДЕТЕЛЬСТВУ

err

diaz

0d

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3726574/24-24 (22) 18.04.84 (46) 07.07.86. Бюл. 1Ф 25 (72) Л.Б.Авгуль, Н.Н.Буйнов и А.Б.Непомнящий (53) 681.327(088.8) (56) Авторское свидетельство СССР

И 696544, кл. С 11 С 21/00, 1979.

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

Ф 809361 кл. С 11 С 11/00, 1981. (54) УСТРОЙСТВО ДЛЯ ДИНАМИЧЕСКОГО

РАСПРЕДЕЛЕНИЯ ПАМЯТИ (57) Изобретение относится к вычислительной технике и может быть исполь— зовано в ЗВМ, йнтерпретирующих программу, записанную на языке высокого уровня, для организации нестраничного обмена между оперативной и внешней памятью, .а также для аппаратной реализации динамического распределения памяти в вычислительных системах.

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

"взвешенных близнецов", при этом накопитель 3 отображает структуру рас11 t! пределяемой памяти в виде дерева .

Устройство работает в двух режимах: реллме поиска свободного блока памяти и в режиме освобождения блока памяти. 1 з.п. ф-лы, 5 ил.

1243031

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

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

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

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

Устройство имеет входы 8-11 с первого по третий и первый 12 и второй 13 выходы. .30

Накопитель 3 состоит (фиг. 4) из элементов памяти, каждый из которых содержит триггер 14, элементы И 15-723., элементы ИЛИ 24-26 и имеет вхоцы 2742 и выходы 43-46. Пять элементов 47- ..

51 памяти обра зуют ячейку памяти накопителя 3 (фиг. 5), входы которой подключены к шинам 52 и 53, а выходы — к шине 54. Элементы 47-49 находятся на уровнях h, h+1 и h+2, эле— менты 50 и 51 — на уровне h+4. Величина h принимает значения О, 2, 4, 6, ..., n-4, где n — четное число.

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

О\ 4ь

2 слов представляется в виде древовидной структуры "взвешенных близне— цов . При этом память разделяется на блоки объема 2, 3 ° 2, 2, Зх 1 -5 VN-Н

12,... 2 двоичньг слов. Все О блоки памяти одного размера представляются с" àòè÷åñêèì регистром (не показан). Следовательно, регистров столько, сколько существует различных размеров (уров.teA) памяти. На каждом 5 уровне h, Ь=О,п, начиная с верхнего нулевого, количество триггеров К g в регистре определяется по рекуррентной формуле

1, если h=0,3;

К1г i „если h — нечетное;

К = К +К1,ь +К, если h четное;

О, если h=n-1;

К1 +К, если й=п.

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

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

Нетрудно заметить, что двоичное дерево этого метода состоит только из типовых ветвей (фиг. 3), что позволяет построить накопитель 3 из одинаковых ячеек памяти (фиг. 5).

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

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

В этом режиме на вход 8 устройства поступает команда Запрос", а на вход 11 — сигнал "Объем", представляющий двоичный код количества запрашиваемых слов г.амяти. По команде Зап— рос" блок 1 выдает на первый вход формирователя 2 серию управляющих сигналов. На второй вход формирователя 2 посту;ает сигнал с выхода пре— образователя 6, который определяет номер уровня, а следовательно, и нсмер регистра накопителя 3, где должен производиться поиск свободного блока памяти. С выхода формирователя 2 на первый вход накопителя 3 поступают управляющие сигналы, которые обеспечиваюг выполнение следующих операций: поиск первого свободного блока памяти, (а значит, первого триггера, находящегося в состоянии О ) на запрашиваемом уровне; отметка выбранного блока (установ«а триггера в "1"); отметка двоичного "дерева", т.е. установка в "1" всех "предков" и "по— томков" выбранного блока (триггера).

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

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

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

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

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

35 и те триггеры — предки, у которых свободны и вторые "потомки".

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

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

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

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

1243031

Уорен

h- 1Ь 3, Л-4J Зробенв

4 1

1243031 ,Б з

Л

27 .У

29 у

39 гв ф)

Ф/

Z2

Л

42

Составитель В.Рудаков

Редактор В.Петраш Техред М.Моргентал Корректор В ° Синицка"

Заказ 3711/52 Тираж 543 Подпис ное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

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