Устройство управления памятью

 

Оп ИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Союз Советскнк

Соцналистнческин

Республик (11)1001 1 00 (61) Дополнительное к авт. свна-ву (22)Заявлено 22.06.81 (21} 3303638/18-24 с прнсоеднненнем заявкн № (23) Приоритет

Опубликовано 28.02 83 Бюллетень № 8

Дата опублнковання описания 28 .02 .83 (51)М. Кл.

G 06 F 9/36

Гесударстввнтьа кемнтет

СССР е делам нэейретеии» н нтнрытий (53) УДК 681. ..32/(088.8) А. П. Запольский, В. Б. Шкляр, В. А и Н. А. Волкова (72) Авторы изобретения (71) Заявитель (54) УСТРОЙСТВО УПРАВЛЕНИЯ ПАМЯТЬЮ

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

Известно устройство управления памятью, реализующее алгоритм замещения страниц LRU (least recently

used - наименее используемый в последнее время), содержащее ассоциативные регистры, связанные между собой так, что каждый из регистров может принять содержимое иэ верхнего соседнего регистра и одновременно передать свое прежнее содержимое в соседний нижний регистр. Входы верхнего ассоциативного регистра соединены с выходами центрального процессора и памяти, выходы нижнего ассоциативного регистра соединены с входами памяти Г1 ). го

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

Наиболее близким к предлагаемому по техническому решению является устройство, содержащее регистр совпадения страниц, схему замещения, дешифратор и блок памяти замещения, вход которого соединен с выходом схемы замещения, первый вход которой, соединен с выходом регистра совпадения страниц, первый вход которого соединен с первым входом устройства, выход блока памяти замещения соединен с входом дешифратора, выход которого соединен с пер3 . 100110 .Фым. выходом устройства. устройство применяется в Э ВИ ЕС-1 035 для организации виртуальной памяти 2 1.

Известное устройство не позволяет реализовать алгоритм замещения

1 В0 для произвольного числа страниц в случае возникновения такой необходимости ° Алгоритм замещения LRU за счет своей достаточно высокой эффективности и доступности аппара — !О турной реализации является наиболее распространенным в системах с виртуальной памятью. Однако способ его реализации предполагает использование жестко определенного числа страниц, 3$ на которое рассчитана аппаратура.

С другой стороны существуют два направления усовершенствования средств реализации алгоритма замещения LRU

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

Второе направление - использование принципиальной возможности алгоритма

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

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

Цель изобретения — повышение достоверности преобразования информации путем реализации функции избирательного отключения страниц при выпол45 нении алгоритма замещения страниц

LRU.

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

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

На фиг. 1 изображена структурная схема устройства управления памятью;

5 1001 на фиг. 2 - функциональная схема блока управления; на фиг. 3 - пример выполнения групп элементов И; на фиг. 4 - пример реализации блока памяти замещения; на фиг.5 - временная диаграмма сигналов, управляющих работой устройства.

Устройство управления памятью содержит регистр 1 совпадения страниц, группу 2 элементов И, дешифра- 10 тор 3, блок 4 памяти замещения, блок 5 управления и регистр 6 отключения страниц (фиг. 1) . Ha чертеже также представлены первый тактовый вход 7, вход 8 кода отключения, второй тактовый вход 9, вход 10 кода совпадения, вход 11 сопровождения микрокоманды, третий тактовый вход 12, выход 13 замещения, вы.ход 14 отключения и выход 15 призна 20 ка отключения. Вход блока 4 соединен с выходом группы 2 элементов И, первый вход которой соединен с выхо,дом регистра 1, первый вход которого соединен с входом 7 устройства. Вы- 2$ ход блока 4 соединен с входом дешиф ратора 3, выход которого соединен с выходом 13 устройства. Вход регистра

6 соединен с входом 8 устройства, а первый выход соединен с выходом 14 устройства. Второй выход регистра 6 соединен с первым входом блока 5, второй вход которого соединен с выходом дешифратора 3 и выходом 13 устройства. Третий, четвертый, пятый и шес- з той входы блока 5 соединены соответственно с входами 9-12 устройства.

Выход 15 устройства соединен с первым выходом блока 5, второй выход которого соединен с вторым входом регист- ра 1, а третий выход блока 5 соединен с вторым входом группы 2 элементов И.

