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

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

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

На фиг.1 представлена структурная .схема устройства; на фиг.2 - схема блока объединения; на фиг.З - схема ;коммутатора.

Устройство содержит группу 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.

Блок объединения содержит (фиг.2) коммутатор 28, с первого по третий сумматоры 29-31, первый элемент 32 сравнения, второй 33, первый 34, третий 35, четвертый 36, пятый 37 регистрыJс первого по третий элементы И-ИЛИ 38-40, первый 41, второй 42 элементы ИЛИ, первый элемент 43 задержки, триггер 44, второй элемент 45 сравнения, пятый 46, четвертый 47 сумматоры, третий элемент ИЛИ 48, четвертый, седьмой, шестой и пятый элементы И-ИЛИ 49-52, третий элемент 153 сравнения, второй 54, третий 55 элементы задержки, четвертый элемент ИЛИ 56 элемент И 57, входы адресов 58 и объемов 59 свободных массивов, входы признаков отсутствия 60 и на- „пичия 61 дёлого массива требуемого размера, вход 62 начального адреса дёлого массива требуемого размера, выходы признака наличия 21 признака отсутствия 22, начального адреса 23 и объема 63 выделяемого массива.

признака выде,ления объема 64, началь- ного адреса 24. и сдвига обращения к памяти 25, модифидированных начального адреса 26 и сдвига обращения к Ламяти 27, входы признака освобождения 17, адреса 18 и объема 19 освобождаемого массива, выходы признака отказа 65, адреса 66 и объема 67 освобождающегося массива.

Коммутатор содержит формирователь 68 импульсов (фиг.З), элемент 69 задержки, блок пар групп элементов И 70, первую 71, вторую 72 группы элементов ИЛИ, триггер 73, первую 74,вторую 75 группы элементов И, входы объемов 58 и адресов .59 свободных массивов, входы запуска 76, и останова 77,, выходы первого 78 и второго 79 свободных массивов, выход 80 отсутствия объединенного массива.

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

Регистр 4 хранит признаки-занятостк листов памяти, вьщеленных под ранее обслуженные запросы, шифратор 5 формирует коды начальных адресов и размеров свободных массивов памяти, а также выдает на выход 20 признак

очистки памяти в случае, когда число свободных массивов превьшает определенный порог и, следовательно, они имеют малые размеры. На группе 1 элементов сравнения сравниваются размеры всех свободных массивов с требуемым размером, поступившим на вход 16 одновременно с признаком запроса на входе 15.

Результат этого сравнения и результат сравнения свободных массивов между собой на блоке 2 поступают на блок 9, где формируются признаки выбора одного из каждой пары массивов под запрос. Эти признаки поступают на группу 11 элементов И, на выходе которой появляется сигнал выбора одного массива из всех свободных (в случае пре- вьшпения какого-либо размера массива над требуемым).

Адрес выбранного массива проходит через соответствующий блок группы 12 элементов И, группу 13 элементов ИЛИ на выход 62 блока 14 объединения. Сигнал с прямого выхода элемента

ИЖ 8 проходит через открытый задержанным на элементе 7 задержки сигналом запроса элемент И 10 на вход 61 блока 14. Этот сигнал означает наличие свободного массива нужного разме

pa - иначе выдается сигнал с инверсного выхода элемента ИЛИ 8 на вход 60 блока 14.

Адрес выделенного массива и его размер проходят через блок 14 вместе с признаком вьщеления массива на дешифратор 3, который вьщает сигналы занятия листов памяти на регистр 4. При освобождении задачей ресурса памяти коды признака отказа 17, размера массива 18 и адреса 19 через блок 14 поступают на дешифратор 3, в котором вырабатываются сигналы освобождения листов памяти, поступаюш;ие на ре гистр 4.

Если не найдено требуемого массив (целого), то начинает работать собственно блок 14 объединения. На входы 58 и 59 коммутатора 28 поступают код о бъемов, адресов свободных массивов с выходов шифратора 5. Исходное положение триггера 44 единичное. Сигнал 60 отсутствия целого массива проходи через открытый элемент И 57 на вход 76 коммутатора 28 и запускает его. На первой и второй группе выходов ко коммутатора 28 по очереди появляются сочетания кодов адресов и объемов каждых двух,свободных массивов. Сумма объемов с выхода сумматора 29 поступает на элемент 32 сравнения, где сравнивается с требуемым объемом с входа 16.

