Устройство для динамического преобразования адреса Советский патент 1986 года по МПК G06F9/36 

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

Целью изобретения является повышение быстродействия устройства.

На фиг. 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. Количество w узлов равно числу ячеек блока 2 ассоциативной памяти.

Блок 13 переадресации (фиг. 3) содержит регистр 41 занятости страниц, шифратор 42 приоритета, группу 43 элементов И, шифратор 44 номера страниц памяти, элемент НЕ 45, элементы И 46 и 47, группу 48 элементо задержки и группу 49 элементов ИЛИ. Шифратор 42 приоритета содержит группу элементов НЕ 50, группу элементов И-НЕ 51, элемент И 52 и группу элементов НЕ 53. Количество элементов И в группе равно количеству страниц памяти.

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

В начале функционирования по входу 12 осуществляется занесение информации, характеризующей начальное

распределение памяти, в блок 2 памяти, регистр 1 ключа и регистр 41. Регистр 27 (фиг. 2) содержит ключ, идентифицирующий вычислительный процесс, регистр 28 - индекс страницы, регистр 29 - маску загруженньк ,а регистр 30 - реальный адрес страницы. Регистр 1 ключа предназначен для идентификации вычислительного процесса (пользователя). В случае переключения с одного процесса на другой в него заносится новый ключ, идентифицирующий новый процесс. Данная информация предназначена для. осуществления ассоциативного поиска. В регистр 41 (фиг. 3) заносится информация о занятости страниц памяти. Единичная информация в ii -м разряде означает, что -я страница занята и не подлежит перераспределению без прерывания вычислительного процесса.

Пусть реализована страничная виртуальная память, Х блоков образуют одну страницу, причем различным вычислительным процессам (пользователям) предоставляется весь объем виртуальной памяти. В ходе функционирования при обращении к виртуальной памяти логический адрес поступает на вход 10 логического адреса памяти и помещается в регистр 4 логического адреса. Индекс блока из регистра 4 поступает в дешифратор 9, на выходе которого вырабатывается маска затребованного блока. Ключ из регистра 1 ключа, индекс страницы из регистра 4 логического адреса и маска затребованного блока из дешифратора 9 поступают в блок 2 памяти, где осуществляется ;ассоциативньй поиск.

Ассоциативный поиск происходит следующим образом.

Ключ из регистра 1 ключа поступает на второй вход схемы 24 сравнения (фиг. 2) в каждом узле 19/19. На первый вход схемы 24 поступает код с регистра 27, содержащий ключ пользователя. В случае их совпадения на выходе схемы 24 воз бужден единичный сигнал. Анало гичг но, в случае совпадения индекса страницы из регистра 4 логического адреса с содержимым регистра 28, на выходе схемы 25 сравнения также возбужден единичный сигнал. Маска затребованного блока из дешифрато3

pa 9 сравнивается с маской загруженных блоков, хранящейся в регистре 29, в схеме 26 сравнения. В случае совпадения масок на выходе схемы 26 возбуждается единичный сигнал

При наличии на выходах всех схем 24 -.26 узла 19J единичных сигнало на выходе элемента И 22 имеется единичный сигнал, который разрешает передачу информации из регистра 30 через группу элементов И 21 и далее через группу элементов ИЛИ 16. в регистр 3 реального адреса,т.е. ассоциативный поиск успешен и прочитана 1-я ячейка ассоциативной памяти.

В случае успешного ассоциативног поиска на остальных выходах ассоциативной памяти (фиг. 2) единичные сигналы отсутствуют.

