Устройство распределения оперативной памяти Советский патент 1989 года по МПК G06F12/00 

:л

со СО

QD

Фие.1

434}

1- 2 1509909

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

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

На фиг. 1 представлена функциональная схема устройства,на фиг. 2 - функциональная схема блока сортировки, на фиг. 3 - диаграмма, поясняющая 15 работу устройства.

Устройство содержит первую 1 и BTOpjTo 2 группы регистров, блок 3 сортировки, третью группу регистров 4, первый 5, второй 6 и третий 7 ре- 20 гистры, генератор 8 импульсов, первый 9 и второй 10 счетчики, сумматор 11, первый 12 и второй 13 элементы сравнения, первый 14, второй 15, третий

30

35

16 и четвертый 17 триггеры, первый 25 18, второй 19, третий 20 и четвертый 21 элементы И и имеют группу 22 вхо- дов размеров массивов памяти, группу 23 входов начальных адресов массивов памяти, вход 24 размера тре- буемого массива памяти, вход 25 запуска, группу адресных выходов 26, выход 27 числа выделенных массивов памяти, выход 28- начального адреса вьщеленного массива памяти, первый 29 и второй 30 сигнальные выходы и выход 31 готовности.

Блок сортировки содержит элемент И 32, триггер 33, ключ 34, группу 35 ячеек коммутации, а в каждой ячейке первый 36 и второй 37 элементы И, триггер 38, ключ 39, элемент 40 сравнения, первый 41 и второй 42 коммутаторы. Блок сортировки имеет первую 43 и вторую 44 группы входов, вход .г 45 синхронизации, первый 46 и второй , 47 выходы. Элемент 12

40

сравнения, элемент

представИ 20, регистр 6 и триггер 15 ляют собой группу элементов для выделения оптимального по размеру ма.с- сива памяти, т.е. массива, длина которого L J 5: L

ТР,

и L J - L,

- mm,

где - размер запрашиваемого Mac сива памяти. Сумматор 11, регистры 4 и 7, элемент 13 сравнения, счетчик 10, элементы И 19, 21 и триггер 17 представляют собой группу элементов Для выделения минимального числа

г 0

5

0

0

5

5

г

0

0

с

массивов памяти в соответствии с запросом. Обе группы элементов работают одновременно.

Принцип выделения оптимального по размеру массива памяти заключается в следующем.

С первого выхода блока сортировки на элемент 12 сравнения последовательно поступают коды размеров массивов памяти, начиная с наибольшего, а с второго выхода блока сортировки - соответствующие им начальные адреса. Если код размера поступившего массива больше либо равен требуемому, то соответствующий ему начальный адрес записывается в регистр 6, а триггер 15 устанавливается в единичное состояние, сигнализируя о вьщелении памяти одним массивом. По окончании работы устройства в регистре 6 находится начальный адрес оптимального по размеру массива памяти.

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

На вход сумматора 11 последовательно поступают коды размеров массивов памяти,начиная с наибольшего, на вход первого регистра третьей группы регистров 4 - соответствующие им начальные адреса. Если суммарная длина поступивших массивов памяти.мень- ше требуемой, то из j-ro регистра 4 , (J 1,п-1) информация переписывает- ся в (+1)-й регистр 4, а в первый регистр группы регистров 4 записывается начальный адрес поступившего массива памяти. Одновременно в счетчике 10 подсчитывается число массивов. Как только суммарная длина массивов превысит размер требуемого массива, запись начальных адресов прекращается. По окончании работы устройства в счетчике 10 хранится . двоичный код числа выделенных массивов N, а в первых N регистрах 4 - начальные адреса выделенных массивов..

Устройство работает следзтащим образом.

В исходном состоянии регистр 7, счетчики 9, 10, триггеры 14-17 и 33, 38 блока сортировки обнулены (цепи :. обнуления не показаны). В регистры 1 по входам 22 записаны коды размеров свободных массивов памяти, в регистры 2 по входам 23 - начальные адреса массивов памяти, причем если некото is

