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

(19) 111 4 С 06 Р 12 00 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(54) УСТРОЙСТВО РАСПРЕДЕЛЕНИЯТИВНОЙ ПАМЯТИ ПЕРА(57) Иэобре тельной тех ройствам уп изобретения ение относится к вычислиике, в частности к уставления памятью, Цель тности- повьппени(21) 43954 (22) 21,03 (46) 23.09 (72) В.И,Б (53) 681.3 (56) Автор Кф 1213484,Авторск Р 1298754,записи в оперативную память эа счетвыделения оптимального по размерумассива оперативной памяти, а при отсутствии массива требуемого размера -эа счет выделения совокупности иэминимального числа массивов. Устройство содержит первую 1 и вторую 2группы регистров, блок 3 сортировки, третью группу регистров 4, первый 5, второй 6 и третий 7 регистры,генератор импульсов 8, первый 9 ивторой 10 счетчики, сумматор 11,первый 12 и второй 13 элементы сравнения, первый 14, .второй 15, третий 16и четвертый 17 триггеры, первый 18,второй 19, тртетий 20 и четвертый21 элементы.,1 з.п. ф-лы, 3 ил.3 150990Изобретение относится к вычислительной технике, в частности к устройствам управления памятью.Цель изобретения - повышение плот 5ности записи в оперативную память засчет выделения оптимального по размеру массива оперативной памяти, апри отсутствии массива требуемогоразмера за счет выделения совокупности из минимального числа массивов.На фиг. 1 представлена Функциональная схема устройства,на фиг, 2функциональная схема блока сортировки, на фиг, 3 - диаграмма, поясняющая 15работу устройства,Устройство содержит первую 1 ивторую 2 группы регистров, блок 3сортировки, третью группу регистров4, первый 5, второй 6 и третий 7 регистры, генератор 8 импульсов, первый9 и второй 10 счетчики, сумматор 11,первый 12 и второй 13 элементы сравнения, первый 14, второй 15, третий16 и четвертый 17 триггеры, первый18, второй 19, третий 20 и четвертый21 элементы И и имеют группу 22 вхо-дов размеров массивов памяти, группу 23 входов начальных адресов массивов памяти, вход 24 размера требуемого массива памяти, вход 25 запуска, группу адресных выходов 26,выход 27 числа выделенных массивовпамяти, выход 28 начального адресавыделенного массива памяти, первый29 и второй 30 сигнальные выходы ивыход 31 готовности.Блок сортировки содержит элементИ 32, триггер 33, ключ 34, группу 35ячеек коммутации, а в каждой ячейке 40первый 36 и второй 37 элементы И,триггер 38, ключ 39, элемент 40 сравнения, первый 41 и второй 42 коммутаторы. Блок сортировки имеет первую43 и вторую 44 группы входов, вход45 синхронизации, первый 46 и второй47 выходы,Элемент 12 сравнения, элементИ 20., регистр 6 и триггер 15 представ..ляют собой группу элементов для выделения оптимального по размеру массива памяти, т,е. массива, длина которого 1, 1 р и 1 - 1 = Ып,где Ь, - размер запрашиваемого мас-сива памяти, Сумматор 11, регистры4 и 7, элемент 13 сравнения, счетчик. 10, элементы И 19. 21 и триггер 17представляют собой группу элементовдля выделения минимального числа массивов памяти в соответствии с запросом. Обе группы элементов работают одновременно.Принцип выделения оптимального по размеру массива памяти заключается в следующем.С первого выхода блока сортировки на элемент 12 сравнения последовательно поступают коды размеров массивов памяти, начиная с наибольшего, а с второго выхода блока сортировки - соответствующие им начальные адреса. Если код размера поступившего массива больше либо равен требуемому, то соответствующий ему начальный адрес записывается в регистр 6, а триггер 15 устанавливается в единичное состояние, сигнализируя о выделении памяти одним массивом, По окончании работы устройства в регистре 6 находится начальный адрес оптимального по размеру массива памяти.Выделение совокупности, состоящей из минимального числа массивов, осуществляется следующим образом.На вход сумматора 11 последовательно поступают коды размеров массивов памяти, начиная с наибольшего, на вход первого регистра третьей группы регистров 4 - соответствующие им начальные адреса. Если суммарная длина поступивших массивов памяти меньше требуемой, то из -го регистра 4, ( = 1,п) информация переписывает- " ся в Я+1)-й регистр 4, а в первый регистр группы регистров 4 записыва- ется начальный адрес поступившего массива памяти. Одновременно в счетчике 10 подсчитывается число массивов. Как только суммарная длина массивов превысит размер требуемого массива, запись начальных адресов прекращается. По окончании работы устройства в счетчике 10 хранится, двоичный код числа выделенных массивов М, а в первых И регистрах 4 - начальные адреса выделенных массивов.,Устройство работает следующим образом. В исходном состоянии регистр 7, счетчики 9, 10, триггеры 14-17 и 33, 38 блока сортировки обнулены (цепи . обнуления не показаны). В регистры 1 по входам 22 записаны коды размеров свободных массивов памяти, в регистры 2 по входам 23 - начальные адреса массивов памяти, причем если некото 11 рый массив памяти занят, то в соответствующий регистр 1 записывается нулевой код, В регистр 5 по входу 24 записан код размера требуемого массива памяти. В исходном состоянии с первого выхода блока сортировки на вход сумматора 11 и элемента 12 сравнения поступает код размера максимального свободного массива памяти, а с второго выхода блока сортировки на вход первого регистра 4 третьей группы и на вход регистра 6 поступает соответствующий ему начальный ад" рес. Если код числа по первому входу элемента сравнения больше, либо равен, кода по второму входу, то на выходе элемента сравнения логическая единица, С приходом по входу 25 импульса запуска триггер 14 переходит в единичное состояние, элемент И 18 открывается и импульсы с генератора 8 импульсов поступают на вход счетчика 9, увеличивая его состояние на единицу. Если код размера поступившего массива памяти больше, либо равен, требуемого, то на выходе элемента 12 сравнения логическая "1", элемент И 20 открыт и импульс с генератора 8 импульсов переводит триггер 15 в единичное состояние, в регистр 6 записывается начальный адрес массива. В противном случае элемент И 20 закрыт; запись информации в регистр 6 не происходит. В исходном состоянии регистр 7 обнулен, на выходе элемента сравнения логический "0", элемент И 21 закрыт, элемент И 19 открыт.Первый импульс с генератора 8 импульсов через элемент И 1.9 записывает суммарную длину массива памяти в регистр 7, в регистр 4 записывается начальный адрес массива памяти, состоя 1 ние счетчика 10 увеличивается на единицу. Кроме того, импульс с генератора импульсов поступает на вход синхронизации блока сортировок и через время ь, , определяемое особенностью работы блока сортировки, на его первом и втором выходах появляется соответственно код размера и начальный адрес очередного массива памяти. В том случае, если к приходу очередного импульса с генератора импульсов суммарная длина массивов памяти, хранящаяся в регистре 7,больше, либо равна требуемой, на выходе элемента 13 сравнения логическая "1", элемент И 19 закрыт, запись информа 50 на входы коммутаторов 42 поступаютначальные адреса массивов памяти, Выделение максимального кода размера и соответствующего ему начального ад-реса памяти осуществляется следующим , образом.В каждой 8-й ячейке коммутации (8 = 1,п-Т) на элементе 40 сравнениясравнивается код размера (8+1)-го массива памяти с наибольшим из предыдущих 8 массивов, Если код по перво 1 Ч 909 6ции в ре ис тры 4, 7, счетчики 10 непрои зводится,С приходом (и+1)-го по счету импульса на выходе переполнения счетчика 9 появляется импульс, которыйустанавливает в нулевое состояниетриггер 14 и, тем самым, отключаетгенератор импульсов, Триггер 16 устанавливается в единицу, что сигнализирует о готовности устройства выдать информацию. Кроме того, если кмоменту окончания работы суммарнаядлина массива не меньше требуемой,то на выходе элемента 13 сравнения логическая "1", элемент И 21 открыти сигнал переполнения с выхода счетчика 9 устанавливает в единичноесостояние триггер 17, что сигнализи 20 рует о выделении совокупности массивов памяти. Устройство завершает работу,Таким образом, по окончании работына выходах 29(30) возможна следующая25 комбинация двоичных сигналов: 1(1)память выделена одним массивом, 0(1)выделена совокупность массивов,0(0) - память не выделена,В первом случае начальный адрес30 выделенного массива находится в ре-.гистре 6, который выдается по выходу28.Во втором случае по выходу 27 изсчетчика 10 выдается двоичный код Ичисла выделенных массивов, начальные35адреса которых из первых М регистров4 выделяются по выходам 26.Блок сортировки (фиг. 2) работает следующим образом.40 В исходном состоянии триггеры 33и 38 обнулены с их инверсных выходовснимается сигнал логической "1", который открывает ключи 34 и 39.По первой группе входов 43 коды45 размеров массивов памяти через открытые ключи 34 и 39 поступают на входыэлементов 40 сравнения и коммутаторов 41, по второй группе входов 44му входу элемента 40 сравнения больше, либо равен, кода по второму входу, то ца выходе элемента 40 сравне- ния логическая "1", коммутаторы 41 и 42 открыты по первому информационному входу, В противном случае коммутаторы открыты по второму информационному входу, Таким образом, на выходе первого коммутатора 41 Я-й ячейки 10 коммутации всегда присутствует код максимального из первых (Я+1) массивов памяти, на выходе второго коммутатора 42 - соответствующий ему начальный адрес. В результате последо вательного сравнения и коммутации на выходе первого коммутаторы 41 (и)й ячейки коммутации появляется кодразмера максимального массива памяти, на выходе второго коммутато ра 42 - соответствующий ему начальный адрес.Появление на выходе элемента сравнения Б-й ячейки коммутации логической "1". говорит о том, что, возможно 25 код на (Я+1)-м входе первой группы входов 43 является максимальным. Если на выходе элемента 40 сравнения Я-йячейки коммутации сигнал Х - = 1, асигнал=Х=О (иЬ 2. Я), 30 то на (Б+1)-м входе первой группы входов 43 присутствует максимальный код, который подлежит исключению из дальнейшего рассмотрения с приходом синхроимпульса по входу 45. Группа элементов И 32, 36, 37 обеспечивает определение и исключение максимального выделенного кода. Это осуществляется следующим образом.40С выхода элемента И 37 Б-й ячейки коммутации на второй вход элемента И 36 (Я)-й ячейки коммутации поступает сигнал, определяемый логической функцией г =. Х Х, Х. где 45 Х - инверсия сигнала на выходе элемента сравнения в Б-й ячейке коммутации. ЕслиХз =1 иГ =1, тос приходом синхроимпульса с входа 45 через элемент И 36 (Я)-й ячейки триггер 38 переходит в единичное состояние, потенциал логического "0" с его инверсного выхода закрывает ключ 39 и Б-й массив памяти из даль-. нейшего рассмотрения исключается. Через время= (и) (Т+ Тком ) .Т су ю Т,ощ - время переключения элемента сравнения.и коммутатора соответственно, на выходе последней ячейки коммутации появляется код размера и начальный адрес максимального из оставшихся массивов памяти. (Если Е = 1, то синхроимпульс через элемент И 32 устанавливает в единичное состояние триггер 33, ключ 34 закрывается).Эпюры на фиг. 3 поясняют работу блока сортировки и устройства в целом, где .1 - момент поступления (обновления) информации на входах блока сортировки, 11 - момент появленйя кода размера и начального адреса массива памяти, на выходах блока сортировки; 111 - момент прихода синхроимпульса на синхровход блока сортировки,Таким образом, предлагаемое устройство позволяет выделить оптимальный по размеру массив оперативной памяти, а при отсутствии такого - совокупность из максимального числа массивов памяти.Формула изобретения1, Устройство распределения оперативной памяти, содержащее первую и вторую группы из и регистров (и - число анализируемых массивов оперативной памяти), три регистра, генератор импульсов, первый и второй триггеры, первый, второй и третий элементы И, два счетчика, два элемента сравнения, сумматор, причем информационные входы К-х регистров первой и второй группы (К = 1,п) являются соответственно входом размера и входом начального адреса К-го массива оперативной памяти устройства, вход размера требуемого массива устройства соединен с информационным входом первого регистра, выход которого соединен с первым входом первого элемента сравнения, вход запуска устройства соединен с входом установки в единичное состояние первого триггера, выход которого соединен с первым входом первого элемента И, второй вход которого соединен с выходом генератора импульсов, выход первого элемента И соединен со счетным входом первого счетчика, счетный вход второго счетчика соединен с выходом второго элемента И, выход первого элемента сравнения соединен с первым входом третьего элемента И, первый вход второго элемента сравнения сое 1509909динен с первым входом сумматора, вход установки в единичное состояние второго триггера соединен с входом записи второго регистра, о т л и ч а ю - щ е е с я тем, что, с целью повышения плотности записи в оперативную память за счет выделения оптимального триггера является выходом готовностиустройства, выход начального .адресавыделенного массива памяти которогосоединен с выходом второго регистра,выход данных второго счетчика является выходом числа выделенных массивов устройства.1по размеру массива оперативной памяти, а при отсутствии массива требуемого размера - за счет выделения.совокупности из минимального числамассивов, в него введены блок сортировки, третья группа регистров, третий и четвертый триггеры, четвертыйэлемент И, причем выходы К-х регистров первой и второй групп соединенысоответственно с К-ми входами первойи второй групп входов блока сортировки, первый выход которого соединен с вторыми входами первого элемента сравнения и сумматора, выходкоторого соединен с информационным 10 15 20 входом третьего регистра, выход которого соединен с первым входом второго 25элемента сравнения, второй вход которого соединен с выходом первого регистра, выход второго элемента сравнения соединен с первым входом чет 1второго элемента И, выход которого соединен с входами записи третьего регистра и регистров третьей группы, выход М-го регистра третьей группы соединен с информационным входом (М+1)-го регистра третьей группы (Мпо1;п=1), выход К-го регистра третьей группы является К-м выходом группы адресных выходов устройства, прямой вход второго элемента И соединен с выходом первого элемента И, вторым входом третьего элемента И и входом синхронизации блока сортировки, второй выход которого соединен с информационным входом третьего регистра и с информационным входом первого регистра третьей группы, выход переполнения первого счетчика соединен с входом установки в нулевое состояние 35 40 первого триггера, с входом установки 50 в единичное состояние третьего триггера и вторым входом четвертого элемента И, выход которого соединен с входом установки в единичное состояние четвертого триггера, выход кото 55 рого является первым сигнальным выходом устройства, второй сигнальныйвыход которого соединен с выходомвторого триггера, выход третьего вертого элемента И и инверсным входом 30 2. Устройство по и. 1, о т л и ч а ю щ е е с я тем, что блок сортировки содержит элемент И, триггер, ключ и группу из пячеек коммутации, а в каждой ячейке коммутации - первый и второй элементы И, триггер ключ, элемент сравнения, первый и второй коммутаторы, причем в каждой ячейке коммутации выход ключа соединен с первым входом элемента сравнения и с первым информационным входом коммутатора, второй информационный вход которого соединен с вторым входом элемента сравнения, выход которого соединен с управляющими входами первого и второго коммутаторов, с первым входом первого элемента И и с инверсным входом второго элемента И, прямой вход которого соединен с вторым входом первого элемента И, выход которого соединен с входом установки в единичное состояние триггера, инверсный выход которого соединен с управляющим входом ключа, третьи входы первых элементов И всех ячеек коммутации соединены с входом синхронизации блока сортировки и с первым входом элемента И, выход которого соединен с входом установки в единичное состояние триггера, инверсный выход которого соединен.с управляющим входом ключа, выход которого соединен с вторым входом первого коммутатора первой ячейки коммутвпии, вьптод первого иоммутеторв К-й ячейки коммутации (К = 1,п) соединен с вторым входом первого коммутатора (К+1)-й ячейки коммутации, выходы первого и второго коммутаторов (п)-й ячейки коммутации являются соответственно первым и вторым выходами блока сортировки, прямой вход второго элемента И К-й ячейки соединен с выходом, второго элемента И (К+1)-й ячейки коммутации причем прямой вход второго элемента И (и)-й ячейки коммутации соединен с входом логической единицы, выход второго элемента И первой ячейки коммутации соединен с вторым входом12 1509909 элемента И, информационный вход ключа соединен с первым входом первойгруппы входов блока сортировки, информационный вход ключа 3-й ячейкикоммутации Ц = 1 рп) соединен сЯ+1)"м входом первой группы входовблока сортировки, первый информационный вход второго коммутатора 3-йячейки коммутации соединен с (3+1)-м входом второй группы входов блока сортировки, второй информационный вход второго коммутатора первой ячейки коммутации соединен с первым входом второй группы входов блока сортировки, выход второго коииутатора К-й ячейки коммутации (К = 1,п"2) соединен с вторым входом второго коммутатора (К+1)-й ячейки коммутации.орректор В. Каба Подпи 5814/47 Тираж 668 Государственного комитета по 13035, Москва, Ж-ЗЗака ВНИИП изобретениям и открытиям при ГКНТ СССР Рауюская наб., д. 4/5 оизводственпо-издательский комбинат "Патент", г.ужгород, ул. Гагарина,30