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

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

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

На фиг, 1 и 2 представлена структурная схема устройства; на фиг, 3 - схема блока дешифрации кодов (БДК); на фиг, 4 - схема блока-шифратора кодов (БШК); на фиг, 5 - схема коммутатора-.

Устройство содержит группу элементов 1 сравнения, матрицу элементов 2 сравнения, БДК 3, регистр 4, БШК 5, второй элемент И 6, элемент задержки, элемент ИЛИ 8, матрицу групп элементов И 9, первый элемент И 10, группу элементов И 11, группу блоков элементов И 12, групггу элементов ИЛИ 13, вход 14 запроса, вход 15 требуемого размера массива памяти, вход 16 отказа, вход 17 размера освобождаемого массива памяти, вход 18 адреса освобождаемого массива памяти, выход 19 признака очистки, выходы 20 признака наличия и 21 признака отсутствия требуемого массива памяти, выход 22 начального адреса выделяемого массива памяти,

БДК 3 содержит первый 23 и второй 24 элементы И-ИЛИ, первый 25 и второй 26 дешифраторы, первый 27 и

второй 28 элементы задержки, группу элементов ИЛИ 29, группу элементов И-ИЛИ 30, блок групп элементов И 31 входы 32 признака выделения и 37 признака освобождения массива памяти, входы 33 адреса выделяемого и 34 освобождаемого массива памяти, входы 35 объема выделяемого и 36 объема освобождаемого массива па:мяти, первую 38 и вторую 39 группы выходов,

Б11К 5 содержит матрицу групп элементов И 40, группу элементов И 41, вторую группу шифраторов 42, первзпо группу шифраторов 43, группу коммутаторов 44, элемент ИЛИ 45, группу ВХОДОВ 46, первую 47 и вторую 48

группы выходов, выход 49 признака очистки памяти.

Коммутатор 44 содержит группу элементов ИЛИ 50, первую 5 и вторую

52 группы элементов И, первый 53 и второй 54 элементы И-ИЛИ, блок групп информационных входов 55, группу управляющих входов 36, выход 57 коммутатора 44, первую 58 и вторую 59

группы информационных входов, выходы 60 объема и 61 адреса свободного массива памяти,

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

в регистре 4 хранятся признаки незанятости распределяемых наименьших объемов памяти под ранее обслуженные запросы. Единичный сигнал на i-M выходе регистра (,Р) означает, что i-й объем памяти в данное время не выделен обслуженным запросом. Выходы регистра 4 анализируются в блоке 5, где вырабатываются коды 48 начальных адресов и 47 размеров свободных областей памяти, а

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

перераспределение памяти между задачами дпя объединения небольших свободных массивов в один массив суммарного объема. Код требуемого объема памяти поступает на вход 15, а

