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

 

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВМДЕТЕЛЬСТВУ

Союз Советских

Социапистических

Республик ())) 903878 (61) Дополнительное к авт. свид-ву (22)Заявлено 10.01.80 (21) 28?1683/ 18-24 с присоеяинение)и заявки М (23) Приоритет

Опубликовано 07.02.82. бюллетень М5

Дата опубликования описания 07, 02,82 (5I)M. Кл.

G 06 F 9/36

Госудврстванньн1 квинтет

СССР

40 делаи нзвбретеиий и открытий (53) УДК 681.325 (088.8) (72) Авторы изобретения

Г.П.Лопато, В.Н.Заблоцкий и Б.В.Це (7I) Заявитель (54) УСТРОЙСТВО ДЛЯ ДИНАИИЧЕСКОГО

ПРЕОБРАЗОВАНИЯ АДРЕСОВ

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

Из дескрипторных регистров, в которые операционная система помещает соответствия между физическими и математическими номерами страниц.

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

Математический номер страницы в адресе представляет собой фактически номер дескрипторного регистра, который должен быть использован при формировании исполнительного адреса. Информация, хранящаяся в дескрипторных регистрах — это физические номера страниц. Для определения физического адреса производится дешифрированне математического номера страницы. Выбирается соответствующий дескрипторный регистр, содержимое которого определяет соответствующий физический адрес ).11 °

Недостатком являются большие

10 затраты на оборудование для реализации дескрипторных регистров. Поэтому такое выполнение аппаратуры преобразования применимо только в системах с очень малым количеством

15 математических страниц.

Наиболее близким к предлагаемому по технической сущности и достигаемому результату является устройство для динамического преобразования адресов, содержащее регистры логического и физического адресов, памяти ключей защиты, битов обращения и битов изменения, схему сравнения, 90387 элемент И, элемент ИЛИ, группу элементов И„ ассоциативные регистры, регистр управления и блок местного управления (2).

Однако устройство имеет бопьшое число страничных прерываний, обусловленное их зависимостью о- числа ассоциативных регистров, количество которых мало по сравнен:.ю с объемом оперативной памяти :.ычислительной системы, низкую скорость работы вследствие того, что поиск замещаемой страницы производит:, .. управляющей программой после обра.— ботки таблиц сегментов и таблиц стра- 1 ниц.

Цель изобретения — сокращение числа страничных прерываний и повышение скорости работы устройства.

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

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

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

И соединен с информационным входом памяти битов обращения, группа yv

8 4 равляющих входов регистра физического адреса и управляющие входы бло-. ка памяти страниц, памяти ключей защиты, второй вход первого и первый и второй входы второго элементов И, второй вход блока элементов И, второй вход элемента ИЛИ и управляющий вход памяти битов обращения соединены соответственно с первой группой выходов и с первым, вторым, третьим и четвертым выходами блока местного управления, пятый выход которого соединен с управляющим входом блока памяти страниц, выходы первой, второй и третьей схем сравнения, памятей битов обращения и изменения и тактовый вход устройства соединены соответственно с первого по шестой входами блока местного управления, группа разрядных выходов управляющего регистра соединена с группой входов блока местного управления, введены генератор расстановки блок памяти страниц и коммутатор, причем вход генератора расстановки и вход старших информационных разрядов блока памяти страниц соединены с выходом регистра логического адреса, а выход генератора расстановки соединен с первым входом коммутатора, вторым входом регистра физического адреса и с адресным входом блока памяти страниц, вход младших информационных разрядов которого соединен с адресным входом устройства, выходы старших и младших разрядов блока памяти страниц соединены соответственно са вторым входом второй схемы сравнения и с третьим входом регистра физического адреса, выход регистра физического адреса соединен со вторым входом коммутатора, выход которого соединен с адресным входом памяти битов обращения, шестой выход и вторая, третья группы выходов блока местного управления соединены с управляющим входом буферного регистра 1f группами управлякпцих входов г."нератора расстановки коммута o;.".- :çäüìoé и восьмой выходы бло.. .. битного управления являются сañ:::.å:..-::=.анно первым и вторым выходами, рерываний устройства.

