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

 

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

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

СОЦИАЛИСТИЧЕСКИ)(РЕСПУБЛИН (19) (11) А1 (5)) 4 С 06 F 6/36

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3904826/24 — 24 (22) 05.06.85 (46) 23.10.86. Бюл. ¹ 39 (72) В.П.Невский (53) 681.32 (088.8) (56) Авторское свидетельство СССР № 966695, кл. G 06 F 9/36, 198 1.

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

¹ 1124300, кл. G 06 F 9/36, 1984. (54) УСТРОЙСТВО ДЛЯ ДИНАМИЧЕСКОГО

ПРЕОБРАЗОВАНИЯ АДРЕСА (57) Изобретение относится к области вычислительной техники и может быть использовано для преобразования логических адресов в физические. Целью изобретения является повышение быстродействия. Устройство содержит регистр ключа, блок ассоциативной памяти, регистр физического адреса, регистр логического адреса, мультиплексор, регистр адреса, два дешифратора, шифратор и блок переадресации. Поставленная цель достигается за счет динамического определения свободных страниц памяти без обра— щения к операционной системе. 4 ил.

1265771

10

40

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

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

На фиг ° 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. Количество m узлов равно числу ячеек блока 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 19„. На первый вход схемы 24 поступает код с регистра 27, содержащий ключ пользователя. В случае их совпадения на выходе схемы 24 воз бужден единичный сигнал. Аналогич.— но, в случае совпадения индекса страницы из регистра 4 логического адреса с содержимым регистра 28, на выходе схемы 25 сравнения также возбужден единичный сигнал. Маска затребованного блока из дешифрато

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

При наличии на выходах всех схем

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

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

В случае неуспешного ассоциативного поиска на выходах всех трех схем 24 — 26 в каждом узел 19

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

И 23 возбужден единичный сигнал, который через элемент ИЛИ 18 поступает на второй управляющий вход бло- 4р ка 13. Если при неуспешном ассоциативном поиске не совпадают индексы страниц, то на втором управляющем входе блока 13 управления — нулевой сигнал. 45

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

И 43 — 43, на вторые входы которых о поступают сигналы с выхода шифратора 42.

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

Если в регистре 41 несколько раз,рядов имеют нулевое значение (соответствующие страницы памяти свободны), то на выходах элементов HF. 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

%

Сигнал с первого управляющего выхода блока 13 поступает на вход управления загрузкой блока 2 ассоциативной памяти (фиг. 2), а именно на первый вход элемента И 38, код номера свободной страницы с информационного выхода блока 13 поступает на информационный вход ассоциативной памяти, а именно на информационные входы третьей группы элементов И 36. 10

В узле 19,, в котором на первом компараторе 24 совпали коды ключей пользователя, сигнал совпадения единично го уровня поступает на второй вход элемента И 38, Сигналы нулевого уров- 15 ня о несовпадении индекса страниц и маски блоков с выходов схем 25 и 26 соответственно поступают на элементы НЕ 39 и 40. Сигналы единичного уровня с выходов элементов НЕ 39 20 и 40 через элемент ИЛИ 37 поступают на третий вход элемента И 38, на выходе которого возбуждается сигнал единичного уровня, который поступает на управляющие входы первой 34, второй 35 и третьей 36 групп элементов И, разрешая передачу информации.

Через первую 34 группу элементов И передается индекс страницы с регистра 4 логического адреса, через вто- 30 рую 35 группу элементов И вЂ” маска блока из первого дешифратора 9, через третью группу 36 элементов И вЂ” . код номера свободной страницы. С выходов групп 34 — 36 элементов И указанная информация через группы элементов ИЛИ 31-33 соответственно передает индекс страницы в регистр 28, маску блока — в регистр 29, номер страницы реальной памяти — в регистр 40

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

На выходах схем 24 - 26 возбуждаются сигналы совпадения единичного уровня. Формируется сигнал еди- 50 ничного уровня на выходе элемента И

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

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

43, поступает на первые входы элементов И 46 и 47, где разрешает формирование сигналов на втором и третьем управляющих выходах блока t3. Выход элемента И 46 является вторым, а выход элемента И 47 третьим управляющими выходами блока управления-.

В том случае, когда не совпали только маски блока, сигналы единичного уровня формируются как на втором, так и на третьем выходах блока 13.

При отсутствии страницы на третьем выходе - единичный сигнал, а на втором выходе — нулевой.

Второй выход блока 13 является выходом 14 устройства, а третий— выходом 15. Единичный сигнал на выходе 15 устройства означает, что необходимо изменить содержимое àññoциативной памяти при участии операционной системы. Вычислительный процесс прерывается, и осуществляется загрузка ассоциативной памяти с использованием входа 12 загрузки. 3агружаемая информация поступает на второй вход элемента И 20 в каждом узле 1< -19 . Если -я шина с выход 4 Щ да второго дешифратора 7 имеет единичный сигнал, то, следовательно, только в -м узле 19 загружаемая ин-. формация, пройдя через элемент И 20, поступает на входы групп элементов

ИЛИ 31 — 33, а с их выхода — в соответствующие регистры. Загрузка ассоциативной памяти происходит по адресу, хранящемуся в регистре 6 апреса (фиг ° 1). Адрес ячейки ассоциативной памяти поступает либо с входа 12,, либо с шифратора 8, когда обнаруживается, что нет только тре- буемого блока, а страница выделена пользователю. В соответствии со зна1265771 чением сигнала на первом управляющем выходе 14 устройства загружается либо только измененная маска блока, либо информация о местонахождении требуемой страницы и блока в реальной памяти. При необходимости может осуществляться перераспределение реальной памяти.

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

1О

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