|)Ъ1й массив памяти занят , то в сеют- ветствующий регистр 1 записывае тся нулевой код, В регистр 5 по входу 24 записан код размера требуемого массива памяти. В исходном состоянии с первого выхода блока сортировки на вход сумматора 11 и элемента 12 сравнения поступает код размера максимального свободного массива памяти, а с второго выхода блока сортировки на вход первого регистра 4 третьей группы и на вход регистра 6 поступает соответствующий ему начальный адрес. Если код числа по первому входу элемента сравнения больше, либо равен, кода по второму входу, то на выходе элемента сравнения логическая единица. С приходом по входу 25 импульса запуска триггер 14 переходит в единичное состояние, элемент И 18 открывается и импульсы с генератора 8 импульсов поступают на вход счетчика 9, увеличивая его состояние на единиду. Если код размера поступившего массива-памяти больше, либо равен, требуемого, то на выходе элемента 12 сравнения логическая 1, элемент И 20 открыт и импульс с генератора 8 импульсов переводит триггер 15 в единичное состояние, в регистр 6 записывается начальный адрес массива.. В противном случае элемент И 20 закрыт-, запись информации в регистр 6 не происходит. В исходном состоянии регистр 7 обнулен, на выходе элемента сравнения логический О, элемент И 21 закрыт, элемент И 19 открыт. Первый импульс с генератора 8 импульсов через элемент И 19 записывает суммарную длину массива памяти в регистр 7, в регистр 4 записывается на- |Чальньй адрес массива памяти, состоя- 1ние счетчика 10 увеличивается на единицу. Кроме того, импульс с генератора импульсов поступает на вход синхронизации блока сортировок и через время , определяемое особенностью работы блока сортировки, на его первом и втором выходах появляется соответственно код размера и начальный адрес очередного массива паг мяти. В том случае, если к приходу очередного импульса с генератора импульсов суммарная длина массивов памяти, хранящаяся в регистре 7,больше, либо равна требуемой, на выходе элемента 13 сравнения логическая 1, элемент И 19 закрыт, запись информаQl) - )

Ш1И в регистрг, 4, 7, счетчики 10 не прои Г1 водите я .

С приходом (n-bl)-ro по счету им- пульса на тзыходе переполнения счетчика 9 появляется импульс, который устанавливает в нулевое состояние триггер 14 и, тем самым, отключает генератор импульсов. Триггер 16 ус0 танавливается в единицу, что сигнализирует о готовности устройства выдать информацию. Кроме того, если к моменту окончания работы суммарная длина массива не меньше требуемой,

5 то на выходе элемента 13 сравнения логическая 1, элемент И 21 открыт и сигнал переполнения с выхода счетчика 9 устанавливает в единичное состояние триггер 17, что сигнализи0 рует о выделении совокупности массивов памяти. Устройство завершает работу.

Таким образом, по окончании работы на выходах 29(30) возможна следующая

5 комбинация двоичных сигналов: 1(1) - память вьщелена одним массивом, 0(1) выделена совокупность массивов, 0(0) - память не вьщелена.

В первом случае начальный адрес вьщеленного массива находится в- регистре 6, который выдается по выходу 28.

Во втором случае по выходу 27 из счетчика 10 выдается двоичный код N чис ла выделенных массивов, начальные адреса которых из первых N регистров 4 выделяются по выходам 26.

Блок сортировки (фиг. 2) работает следующим образом.

В исходном состоянии триггеры 33 и 38 обнулены с их инверсных выходов снимается сигнал логической 1, который открывает ключи 34 и 39.

По первой группе входов 43 коды размеров массивов памяти через отк15ы- тые ключи 34 и 39 поступают на входы элементов 40 сравнения и коммутаторов 41, по второй группе входов 44 на входы коммутаторов 42 поступают начальные адреса массивов памяти. Выделение максимального кода размера и соответствующего ему начального адреса памяти осуществляется следующим образом.

В каждой S-й ячейке коммутации (S 1 ,п-Т) на элементе 40 сравнения сравнивается код размера (S+1)-ro массива памяти с наибольшим из предыдущих S массивов. Если код по перво0

5

0

5

0

5

му входу элемента 40 сравнения боль- , ше, либо равен, кода по второму входу, то ча выходе элемента 40 сравнения логическая 1, коммутаторы 41 и 42 открыты по первому информационному входу. В противном случае коммутаторы открыты по второму информационому входу. Таким образом, на выходе первого коммутатора 41 S-й ячейки коммутации всегда присутствует код максимального из первых (S+1) массивов памяти, на выходе второго коммутатора 42 - соответствующий ему начальный адрес. В результате последовательного сравнения и коммутации на выходе первого коммутаторы 41 (п-1)й ячейки коммутации появляется код размера максимального массива памяти, на выходе второго коммутатора 42 - соответствующий ему начальный адрес.

Появление на выходе элемента сравнения S-й ячейки коммутации логической 1 говорит о том, что, возможно код на (S+1)-M входе первой группы входов 43 является максимальным. Если на выходе элемента 40 сравнения S-й ячейки коммутации сигнал Х 1, а сигнал Х 0(п-1 ), то на (S+1)-M входе первой группы входов 43 присутствует максимальный код, который подлежит исключению из дальнейшего рассмотрения с приходом синхроимпульса по входу 45. Группа элементов И 32, 36, 37 обеспечивает определение и исключение максимального вьщеленного кода. Это осуществляется следующим образом.