Нр»- этом генератор расстановки содеряыт блок элементов ИСКЗПОЧА10ШЕЕ ИГИ, первый, второй регистры, коммутатор и генератор псевдослу5 903878 6 чайных чисел, причем вход блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с входом генератора расстановки, выход блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с первыми входами коммутатора и регистров, выход первого из которых соединен со вторым входом коммутатора, а выход второго регистра соединен со вторым входом первого регистра, третьим входом коммутатора и входом генератора псевдослучайных чисел, выход которого соединен со вторым входом второго регистра, управляющие входы регистров и коммутатора соединены ,с группой управляющих входов генератора расстановки, а выход коммутатора является выходом генератора расстановки.

15

25

55

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

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

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

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

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

ИЛИ соединен с выходом тринадцатого элемента И, первый вход шестого элемента ИЛИ и второй вход пятого элемента ИЛИ соединены с выходом ;. первого элемента И, выходы четырнадцатого и пятнадцатого элементов

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

7 90 динены с выходом одиннадцатого элемента И, выход восьмого элемента

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

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

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

И соецинен с восьмым выходом блока.

Иа фиг. 1 приведена структурная схема устройства для динамического преобразования адресов; на фиг. 2 — функциональная схема генератора расстановки; на фиг. 3 — то же, местного блока управления.

Устройство для динамического преобразования адресов (фиг. 1) содер-. жит регистр 1 логического адреса, регистр 2 физического адреса, буферный регистр 3, память 4 ключей защиты, схемы 5-7 сравнения, память

8 битов изменения, память 9 битов обращения, элементы И 10 и 11, элемент ИЛИ 12, блок элементов И 13, управляющий регистр 14, блок 15 местного управления, блок 16 памяти страниц, генератор 17 расстановки, коммутатор 18, выходы 19-29 блока 15 местного управления, входы 30-35 блока 15 местного управления 30-35, информационный вход

36 устройства., адресный вход 37 устройства, вход 38 режима устройства, тактовый вход 39 устройства.

Генератор 17 расстановки (фиг. 2) содержит блок элементов ИСКЛЮЧА10Г4ЕЕ ИЛИ 40, регистры 4! и 42, комму5

2О

3Î

50 татор 43, генератор 44 псевдослучайных чисел.

Блок 15 местного управления(фиг.3) содержит элемент 45 задержки, триггеры 46, элементы ИЛИ 47-49, элементы И 50-66, элементы ИЛИ 67-73, элемент 74 задержки.

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

Блок 15 местного управления предназначен для выработки управляющих сигналов..

Память 4 ключей защиты, память 8 битов изменения, память 9 битов обращения и блок 16 памяти страниц обеспечивают адресацию для каждой физической страницы оперативной памяти.

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

После загрузки виртуальной страницы в оперативную память по адресу, который находится в регистре 2 физического адреса, блок IS местного управления возбуждает управляющие сигналы на выходах 21-23. Адрес с выхода старших разрядов регистра 2 физических адресов поступает на адресный вход памяти битов обращения через коммутатор 18, что обеспечивается потенциалом логического нуля на выходе 27 блока 15.

Управляющий сигнал на выходе 21 блока 15 разрешает установление соответствующей входной информации на информационных входах памяти 4

903878

9 ключей защиты и памяти 9 битов обращения путем подачи потенциалов логической единицы на вторые входы блока элементов И 13 и элемента И 11.

По сигналам 21 н 22 производится запись входной информации в память

4 ключей защиты, память 8 битов изменения и память 9 битов обращения соответственно.

Память 8 битов изменения пред- !О назначена для идентификации тех страниц, в которые вносились изменения при выполнении рабочей программы.

Поэтому после загрузки страницы в оперативную память производится обнуление соответствующего бита памяти 8 битов изменения, что обеспечивается отсутствием сигнала на выходе 24 блока 15, который управляет элементом И 10, 20

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

15 местного управления не возбуждается. Поэтому нулевые значения с выходов элементов И 11 и блока элементов И 13 записываются в память

4 ключей защиты и память 9 битов обращения.