Блок 5 управления (фиг. 2) содержит первый элемент И 16, первую группу 17.элементов И, вторую группу

18 элементов И, второй элемент И 19, третью группу 20 элементов И, триггер

21 отключения, первый и второй элементы ИЛИ 22 и 23 и группу 24 элементов ИЛИ.Блок 5 предназначен для управления работой устройства и организа-:1 ции отключения какой-либо страницы при выполнении алгоритма замещения страниц LRU ðåàëèçîâàííoãî в устройстве.

Выход триггера 21 соединен с выходом

15 устройства и первым входом эле$$ мента И 16, второй вход которого соединен с входом 11 устройства и с первыми входами элементов И группы 17, 100 6 группы 18 и элемента ИЛИ 22. Второй вход элемента 22 соединен с выходом элемента И 16, а выход соединен с первым входом элемента И 19. Второй вход элемента И 19 соединен с входом 12 устройства, а выход срединен с входом группы 2 элементов И. Первый и второй входы группы 20 соединены соответственно с выходами дешифратора 3 и регистра 6, а выход группы 20 соединен с вторым входом группы 18 и входом элемента ИЛИ 23, выход которого соединен с первым входом триггера 21. Второй вход триггера 21 соединен с входом 9 устройства, выход группы 24 .соединен с входом регистра 1, вход 10 устройства соединен с вторым входом группы 17 выход которой соединен с первым входом группы 24. Второй вход группы

24 соединен с выходом группы 18.

Группа 2 элементов И (фиг. 3) содержит и элементов И 25„,...,25,, где n - число страниц, содержащйхся в устройстве. Группа 2 предназначена для получения сигналов, осуществляющих модификацию информации в блоке 4. Первый вход каждого элемента 25 ,25„ соединен с соответствующим разрядным выходом регистра 1, а выход каждого элемента 25 соединен с входом блока 4. Вторые входы каждого элемента 25 соединены друг с другом и с блоком 5 управления.

Блок 4 памяти замещения (фиг.4) содержит К триггеров 261, ..., 26 к, и (и-1) где К = - Блок 4 предназначен ! для хранения информации о последовательности обращений к страницам, позволяющей выделить страницу, наименее используемую в последнее время (алгоритм LRU) . Входы триггеров

26 соединены с выходами группы 2, а выходы триггеров 26 соединены с входом дешифратора 3. Обозначим триггеры 26 через Т;, где 1

12 13 Я 1п

23 24 Zг1

Установочные входы S всех триггеров строки L (Т L+ Ò L+3 Т, „) соеди00 8

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

Рассмотрим выполнение микрокоманды А (фиг. 5), в которой осуществляется обращение к странице (микрокоманда В - это любая другая микрокоманда, реализуемая в устройст- о ве обработки). Вход 11 предназначен для передачи сигнала о том, что выполняется микрокоманда А. В ходе выполнения любой микрокоманды устройство;получает тактовые импульсы

ТИ1, ТИ2, ТИЗ, поступающие соответственно на входы 7,12 и 9. Регистр

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

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

Рассмотрим работу устройства в

SS этом случае.В течение всего времени выполнения микрокоманды А на входе

11 устройства присутствует признак

7 10011 нены между собой и также с входами сброса R всех триггеров столбца

1. (Т1 Т2 . ° . Т1 11), Дешифратор 3 предназначен для дешифрации информации, поступающей из > блока 4, с целью определения страницы, наименее используемой в последнее время. Дешифратор возбуждает один из ll выходов F по следующему закону: „„

1О М-1 м Т1м 1 . 1<М<п

1м. м - 0

Возбужденный выход и определяет страницу по правилу замещения LRU Регистр 1 предназначен для хранения информации о последнем запросе какойлибо страницы. Разрядность регистра равна и разрядам. Единичное состояние l-го бита говорит о том, что бы26 ла запрошена i-ая страница. Регистр

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

?S регистра также равна и разрядам. Единичное состояние i- го бита означает, что из алгоритма исключена страница

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

I микрокоманды А (единичный сигнал).

Данный сигнал поступает на первый вход группы 17 (фиг. 2) и разрешает прохождение сигналов с входа 10 устройства на первый вход группы 24.

