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

 

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

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

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

РЕСПУБЛИК (5D 4 С 06 F 12/00

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

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3884649/24-24 (22) 15,04.85. (46) 15.02.87. Бюл, Р 6 (72) М. М. Зарецкий, С, В. Ефимов, В. В. Мазаник и Н. В. Лебедев (53) 681.3(088.8) (56) Авторское свидетельство СССР

У 881722, кл. G 06 F 3/04, 1981

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

9. 1213484, кл. G 06 F 3/04, 1984. (54) .УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

РЕСУРСОВ ОПЕРАТИВНОЙ IIAMHTH (57) Изобретение относится к области цифровой вычислительной техники, в частности к устройствам для распределения ресурсов в вычислительных комплексах, и может быть использовано для распределения оперативной памяти в вычислительных комплексах, Целью изобретения является

SU 1290 35 А1 расширение функциональных возможностей устройства за счет учета занятости оперативной памяти на основании информации запросов ресурсов и отказов от ресурсов оперативной памяти. Устройство содержит группу элементов сравнения, матрицу элементов сравнения, блок дешифрации кодов, блок-шифратор кодов, регистр, первый, второй элементы И, элемент задержки, элемент ИЛИ, матрицу групп элементов И, группу элементов И, группу блоков элементов И, группу элементов ИЛИ, Устройство учитывает занятость оперативной памяти вычислительного комплекса и выделяет на а запрос вычислительных ресурсов комплекса точно требуемый объем памяти, что обеспечивает экономное ее использование. 2 з.п. ф-лы. 5 ил. С:

90335 2

1 12

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

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

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

Устройство содержит группу элементов 1 сравнения, матрицу элементов 2 сравнения, БДК 3, регистр 4, БШК 5, второй элемент И 6, элемент 7 задержки, элемент ИЛИ 8, матрицу групп элементов И 9, первый элемент

И 10, группу элементов И 11, группу блоков элементов И 12, группу элементов ИЛИ 13, вход 14 запроса, вход

15 требуемого размера массива памяти, вход 16 отказа, вход 17 размера

J освобождаемого массива памяти, вход

18 адреса освобождаемого массива памяти, выход 19 признака очистки, выходы 20 признака наличия и 21 признака отсутствия требуемого массива памяти, выход 22 начального адреса выделяемого массива памяти, БДК 3 содержит первый 23 и вто рой 24 элементы И-ИЛИ, первый 25 и второй 26 дешифраторы, первый 27 и второй 28 элементы задержки, группу элементов ИЛИ 29, группу элементов

И-ИЛИ 30, блок групп элементов И 31, входы 32 признака выделения и 37 прйзнака освобождения массива памя" ти, входы 33 адреса выделяемого и

34 освобождаемого массива памяти, входы 35 объема выделяемого и 36 объема освобождаемого массива па;мяти, первую 38 и вторую 39 группы выходов.

BI% 5 содержит матрицу групп эле" ментов И 40, группу элементов И 41, вторую группу шифраторов 42, первую группу шифраторов 43; группу коммутаторов 44, элемент ИЛИ 45, группу входов 46, первую 47 и вторую 48

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

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

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

60 объема и 61 адреса свободного массива памяти °

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

В регистре 4 хранятся признаки незанятости распределяемых наименьших объемов памяти под ранее обслуженные запросы. Единичный сигнал на

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

I массивов и целесообразным является перераспределение памяти между задачами для объединения небольших свободных массивов в один массив суммарного объема. Код требуемого объема памяти поступает на вход 15, а сопровождающий этот код сигнал запроса — на вход 14, Группа элемен" тов 1 сравнения вырабатывает сигналы ai означакнцие, что размер i-го свободного массива не меньше размера требуемого и i-й массив можно выделить под запрос (i=l,M), Матрица элементов 2 сравнения вырабатыаает сигеапи Ът1.(i=I,М-Т, j=i,М-I j, означающие, что размер (j+1)-го массива не меньше размера i-го массива, Сигналы а;, a(j+1), bij поступают на ij "ю группу элементов И 9 матрицы, на выходе второго элемента

И 9 которой вырабатывается сигнал

dij (равный единице, если из i-го и (j+1)-ro массивов под запрос выделяется i-й массив), а на выходе третьего элемента И 9 — сигнал 3ij (равный единице, если из этих же двух массивов под запрос выделяется (j+1)-й массив). Если эти массивы . меньше трeáyeMoro, то 611 Ы1=0. На вход i-го епемеета И И алом еостУпают сигналы di j (j=i М-1) и сива, которые переключают соответствующие разряды регистра 4. После этого переключения БШК 5 формирует новые коды адресов и объемов свободных массивов, поскольку объем U, был выделен под запрос. К моменту формирования кодов сигнал 20 погашается, что свидетельствует о том, что код на выходе 22 не соответствует адресу выделенного массива, поскольку состояние регистра 4 изменилосье

В случае освобождения какой-либо задачей ресурса памяти на устройство поступают коды адреса 18 и размера 17 освобождаемого массива, признак отказа 16, В блоке 3 выбираются

I ! выходы 39 с номерами от А до А +

I н н

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

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

БДК 3 работает следующим образом. По сигналу 32 выделения (37 ос- . вобождения) массива через элементы

И-ИЛИ 23 и 24 на дешифраторы 25 и

26 проходят коды 33 адреса и 35 размера выделяемого (34 адреса и 36 размера освобождаемого) массива ° На

i-м выходе дешифратора 25, соответствующем адресу, сигнал принимает единичное значение и поступает на

i-e элементы И j-х элементов И-ИЛИ

30 (Т - i P, j=i,Р). На выходе груп" пы элементов ИЛИ 29 — код, в котором

Т-й сигнал равен единице (I=),Ч, где V - размер массива}, 1-й сигнал поступает на (m-1+1)-й элемент И ш-х элементов И-ИЛИ 30 (ш=1,Р). На выходах группы элементов И-ИЛИ 30 единичное значение принимают сигналы с А-ro по (А+Ч-1)-й (А и Ч адрес и размер массива), которые через первые (вторые) элементы И 31 групп блока при наличии задержанного на элементе 27 (28) задержки сигнала 32 (37) выдаются на выходы