При обращении к оперативной памяти по адресу, находящемуся в регистре 2 физического адреса, с помощью первой схемы 5 сравнения производится сравнение значения ключа 40 защиты памяти, присвоенного данной физической странице при загрузке ее и оперативную память, со значением поля ключа защиты памяти регистра слова состояния программы. В этом 4> случае сигнал с выхода 23 блока 15 местного управления, управляющий блоком элементов И 13, разрешает прохождение значения ключа защиты памяти слова состояния программы на вход первой схемы 5 сравнения. Тогда же сигнал с выхода 24 блока -15 местного управления разрешает установку соответствующего бита памяти 8 битов изменения, если установлен триггер

55 режима памяти. Триггер режима памяти устанавливается, если обращение к оперативной памяти производится для записи информации.

1О

Генератор 17 расстановки предназначен для реализации алгоритмов, которые расставляЬт (перемешивают) случайным образом определенные биты виртуального адреса.

Регистр 2 физического адреса, генератор 17 расстановки, блок 16 памяти страниц, буферный регистр 3 и вторая 6 и третья 7 схемы сравнения используются для ускорения преобразования виртуальных адресов в физические .адреса оперативной памяти. В буферном регистре 3 находится значение логического адреса последнего обращения к оперативной памяти, а в регистре 2 физического адреса -. соответствующий этому логическому адресу физический адрес страницы оперативной памяти. Если при последующем обращении к оперативной памяти третьей схемой 7 сравнения путем сравнения содержимого старших разрядов регистра 1 логического адреса и буферного регистра 3 установлено, что предыдущее обращение к памяти производилось по тому же логическому адресу, то соответствующий физический адрес страницы находится в старших разрядах регистра 2 физического адреса, а адрес внутри страни- цы определяется содержимым младших разрядов регистра 1 логического адреса.

Если схемой 7 сравнения установлено несовпадение содержимого старших разрядов регистра l логического адреса и буферного регистра 3, то переадресация выполняется с помощью генератора 17 расстановки, блока !

6 памяти страниц и второй схемы

6 сравнения. В старших разрядах блока

16 памяти страниц хранятся логические адреса, а в младших разрядах блока 16 памяти страниц — соответствующие им физические адреса оперативной памяти. Количество ячеек в блоке 16 памяти страниц соответствует количеству физических страниц во всем объеме оперативной памяти. Заполнение блока 16 памяти страниц управляется генератором 17 расстановки путем перемешивания случайным об разом битов старших разрядов регистра 1 логического адреса, чтобы выбрать ячейку блока 16 памяти страниц, содержимое которой определяетсоответствие между логическим и физи11 90387 ческим адресами, и в которой с наибольшей вероятностью находится требуемый логический адрес, поскольку несколько значений логических адресов могут иметь одно и то же значение расстановки..

Алгоритм расстановки, применяемый в генераторе 17 расстановки для определения адреса входа в блок 16 памяти страниц, использует блок эле- 10 ментов ИСКЛЮЧАЮЦЕЕ ИЛИ 40, на вход которого поступают в обратном порядке ичмладших битов с выхода старших разрядов регистра 1 логического адреса (m=2 количество физи- 15 ческих страниц во всем объеме оперативной памяти) блока. Значения с выхода блока элементов ИСКЛЮЧАЮ!ЦЕЕ И!!И

40 через коммутатор 43 поступают на адресный вход блока 16 памяти стра- щ ниц.

Преобразование виртуальных адресов с помощью генератора 17 расстановки, блока 16 памяти страниц и схемы 6 сравнения осуществляется сле-д дующим образом.

Эта проверка наличия страницы в оперативной памяти производится потому что при удалении страницы иэ оперативной памяти очистки блока 16 памяти страниц не производится. Если в загруженную страницу, физический адрес которой находится в регистре

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

6 с содержимым старших разрядов ре35 гистра логического адреса. Если сравнение произошло, то в старшие разряды регистра 2 физического адреса переписывается значение физи40 ческого адреса с выхода младших раз.рядов блока 16 памяти страниц, а адрес внутри страницы определяется содержимым младших разрядов регистра