Устройство для динамического преобразования адреса, содержащее регистр ключа, блок ассоциативной,памяти, регистр физического адреса, регистр логического адреса, мультиплексор, регистр адреса, вход загрузки устройства подключен к информационному входу регистра ключа, информационному входу блока ассоциативной памяти и к первому информационному входу мультиплексора, выход 30 которого через регистр адреса подключен к входу первого дешифратора, выход которого подключен х адресному входу блока ассоциативной памяти, адресный выход которого через шифратор подключен к второму информационному входу мультиплексора, выход регистра ключа подключен к входу задания ключа блока ассоциативной памяти, информационный выход которого 40 подключен к старшим разрядам информационного входа регистра физическо: го адреса, выход которого подключен к выходу физического адреса устройства, выходы индекса страницы и но- 4 мера блока и байта регистра логического адреса подключены соответственяо к входу индекса страницы блока ассоциативной памяти и к младшим разрядам информационного входа регистра физического адреса, выход индекса блока памяти регистра логического адреса через второй дешифратор подключен к входу маски блока ассоциативной памяти, вход логического адреса устройства подключен к информационному входу регистра логического адреса, о т л и.ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введен блок переадресации, содержащий регистр занятости страниц, шифратор приоритета, группу элементов И, шифратор номера страниц памяти, элемент НЕ, два элемента, И, группу элементов задержки и группу элементов ИЛИ, причем К вЂ” и разряд входа загрузки устройства подключен к первому входу К-ro элемента ИЛИ группы блока переадресации (К=1, q, где и — количество страниц памяти) и к входу установки в поле" регистра занятости страниц, вход установки в "1" которого подключен к выходу К-го элемента ИЛИ группы блока переадресации, выход регистра занятости страниц подключен к входу шифратора приоритета, первый выход которого подключен к первому входу первого элемента И группы блока переадресации, выход которого подключен к первым входам первого и второго элементов И блока переадресации и через элемент НЕ блока переадресации к входу управления записью блока ассоциативной памяти, первый и второй выходы приз наков блока ассоциативной памяти подключены к вторым входам соответственно первого и второго элементов

И блока переадресации, выходы которых подключены соответственно к выходам индикации отсутствия свободных блоков памяти и свободных страниц памяти устройства, второй вход второго элемента И блока переадресации подключен к второму входу первого элемента И группы блока переадресации и к первому входу (К+!) -го элемента И группы блока переадресации, второй вход которого подключен к (К+1)-му выходу шифратора приоритета, выход (К+!)-го элемента И группы блока переадресации подключен через К-й элемент задержки группы к второму входу К-го элемента ИЛИ группы блока переадресации и к К-му входу шифратора номера страниц памяти, выход которого подключен к входу номера страниц блока ассоциативной памяти, причем блок ассоциативной памяти содержит группу элементов ИЛИ, два элемента ИЛИ и группу узлов запоминания, каждый из которых содержит пять групп элементов И, три элемента И, три схемы сравнения, четыре регистра, три группы элементов ИЛИ, 1265771

10 два элемента НЕ и элемент ИЛИ, причем выход К-го элемента И первой группы узла подключен к К-му разряду информационного входа первого регистра и к первым входам К-х элемен- 5 тов ИЛИ первой, второй и третьей групп узла, выходы которых подключены соответственно к К-м разрядам информационных входов второго, третьего и четвертого регистров, выходы регистров с первого по третий подключены соответственно к первым входам схем сравнения с первой по третью, выход К-го разряда четвертого регистра подключен к первому входу К-го 5 элемента И второй группы Р-го узла, выход которого подключен к первому входу P-го элемента ИЛИ группы блока ассоциативной памяти (Р=1,в, где rn — количество ячеек блока ас- 20 социативной памяти), выход которого подключен к р -му разряду информационного выхода блока ассоциативной памяти, выход первой схемы сравнения подключен к первым входам первого, второго и третьего элементов И узла, выход второй схемы сравнения к вторым входам второго и третьего элементов И узла и через первый элемент HE узла к первому входу элемен» 30 та ИЛИ узла, выход которого подключен к второму входу первого элемента И узла, выход которого подключен к первым входам элементов И третьей, четвертой и пятой групп узла, выхо- З5 ды К-х элементов И которых подключены соответственно к вторым входам

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

НЕ узла к второму входу элемента ИЛИ узла, выход второго элемента И узла подключен к вторым входам элементов

И второй группы узла и к P-му входу первого элемента ИЛИ блока ассоциативной памяти, выход которого подключен к первому выходу признаков блока ассоциативной памяти, выход третьего элемента И Р вЂ” го узла подключен к P-му разряду адресного выхода блока ассоциативной памяти и к Р-му входу второго элемента ИЛИ блока ассоциативной памяти, выход которого подключен к второму выходу признаков блока ассоциативной памяти, P-й выход первого дешифратора подключен к первым входам элементов И первой группы P ãî узла, второй вход К-го элемента И первой группы узла подключен к К-му разряду информационного входа блока ассоциативной памяти, третий вход первого элемента И P-ro узла подключен к входу управления записью блока ассоциативной памяти, К-й разряд второго входа третьей схемы сравнения

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

P-го узла подключен к К-му разряду входа номера страниц блока ассоциативной памяти, К-е разряды вторых входов элемента И третьей группы Pro узла и второй схемы сравнения подключены к К-му разряду входа индекса страниц блока ассоциативйой памяти, второй вход первой схемы сравнения P-ro узла подключен к входу задания ключа блока ассоциативной памяти.

j265771! 26577!

12

Составитель М.Силин

Редактор И.Николайчук Текред В.Кадар Корректор Г,Решетник

Заказ 5665/46 Тираж 671 Подписное

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

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

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