Одновременно вычисляются адрес конца первого массива на сумматоре 30 и величина объема, которую надо вьщелить из второго массива под запрос, на вычитаюш;ем сумматоре 31. Если сумма каких-то двух объемов не меньше требуемого, то элемент 32 сравнения выдает единичный сигнал, по которому триггер 44 переключается в О, остановится перебор пар; массивов на выходах коммутатора 28, что приводит к появлению на этих выходах нулевых кодов, нулевой суммы на выходе сумматора 29 и переключению выхода элемента 32 в О через определенное время, на регистры 33 и 37 принимаются коды адреса первого массива, адреса второго массива, объем первого массива, вьщеляемого числа листов из второго массива и

адрес конца первого массива соответ- g. ненному массиву, то элемент 45 сравственно.

Кроме того, через элементы И-ИЛИ 38 и 39 на дешифратор 3 проходят коды адреса 23 и объема 63 йервого

нения выдает нулевой сигнал.

Далее анализируют, в каком (первом или втором) массиве находится конкретный адрес обращения, который

0

5

g

Q

0

5

0

5

0

массива и признак выделения массива 64, а также выдается сигнал ответа устройства 21. Через время,, необходимое для отработки кодов в дешифраторе 3, сигнал с выхода элемента 43 задержки выдает на выходы 23,63,64 коды адреса второго массива. Дешифратор 3 отрабатывает и эти коды, переключая соответствующие разряды регистра 4 в О.

В случае отсутствия пары массивов с требуемым суммарным объемом по окончании переобора в коммутаторе 28 появляется сигнал на выходе 80, проходящий через элемент И-ИЛИ 40 на выход 22 устройства как признак отказа в запросе. Если при oбcл saiвaнии других запросов появляется сигнал на входе 60, то, поскольку триггер 44 выключен, элемент И ,57 закрывается, а элемент И 40 по сигналам на третьем и четвертом входах выдает признак отказа.

При освобождении каждого массива поступивший адрес и хранящийся в регистре 33 адрес объединенного массива сравниваются на элементе 53 сравнения. При несовпадении адресов на выходах 66, 67 элементами И-Ш1И 52 и 51 выдаются коды адреса и объема с входов 18 и 19 (а также признак освобождения с входа 17 через элемент ИЛИ 56 на выход. 65) и далее на дешифратор 3. При совпадении адресов сначала вьщаются коды объема и адреса первого массива, признака освобождения, а затем через время задержки на элементах 54 и 55 задержки- коды объема и адреса второго массива и признак освобождения. Кроме того, триггер 44 включается, что означает готовность устройства к выделению объединенного массива очередному запросу.

При обращении к памяти считается, что выделенный объем непрерывен. Для модификации адреса обращения с целью обеспечения правильности обращения используются элементы 45-50. На входы 24 и 25 поступают базовый адрес (номер первого листа массива) и сдвиг обращения (номер листа в массиве) . Если идет обращение к объединения выдает нулевой сигнал.

Далее анализируют, в каком (первом или втором) массиве находится конкретный адрес обращения, который

с выхода сумматора 46 поступает на вычитающий сумматор 47 вместе с адресом конца первого массива с регист- ра 37, EcJiH адрес обращения находится в -первом массиве, что определяется знаковым разрядом разности адресов, то выход элемента ИЛИ 48 пропускает через элементы И-ИЛИ 49 и 50 исходные коды адреса и сдвига (то же будет.

если идет обращение не к объединенно- tO группы и входом блока элементов

му массиву) на выходы 26 и 27, Если адрес обращения находится во втором массиве из тех, которые выделены и объединены, то на выходе 27,26 вы- дяются коды начала второго массива с регистра 34 -и сдвига во втором массиве с сумматора 47, равного разности полного адреса обращения и адреса конца первого массива.

Коммутатор 28 работает следующим образом. Сигнал запуска потенциального вида на входе 76 поступает на формирователь 68, с выхода которого импульсный сигнал устанавливает триггер 73 в 1 и запускает элемент 69 задержки, выходные сигналы которого по очереди открывают пары групп элементов И 70 блока. Коды объемов и адресов двух выбранных свободных массивов с выхода одной из пар групп элементов И 70 блока проходят через группы элементов ИЛИ 71, 72 и И 73, 74 на выходы 78 и 79. Таким образом, на выходах 78 и 79 появляются коды