l логического адреса l. Если совпа45 дение не произошло, то вырабатывается сигнал страничного прерывания, и в первый и второй регистры 41 и

42 генератора 17 расстановки записы» ваются значения с выхода блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 40 генератора 17 под действием управляющего сигйала 25.

Во время программной обработки страничного прерывания с помощью ре» гистра 2 физического адреса, генера- 55 тора 17 расстановки, блока 16 памяти страниц, памяти 8 битов изменения и памяти 9 битов обращения опре8, 12 деляется.физический адрес свободной страницы в оперативной памяти или, если свободной страницы нет, физический адрес страницы, которая возможно будет эамещаться.

Во время одного цикла поиска выполняется следующее.

Под действием управляющего сигнала на выход коммутатора 43 генератора 17 расстановки поступает содержимое регистра 41. Это значение с выхода генератора 17 расстановки поступает на адресный вход блока 16 памяти страниц и через коммутатор 18 — на адресный вход памяти 9 битов обращения. Содержимое выбранной ячейки памяти 9 битов обращения, поступающее в блок 15 местного управления, указывает, свободна ли страница оперативной памяти, адрес которой находится .в регистре 41 генератора 17 расста новки

Содержимое младших разрядов вы-. бранной ячейки блока 16 памяти записывается в старшие разряды регистра

2 физического адреса. Если страница, адрес которой находится в регистре 41 генератора 17 расстановки, свободна, то поиск заканчивается, а содержимое регистра 41 переписывается в регистр 42. Если страница загружена, то на адресные входы памяти 8 битов изменения и памяти 9 битов обращения поступает содержимое старших разрядов регистра 2 физического адреса. Содермммое выбранной ячейки памяти 9 битов обращения, поступающее в блок 15 местного управления, указывает, свободная ли страница оперативной памяти, адрес которой находится в старших разрядах регистра 3 физических адресов, Если страница свободна, то поиск заканчивается и содержимое регистра 41 переписывается в регистр 42, а если страница загружена, то содержимое выбранной ячейки памяти 8 битов изменения указывает, вносились ли изменения в страницу, физический адрес которой находится в старших разрядах регистра 2 физических адресов.!

3878 !

10!

30

40

55, 2 физического адреса, не вносились изменения, то содержимое регистра 4! переписывается в регистр 42, а в регистр 41 записывается сформированное генератором 44 псевдослучайных чисел значение. Если изменения вносились, то в регистр 41 записывается сформированное генератором 44 псевдослучайных чисел значение. Далее, если возможно, процесс поиска повторяется.

Генератор 44 псевдослучайных чисел генератора 17 расстановки предназначен для формирования псевдослучайных чисел и реализации алгоритма.

Рег. 41-целая часть от (бх 0ег М ) od2. !! где m=2 — количество физических

2.и страниц во всем объеме оперативной памяти.

Поэтому первый вход генератора

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

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

Устройство для динамического преобразования адресов работает в пя,ти режимах следующим образом.

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

Первый режим — переадресация.

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

27 которые устанавливаются при ус-

) тановке первого разряда управляющего регистра 14 через элементы ИЛИ 70, 71 и 73, соответственно, код ключа защиты из регистра слова состояния программы через элементы И 13 группы поступает на вход первой схемы

5 сравнения, сформированный группой элементов ИСКЛЮЧАИЦЕЕ ИЛИ 40 генератора 17 расстановки адрес обращения к блоку 16 памяти страниц через коммутатор 43 поступает на выход генератора 17 расстановки, а на вход памяти ". битов обращения поступает содержимое регистра 2 физического адреса.

Во время деиствия тактового импульса СО производится сравнение содержимого старших разрядов регистра 1 логического адреса с содержимым буферного регистра 3, чтение значения ключа защиты памяти из памяти 4 ключа защиты и чтение идентификатора наличия страницы в памяти из памяти 9. битов обращения по адресу, находящемуся в регистре 2 физического ад- реса, а также чтение иэ блока 16 памяти страниц с последуюцим сравнением содержимого старших разрядов блока 16 и регистра логического адреса

