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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК ЯО 1243 О(51) 4 С 11 С 8/00 ИСАНИЕ ИЗОБРЕТЕНИЯ ВТОРСНОМУ СВИДЕТЕЛЬСТВУ ТВО ДЛЯ ДИНАМИЧЕСКОГОПАМЯТИение относится к ике и может бытьйнтерпретирующих про санную на языке высоко организации нестра(54) УСТРОЙС РАСПРЕДЕЛЕНИЯ (57) Изобрет тельной техн зовано в ЗВМ грамму, запи уровня, лля вычисли исполь -ничн Зал УГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТ(56) Авторское свидетельство СССРИ 696544 ь кл. С 11 С 21/00 1979.Авторское свидетельство СССРВ 809361, кл. С 11 С 11/00, 1981. го обмена между оперативной и внешней памятью, .а также для аппаратной реализации динамического распределения памяти в вычислительных системах, Цель изобретения - расширение области применения устройства. Устройство содержит блок 1 управления, формирователи управляющих сигналов 2 и сиг-налов ошибки 5, накопитель 3, шифратор 4, преобразователь 6 кодови дешифтор 7. Устройство реализует метод "взвешенных близнецов", при этом накопитель 3 отображает структуру рас 1 пределяемой памяти в виде дерева .Устройство работает в двух режимах: режиме поиска свободного блока памяС ти и в режиме освобождения блока памяти, 1 з.п. ф-лы, 5 ил.1243031 Изобретение относится к Вычислительной технике и может быть исполь - зовано в ЭВМ, интерпретирующих программу, записанную на языке высокого уровня, для организации нестраничного обмена между оперативной и внешней памятью, а также для аппаратной реализации динамического распределения памяти в вычислительных системах.Цель изобретения - расширение области применения устройства за счет уменьшения потерь распределяемой памяти.На фиг. 1 изображена структурная схема устройства для динамического распределения памяти; на фиг, 2 древовидная структура памяти по методу "взвешенных близнецов; на фиг. 3 - типовая ветвь "дерева"; на фиг. 4 - структурная схема элемента памяти; на фиг. 5 - структурная схема ячейки памяти накопителя,Устройство содержит блок 1 управления, формирователь 2 управляющих сигналов, накопитель 3, шифратор 4, 25 формирователь 5 сигналов ошибки, преобразователь 6 кодов и дешифратор 7. Устройство имеет входы 8-11 с первого по третий и первый 12 и второй 13 выходы. 30Накопитель 3 состоит (Фиг, 4) из элементов памяти, каждый из которых содержит триггер 14, элементы И 15-,23., элементы ИЛИ 24-26 и имеет вхоцы 27- 42 и выходы 43-46, Пять элементов 47-35 51 памяти образуют ячейку памяти накопителя 3 (Фиг, 5), входы которой подключены к шинам 52 и 53, а выходы - к шине 54, Элементы 47-49 находятся на уровнях Ь, 1 т+1 и Ь+2, эле - менты 50 и 51 - на уровне Ь+4, Величина й принимает значения О, 2, 4, 6, , п, где и - четное число. Вся распределяемая память объема 1 фО2 слов представляется в виде древовидной структуры "взвешенных близне - цов . При этом память разделяется нд блоки объема 2 , Зф 2 , 2 , Зк1 5 и-к,ф 2 , ,2 двоичньг слов, ВсеО блоки памяти одного размера представляются статическим регистром (не показан). Следовательно, регистров столько, сколько существует различных размеров (уровней) памяти. На кдждом уровне Ь, В=О,п, начиная с верхнего нулевого, количество триггеров К 11 в регистре определяется по рекуррентной Формуле 21, если Ь=0,3;Кьесли Ь - нечетное;К = К 1, +К 1,. +К, если Ь четное;О, если Ь=п;К 1. +К ц, если Ь=п.Совокупность регистров составляет накопитель 3, который, таким образом, отображает структуру распределяемой памяти в виде "дерева", Единичное состояние некоторого триггера регистра уровня означает, что соответствующий блок памяти занят и не может быть распределен; нулевое состояние триггера свидетельствует о незанятости блока памяти,Н фиг. 2 приведена древовиднаяструктура памяти по методу взвешенных близнецов" для 11 уровней (1 т=-0,10).Нетрудно заметить, что двоичное ндерево этого метода состоит только изтиповых ветвей (фиг, 3), что позволяет построить накопитель 3 из одинаковых ячеек памяти (фиг, 5),Рассмотрим работу устройствав двух режимах.1, Выполнение команды "Запрос" (вы,цача адреса свободного блока памяти).В этом режиме на вход 8 устройствапоступает командаЗапрос", а навход 11 - сигнал "Объем", представляюцдй двоичный код количества запрашиваемых слов гамяти, По команде 13 ап -рос" блок 1 выдает на первый входФормирователя 2 серию управляющихсигналов. На второй вход формирователя 2 поступает сигнал с выхода пре -образователя 6, который определяет номер уровня, а следовательно,и нсмер регистра накопителя 3, гдедолжен производиться поиск свободного блока памяти. С выхода формирователя 2 на первый вход накопителя 3поступают управляющие сигналы, которые обеспечиваюг выполнение следующих операций:поиск первого свободного блокапамяти, (а значит, первого триггера,находящегося в состоянии О ) на запрашиваемом уровне;отметка выбранного блока (установка триггера в "1");отметка двоичного "дерева", т,е. установка в "1" всех "предков" и "потомков" вццбрднного блока (триггера).На вход цгифратора 4 постУпает сигнал возбуждения с выхода накопителя 3, по которому шифратор формирует цвончный адрес блока памяти, соответ твуюшего выбранному триггеру. С вы з 12430хода 12 шифратора 4 снимается адрессвободного блока памяти.Если на запрашиваемом уровне сво -бодных блоков памяти нет, формирователь 5 вырабатывает сигнал "Ошибка",который снимается с выхода 13 устройРства,11, Выполнение команды "Возврат"(освобождение блока памяти).В этом режиме на вход 9 устройства 0поступает команда "Возврат", навход 10 - начальный адрес освобождаемой памяти, на вход 11 - двоичныйкод количества освобождаемых словпамяти, 15Преобразователь б, как и в первомрежиме, вырабатывает сигнал, определяющий уровень, на котором происходит освобождение блока памяти. Дешифратор 7 выдает управляющие сигналы 20на те триггеры накопителя 3, которыесоответствуют блокам памяти, имеющимначальный адрес, равный адресу, поступившему на вход 10 устройства(блоки памяти различных уровней могут 25иметь одинаковые начальные адреса, нони на одном уровне нет двух блоковс одинаковыми адресами), По сигналамс выхода формирователя 2 и дешифратора 7 определяется освобождаемыйблок памяти, Триггер, соответствующийэтому блоку, устанавливается в состояние "О". Затем производится отметкадвоичного "дерева" в накопителе 3:обнуляются все триггеры - "потомки"35и те триггеры - предки, у которыхсвободны и вторые "потомки",Формула изобретения 1. Устройство для динамического распределения памяти, содержащее шифратор, выход которого является первым выходом устройства, и блок управления, входы которого являются первым и вторым входами устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения устройства за счет уменьшения потерь распределяемой памяти, в него введены преобразователь кодов, формирователь управляющих сигналов, дешифратор, накопитель и формирователь 31сигналов ошибки выход которого является вторым выходом устройства, первый вход соединен с первым выходом накопителя, второй вход соединен с первым входом устройства, выход блока управления соединен с первым входом накопителя, второй выход которого подключен к входу шифратора, второй вход соединен с выходом дешифратора, вход которого является третьим входом устройства, четверты входом которого является вход преобразователя кодов, выход которого соединен с вторым входом формирователя управляющих сигналов и третьим входом формирователя сигналов ошибки. 2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что каждая ячейка памяти накопителя содержит элементы памяти с первого по пятый, причем первые информационные входы второго и пятого элементов памяти подключены к первому информационному выходу первого элемента памяти, второй информационный вход которого подключен к информационному выходу второго элемента памятия и первым инфор - мационным входам третьего и четвертого элементов памяти, третий информационный вход первого элемента памяти соединен с информационным выходом пятого элемента памяти, второй и третий информационные входы второго элемента памяти подключены соответственно к информационным выходам третьего и четвертого элементов памяти, вход приоритета пятого элемента памяти соединен с выходом приоритета четвертого элемента памяти, первый информационный вход первого элементапамяти, управляющие входы элементов памяти, входы приоритета элементов памяти, кроме пятого, вторые и третьи информационные входы третьего, четвертого и пятого элементов памяти являются входами ячейки памяти, выходами которой являются информационные выходы элементов памяти, кроме второго, адресные выходы элементов памяти и выходы приоритета элементов памяти, кроме четвертого.Тираж 543 Подп сударственного комитета С ам изобретений и открытий ва, Ж, Раушская наб.,ноеР 45 Производственно-полиграфическое предприятие, г,ужгород, ул