сопровождающий этот код сигнал запроса - на вход 14, Группа элементов 1 сравнения вырабатывает сигналы ai, означакяцие, что размер i-ro свободного массива не меньше размера тр€;буемого и i-й массив можно выделить под запрос (), Матрица элементов 2 сравнения вырабаты- вает сигналы bij(,М-1; ,M-l), означакж(ие, что размер (j + l)-ro

массива не меньше размера 1-го массива. Сигналы а , a(j+l), bij поступают на ij-ю группу элементов И 9 матрицы, на вькоде второго элемента И 9 которой вырабатывается сигнал

dij (равный единице, если из 1-го и (J + |)TO массивов под запрос выделяется i-й массив), а на выходе третьего элемента И 9 - сигнал Pij (равный единице, если из этих же

двух массивов под запрос выделяется (3+1)-й массив). Если эти массивы меньше требуемого, то , На вход i-ro элемента И 11 группы поступают сигналы dij (, М-1) и

IK, i-1 (, 1-1) означающие при значении 1 выбор i-го массива среди массивов с i-го до М-го (dij) и среди массивов с 1-го до i-ro (К, 1-1), Эти сигналы принимают единич- нов значение на входах только одного из М элементов И 11, поэтому среди выходов группы элементов И 11 только один сигнал принимает единичное значение, причем номер этого . 10 сигнала в группе соответствует номеру того свободного массива памяти, который является оптимальным для данного запроса по критерию V. -V min /0 (V. и V - размеры i-ro15

и требуемого массивов). Единичный сигнал на выходе i-ro элемента И 11 группы открывает i-ю группу элементов И 12 блока, через кот.орую и далее через, группу элементов ИЛИ 13 20 на выход 22 выдается код начального адреса i-ro массива с i-ro выхода 48 группы выходов БШК. Одновременно с выдачей кода адреса выдается признак 20 наличия требуемого массива, 25 сформулированный из задержанного на элементе 7 задержки и прошедшего через элемент И 6 сигнала запроса. Формирование признака 20 происходит- на элементе И 10 в случае превьш1е- 30 ния (равенства) размера хотя бы одного из свободных массивов над размерами требуемого массива, что опредеяется появлением на прямом выходе элемента ИЛИ 8 единичного сигнала j ак результата логического сложения сигналов с выходов группы элементов 1 сравнения. В противном случае с нверсного выхода элемента ИЛИ 8 выается на выход 21 признак отсут- 40 ствия требуемого массива,. Единичный сигнал 20, вырабатываемый при удовлетворении запроса, через ин- версный вход элемента И 6 гасит сигнал на входе элемента 7 задержга, 45 что обеспечивает гашение сигнала 20 через время, примерно равное времени задержки на элементе 7, Сигнал 20 импульсной формы используется в БДК 3, где он открывает выход БДК, 50 переключаюпщй состояние разрядов егистра 4, В БДК происходит выбор азрядов регистра 4, которые надо переключать в нулевое состояние, так как соответствующие им распре- 55 деляемые объемы памяти выделены под данный запрос. Выбираются выходы 38 БДК с номерами отА -1 , код начального адреса вьоделяемого массива, которые переключают соответствующие разряды регистра 4, После этого переключения БШК 5 формирует новые коды адресов и объемов свободных массивов, поскольку объем V был выделен под запрос, К моменту формирования кодов сигнал 20 погашается, что свидетельствует 9 том, что код на выходе 22 не соответствует адресу выделенного массива, поскольку состояние регистра 4 изменилось ,

В случае освобождения какой-либо задачей ресурса памяти на устройство поступают коды ащреса 18 и размера 17 освобождаемого массива, признак отказа 16, В блоке 3 выбираются выходы 39 с номерами от А до А + +V -1 (А и VP - начальный адрес и размер освобождаемого массива), которые переключают в единичное состояние . соответствующие разряды регистра 4, что свидетельствует о возмож- ности вьоделения освободившейся памяти под новые запросы. Перед началом работы устройства подаются признак 16, адрес 18 начала и размер 17 всего распределяемого массива памяти , что означает незанятость всей памяти и обеспечивает установку всех разрядов регистра 4 в единичное состояние,

ч

БДК 3 работает следуюшрм образом. По сигналу 32 выделения (37 освобождения) массива через элементы И-ИЛИ 23 и 24 на дешифраторы 25 и 26 проходят коды 33 адреса и 35 размера выделяемого (34 адреса и 36 размера освобождаемого) массива , На i-M выходе дешифратора 25, соответствующем адресу, сигнал принимает единичное значение и поступает на i-e элементы И j-x элементов И-ИЛИ 30 (liiiP, ). На выходе группы элементов ИЛИ 29 - код, в котором 1-й сигнал равен единице (,V, где V - размер массива), t-й сигнал поступает на (m-1+l)-й элемент И т-х элементов И-ИЛИ 30 (,Р), На выходах группы элементов И-ШШ 30 единичное значение принимают сигналы с А-го по (А+У-1)-й (А и V - адрес и размер массива), которые через первые (вторые) элементы И 31 групп блока при наличии задержанного на элементе 27 (28) задержки сигнала 32 (37) вьщаются на выходы 38 Г39) БДК.

БШК 5 работает следующим образом. i-я строка матрицы групп элементов И 40 вырабатывает распределенный код числа единичных сигналов, следующих в группе входов 46 подряд, начи- 5 ная с i-ro входа, т,.е. числа незанятых объемов памяти. На шифраторах 43 группы распределенный код преобразуется в двоичный, i-й элемент И 41 группы вырабатывает признак Ю чала нового свободного массива в случае единичного значения (i+l)-ro и нулевого значения i-ro входов 46, По признаку на (L+)-M шифраторе 42 группы вырабатывается двоич- 5 ный код адреса, равного адресу (1+1)-го распределяемого объема в памяти (в простейшем случае этот адрес равен i+1). Признаки начала свободных массивов, их размеры и адреса с выходов элементов И 41, шифраторов 43 и 42 поступают на коммутаторы 44, которые выдают коды 47 объема и 48 адреса первых М свободных массивов памяти. Если число свободных массивов больше М, то элемент ИЛИ 45 вырабатывает сигнал 49 очистки памяти,