Физический адрес страницы считается найденным и находится в регистре 2 физического адреса, если страница находится в оперативной памяти, третьей схемой сравнения установлено совпадение и не произошло ошибки по защите памяти, Если прерывание по защите оперативной памяти не произошло, то по сигналу с выхода элемента

74 задержки открывается элемент И 64,который через элемент ИЛИ 49 открывает элемент И 53, сигнал с выхода 24 которого открывает элемент И IO позволяющий установить соответствуюций бит памяти 8 битов изменения,, если установлен триггер режима оперативной памяти (производится обращение в оператив15

903878

40 ную память для записи информации), Если схемой 7 сравнения установлено совпадение, в момент действий тактового импульса открыт элемент И 65; сигнал с выхода которого через эле- 5 мент ИЛИ 48 при установлении, что страница находится в оперативной памяти, и схемой 5 сравнения установлена ошибка по защите памяти, открыва" ет элемент И 60, сигнал с выхода 29 которого устанавливает запрос на прерывание по защите памяти. Если третьей схемой 7 сравнения установлено несовпадение, а схемой 6 сравнения установлено, что логический адрес, 15 находящийся в старших разрядах блока

16 памяти страниц, совпал с логическим адресом, находящимся в регистре 1 логического адреса, то во время действия тактового импульса че- 20 рез открытые элементы И 66 и 56, через элементы ИЛИ 67 и 72 управляющие сигналы с выходов 20 и 26 поступают соответственно на управляю щие входы регистра 2 физического адреса 2 и буферного регистра 3.

Содержимое старших разрядов регистра 1 логического адреса переписывается в буферный регистр 3, а содержимое младших разрядов выбран,ной генератором 17 ячейки блока 16 памяти страниц переписывается в регистр 2 физического адреса. В этом случае из памяти 4 ключей защиты и памяти 9, битов обращения читается информация по адресу, находящемуся в регистре 2 физического адреса. Фи- зический адрес страницы считается найденным и находится в регистре 2 физического адреса, если страница находится в оперативной памяти, второй схемой 6 сравнения установлено совпадение и не произошло ошибки по защите памяти.

Если прерывание по защите one- 45 ративной памяти не произошпо, то по сигналу с выхода элемента 45 задержки открывается элемент И

63, сигнал с выхода которого через элемент ИЛИ 49 открывает . 50 элемент И 53, сигнал с выхода 24 которого открывает элемент И 10, .позволяющий установить соответствующий бит памяти 8 битов изменения, если установлен. триггер режжиа опе- Ы ратйвной памяти (производится обращение в оперативную память для записи информации) . Если схемой 6 сравнения установлено сравнение, в момент действия тактовбго импульса открыт элемент И 66, сигнал с выхода которого через элемент

ИЛИ 48 при установлении, что страница находится в оперативной памяти и схемой 5 сравнения установлена ошибка по защите памяти, открывается элемент И 60, сигнал с выхода 29 которого устанавливает запрос на прерывание по защите памяти. Прерывание по защите памяти обрабатывается управляющей программой.

Если во время действия тактового импульса схемами 6 и 7 сравнения установлено несовпадение, то открывается элемент И 59, сигнал с выхода 28 которого вызывает запоминание номера ячейки блока 16 памяти страниц, по которому производилось обращение, в регистрах 40 и 41 генератора 17 расстановки и вызывает страничное прерывание, обрабатываемое управляющей программой.

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

Второй режим — циклический поиск.

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

14. В течение одного цикла поиска нулевое состояние триггера 46 открывает элемент И 62, сигнал, с выхода 25 которого через коммутатор 43 генератора 17 расстановки коммутирует содержимое регистра 41 на выход генератора 17 расстановки. Во время деиствия тактового импульса из памяти

9 битов обращения производится чтение по адресу, поступающему на ее адресный вход через коммутатор 18 с выхода генератора 17 расстановки при наличии сигнала с выхода 27 открытого элемента И 58

Содержимое выбранной ячейки памяти 9 битов обращения определяет, 9038

78 l8 загружена ли страница оперативнои памяти с номером, определяемым адресом обращения к памяти 9 битов обращения. Если физическая страница свободна, от открывается элемент И 61, сигнал с выхода которого устанавливает триггер 46, определяющий окончание поиска и закрывающий элемент