На вход 10 (имеющий разрядность п, равную числу страниц, на которое рассчитано устройство) поступает информация о том, какая страница запрошена в микрокоманде А. Единичный сигнал указывает на запрашиваемую страницу. Сигналы с выхода группы 24 подаются на второй вход регистра 1 и записываются по ТИ, поступающему на первый вход регистра 1 с входа 7.

Сигнал с входа 11 проходит через элемент 22 (фиг. 2), поступает на первый вход элемента 19 и разрешает прохождение ТИ с входа 12 через элемент 19 на второй вход группы 2.

В группе 2 (фиг. 3) ТИ 2 подается на вторые входы элементов 25 и так как на первом вхоае оаного из элементов

25 присутствует единичный сигнал с выхода регистра 1, то вырабатывается сигнал обновления, поступающий на вход блока 4 и производится его обновление. Новое состояние блока

4 девЛпфрируется дешифратором 3, сигналы с выхода которого поступают на и разрядный выход 13» указывая, какая страница является кандидатом на удаление согласно алгоритму LRU.

Так как в регистре 6 все разряды находятся в нулевом состоянии (нет отключения), то на выходах элементов

И группы 20 присутствуют нулевые сигналы, которые, проходя через элемент 23 записывают "нуль" в триггер 21 по сигналу ТИ 1с входа 9 °

Пусть после микрокоманды А выполняется микрокоманда В. В этой микрокоманде на входе 11 присутствует нулевой сигнал, которы|", с выхода триггера 21 блокирует элемент

16, поэтому на выходе элемента 22 появляется "нуль", так как на двух его входах присутствуют нулевые сигналы. Поэтому ТИ с входа 12 не проходит через элемент 19 на второй вход группы 2 и она не вырабатывает сигнала обновления . поступающего на вход блока 4. Таким образом, в случае нулевого состояния регистра 6 в микрокоманде А производится изменение блока 4 согласно запросам страниц. В других микрокомандах

В изменения блока 4 не происходит.

10011

Рассмотрим работу устройства в том случае, если хотя бы один разряд (например К) регистра 6 равен единице. Микрокоманда А выполняется аналогично, т.е. происходит обновление 5 блока 4 согласно запросу страницы.

Если же после обновления дешифратор 3 указывает, что кандидатом на удаление не является страница К, то сигнал на выходе группы 20 равен "ну- 1В лю" и в результате триггер 21 не устанавливается в состояние "1". Это приводит к тому, что в следующей микрокоманде В не будет обновления блока 4. Если же после обновления дешифратор 3 указывает, что кандидатом на удаление является страница

К, то выход соответствующего элемента И из группы 20 будет находиться в состоянии единица и по сигналу 20

ТИЗ с входа 9 триггер 21 устанавливается в состояние "1".

В следующей микрокоманде В сигналы с выхода группы 20 через группы

18 и 24 подаются на вход регистра

1. При этом сигнал на выходе элемента

"16 равен "единице", так как триггер 21 установлен в состояние единица, тем самым разрешая прохождение

ТИ с входа 12 на второй вход группы 30

2. В результате происходит обновление блока 4 по сгенерированному запросу от страницы К. После обновления код на выходе дешифратора 3 указывает ra другую страницу т.е. тригУ зз гер 21 не установится в состояние единица и устройство не обновляет блок

4 в последующих микрокомандах типа В.

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

45 т.е. осуществляется обход отключенных страниц или, другими словами

1 устройство не может указать на отключенную страницу с целью ее замещения.

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

00 10

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

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

Технико-экономический эффект изобретения по сравнению с базовым объектом ЕС-1035, являющимся также прототипом, состоит в том, что за счет продолжения вычислительного процесса при выходе из строя части оборудования, связанного с переадресацией при обращении к памя.,ти, увеличивается время наработки на отказ, а наличие адаптивных свойств позволяет устройству оптимальным образом настраиваться на обработку конкретного набора задач и тем самым увеличивать производительность ЭВМ.

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

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

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

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

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

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

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

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

1. Патент США У 3806883, кл. 340-172.5, опублик. 1974.

2. Гущенсков Б.Н. и др. Организация виртуальной памяти ЕС-1035.-"Вопрусы радиоэлектроники", сер. ЭВТ, вып. 13, 1976,(прототип).

1001100

1001100

Составитель Г. Виталиев

Редактор Н. Стащишина Техред M. Коштура Корректор О. Билак

Заказ 1397/5< Тираж 704 Подписное

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

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

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