В случае неуспешного ассоциативного поиска на выходах всех трех схем 24-26 в каждом узел 19, 9 нет одновременно единичных сигналов . Выход элемента И 22 ни в одной группе не имеет единичного значения, поэтомз на инверсном выходе элемента ИЛИ 17 имеется единичный сигнал, который поступает на первый управляющий вход блока 13 (фиг. 1) и указывает, что при данной загрузке ассоциативной памл и преобразование адреса невозможно. Если при неуспешном ассоциативном поиске не совпадают лишь маски блока, то на выходах схем 24 и 25 - единичные сигналы, а навыходе схемы 26 нулевой сигнал. На выходе элемента И 2-3 возбужден единичный сигнал, который через элемент ИЛИ 18 поступает на второй управляюш 1й вход блока 13. Если при неуспешном ассоциативном поиске не совпадают индексы страниц, то на втором управляющем входе блока 13 управления - нулевой сигнал.

В блок 13 (фиг. 3) в случае не- . успешного поиска сигнал единичного уровня с первого управляющего входа поступает на первые входы элементов ;И 43g - 43, на вторые входы которых поступают сигналы с выхода шифратора 42.

Шифратор 42 работает следующим образом.

Если в регистре 41 несколько разрядов имеют нулевое значение (соответствующие страницы памяти свобод657714

ны), то на выходах элементов НЕ (1 - не унитарньй код. Единичный сигнал с, выхода элемента НЕ 50 с меньшим номером поступает на вход 5 соответствующего элемента И-НЕ 51, на выходе Которого формируется нулевой уровень, поступающий на первые входы,последующих элементов И-НЕ, запрещая прохождение через них еди0 ничной информации. Таким образом, на выходе элемента И-НЕ 51, соответствующего меньшему номеру разряда регистра 41 с нулевым значением, имеесся нулевой уровень, а на выхо5 дах остальных - единичный. На выходах элементов НЕ формируется унитарный код наименыиего номера страницы из числа свободных. В том случае, когда все разделы

20 регистра 41 имеют единичное значение (все страницы памяти заняты), на выходе элемента И 52 формируется единичный сигнал, указывающий на необходимость распределения памяти

с участием операционной системы.

Таким образом, при неуспешном ассоциативном поиске и наличии свободных страниц на вькоде элемента И

имеется нулевой сигнал, а на выходах элементов И 43,-43 - унитарный код свободной страницы с меньшим номером. Унитарньм код свободной страницы поступает на вход

шифратора 44, где преобразуется в двоичный позиционный. Сигнал нулевого уровня с выхода элемента И 43 поступает на вход элемента НЕ 45, на выходе которого возбуждается

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

информационном выходе - код номера первой из свободных страниц. Унитарный код с выходов элементов 43(-43 через элементы 48 ,-48, задержки (задержка равна периоду следования

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

Сигнал с первого управляющего выхода блока 13 поступает на вход управления загрузкой блока 2 ассоциативной памяти (фиг. 2), а именно на первьй вход элемента И 38, код номера свободной странищ, с информационного выхода блока 13 поступает на информационный вход ассоциативной памяти, а именно на информационные входы третьей группы элементов И 36. В узле 19;, в котором на первом компараторе 24 совпали кода ключей пользователя, сигнал совпадения единично го уровня поступает на второй вход элемента И 38. Сигналы нулевого уровня о несовпадении индекса страниц и маски блоков с выходов схем 25 и 26 соответственно поступают на элементы НЕ 39 и 40. Сигналы единичного уровня с выходов элементов НЕ 39 и 40 через элемент ИЛИ 37 поступают на третий вход элемента И 38, на выходе которого возбуждается сигнал единичного уровня, который поступает на управляющие входы первой 34, второй 35 и третьей 36 групп элементов И, разрешая передачу информации. Через первую 34 группу элементов И передается индекс страницы с регистра 4 логического адреса, через вторую 35 группу элементов И - маска блока Из первого дешифратора 9, через третью группу 36 элементов И -. код номера свободной страницы. С выходов групп 34 - 36 элементов И указанная информация через группь элементов ИЛИ 31-33 соответственно передает индекс страницы в регистр 28, маску блока - в регистр 29, номер страницьт реальной памяти - в регистр 30. Таким образом, без участия операционной системы создаются условия для успешного ассоциативного поиска по заявке пользователя, ей ключ входит в состав списка разрешенных (совпадает с кодом регистра ключа 1 ).

На выходах схем 24 - 26 возбуждаются сигналы совпадения единичного уровня. Формируется сигнал единичного уровня на выходе элемента И 22, разрешакяций вьщачу номера страницы из регистра 30 через группу элементов И 21. Номер страницы через группу элементов ИЛИ 16 передается в регистр 3, в него же из регистра 4 логического адреса поступает также номер блока и номер байта, образуя реальный адрес, который поступает на выход 11 устройства. Таким образом, осуществляется динамическое преобразование адреса. Ееи при неуспешном ассоциативном поиске свободные страницы отсутствуют, сигнал нулевого уровня с первого управляющего выхода блока 13 поступает на вход управления загрузкой

блока 9 ассоциативной памяти (а именно на первый вход элемента И 38) и запрещает изменение содержимого блока 2 ассоциативной памяти без участия операционной системы. Кроме

Того, в блоке (фиг. 3) сигнал единичного уровня с выхода элемента И 43 О) поступает на первые входы элементов И 46 и 47, где разрешает формирование сигналов на втором и третьем управляющих выходах блока 1-3. Выход элемента И 46 является вторым, а выход элемента И 47 третьим управляющими выходами блока управления, В том случае, когда не совпали только маски блока, сигналы единичного уровня формируются как на втором, так и на третьем выходах блока 13. При отсутствии страницы на третьем выходе - единичный сигнал, -а на

втором выходе - нулевой.

Второй выход блока 13 является выходом 14 устройства, а третий выходом 15. Единичный сигнал на выходе 15 устройства означает, что не

обходимо изменить содержимое ассоциативной памяти при участии операционной системы. Вычислительный процесс прерывается, и осуществляется загрузка ассоциативной памяти с использованием входа 12 загрузки. Загружаемая информация поступает на второй вход элемента И 20 в каждом узле . Если i -я шина с вьпсода второго дешифратора 7 имеет е щничный сигнал, то, следовательно, только в 1-м узле 19 загружаемая ий-. формахдая, пройдя через элемент И 20, поступает на входы групп элементов ШЮ 31 -33, ас их вькода - в соответствуюш 1е регистры. Загрузка ассоциативной памяти происходит по адресу, хранящемуся в регистре 6 адреса (фиг. 1). Адрес ячейки ассоциативной памяти поступает либо с вхо

да 12., либо с шифратора В, когда обнаруживается, что нет только требуемого блока, а страница выделена пользователю. В соответствии со зна7

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

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

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

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

657718

тем, что, с целью повышения быстродействия, в него введен блок переадресации, содержащий регистр занятости страниц, шифратор приоритета, 5 группу элементов И, шифратор номера страниц памяти, элемент НЕ, два элемента, И, группу элементов задержки и группу элементов ИЛИ, причем К-й разряд входа загрузки устройства О подключен к первому входу К-го элемента ИЛИ группы блока переадресации (,h , где п- количество страниц памяти) и к входу установки в поле регистра занятости страниц, 5 вход установки в 1 которого подключен к выходу К-го элемента ИЛИ группы блока переадресации, выход регистра занятости страниц подключен к входу шифратора приоритета, 20 первый вькод которого подключен к первому входу первого элемента И группы блока переадресации, выход которого подключен к первым входам первого и второго элементов И блока 25 переадресации и через элемент НЕ блока переадресации к входу управления записью блока ассоциативной памяти, первьй и второй выходы признаков блока ассоциативной памяти 0 подключены к вторым входам соответственно первого и второго элементов И блока переадресации, выходы которых подключены соответственно к выходам индикации отсутствия свобод5 ных блоков памяти и свободных страниц памяти устройства, второй вход второго элемента И блока переадресации подключен к второму входу пер вого элемента И группы блока пере0 адресации и к первому входу (К+1)-гв элемента И группы блока переадреса.ции, второй вход которого подключен к (К+1)-му выходу шифратора приоритета, выход (K+D-ro элемента И груп 5 пы блока переадресации подключен через К-й элемент задержки группы к второму входу элемента ИЛИ группы блока переадресации и к К-му входу шифратора номера страниц памяти, 0 выход которого подключен к входу номера страниц блока ассоциативной памяти, причем блок ассоциативной памяти содержит группу элементов ИЛИ, два элемента ЮШ и группу узлов за5 поминания, каждый из которых содержит пять групп элементов И, три элемента И, три схемы сравнения, четыре регистра, три группы элементов ИЛИ, два элемента НЕ и элемент ИЛИ, причем выход К-го элемента И первой группы узла подключен к К-му разряду информационного входа первого регистра и к первым входам К-х элементов ИЛИ первой, второй и третьей групп узла, выходы которых подключены соответственне к К-м разрядам информационных входов второго, третьего и четвертого регистров, выходы регистров с первого по третий подклю чены соответственно к первым входам схем сравнения с первой по третью, выход К-го разряда четвертого регистра подключен к первому входу К-го элемента И второй группы Р-го узла, выход которого подключен к первому входу Р-го элемента ИЛИ группы блока ассоциативной памяти (,т, где m - количество ячеек блока ассоциативной памяти), выход которого подключен к р-му разряду информационного выхода блока ассоциативной памяти, выход первой схемы сравнения подключен к первым входам первого, второго и третьего элементов узла, выход второй схемы сравнения к вторым входам второго и третьего элементов И узла и через первый эле мент НЕ узла к первому входу элеме та ИЛИ узла, выход -которого подключен к второму входу первого элемента И узла, выход которого подключен к первым входам элементов И третьей четвертой и пятой групп узла, выходы К-х элементов И которых подключе ны соответственно к вторым входам К-х элементов ИЛИ первой, второй и третьей групп узла, третьей схемы сравнения подключен к третьим входам второго и третьего элементов И узла и через второй элемент НЕ узла к второму входу элемента ИЛИ узла, выход второго элемента И узла подключен к вторым входам элементов И второй группы узла и к Р-му входу первого элемента ИЛИ блока ассоциативной памяти, выход которого подключен к первому выходу признаков блока ассоциативной памяти, выход третьего элемента И Р-го узла подключен к Р-му разряду адресного выхода блока ассоциативной памяти и к Р-му входу второго элемента РШИ блока ассоциативной памяти, выход которого подключен к второму вых.оду признаков блока ассоциативной памяти, Р-й выход первого дешифратора подключен к первым входам элементов И первой группы Р-го узла, второй вход К-го элемента И первой гругьпы узла подключен к К-му разряду информационного входа блока ассоциативной памяти, третий вход первого элемента И Р-го узла подключен к входу управления записью блока ассоциативной памяти, К-й разряд второго входа третьей схемы сравнения Р-го узла подключен к К-му разряду входа маски блока ассоциативной памяти и к второму входу К-го элемента И четвертой группы узла, второй вход К-го элемента И пятой группы Р-го узла подключен к К-му разряду входа номера страниц блока ассоциативной памяти, К-е разряды вторых входов элемента И третьей группы Рго узла и второй схемы сравнения подключены к К-му разряду входа индекса страниц блока ассоциативной памяти, второй вход первой схемы сравнения Р-го узла подключен к входу задания ключа блока ассоциативной памяти.

45 t4 1

Фие.2

Изобретение относится к области вычислительной техники и может быть использовано для преобразования логических адресов в физические. Целью изобретения является повышение быстродействия . Устройство содержит регистр ключа, блок ассоциативной памяти, регистр физического адреса, регистр логического адреса, мультиплексор, регистр адреса, два дешифратора, шифратор и блок переадресации. Поставленная цель достигается за счет динамического определения свободных страниц памяти без обращения к операционной системе. 4 ил.