И 62.

Если физическая страница загружена (триггер 46 не установлен), то производится запись содержимого младших разрядов блока 16 памяти страниц в регистр 2 физического адреса при наличии управляющего сигнала с выхода 15

20 элемента HJM 67 (элемент И 58 от" крыт) В момент действия тактового импульса производится чтение из памятей 8и 9 битов соответственно, изменения и обращения по адресу, на- 20 ходяц1емуся в регистре 2 физического адреса. Этот адрес поступает на адресный вход памяти 9 битов обращения через коммутатор !8 при наличии на его управляющем выходе сигнала с выхода 27 элемента ИЛИ 73 (элемент

И 57 открыт) . Если страница оперативной памяти свободна, то сигнал с выхода памяти 9 битов обращения открывает элемент И 61 и устанавли- ЗО вает триггер 46 (поиск закончен) .

Если страница оперативной памяти загружена и в нее не вносилось изменений, то содержимое регистра 41 генератора 17 расстановки переписывается в регистр 42, а сформированное генератором 44 псевдослучайных чисел значение записывается в регистр

41 по сигналам 25 с выхода открытых элементов И 54 и 55 соответственно. 4о

Цикл поиска повторяется, если в течение предыдущего цикла не устанавливается триггер 46 или, при установленном триггере второго разряда регистра 14,. управляющая программа 45 устанавливает триггер шестого разряда регистра 14, который закрывает элемент И 62. Триггер шестого разряда управляющего регистра !4 обеспечивает приостановку поиска. 50

Третий режим — однотактный поиск.

Однотактный поиск производится так же, как цикл циклического поиска, за исключением того, что на выход коммутатора 43 генератора 17 расстановки поступает содержимое регистра 42 при наличии управляющего сигнала с выхода 25. При однократ-. ном поиске элемент И 62 закрыт, поэтому регистр 41 в работе не участвует и определяется, свободна ли страница оперативной памяти, адрес которой находится в регистре 42. Если эта физическая страница загружена, то проверяется, загружена ли страница оперативной памяти, адрес которой находится в ячейке блока 16 памяти страниц, выбираемой по содержимому регистра 42 генератора 17 расстановки. Адрес свободной страницы или страницы, подлежащей удалению, находится в регистре 2 физического адреса, куда он переписывается из регистра 42 по сигналу с выхода 20 элемента И 51, если страница оперативной памяти с этим адресом свободна. В остальных случаях в регистр 2 физического адреса загружается содержимое младших разрядов ячейки блока 16 памяти страниц, адрес которой находится в регистре 42, по тактовому импульсу при открытом элементе И 58.

Если страница, адрес которой находится в регистре 2, загружена и в

Одновременно с началом циклического поиска управляющая программа определяет наличие требуемой страницы в оперативной памяти с помощью

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

903878 нее вносились изменения, то она удаляется из оперативной памяти. Далее производится коррекция таблиц переадресации, Кали в загруженную страницу изменения не вносились, то эта физическая страница считается свободной, и в таблицах переадресации корректируются соответствующие биты доступности. Затем в свободную страницу оперативной памяти загружается требуемая страница, после чего производится коррекция таблиц страниц. Логический адрес требуемой страницы находится в регистре 2логического адреса, а.соответствующий ему !5 физический адрес поступает на выходной шине 37 оперативной памяти в ре-. гистр 2 физического адреса и на вход младших разрядов блока 16 памяти страниц. Загрузка физического и ло- 20 гического адресов, значения ключа зац!иты памяти и очистка памяти 8 битов изменения и памяти 9 битов обращения осуществляются при установке триггера четвертого разряда управля- 25 ющего регистра !4..

Четвертый режим — коррекция блоков памяти.!