38 (39) БПК.

50 з 1290335

1K, i-1 (K=I, I.-1), оаиачаюиие при значении "1" выбор i-го массива среди массивов с 1-го до м-ro (dij) и среди массивов с 1-го до i-го (fK, i-1). Эти сигналы принимают единичное значение на входах только одного из М элементов И 11, поэтому среди выходов группы элементов И 11 только один сигнал принимает единичное значение, причем номер этого 10 сигнала в группе соответствует номеру того свободного массива памяти, который является оптимальным для данного запроса по критерию V. -V = .! Т

=т п >,О (V. и Ч вЂ” размеры i-ro 15 и требуемого массивов), Единичный сигнал на выходе i-го элемента И 11 группы открывает i-ю группу элементов И 12 блока, через которую и далее через, группу элементов ИЛИ 13 20 на выход 22 выдается код начального адреса i-го массива с i-ro выхода

48 группы выходов БШК, Одновременно с выдачей кода адреса выдается признак 20 наличия требуемого массива, сформулированный из задержанного на элементе 7 задержки и прошедшего через элемент И 6 сигнала запроса, Формирование признака 20 происходит. на элементе И 10 в случае превыше- 30 ния (равенства) размера хотя бы одного из свободных массивов над размерами требуемого массива, что определяется появлением на прямом выходе элемента ИЛИ 8 единичного сигнала как результата логического сложения сигналов с выходов группы элементов

1 сравнения, В противном случае с инверсного выхода элемента ИЛИ 8 выдается на выход 21 признак отсут- щ ствия требуемого массива,. Единичный сигнал 20, вырабатываемый при удовлетворении запроса, через ин. версный вход элемента И 6 гасит сигнал на входе элемента 7 задержки, что обеспечивает гашение сигнала

20 через время, примерно равное времени задержки на элементе 7. Сигнал

20 импульсной формы. используется в

БДК 3, где он открывает выход БДК, переключающий состояние разрядов регистра 4, В БДК происходит выбор разрядов регистра 4, которые надо переключать в нулевое состояние, так как соответствующие им распределяемые объемы памяти выделены под данный запрос, Выбираются выходы 38

БДК с номерами от А„до A. +V -1, rpe A„ .— код начального адреса вйделяемого мас129

БШК 5 работает следующим образом, i-я строка матрицы групп элементов

И 40 вырабатывает распределенный код числа единичных сигналов, следующих в группе входов 46 подряд, начиная с 1 го входа, T,,е. числа незанятых объемов памяти. На шифраторах

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

И 41 группы вырабатывает признак начала нового свободного массива в случае единичного значения (i+1)-ro и нулевого значения i-го входов 46.

По этому признаку на (i+1)-м шифраторе 42 группы вырабатывается двоичный код адреса, равного адресу (i+1) -го распределяемого объема в памяти (в простейшем случае этот адрес равен i+1). Признаки начала свободных массивов, их размеры и адре- са с выходов элементов И 41, шифраторов 43 и 42 поступают на коммутаторы 44, которые выдают коды 47 объема и 48 адреса первых М свободных массивов памяти, Если число свободных массивов больше M то элемент

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

i+2), На выходе j-го элемента ИЛИ 50 группы — единичный сигнал, если ука" занный массив выдан через один иэ предыдущих коммутаторов 44, и поэтому этот массив не выдается через данный коммутатор: единичный выход

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

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

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

10 под запрос требуемый объем памяти, и учитывать освобождение памяти при отказе от ресурсов, Формул а изобретения