пары массивов, на выходе 78 - первого 35 ми памяти, объем каждого из которых массива, на выводе 79 - с второго по меньше требуемого, в него введен блок массива, затем на йыходе 78 - объединения, причем выходы элементов

второго, а на выходе 79 - с третьего по К-й и т.д., пока сигнал с входа 77 не переключит триггер 73 в О, который своим выходным сигналом закроет группы элементов И 74 и 75. После окончания перебора всех пар массиврв с М+1-ГО выхода элемента 69 задержки выдается сигнал окончания перебора.

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

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

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

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

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

ИЛИ группы, выход адресов и объемов свободных массивов памяти шифратора

40 соединены соответственно с первым, вторым, третьим входами блока объединения, выход первого элемента И, инверсный выход элемента- ИЛИ и вход объема требуемого массива устройства

45 соединены соответственно с четвертым пятым и шестым входами блока объединения, входы признака освобождения, адреса и размера освобождаемого массива устройства соединены соответст50 венно с седьмым, восьмым и девятым входами блока объединения, первый, второй, третий и четвертый выходы блока объединения соединены с входам начального адреса, сдвига обращения, признаков отсутствия и наличия требуемого массива устройства, пятый выход блока объединения соединен с выходом адреса вьщеляемого массива

1328820

устройства, выходы с пятого по деся- нен с шиной единичного потенциала тый блока объединения подключены к устройства, шестой вход блока соеди- входам с первого по шестой дешифрато- нен с вторыми входами первого эле- ра, входы начального адреса и мента сравнения и третьего сумматора сдвига обращения устройства под- и четвертым входом второго элемен- ключены к десятому и один- та И-ИЛИ, выходы третьего, второго надцатому входам блока объеди- сумматоров соединены с информацион- нения..ными входами четвертого, пятого ре1Q гистров соответственно, выход перво2. Устройство по П.1, о т л и - го регистра подключен к пятому входу ч ающе е с я тем, что блок объе- первого элемента И-ИЛИ и первым вхо- динения содержит коммутатор, с пер- дам четвертого, пятого элементов вого по пятый сумматоры, с первого И-ИЛИ, выход второго регистра соеди- по пятый регистры, с первого по тре- 15 .- шестым входом первого элемен- тий элементы сравнения, триггер, с та И-ИЛИ, первым входом второго, первого по седьмой элементы И-ИЛИ, третьего элементов сравнения и вторьм с первого по четвертый элементы ИЛИ, входом пятого элемента И-ИЛИ, выход с первого по третий элементы задерж- третьего регистра соединен с пятым ки и элемент И, причем входы блока 20 входом второго элемента И-ИЛИ и пер- с первого по третий подключены соот- вым входом шестого элемента И-ИЛИ, ветственно к первому входу первого выход четвертого регистра соединен элемента И-ШШ, к первому и второму с шестым входом второго элемента входам коммутатора, выходы адреса И-ИЛИ и вторым входом шестого эле- и объема памяти первой группы выхо- 25 мента И-ИЛИ, выход пятого регистра дов которого соединены соответствен- соединен с первым входом четвертого но с информационным входом первого сумматора, вв1ходы модуля и знакового регистра и с первым входом перво го разряда которого соединены соответст- сумматора, четвертый вход блока сое- венно с первыми входами седьмого динен с вторым входом первого элемен- зо элемента И-ИЛИ и третьего элемента та И-ИЛИ, с первым входом второго ИЛИ, второй вход которого соединен элемента И-ИЛИ и с первым входом пер- с выходом второго элемента сравнения, вого элемента ИЛИ, пятый вход блока выход третьего элемента ИЛИ соединен соединен с первыми входами элемента с вторыми, третьими входами четвер- И и третьего элемента И-ИЛИ, выход того и седьмого элементов И-ИЛИ, элемента И соединен с третьим входом седьмой вход блока соединен с первым коммутатора, выход первого сумматора входом четвертого элемента ИЛИ и соединен с первым входом первога, эле- через второй элемент задержки с вто- мента сравнения, выход которого сое- рым входом четвертого элемента ИЛИ, динен с входами синхронизации с пер- д восьмой вход блокаподключен к тре- вого по пятый регистров, нулевым вхо- тьему входу шестого элемента ИЛИ, . дом триггера, вторыми входами второ- девятый вход блока соединен с вторым го элемента И-ШШ и первого элемен- . входом третьего элемента сравнения та ИЛИ, третьим входом первого эле- и третьим входом пятого элемента мента И-ИЛИ, четвертым входом комму- д И-ИЛИ, десятый вход блока соединен татора и через первый элемент задерж- с четвертым входом четвертого элемен- ки с первым входом второго элемента та И-ИЛИ, вторым входом второго зле- ИЛИ, четвертым входом первого и трё- мента сравнения и первьм входом пя- тьим входом второго элементов И-ИЛИ, того сумматора, одиннадцатый вход выход адреса второй группы выходов g блока соединен с четвертым входом коммутатора соединен с информационным седьмого элемента И-ИЛИ и вторым вхо- входом второго регистра и первым вхо- дом пятого сумматора, выход которого дом второго сумматора, выход объема соединен с вторым входом четвертого памяти второй группы выходов комму- сумматора, выход первого элемента татора соединен с вторыми входами с соединен с вторым входом второго первого, второго сумматоров, первым элемента ИЛИ, выходы блока с первого входом третьего сумматора и информа- по десятый соединены соответственно ционным входом третьего регистра, с выходами четвертого, седьмого, третий вход второго сумматора соеди- . третьего элементов И-ИЛИ, первого