К-й коммутатор 44 работает следу- образом. На i-й вход j-ro эле- 30 мента ИЛИ 50 поступает признак того, что иачинаюшяйся с адреса 2K+J-2 свободный массив уже выдан через i-й коммутатор 44 (,К-1; ,К-2

20

25

группы входов 58. Признак выдачи кодов объема и адреса через данный коммутатор выдается с выхода одного из элементов И 52 группы на выход 57 для использования в последующих коммутаторах,

Таким образом, устройство позволяет сохранить информацию о занятых массивах памяти, выделять под запрос требуемый объем памяти и учитывать освобождение памяти при отказе от ресурсов,

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

1, Устройство для распределения ресурсов оперативной памяти, содержащее группу элементов сравнения, матрицу элементов сравнения, элемент задержки, элемент ИЛИ, первый элемент И, группу элементов И, группу блоков элементов И, группу элементов ИЛИ, причем вход объема требуемого массива памяти устройства подключен к первым входам элементов сравнения группы, выходы которых подключены к входам элемента ИЛИ, прямой выход которого подключен к первому входу первого элемента И, второй вход которого подключен к выходу элемента задержки, выход первого элемента И подключен к выходу признака наличия требуемого массива памяти устройства, выходы

i+2). На выходе j-ro элемента ИЛИ 50 35 элементов И группы подключены к управляю1дим входам блоков элементов И группы, выходы которых подключены к входам элементов ИЛИ группы, выходы которых подключены к выходу

группы - единичный сигнал, если указанный массив выдан через один из предыдуш х коммутаторов 44, и поэтому этот массив не выдается через данный коммутатор: единичный выход j-ro элемента ИЛИ 50 не пропускает через j-й элемент И группы 51 признак начала нового свободного массива, начинающегося с адреса 2Ktj-2, поступающий с j-ro входа группы входов 56, Единичные выходы группы 51 элементов И соответствуют свободным массивам, не выданным через предыдущие коммутаторы; на выходах группы 52 элементов И и выходах первого и второго элементов И- группы 51 единичное значение принимает только сигнал, соответствующий массиву из указанных, имеющему меньший адрес, Единичное значение этого сигнала пропускает на выходы 60 и 61 через элементы И-ИЛИ 53 и 54 коды объема, поступающего с группы входов 59, и адреса, поступающего с

5

0

0

5

группы входов 58. Признак выдачи кодов объема и адреса через данный коммутатор выдается с выхода одного из элементов И 52 группы на выход 57 для использования в последующих коммутаторах,

Таким образом, устройство позволяет сохранить информацию о занятых массивах памяти, выделять под запрос требуемый объем памяти и учитывать освобождение памяти при отказе от ресурсов,

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

1, Устройство для распределения ресурсов оперативной памяти, содержащее группу элементов сравнения, матрицу элементов сравнения, элемент задержки, элемент ИЛИ, первый элемент И, группу элементов И, группу блоков элементов И, группу элементов ИЛИ, причем вход объема требуемого массива памяти устройства подключен к первым входам элементов сравнения группы, выходы которых подключены к входам элемента ИЛИ, прямой выход которого подключен к первому входу первого элемента И, второй вход которого подключен к выходу элемента задержки, выход первого элемента И подключен к выходу признака наличия требуемого массива памяти устройства, выходы

5 элементов И группы подключены к управляю1дим входам блоков элементов И группы, выходы которых подключены к входам элементов ИЛИ группы, выходы которых подключены к выходу

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

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