f5

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

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

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

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

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

50 элемент И и матрица групп элементов

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

55 к выходу первого элемента И и входу элемента задержки, входы признака выделения массива памяти, адреса выделяемого массива памяти, адреса освобождаемого массива памяти, объе1290335 8

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

ij-х (i=1,M-I, j=i,M-I, где M — число анализируемых свободных массивов памяти) и вторым входам (К, i=x - I ) (i=2, M-1, К= I, i-1) элементов сравнения матрицы, выход ij-ro (i=1 М-1; j-=i M-1) элемента сравнения матрицы подключен к инверсному входу первого элемента И ij-й группы матрицы, выход которого подключен .к инверсному взводу второго элемента И той же группы матрицы, прямой вход которого подключен к выходу

j-го элемента сравнения группы, прямые входы первого и третьего элементов И ij-й группы матрицы элементов И подключены к выходу (j+1)-го элемента сравнения группы, выход второго элемента И ij-й группы матрицы подключен к инверсному входу третьего элемента И той же группы матрицы и входу i-го элемента И группы, выход третьего элемента И

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

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

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

5 го элементов И-ИЛИ и через второй элемент задержки - к первым входам всех элементов И второй группы блока,. входы адреса выдаваемого массива памяти, адреса освобождаемого массива памяти, объема выделяемого массива памяти и объема освобождаемого массива памяти подключены соответственно к вторым входам первого и второго элементов И, первого и второго элементов И-ИЛИ, выходы первого и второго элементов И-ИЛИ подключены соответственно к входам первого и второго дешифраторов, i-й (i=1,Р, где P — минимальное число распределяемых массивов памяти) выход первого дешифратора подключен к первому входу i-го элемента И j-ro (j =i, Ð) элемента И-ИЛИ группы, выход которого подключен к вторым входам

j-x элементов И первой и второй групп блока, i-й (i=1 P-1) выход второго дешифратора подключен к первому входу i"ãî элемента ИЛИ группы, второй вход которого подключен к выходу (i+1)-ro (i=1, P-2) элемента ИПИ группы, второй вход (P-1)-го элемента ИЛИ группы подключен к P-му выходу второго дешифратора, выход i-го

ii=l, РЧ) элемента ИЛИ группы подключен к второму входу i-го (i=1, P-1) элемента И j ro (j i, P-1) элемента И-ИЛИ группы, P-й выход второго дешифратора подключен к второму входу первого элемента И P" ro элемента И-ИЛИ группы, выходы элементов И первой и второй групп блока подключены соответственно к первой и второй группам выходов блока дешифрации кодов, 3, Устройство по п. 1, о. т л ич а ю щ е е с я тем, что блок шиф- . рации кодов содержит матрицу групп элементов И, группу элементов И, группы коммутаторов, первую и вто9 12903 рую группы шифраторов и элемент ИЛИ,( причем i"é вход группы блока-шифратора кодов подключен к первому входу первого и прямому входу второго элементов И ii-й (i=1 P-1) группы матрицы, к вторым входам первых элементов И (j, i-1)-х (i=2, Р, j=l, i-1) групп матрицы, к прямому входу .. (i-1)-го элемента И группы и к инверсному входу i" го (i=1, Р-1) элемента И группы, выход первого эле, мента И ij-й (j=l, P-1) группы матрицы подключен к инверсному входу второго элемента И той же группы матрицы, к первому входу первого и прямому входу второго элемента И (i, )+1 )-й (j=i, Р-2) группы матриW»;r выход нторого элемента И ij-й группы (j=i, P-1) матрицы и выход первого элемента И (i P-I)-й группы матрицы подключены к входу i-го шифратора первой группы, первый вход группы блока-шифратора кодов подключен к входу первого шифратора, второй группы и к первому управляющему входу группы первого коммутато35 10 ра группы, выход ) -го (i=l, Р) шифратора первой группы подключен к (i-2К+.2)-му информационному входу (К=l, И+1) первой группы К-го коммутатора группы, к (i-2К+2)-му информационному входу второй группы которого подключен выход i-го шифратора второй группы, вход которого и (i-2K+2)- и управляющий вход группы

К-ro коммутатора группы подключены к выходу (i-1)-го (i=2, P) элемента

И групг(ы, группа выходов i-ro (i=

=l A) коммутатора группы подключе— на к к-й группе информационных входов блока j-го (j=i+1, M+1) коммутатора группы, первый выход i-ro коммутатора группы подключен к i-му выходу первой группы блока-шифратора кодов, второй выход >-го коммутатота группы подключен к i-му выходу второй группы блока-шифратора .кодов, первый выход (М+1 )-ro коммутатора группы подключен к входам элемента

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

1290335

Составитель С, Бурухин

Редактор И. Рыбченко ТехредЛ.Сердюкова Корректор О. Луговая

Заказ 7904/48 Тираж 673 Подписное

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

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

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