С вьгхода элемента И 37 S-й ячейки коммутации на второй вход элемента И 36 CS-1)-й ячейки коммутации поступает сигнал, определяемы -1 логической функцией fg - Хд- KS, ... X ,,, где Хз - инверсия сигнала на выходе элемента сравнения в S-й ячейке коммутации. Если Хд-ч 1 и fg 1, то с приходом синхроимпульса с входа 45 через элемент И 36 (S-1)-й ячейки триггер 38 переходит в единичное состояние, потенциал логического О с его инверсного выхода закрывает ключ 39 и S-й массив памяти из дальнейшего рассмотрения исключается. Через время о (п-1)( + )

ер коМ

ком время переключения сравнения и коммутатора соответственно, на выходе последней

где Т,р, элемента

ячейки коммутации появляется код размера и начальный адрес максимального из оставшихся массивов памяти. (Если f; 1, то синхроимпульс через элемент И 32 устанавливает в единичное состояние триггер 33, ключ 34 закрывается).

Эпюры на фиг. 3 поясняют работу

блока сортировки и устройства в целом, где I - момент поступления (обновления) информации на входах блока сортировки, II - момент появления кода размера и начального адреса

массива памяти, на выходах блока сортировки; III - момент прихода синхроимпульса на синхровход блока сортировки. I

Таким образом, предлагаемое устройство позволяет выделить оптимальный по размеру массив оперативной памяти, а при отсутствии такого - совокупность из максимального числа массивов памяти.

0

5 0 5

0

5

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

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

10

15

20

91509909

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

память за счет выделения оптимального I V

по размеру массива оперативной памяти, а при отсутствии массива требуемого размера - за счет выделения, совокупности из минимального числа массивов, в него введены блок сортировки, третья группа регистров, третий и четвертый триггеры, четвертый элемент И, причем выходы К-х регистров первой и :второй групп соединены соответственно с К-ми входами первой и второй групп входов блока сортировки, первый выход которого соединен с вторыми входами первого элемента сравнения и сумматора, выход которого соединен с информадионным входом третьего регистра, выход которого соединен с первым входом второго 25 элемента сравнения, второй вход которого соединен с выходом перв.ого регистра, выход второго элемента сравнения соединен С первым входом четвертого элемента И и инверсным входом 30 второго элемента И, выход которого соединен с входами записи третьего регистра и регистров третьей группы, выход М-го регистра третьей группы соединен с информационным входом i (М+1)-го регистра третьей группы (М 1,11-1), выход К-го регистра третьей группы является К-м выходом группы адресных выходов устройства, прямой вход второго элемента И соединен с выходом первого элемента И, вторым входом третьего элемента И и входом синхронизации блока сортировки, второй выход которого соединен с информационным входом третьего регистра и с информационным входом первого регистра третьей группы, выход переполнения первого счетчика соединен с входом установки в нулевое состояние первого триггера, с входом установки в единичное состояние третьего триггера и вторым входом четвертого элемента Н, выход которого соединен с входом установки в единичное состояние четвертого триггера, выход которого является первым сигнальным выходом устройства, второй сигнальный выход которого соединен с выходом второго триггера, выход третьего

35

40

45

50

55

10

триггера является выходом roTOBHocfit устройства, выход начального .адреса выделенного массива памяти которого соединен с выходом второго регистра,, выход данных второго счетчика является выходом числа выделенных массивов устройства.

0

5

0

5 0

5

0

5

0

5

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

. n1509

элемента И, информационный вход ключа соединен с первым входом первой группы входов блока сортировки, информационный вход ключа j-й ячейки коммутации (j Т7п-Т) соединен с (j+1)-M входом первой группы входов блока сортировки, первый информационный вход второго коммутатора j-й ячейки коммутации соединен с (j+1)-M

12

входом второй группы входов блока сортировки, второй информационный вход второго коммутатора первой ячейки коммутации соединен с первым входом второй группы входов блока сортировки, выход второго коммутатора К-й ячейки коммутации (К 1,п-2) соединен с вторым входом второго коммутатора (К+1)-й ячейки коммутации.

Изобретение относится к вычислительной технике , в частности, к устройствам управления памятью. Цель изобретения - повышение плотности записи в оперативную память за счет выделения оптимального по размеру массива оперативной памяти, а при отсутствии массива требуемого размера - за счет выделения совокупности из минимального числа массивов. Устройство содержит первую 1 и вторую 2 группы регистров, блок 3 сортировки, третью группу регистров 4, первый 5, второй 6 и третий 7 регистры, генератор импульсов 8, первый 9 и второй 10 счетчики, сумматор 11, первый 12 и второй 13 элементы сравнения, первый 14, второй 15, третий 16 и четвертый 17 триггеры, первый 18, второй 19, третий 20 и четвертый 21 элементы И. 1 з.п. ф-лы, 3 ил.

Редактор О.Головач

Составитель А.Иванов Техред М.Дидык

Ж

Ж

Фие.З

Корректор В. Кабаций