9 1

элемента ИЛИ, первого,, второго эле- ментов И-ИЛИ, второго элемента ИЛИ, четвертого элемента ИЛИ, шесто- ;Го и пятого элементов И-ИЛИ, еди ничный выход триггера соединен с вторыми входами элемента И и третьего элемента , нулевой выход триггера соединен с третьим входом третьего элемента И-ИЛИ, четвертый вход которого соединен с третьим выходом коммутатора, прямой выход третьего элемента сравнения соединен с единичным входом триггера, четвертыми входами пятого, шестого элементов И-ИЛИ и через третий элемент задержки с пятыми входами пятого, шестого элементов И-ИЛИ, инверсный выход третьего элемента сравнения соединен .с шестыми входами пятого, шестого элементов И-ЙЛИ.

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

53 58

i6

2882010

с четвертым входом коммутатора, выход триггера соединен с первыми входами элементов И первой и второй групп, выходы элементов И первой, второй групп соединены-соответственно с первой, второй группами выходов коммутатора, вторые входы элементов И первой, второй групп соединены соответствен- 10 но с выходами элементов ИЛИ первой, второй групп, выходы с 1-го по М-й элемента задержки подключены к первым входам элементов И с 1-го по М-ю пар групп блока, выходы элементов И пер- 15 вых и вторых групп блока подключены к входам элементов ИЛИ первой, второй группы соответственно, Р-е () k - максимально возможное число свободных объемов памяти), входы первой, 20 второй.групп входов коммутатора соединены с вторыми входами элементов И пердых групп С-х пар блока (С CTTCg,

С (k-i)H-l, C, S(k-i)) и с Бто- ,

25 рыми входами элементов И вторых групп пар блока Р-1-Е,,

В . (k-i)+B,, В, 1,Р-1),

30

М+1-Й выход элемента задержки (k-i) соединен с третьим

коммутатора. S 61

ffj

18

LJ-I 19

Изобретение относится к области вычислительной техники, в частности к устройствам управления ЦВМ, и может быть использовано для построения устройств распределения памяти в вы- числительных комплексах. Целью изобретения является расширение области использования за счет работы с блоками памяти, объем каждого из которых меньше требуемого. Устройство содержит группу 1 элементов сравнения, блок 2 элементов сравнения, дешифратор 3, регистр 4, шифратор 5, первый элемент И 6, элемент 7 задержки, элемент ИЛИ 8, блок 9 групп элементов И, второй элемент И 10, группу 11 элементов И, группу 12 блоков элементов И, группу 13 элементов ИЛИ, блок 14 объединения. Имеющийся в устройстве блок 14 объединения позволяет, выделить под запрос требуемый объем памяти путем объединения пары свободных массивов. 2 з.п. ф-лы, 3 ил. с J11dT92t 25Z6Z12m 6 И ШИП го 15 фиг.1