55 к выходу первого элемента И и входу элемента задержки, входы признака и щеления массива памяти, адреса выделяегмого массива памяти, адреса освоболсдаемого массива памятк--, объема выделяемого массива памяти, объема освобождаемого массива памяти,, признака освобождения массива памяти блока дешифрации кодов подключены соответственно к выходу первого элемента И, выходам элементов ИЛИ группы, входам адреса освобождаемого, массива памяти, требуемого размера массива памяти, размера освобождаемого массива памяти и отказа устройства, первая и вторая группы выходов блока дешифрации кодов подключены соответственно к сбросовому и установочному входам регистра, выходы которого подключены к группе входов блока шифрации кодов, выход очистки которого подключен к выходу признака очистки устройства, первая группа выходов блока шифрации кодов подключена к вторым входам элементов сравнения группы, первым входам ij-x (,М-1, ,M-l, где М - число анализируемых свободных массивов памяти) и вторым входам (К, ) (, М-1 , , i-l) элемен- тов сравнения матрицы, выход ij-ro (,M-l; ,M-l) элемента сравнения матрицы подключен к инверсному входу первого элемента И ij-й группы матрицы, выход которого подключен к инверсному второго элемента И той же группы матрицы, прямой вход которого подключен к выходу j-ro элемента сравнения группы, прямые входы первого и третьего элементов И ij-й группы матрицы элементов И подключены к выходу (j+l)-ro элемента сравнения группы, выход второго элемента И ij-й группы матрицы подключен к инверсному входу третьего элемента И той же группы матрицы и входу i-ro элемента И группы, выход третьего элемента И ij-й группы матрицы подключен к вхо- ДУ (j + O-ro элемента И группы, инверсный выход элемента ИЛИ подключен к выходу признака отсутствия требуемого массива устройства, вторая группа выходов блока-шифратора кодов подключена к информационным входам блоков элементов И группы,

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

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

массива памяти, объема выделяемого массива памяти и объема освобождаемого массива памяти подключены соответственно к вторым входам первого и второго элементов И, первого и

второго элементов И-ИЛИ, выходы первого и второго элементов И-ИЛИ подключены соответственно к входам первого и второго дешифраторов, i-й (,Р, где Р - минимальное число

распределяемых массивов памяти) выход первого дешифратора подключен к первому входу i-ro элемента И j-ro (,P) элемента И-ИЛИ группы, выход которого подключен к вторым входам

J-X элементов И первой и второй . групп блока, i-й ( , Р-1) выход второго дешифратора подключен к первому входу i-ro элемента ИЛИ группы, второй вход которого подключен к выходу (i+l)-ro ( , Р-2) элемента ИЛИ группы, второй вход (Р-1)-го элемента ИЛИ группы подключен к Р-му вы- ходу второго дешифратора, выход i-ro ( Р-1) элемента ИЛИ группы под-

ключей к второму входу i-ro (, Р-1) элемента И j-ro (,.P-l) элемента И-ИЛИ группы, Р-й выход второго дешифратора подключен к второму входу первого элемента И Р-го

элемента И-ИЛИ группы, выходы элементов И первой и второй групп блока, подключены соответственно к первой и второй группам выходов блока дешифрации кодов,

3, Устройство по п, 1, о т л и - чающееся тем, что блок шифрации кодов содержит матрицу групп элементов И, группу элементов И, группы коммутаторов, первую и вторую группы шифраторов и элемент ИЛИ, причем i-й вход группы блока-шифратора кодов подключен к первому входу первого и прямому входу второго элементов И ii-й (, Р-1) группы матрицы, к вторым входам первых элементов И (J, i-l)-x ( J I, i-O групп матрицы, к прямому входу ., (i-l)-го элемента И группы и к инверсному входу 1-го (, Р-1) элемента И группы, выход первого элемента И ij-й (, Р-1) группы матрицы подключен к инверсному входу второго элемента И той же группы матрицы, к первому входу первого и прямому входу второго элемента И (i j+l)ft (, Р-2) группы матрицы, выход второго элемента И ij-й группы (, ) матрицы и выход первого элемента И (i, Р-1)-й группы матрицы подключены к входу i-ro шифратора первой группы, первый вход группы блока-шифратора кодов подключен к входу первого шифратора второй группы и к первому управляющему входу группы первого коммутато

5

0

5

pa группы, выход i-ro (, Р) шифратора первой группы подключен к (i-2K+2)-My информационному входу (, М+1) первой группы К-го коммутатора группы, к (i-2K+2)-My информационному входу второй группы которого подключен выход i-ro шифратора второй группыJ вход которого и (i-2K+2)-й управляющий вход группы К-го коммутатора группы подключены к выходу (i-1)-го (, Р) элемента И групгй, группа выходов i-ro (i 1, М) коммутатора группы подключена к i-й группе информационных входов блока j-ro (, М+1) коммутатора группы, первый выход i-ro коммутатора группы подключен к i-му выходу первой группы блока-шифратора кодов, второй выход i-ro коммута- тота группы подключен к i-му выходу второй группы блока-шифратора .коДов, первый выход (М+Г)-го коммутатора группы подключен к входам элемента ИЛИ, выход которого подключен к выходу признака очистки блока-шифратора кодов.

Изобретение относится к области цифровой вычислительной техники, в частности к устройствам для распределения ресурсов в вычислительных комплексах, и может быть использовано для распределения оперативной памяти в вычислительных комплексах. Целью изобретения является расширение функциональных возможностей устройства за счет учета занятости оперативной памяти на основании информации запросов ресурсов и отказов от ресурсов оперативной памяти. Устройство содержит группу элементов сравнения, матрицу зле- ментов сравнения, блок дешифрации кодов, блок-шифратор кодов, регистр, первый, второй злементы И, элемент задержки, элемент ИЛИ, матрицу групп элементов И, группу элементов И, группу блоков элементов И,, группу элементов ИЛИ. Устройство учитывает занятость оперативной памяти вычислительного комплекса и выделяет на запрос вычислительных ресурсов комплекса точно требуемый объем памяти, что обеспечивает экономное ее не- пользование. 2 з.п, ф-лы, 5 ил. S (Л с ю о о 00 со ел

Чр

ktf

33

Л

ZJ

5

К

36

2e

-fwll

т

5

г г Г

|« РП f

JV

J9I я

39

Фиг.З

X

т

Физ.д.

57