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

(59 4 С 06 Р 12/ ОПИСАНИЕ ИЗОБРЕТЕНИЯ ЕТЕЛЬСТВУ А ВТОРСКОМУ операх ком- вляется ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ(56) Авторское свидетельство СССР У 881722, кл. С 06 Р 3/04, 1981.Авторское свидетельство СССР В. 1213484) кл. С 06 Р 3/04, 1984. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ ОПЕРАТИВНОЙ ПАМЯТИ (57) Изобретение относится к области цифровой вычислительной техники, в частности к устройствам для распределения ресурсов в вычислительных комплексах, и может быть использовано для распределения тивной памяти в вычислительны ппексах, Целью изобретения я расширение функциональных возможностей устройства за счет учетазанятости оперативной памяти на основании информации запросов ресурсов иотказов от ресурсов оперативной памяти. Устройство содержит группуэлементов сравнения, матрицу элементов сравнения, блок дешифрациикодов, блок-шифратор кодов, регистр,первый, второй элементы И, элементзадержки, элемент ИЛИ, матрицу группэлементов И, группу элементов И,группу блоков элементов И, группуэлементов ИЛИ, Устройство учитываетзанятость оперативной памяти вычислительного комплекса и выделяет назапрос вычислительных ресурсов комплекса точно требуемый объем памяти,что обеспечивает экономное ее использование. 2 з,п. ф-лы, 5 ил.90335 2 группы выходов, выход 49 признакаочистки памяти.Коммутатор 44 содержит группуэлементов ИЛИ 50, первую 51 и вторую52 группы элементов И, первый 53 ивторой 54 элементы И-ИЛИ, блок группинформационных входов 55, группу управляюших входов 56, выход 57 коммутатора 44, первую 58 и вторую 59группы информационных входов, выходы60 объема и 61 адреса свободногомассива памяти,Устройство работает следующимобразом,В регистре 4 хранятся признакинезанятости распределяемых наименьших объемов памяти под ранее обслу 10 5 женные запросы. Единичный сигнал на х-м выходе регистра (1=1,Р) означает, что 1-й объем памяти в данное время не выделен обслуженным запросом, Выходы регистра 4 анализируются в блоке 5, где вырабатываются коды 48 начальных адресов и 47 размеров свободных областей памяти, а также признак 19 очистки памяти, означающий, что число свободных массивов больше числа М анализируемых 3массивов и целесообразным является перераспределение памяти между задачами для объединения небольших свободных массивов в один массив суммарного объема. Код требуемого объема памяти поступает на вход 15, а сопровождающий этот код сигнал запроса - на вход 14, Группа элемен" тов 1 сравнения вырабатывает сигналы а 1, означакнцие, что размер 1-го свободного массива не меньше размера требуемого и 1-й массив можно выделить под запрос (=1,М), Матрица элементов 2 сравнения вырабатыаает сигеапи Ът 1.1 хщТМ-Т 1 1 х,М), означающие, что размер (1+1)-го массива не меньше размера -го массива, Сигналы а;, аЦ+1), Ь 1 поступают на 11"ю группу элементов И 9 матрицы, на выходе второго элемента И 9 которой вырабатывается сигнал ЙЦ (равный единице, если из 1-го и Я+1)-го массивов под запрос выделяется х-й массив), а на выходе третьего элемента И 9 - сигнал 1 Ц (равный единице, если из этих же двух массивов под запрос выделяется (1+1)-й массив). Если эти массивы . меньше требуемого, то ИЦ 113=0. На вход а"го епемеета И 1 готппм наступают сигналы Й 1 (1=1, М) и 20 25 30 35 40 45 50 55 БДК 3 содержит первый 23 и вто рой 24 элементы И-ИЛИ, первый 25 ивторой 26 дешифраторы, первый 27 ивторой 28 элементы задержки, группуэлементов ИЛИ 29, группу элементовИ-ИЛИ 30, блок групп элементов И 31,входы 32 признака выделения и 37прйзнака освобождения массива памя"ти, входы 33 адреса выделяемого и34 освобождаемого массива памяти,входы 35 объема выделяемого и 36объема освобождаемого массива па;мяти, первую 38 и вторую 39 группывыходов,БЧК 5 содержит матрицу групп эле" ментов И 40, группу элементов И 41, вторую группу шифраторов 42, первую группу шифраторов 43; группу коммутаторов 44, элемент ИЛИ 45, группу входов 46, первую 47 и вторую 4812Изобретение относится к цифровойвычислительной технике, в частностик устройствам для распределения оперативной памяти, и может быть использовано для распределения оперативной памяти в вычислительных комплексах,Целью изобретения является расширение функциональных возможностейустройства за счет учета занятостиоперативной памяти на основании инфор. мации запросов ресурсов и отказовот ресурсов оперативной памяти,На фиг, 1 и 2 представлена структурная схема устройства; на фиг. 3 -. схема блока дешифрации кодов (БДК);на фиг, 4 - схема блока-шифраторакодов (БШК); на фиг, 5 - схема коммутатора,Устройство содержит группу элементов 1 сравнения, матрицу элементов 2 сравнения, БДК 3, регистр 4,БШК 5, второй элемент И 6, элемент 7задержки, элемент ИЛИ 8, матрицугрупп элементов И 9, первый элементИ 10, группу элементов И 11, группублоков элементов И 12, группу элементов ИЛИ 13, вход 14 запроса, вход15 требуемого размера массива памяти, вход 16 отказа, вход 17 размераосвобождаемого массива памяти, вход18 адреса освобождаемого массива памяти, выход 19 признака очистки, выходы 20 признака наличия и 21 признака отсутствия требуемого массивапамяти, выход 22 начального адресавыделяемого массива памяти,сива, которые переключают соответствующие разряды регистра 4. После этого переключения БШК 5 формирует новые коды адресов и объемов свободных массивов, поскольку объем Ч, был выделен под запрос. К моменту формирования кодов сигнал 20 погашается, что свидетельствует о том, что код на выходе 22 не соответствует адресу выделенного массива, поскольку состояние регистра 4 изменилосьеВ случае освобождения какой-либо задачей ресурса памяти на устройство поступают коды адреса 18 и размера 17 освобождаемого массива, признак отказа 16. В блоке 3 выбираютсявыходы 39 с номерами от А до А +н н +Ч -1 (А и Ч - начальный адрес ио Н Оразмер освобождаемого массива), которые переключают в единичное состояние.соответствующие разряды регистра 4, что свидетельствует о возможности выделения освободившейся памяти под новые запросы, Перед началом работы устройства подаются признак 16, адрес 18 начала и размер 17 всего распределяемого массива памяти, что означает незанятость всей памяти и обеспечивает установку всех разрядов регистра 4 в единичное состояние. БДК 3 работает следующим образом. По сигналу 32 выделения (37 ос- . вобождения) массива через элементы И-ИЛИ 23 и 24 на дешифраторы 25 и 26 проходят коды 33 адреса и 35 размера выделяемого (34 адреса и 36 размера освобождаемого) массиваНа д-м выходе дешифратора 25, соответствующем адресу, сигнал принимает единичное значение и поступает на д-е элементы И 1-х элементов И-ИЛИ 30 (ТР, =1,Р), На выходе груп" пы элементов ИЛИ 29 - код, в котором к-й сигнал равен единице (1=1,Ч, где Ч - размер массива), 1-й сигнал поступает на (ш+1)-й элемент И ш-х элементов И-ИЛИ 30 (ш=1,Р). На выходах группы элементов И-ИЛИ 30 единичное значение принимают сигналы с А-го по (А+Ч)-й (А и Ч адрес и размер массива), которые через первые (вторые) элементы И 31 групп блока при наличии задержанного на элементе 27 (28) задержки сигнала 32 (37) выдаются на выходы 33 (39) БПК. 50 3 12903351 к, е(к=1, -1), оаиачаюиие призначении "1" выбор 1-го массива среди массивов с 1 -го до М-го (411) исреди массивов с 1-го до 1-го (1 К,-1). Эти сигналы принимают единичное значение на входах только одного из М элементов И 11, поэтому среди выходов группы элементов И 11только один сигнал принимает единичное значение, причем номер этого 10сигнала в группе соответствует номеру того свободного массива памяти,который является оптимальным дляданного запроса по критерию Ч. -Ч =Т=шп ,О (Ч. и Ч - размеры 1-го 15и требуемого массивов), Единичныйсигнал на выходе 1-го элемента И 11группы открывает 1-ю группу элементов И 12 блока, через которую и далее через, группу элементов ИЛИ 13 20на выход 22 выдается код начальногоадреса 1.-го массива с 1-го выхода48 группы выходов БШК, Одновременнос выдачей кода адреса выдается признак 20 наличия требуемого массива,сформулированный из задержанного наэлементе 7 задержки и прошедшего через элемент И 6 сигнала запроса,Формирование признака 20 происходитна элементе И 10 в случае превыше 30ния (равенства) размера хотя бы одного из свободных массивов над разме"рами требуемого массива, что определяется появлением на прямом выходеэлемента ИЛИ 8 единичного сигналакак результата логического сложениясигналов с выходов группы элементов1 сравнения, В противном случае синверсного выхода элемента ИЛИ 8 выдается на выход 21 признак отсут- щствия требуемого массива,. Единичный сигнал 20, вырабатываемый приудовлетворении запроса, через ин. версный вход элемента И 6 гасит сигнал на входе элемента 7 задержки, 45что обеспечивает гашение сигнала20 через время, примерно равное времени задержки на элементе У. Сигнал20 импульсной форьы.используется вБДК 3, где он открывает выход БДК,переключающий состояние разрядоврегистра 4, В БДК происходит выборразрядов регистра 4, которые надопереключать в нулевое состояние,так как соответствующие им распределяемые объемы памяти выделены подданный запрос, Выбираются выходы 38БДК сномерами отАдоА+Ч, -1, гдеА. -код начального адреса вйделяемого мас"-я строка матрицы групп элементовИ 40 вырабатывает распределенныйкод числа единичных сигналов, следующих в группе входов 46 подряд, начиная с -го входа, те. числа незанятых объемов памяти. На шифраторах43 группы распределенный код преобразуется в двоичный, -й элементИ 41 группы вырабатывает признак начала нового свободного массива вслучае единичного значения (1.+1)-гои нулевого значения -го входов 46.По этому признаку на (1+1)-м шифраторе 42 группы вырабатывается двоичный код адреса, равного адресу(1+1) -го распределяемого объема впамяти (в простейшем случае этот адрес равен +1). Признаки начала свободных массивов, их размеры и адре-са с выходов элементов И 41, шифраторов 43 и 42 поступают на коммутаторы 44, которые выдают коды 47объема и 48 адреса первых М свободных массивов памяти, Если число свободных массивов больше М, то элементИЛИ 45 вырабатывает сигнал 49 очистки памяти,К-й коммутатор 44 работает следующим образом, На -й вход 1-го элемента ИЛИ 50 поступает признак того,что начинающийся с адреса 2 К+1-2свободный массив уже выдан через 1-йкоммутатор 44 (=1,К; 1=1,К 1+2), На выходе 1-го элемента ИЛИ 50группы - единичный сигнал, если ука"занный массив выдан через один иэпредыдущих коммутаторов 44, и поэтому этот массив не выдается черезданный коммутатор: единичный выход1-го элемента ИЛИ 50 не пропускаетчерез 1-й элемент И группы 51 признак начала нового свободного массива, начинающегося с адреса 2 К+1-2,поступающий с 1-го входа группы входов 56. Единичные выходы группы 51элементов И соответствуют свободныммассивам, не выданным через предыдущие коммутаторы; на выходах группы 52 элементов И и выходах первогои второго элементов И группы 51единичное значение принимает только сигнал, соответствующий массивуиз укаэанных, имеющему меньший адрес, Единичное значение этого сигнала пропускает на выходы 60 и 61через элементы.И-ИЛИ 53 и 54 кодыобъема, поступающего с группы входов 59, и адреса, поступающего с 0335 6. группы входов 58, Признак выдачикодов объема и адреса через данныйкоммутатор выдается с выхода одногоиз элементов И 52 группы на выход57 для использования в последующихкоммутаторах,Таким образом, устройство позволяет сохранить информацию о занятых массивах памяти, выделять10 под запрос требуемый объем памяти,и учитывать освобождение памяти приотказе от ресурсов,Формула изобретения1, Устройство для распределенияресурсов оперативной памяти, содержащее группу элементов сравнения,матрицу элементов сравнения, эле мент задержки, элемент ИЛИ, первыйэлемент И, группу элементов И, группу блоков элементов И, группу элементов ИЛИ, причем вход объема требуемого массива памяти устройства 25 подключен к первым входам элементов сравнения группы, выходы которых подключены к входам элементаИЛИ, прямой выход которого подключен к первому входу первого элемен та И, второй вход которого подключен к выходу элемента задержки,выход первого элемента И подключенк выхоцу признака наличия требуемогомассива памяти устройства, выходы 35 элементов И группы подключены к управляющим входам блоков элементов Игруппы, выходы которых подключенык входам элементов ИЛИ группы, выходы которых подключены к выходу 40 начального адреса выделяемого массина памяти устройства, о т л и -ч а ю щ е е с я тем, что, с цельюрасширения функциональных возможно-.стей за счет учета занятости опера тивной памяти на основании информации запросов ресурсов и отказов отресурсов оперативной памяти, в неговведены блок дешифрации кодов, регистр, блок шифрации кодов, второй 50 элемент И и матрица групп элементовИ, причем вход запроса устройстваподключен к прямому входу второгоэлемента И, инверсный вход и выходкоторого подключены соответственно 55 к выходу первого элемента И и входуэлемента задержки, входы признакавыделения массива памяти, адресавыделяемого массива памяти, адресаосвобождаемого массива памяти", объе 1290335 8ма выделяемого массива памяти, объема освобождаемого массива памяти,. признака освобождения массива памяти блока дешифрации кодов подключены соответственно к выходу первого элемента И, выходам элементов ИЛИ группы, входам адреса освобождаемого, массива памяти, требуемого размера массива памяти, размера освобождаемого массива памяти и отказа устройства, первая и вторая группы выходов блока дешифрации кодов подключены соответственно к сбросовому и установочному входам регистра, выходы которого подключены к группе входов блока шифрации кодов, выход очистки которого подключен к выходу признака очистки устройства, первая группа выходов блока шиФрации кодов подключена к вторым входам элементов сравнения группы, первым входам Ц-х (1=1,М, З=д,М, где .М - число анализируемых свободных массивов памяти) и вторым входам (К, д=х -1) (1=2, М, К=1, -1) элементов сравнения матрицы, выход Ц-го (=1,М; 3=,М) элемента сравнения матрицы подключен к инверсному входу первого элемента И Ц-й группы матрицы, выход которого подключен к инверсному взводу второго элемента И той же группы матрицы, прямой вход которого подключен к выходу 3-го элемента сравнения группы, прямые входы первого и третьего элементов И Ц-й группы матрицы элементов И подключены к выходу Я+1)-го элемента сравнения группы, выход второго элемента И Ц-й группы матрицы подключен к инверсному входу третьего элемента И той же группы матрицы и входу -го элемента И группы, выход третьего элемента И 13-й группы матрицы подключен к входу (3+1)-го элемента И группы, ин- версный выход элемента ИЛИ подключен к выходу признака отсутствия требуемого массива устройства, вторая группа выходов блока-шифратора кодов подключена к информационным входам блоков элементов И группы,2, Устройство по п. 1, о т л и -ч а ю щ е е с я тем, что блок.дешифрации кодов содержит первый,второй элементы.И-ИЛИ, первый, второй дешифраторы, первый, второй элементы задержки, группу элементов ИЛИ, группы элементов И-ИЛИ, блок групп элементов И, причем вход приз нака выделения массива памяти блока дешифрации кодов подключен к прямым входам первых элементов И первого и второго элементов И-ИЛИ, к инверснымиер- хо о ого овходам вторых элементов И первого второго элементов И-ИЛИ и через п вый элемент задержки - к первым в дам всех элементов И первой группь блока, вход признака освобождения10 массива памяти блока дешифрации к дов подключен к инверсным входам первых элементов И первого и втор элементов И-ИЛИ, к первым входам вторых элементов И первого и втор5 го элементов И-ИЛИ и через второй го 25 35 40 45 50 55 элемент задержки - к первым входам всех элементов И второй группы блока, входы адреса выдаваемого массива памяти, адреса освобождаемого массива памяти, объема выделяемого массива памяти и объема освобождаемого массива памяти подключены соответственно к вторым входам первого и второго элементов И, первого и второго элементов И-ИЛИ, выходы первого и второго элементов И-ИЛИ подключены соответственно к входам первого и второго дешифраторов, х-й (а=1,Рр где Р - минимальное числораспределяемых массивов памяти) выход первого дешифратора подключен кпервому входу -го элемента И 3-гоЯ=1,Р) элемента И-ИЛИ группы, выходкоторого подключен к вторым входам3-х элементов И первой и второйгрупп блока, х-й (=1, Р) выходвторого дешифратора подключен к первому входу "го элемента ИЛИ группы,второй вход которого подключен к выходу (1+1)-го (1=1, Р) элемента ИПИгруппы, второй вход (Р)-го элемента ИЛИ группы подключен к Р-му выходу второго дешифратора, выход -го(т=Г, РЧ) элемента ИЛИ группы подключен к второму входу д-го (х=1,Р) элемента И 3-го Ц=, Р)элемента И-ИЛИ группы, Р-й выходвторого дешифратора подключен к второму входу первого элемента И Р"гоэлемента И-ИЛИ группы, выходы элементов И первой и второй групп блока подключены соответственно к первой и второй группам выходов блокадешифрации кодов,3, Устройство по п. 1, о. т л ич а ю щ е е с я тем, что блок шифрации кодов содержит матрицу группэлементов И, группу элементов И,группы коммутаторов, первую и вто 9 12903 рую группы шифраторов и элемент ИЛИ,( причем 1"й вход группы блока-шифратора кодов подключен к первому входу первого и прямому входу второго элементов И 1 д-й (1=1, Р) группы матрицы, к вторым входам первых элементов И (1, -1)-х (х=2, Р, 1=1, 1-1) групп матрицы, к прямому входу ., (д)-го элемента И группы и к инверсному входу 1-го (=1, Р) эле кт мента И группы, выход первого эле,мента И 13-й (3 =1, Р) группы матрицы подключен к инверсному входу второго элемента И той же группы матрицы, к первому входу первого и прямому входу второго элемента И (1, 3+1)-й (3=3., Р) группы матрицы; выход нторого элемента И к 1-й группы =к, Р) матрицы и выход первого элемента И (, Р)-й группы матрицы подключены к входу 1-го шифратора первой группы, первый вход группы блока-шифратора кодов подключен к входу первого шифратора , второй группы и к первому управляющему входу группы первого коммутато 35 10ра группы, выход ).-го (1=1, Р) шифратора первой группы подключен к (-2 К+2)-му информационному входу (К=1, М+1) первой группы К-го коммутатора группы, к (1-2 К+2)-му информационному входу второй группы которого подключен выход 1-го шифратора второй группы, вход которого и (-2 К+2)- й управляющий вход группы К-го коммутатора группы подключены к выходу (1-1)-го (=2, Р) элемента И групг(ы, группа выходов 1-го (1= =1, М) коммутатора группы подключе - на к к-й группе информационных входов блока 1-го (1=хт 1, Мт 1) коммутатора группы, первый выход -го коммутатора группы подключен к -му выходу первой группы блока-шифратора кодов, второй выход ).-го коммутатота группы подключен к -му выходу второй группы блока-шифратора .кодов, первый выход (М+1)-го коммутаторагруппы подключен к входам элемента ИЛИ, выход которого подключен к выходу признака очистки блока-шифратора кодов.3290335 Составитель С, Бурухинедактор И. Рыбченко ТехредЛ.Сердюкова Корректор О, Луговая а Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 з 7904/48 Тираж ВНИИПИ Государств по делам изоб 313035, Москва, Ж73 Подписнонного комитета СССРетений и открытийРаушская наб д, 4/