При установке триггера четвертого разряда регистра 14 по сигналу с выхода 26 элемента ИЛИ 72 содержимое регистра 2 физического адреса через коммутатор 18 поступает на адресный вход памяти 9 битов обраще35 ния, а по сигналу с выхода 25 элемента ИЛИ 71 значение, сформированное группой элементов ИСКЗПОЧА10ЩЕЕ ИЛИ 40 генератора 17 расстановки, через коммутатор 43 поступает на адресный вход блока 16 памяти страниц. Сигнал с выхода 23 элемента ИЛИ 70 открывает элемент И 11 и элементы И 13 блока„ в результате чего открывается элемент И 11, а на информацион45 ный вход памяти 4 ключей защиты IIQ ступает значение ключа защиты с выхода регистра слова состояния программы.

В момент действия тактового импульса через открытый элемент И 50

50 по сигналам с выходов 19 и 20 элемента И 50, с выходов 21 и 22 элемента ИЛИ 69 производится запись в блок 16 памяти страниц логического и физического адресов с выходов реФ гистра 1 логического адреса и выходной шины 37 оперативной памяти соответственно, в регистр 2 физическо20

ro адреса — запись физического адреса с выходной шины 37 оперативной памяти, в память 4 ключей защиты — запись значения ключа защиты, в память 9 битов обращеииязапись логической единицы, а в память 8 битов изменения — запись логического нуля. После этого обработка страничного прерывания закончена, Если страница удаляется из оперативной памяти, а последуюц|ая загрузка ее не производится, то устанавливается триггер пятого разряда управляющего регистра 14, что обеспечивает очистку памяти 4 ключей защиты, памяти 8 битов изменения и памяти 9 битов обращения.

Пятый режим — очистка.

Очистка памяти 4 ключей защиты, памяти 8 битов изменения и памяти

9 битов обращения производится аналогично"записи в них информации за исключением того„ что сигнал с выхода 23 не вырабатывается, поэтому в соответствующие ячейки памятей 4, 8 и 9 записываются нулевые значения, а сигнал записи с выхода элемента ИЛИ 69 вырабатывается при открытом элементе И 52 во время действия тактового импульса.

Во время выполнения операций ввода — вывода, осуществляющих загрузку или удаление страниц при страничных прерываниях, управляющая программа может разрешить выполнение следующей задачи, готовой к выполнению. Если при выполнении такой программы возникло страничное прерывание,. то оно подавляется управляющей программой, а выполнение задачи занкачивается (ее выполнение будет возобновлено с команды, вызвавшей страничное прерывание), управляющая программа может разрешить выполнение следующей задачи и т.д. В этих случаях, если устройство работало в режиме циклическог;. ;оиска, устанавливаются триггеры я:=стого и первого разрядов управляющ . ;."о регистра 14, что приводит к приостановке циклического поиска и работе устройства в режиме переадресации.

Таким образом, применение изобретения позволяет сократить число страничных прерываний путем увели2) чозо чения объема рабочего комплекта страниц, т.е. числа виртуальных страниц, с помощью аппаратурных средств устройства, что особенно эффективно прн мультипрограммной работе вычислитель5 ной системы.

78 22 менения и тактовый вход устройства соединены соответственно с первого по шестой входами блока местного управления, группа разрядных выходов управляющего регистра соединена с группой входов блока местного управформула изобретения

l0

1. Устройство для динамического преобразования адресов, содержащее регистры логического и физического адресов, буферный регистр, память ключей защиты, три схемы сравнения, . па i™".òTü б иHтTоOв иHз3мMеBнHеeнHиHя, память битов обращения, два элемента И, эле— мент ИЛИ, блок элементов if управля" ищнй регистр и блок местного управления, причем выход регистра физического адреса соединен с адресными входами памяти битов изменения и памяти ключей защиты, выход которой соединен с первым входом первой схемы сравнения, второй вход которой и информа- 5 ционный вход памяти ключей защиты соединены с выходом блока элементов

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

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

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

2. Устройство по и. 1, о т л и— ч а ю щ е е с я тем, что генератор расстановки содержит блок элементов

ИСКЛЮЧАЮЩЕЕ ИЛИ, два регистра, коммутатор и генератор псевдослучайных чисел, причем вход блока элементов

ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с входом генератора расстановки, выход блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с первыми входами коммутатора и регистров, выход первого из которых соединен со вторым входом коммутатора, а выход второго регистра соединен со вторым входом первого регистра, третьим входом коммутатора и входом генератора псевдослучайных чисел, выход которого соединен со вторым входом второго регистра, уп23 9038 равляющие входы первого и второго регистров и коммутатора соединены с группой управляющих входов генератора расстановки, а выход коммутатора является выходом генератора 5 расстановки.

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

