Устройство для динамического преобразования адреса

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИН А 50 4 С 06 Г 6 ТЕНИЯ ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПЭ ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ ОПИСАНИЕ АВТОРСКОМУ СВИДЕТЕЛЬСТВ(54) УСТРОЙСТВО ДЛЯ ДИНАМИЧЕСКОГОПРЕОБРАЗОВАНИЯ АДРЕСА(57) Изобретение относится к областивычислительной техники и может быть использовано для преобразования логических адресов в физические. Цель изобретения является повышение быст родействия. Устройство содержит регистр ключа, блок ассоциативной памяти, регистр физического адреса, регистр логического адреса, мультиплексор, регистр адреса, два дешифратора, шифратор и блок переадресации. Поставленная цель достигается за счет динамического определения свободных страниц памяти без обращения к операционной системе. 4 ил.510 15 20 25 30 35 40 45 50 55 Изобретение относится к вычислительной технике и предназначено для преобразования логических адресов в физические.Целью изобретения является повышение быстродействия устройства.На фиг1 приведена функциональная схема устройства на фиг. 2 функциональная схема блока ассоциативной памяти; на фиг. 3 - функциональная схема блока переадресации, на фиг. 4 - функциональная схема шифратора приоритета.Устройство содержит регистр 1 ключа, блок 2 ассоциативной памяти, регистр 3 физического адреса, регистр 4 логического адреса, мультиплексор 5, регистр 6 адреса, дешифратор 7, шифратор 8, дешифратор 9, вход 10 логического адреса устройства, выход 11 физического адреса устройства, вход 12 загрузки устройства, блок 13 переадресации, выходы 14 и 15 индикации соответственно отсутствия свободных блоков памяти и отсутствия свободных страниц памяти устройства.Блок 2 ассоциативной памяти (фиг. 2) содержит группу 16 элементов ИЛИ, элементы ИЛИ 17 и 18, группу узлов 19 запоминания, каждый из которых содержит группы 20 и 21 элементов И, элементы И 22 и 23, схемы 24 - 26 сравнения, регистры 27 - 30, группы 31 - 33 элементов ИЛИ, группы 34 - 36 элементов И, элемент ИЛИ 37, элемент И 38, элементы НЕ 39 и 40, Количество е узлов равно числу ячеек блока 2 ассоциативной памяти.Блок 13 переадресации (фиг. 3) содержит регистр 41 занятости страниц, шифратор 42 приоритета, группу 43 элементов И, шифратор 44 номера страниц памяти, элемент НЕ 45, элементы И 46 и 47, группу 48 элементов задержки и группу 49 элементов ИЛИ.Шифратор 42 приоритета содержит группу элементов НЕ 50, группу элементов И-НЕ 5 1, элемент И 52 и группу элементов НЕ 53. Количество элементов п в группе равно количеству страниц памяти.Устройство работает следующим образом.В начале функционирования по входу 12 осуществляется занесение информации, характеризующей начальное распределение памяти, в блок 2 памяти, регистр 1 ключа и регистр 41.Регистр 27 (фиг, 2) содержит ключ,идентифицирующий вычислительный процесс, регистр 28 - индекс страницы,регистр 29 - маску загруженных бло ков,а регистр 30 - реальный адресстраницы. Регистр 1 ключа предназначен для идентификации вычислительного процесса (пользователя). В случаепереключения с одного процесса надругой в него заносится новый ключ,идентифицирующий новый процесс. Данная информация предназначена для осуществления ассоциативного поиска. В регистр 4 1 (фиг. 3) заноситсяинформация о занятости страниц памяти, Единичная информация в к -мразряде означает, что 1 -я страница занята и не подлежит перераспределению без прерывания вычислительного процесса.Пусть реализована страничная виртуальная память, К- блоков образуют одну страницу, причем различным вычислительным процессам (пользователям) предоставляется весь объем виртуальной памяти. В ходе функционирования при обращении к виртуальной памяти логический адрес поступает на вход 10 логического адреса памяти и помещается в регистр 4логического адреса, Индекс блока изрегистра 4 поступает в дешифратор9, на выходе которого вырабатываетсяМаска затребованного блока. Ключ изрегистра 1 ключа, индекс страницыиз регистра 4 логического адреса имаска затребованного блока из дешифратора 9 поступают в блок 2 памяти, где осуществляется .ассоциативный поиск. Ассоциативный поиск происходитоследующим образом.Ключ из регистра 1 ключа поступает на второй вход схемы 24. сравнения (фиг. 2) в каждом узле 19 г, На первый вход схемы 24 поступает код с регистра 27, содержащий ключ пользователя. В случае их совпадения на выходе схемы 24 воз бужден единичный сигнал. Аналогич; но, в случае совпадения индекса страницы из регистра 4 логического адреса с содержимым регистра 28, на выходе схемы 25 сравнения также возбужден единичный сигнал. Маска затребованного блока из дешифратора 9 сравнивается с маской загруженных блоков, хранящейся в регистре 29, в схеме 26 сравнения. В случае совпадения масок на выходе схемы 26 возбуждается единичный сигнал. 5При наличии на выходах всех схем 24 - 26 узла 19; единичных сигналов на выходе элемента И 22 имеется единичный сигнал, который разрешает передачу информации из регистра 30 , 0 через группу элементов И 21 и далее через группу элементов ИЛИ 16 в регистр 3 реального адреса,т.е. ассоциативный поиск успешен и прочитана -я ячейка ассоциативной памяти. 15В случае успешного ассоциативного поиска на остальных выходах ассоциативной памяти (фиг. 2) единичныесигналы отсутствуют.В случае неуспешного ассоциативного поиска на выходах всех трехсхем 24 - 26 в каждом узел 199 нет одновременно единичных сигналов. Выход элемента И 22 ни в одной группе не имеет единичного зна -чения, поэтому на инверсном выходеэлемента ИЛИ 17 имеется единичныйсигнал, который поступает на первыйуправляющий вход блока 13 (фиг. 1)и указывает, что при данной загрузке ассоциативной памяти преобразование адреса невозможно. Если принеуспешном ассоциативном поиске несовпадают лишь маски блока, то навыходах схем 24 и 25 - единичныесигналы, а навыходе схемы 26нулевой сигнал. На выходе элементаИ 23 возбужден единичный сигнал,который через элемент ИЛИ 18 поступает на второй управляющий вход бло Ока 13, Если при неуспешном ассоциативном поиске не совпадают индексыстраниц, то на втором управляющемвходе блока 13 управления - нулевойсигнал. 45В блок 13 (фиг. 3) в случае неуспешного поиска сигнал единичногоуровня с первого управляющего входапоступает на первые входы элементовИ 43- 43, на вторые входы которых опоступают сигналы с выхода шифратора 42,Шифратор 42 работает следующим образом.55Если в регистре 41 несколько раз,рядов имеют нулевое значение (соответствующие страницы памяти свободны), то на выходах элементов НЕ 50- 50 и - не унитарный код. Единичный сигнал с выхода элемента НЕ 50 сменьшим номером поступает на вход соответствующего элемента И-НЕ 5 1, на выходе которого формируется нуле. вой уровень, поступающий на первые входы. последующих элементов И-НЕ, запрещая прохождение через них единичной информации. Таким образом, на выходе элемента И-НЕ 5 1, соответствующего меньшему номеру разряда регистра 41 с нулевым значением, имеется нулевой уровень, а на выходах остальных - единичный. На выходах элементов НЕ 53-53 формируется унитарный код наименьшего номера страницы из числа свободных.В том случае, когда все разделы регистра 41 имеют единичное значение (все страницы памяти заняты), на выходе элемента И 52 формируется единичный сигнал, указывающий на необходимость распределения памяти с участием операционной системы.(Таким образом, при неуспешном ассоциативном поиске и наличии свободных страниц на выходе элемента И 43 имеется нулевой сигнал, а на выходах элементов И 43,-43- унитарный код свободной страницы с меньшим номером, Унитарный коц свободной страницы поступает на вход шифратора 44, где преобразуется в двоичный позиционный, Сигнал нулевого уровня с выхода элемента И 43 поступает на вход элемента НЕ 45, на выходе которого возбуждается сигнал единичного уровня. На первом управляющем выходе блока управления - сигнал единичного уровня, разрешающий изменение информации в регистрах ассоциативной памяти, а на информационном выходе - код номера первой из свободных страниц. Унитарный код с выходов элементов 43-43 через элементы 48 -48задержки (задержка равна периоду следования логических адресов по входу 10) и через элементы ИЛИ 49 -49 ц поступает на единичные входы триггеров регистра 4 1 занятссти страниц.Разряд, соответствующий первой из свободных страниц, переводится из нулевого в единичное состояние, и впредь данная страница считается занятой.12657 25 5Сигнал с первого управляющего выхода блока 13 поступает на вход управления загрузкой блока 2 ассоциативной памяти (фиг. 2), а именно на первый вход элемента И 38, код номера свободной страницы с информационного выхода блока 13 поступает на информационный вход ассоциативной памяти, а именно на информационные входы третьей группы элементов И 36. 10 В узле 19 в котором на первом компараторе 24 совпали коды ключей пользователя, сигнал совпадения единично го уровня поступает на второй вход элемента И 38, Сигналы нулевого уров ня о несовпадении индекса страниц и маски блоков с выходов схем 25 и 26 соответственно поступают на элементы НЕ 39 и 40, Сигналы единичного уровня с выходов элементов НЕ 39 20 и 40 через элемент ИЛИ 37 поступают на третий вход элемента И 38, на выходе которого возбуждается сигнал единичного уровня, который поступает на управляющие входы первой 34, второй 35 и третьей 36 групп элементов И, разрешая передачу информации. Через первую 34 группу элементов И передается индекс страницы с регистра 4 логического адреса, через вто рую 35 группу элементов И - маска блока из первого дешифратора 9, через третью группу 36 элементов И - .код номера свободной страницы. С выходов групп 34 - 36 элементов И ука- з 5 занная информация через группы элементов ИЛИ 31-33 соответственно передает индекс страницы в регистр 28, маску блока - в регистр 29, номер страницы реальной памяти - в регистр 40 30, Таким образом, без участия операционной системы создаются условия для успешного ассоциативного поиска по заявке пользователя, 1 ей ключ входит в состав списка разрешенных 45 (совпадает с кодом регистра ключа 1).На выходах схем 24 - 26 возбуждаются сигналы совпадения единичного уровня. формируется сигнал еди ничного уровня на выходе элемента И 22, разрешающий выдачу номера страницы из регистра 30 через группу элементов И 21, Номер страницы через группу элементов ИЛИ 16 переда ется в регистр 3, в него же из регистра 4 логического адреса поступает также номер блока и номер байта, образуя реальный адрес, который поступает на выход 11 устройства. Таким образом, осуществляется динамическое преобразование адреса. Если при неуспешном ассоциативном поиске свободные страницы отсутствуют, сигнал нулевого уровня с первого управляющего выхода блока 13 поступает на вход управления загрузкой блока 9 ассоциативной памяти (а именьно на первый вход элемента И 38) и запрещает изменение содержимого блока 2 ассоциативной памяти без участия огерацианной системы. Кроме того, в блоке (фиг. 3) сигнал единичного уровня с выхода элемента И 43 р поступает на первые входы элементов И 46 и 47, где разрешает формирование сигналов на втором и третьем управляющих выходах блока 13. Выход элемента И 46 является вторым, а выход элемента И 47 третьим управляющими выходами блока управления. В том случае, когда не совпали только маски блока, сигналы единичного уровня формируются как на втором, так и на третьем выходах блока 13. При отсутствии страницы на третьем выходе - единичный сигнал, а на втором выходе - нулевой.Второй выход блока 13 является выходом 14 устройства, а третий - выходом 15. Единичный сигнал на выходе 15 устройства означает, что необходимо изменить содержимое ассоциативной памяти при участии операционной системы. Вычислительный процесс прерывается, и осуществляется загрузка ассоциативной памяти с использованием входа 12 загрузки. Загружаемая информация поступает на второй вход элемента И 20 в каждом узле 1 ч -19 . Если-я шина с выход 4 Щфда второго дешифратора 7 имеет единичный сигнал, то, следовательно, только в-м узле 19 загружаемая ин-. формация, пройдя через элемент И 20, поступает на входы групп элементов ИЛИ 31 - 33, а с их выхода - в соответствующие регистры. Загрузка ассоциативной памяти происходит по адресу, хранящемуся в регистре 6 апреса (фиг1). Адрес ячейки ассоциативной памяти поступает либо с входа 12 либо с шифратора 8, когда обнаруживается, что нет только тре" буемого блока, а страница выделена пользователю. В соответствии со значением сигнала на первом управляющем выходе 14 устройства загружается либо только измененная маска блока, либо информация о местонахождении требуемой страницы и блока в реальной памяти. При необходимости может осуществляться перераспределение реальной памяти.Таким образом, предлагаемое устройство обеспечивает динамическое преобразование адреса как при успешном ассоциативном поиске, так и в случае неуспешного ассоциативного поиска при наличии свободных страниц реальной памяти, без. прерывания вычислительного процесса. 1 О Формула изобретения Устройство для динамического пре образования адреса, содержащее регистр ключа, блок ассоциативной,памяти, регистр физического адреса, регистр логического адреса, мультиплексор, регистр адреса, вход загрузки устройства подключен к информационному входу регистра ключа, информационному входу блока ассоциативной памяти и к первому информационному входу мультиплексора, выход 30 которого через регист 1 адреса подключен к входу первого дешифратора, выход которого подключен х адресному входу блока ассоциативной памяти, адресный выход которого через шифратор подключен к второму информационному входу мультиплексора, выход регистра ключа подключен к входу задания ключа блока ассоциативной памяти, информационный выход которого 40 подключен к старшим разрядам информационного входа регистра физического адреса, выход которого подключен к выходу Физического адреса устройства, выходы индекса страницы и но мера блока и байта регистра логического адреса подключены соответственяо к входу индекса страницы блока ассоциативной памяти и к младшим разрядам информационного входа регистра Физического адреса, выход индекса блока памяти регистра логического адреса через второй дешифратор подключен к входу маски блока ассоциативной памяти, вход логического ад- у реса устройства подключен к информационному входу регистра логического адреса, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введен блок переадресации, содержащий регистр занятости страниц, шифратор приоритета,группу элементов И, шифратор номерастраниц памяти, элемент НЕ, два элемента, И, группу элементов задержкии группу элементов ИЛИ, причем К-йразряд входа загрузки устройстваподключен к первому входу К-го элемента ИЛИ группы блока переадресации (К=1, ь, где О - количествостраниц памяти) и к входу установкив поле" регистра занятости страниц,вход установки в "1" которого подключен к выходу К-го элемента ИЛИгруппы блока переадресации, выходрегистра занятости страниц подключен к входу шифратора приоритета,первый выход которого подключен кпервому входу первого элемента Игруппы блока переадресации, выходкоторого подключен к первым входампервого и второго элементов И блокапереадресации и через элемент НЕблока переадресации к входу управления записью блока ассоциативнойпамяти, первый и второй выходы признаков блока ассоциативной памятиподключены к вторым входам соответственно первого и второго элементовИ блока переадресации, выходы которых подключены соответственно к выходам индикации отсутствия свободных блоков памяти и свободных страниц памяти устройства, второй входвторого элемента И блока переадресации подключен к второму входу первого элемента И группы блока переадресации и к первому входу (К+1) -гоэлемента И группы блока переадресации, второй вход которого подключенк (К+1)-му выходу шифратора приоритета, выход (К+1)-го элемента И группы блока переадресации подключенчерез К-й элемент задержки группы квторому входу К-го элемента ИЛИ группы блока переадресации и к К-му входу шифратора номера страниц памяти,выход которого подключен к входуномера страниц блока ассоциативнойпамяти, причем блок ассоциативнойпамяти содержит группу элементов ИЛИ,два элемента ИЛИ и группу узлов запоминания, каждый из которых содержит пять групп элементов И, три элемента И, три схемы сравнения, четыререгистра, три группы элементов ИЛИ, 1265771два элемента НЕ и элемент ИЛИ, причем выход К-го элемента И первойгруппы узла подключен к К-му разрядуинформационного входа первого регистра и к первым входам К-х элементов ИЛИ первой, второй и третьейгрупп узла, выходы которых подключены соответственно к К-м разрядам информационных входов второго, третьего и четвертого регистров, выходы 1 Орегистров с первого по третий подключены соответственно к первым входамсхем сравнения с первой по третью,выход К-го разряда четвертого регистра подключен к первому входу К-го 15элемента И второй группы Р-го узла, выход которого подключен к первому входу Р-го элемента ИЛИ группыблока ассоциативной памяти (Р=1,й,где й - количество ячеек блока ассоциативной памяти), выход которогоподключен к-му разряду информационного выхода блока ассоциативнойпамяти, выход первой схемы сравнения подключен к первым входам первого, второго и третьего элементов Иузла, выход второй схемы сравненияк вторым входам второго и третьегоэлементов И узла и через первый элемент НЕ узла к первому входу элемен 30та ИЛИ узла, выход которого подключен к второму входу первого элемента И узла, выход которого подключенк первым входам элементов И третьей,четвертой и пятой групп узла, выхо- З 5ды К-х элементов И которых подключены соответственно к вторым входамК-х элементов ИЛИ первой, второй итретьей групп узла, выход третьейсхемы сравнения подключен к третьимвходам второго и третьего элементов И узла и через второй элемент НЕ узла к второму входу элемента ИЛИузла, выход второго элемента И узлаподключен к вторым входам элементовИ второй группы узла и к Р-му входупервого элемента ИЛИ блока ассоциативной памяти, выход которого подключен к первому выходу признаковблока ассоциативной памяти, выходтретьего элемента И Р-го узла подключен к Р-му разряду адресного выхода блока ассоциативной памяти ик Р-му входу второго элемента ИЛИблока ассоциативной памяти, выходкоторого подключен к второму выходупризнаков блока ассоциативной памяти, Р-й выход первого дешифратораподключен к первым входам элементов И первой группы Р-го узла, второй вход К-го элемента И первой группы узла подключен к К-му разрядуинформационного входа блока ассоциативной памяти, третий вход первогоэлемента И Р-го узла подключен квходу управления записью блока ассоциативной памяти, К-й разряд второго входа третьей схемы сравненияР-го узла подключен к К-му разрядувхода маски блока ассоциативной памяти и к второму входу К-го элемента И четвертой группы узла, второйвход К-го элемента И пятой группыР-го узла подключен к К-му разрядувхода номера страниц блока ассоциативной памяти, К-е разряды вторыхвходов элемента И третьей группы Рго узла и второй схемы сравненияподключены к К-му разряду входа индекса страниц блока ассоциативйойпамяти, второй вход первой схемысравнения Р-го узла подключен квходу задания ключа блока ассоциативной памяти.265771 12 Составитель М.Ситор И.Николайчук Текред В,Кадар тор Г,Решетник Тираж 67 Подписиомитета СССРоткрытий Заказ 4/5 ская н иятие,оизводственно-полиграфическое 65/46 ВНИИПИ Го по дела 113035, Мос