И, элементы ИЛИ, триггер и два эле- 1О мента задержки, причем первые входы первого, второго и третьего =,ïåментов И соединены соответственно с первым, вторым и третьим входами группы входов блока, первые вхо- 1S ды элементов И с четвертого по седьмой соединены с четвертым входом группы входов блока, первый, второй и третий входы восьмого элемента И соединены соответственно с шестым, вторым и пятым входами группы входов блока, вторые входы первого, второго и третьего элементов И и первые входы девятого, десятого и одиннадцатого элементов И соединены с шестым входом блока, четвертый вход восьмого элемента И соединен с выходом триггера, вторые входы девятого и одиннадцатого элементов И соединены с выходом первого элемента ИЛИ,-:второй вход пятого элемента

И соединен с выходом двенадцатого элемента И и с первым входом второго элемента ИЛИ, первые входы двенадцатого, тринадцатого, четырнадцатого и пятнадцатого элементов И и второй вход шестого элемента 1I соединены с третьим входом блока, вторые входы. двенадцатого, пятнадцато го и третий вход шестого элементов

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

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

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

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

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

И соединен с первым выходом блока, шестой вход блока соединен со вторым входом третьего элемента ИЛИ и через второй элемент задержки со вторым входом четырнадцатого элемента И, единичный и нулевой входы триггера соединены соответственно с выходом шестнадцатого элемента И и с шестым вхо дом группы входов блока, второй вход второго элемента ИЛИ соединен с выходом тринадцатого элемента И, первый вход шестого элемента ИЛИ и второй вход пятого элемента ИЛИ соединены с выходом первого элемента И, выходы четырнадцатого и пятнадцатого элементов И соединены соответственно с первым и вторым входами четвертого элемента ИЛИ, выходы первого, второго элементов И и десятого элемента ИЛИ соединены соответственно с первым, вторым и третьим выходами первой группы выходов блока, пер" вые входы пятого и десятого элементов ИЛИ соединены с выходом пятого элемента И, второй вход десятого элемента ИЛИ соединен с первым выхо дом третьей группы выходов блока и с выходом одиннадцатого элемента И, выход восьмого элемента ИЛИ соединен со вторым выходом третьей группы выхоцов блока, второй вход шестого элекеята ИЛИ соединен с выходом третьего :.цемента И, выход седьмого элемент.. В .M соединен с пятым выходом блока .":. с первым входом восьмого элемента ИЛИ, выход четвертого элемента И соединен с третьим выходом блока, выход девятого элемента ИЛИ соединен с четвертым выходом второй группы выходов блока, пятый выход второй группы выходов блока соеди25

0ЗВ7Я нен с первым входом первого элемента ИЛИ, первый и второй выходы седьмого и девятого элементов ИЛИ соединены соответственно с первым и четвертым входами группы входов блока, второй вход восьмого элемента ИЛИ соединен с выходом девятого элемента И, выход пятого элемента ИЛИ сое.динен с шестым выходом блока, выход шестого элемента И соединен с седьмым выходом блока и с шестым выхо26 дом второй группы выходов блока, выход седьмого элемента И соединен с восьмым выходом блока.

Источники:информации, принятые во внимание при экспертизе

Карцев М.А. Архитектура цифровых вычислительных машин. М., "Наука", 1978, с. 158-160.

2. Катцан Г. Вычислительные машины системы 370. М., "Мир", 1974, с. 410-436 (прототип).

19

21

2Я 1

J2 и

oui.1

903878

21

22

26

Составитель M.Êóäðÿøåâ

Редактор А. Шишкина Техред M. Надь КорректорА.Дзятко

М

Заказ 123/31 Тираж 731 Подписное

ВНИИПИ Государственного комитета СССР

Ф по делам изобретений и открытий

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

Филиал ППП Патент", г. Ужгород, ул. Проектная, 4