Устройство управления памятью Советский патент 1983 года по МПК G06F9/36 

1

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

Известно устройство управления памятью, реализующее алгоритм замещения страниц LRU (least recently used - наименее используемый в последнее время), содержащее ассоциативные р регистры, связанные между собой так, что каждый из регистров может принять содержимое из верхнего соседнего регистра и одновременно передать свое прежнее содержимое в соседний ниж- ,5 НИИ регистр. Входы верхнего ассоциативного регистра соединены с выходами центрального процессора и памяти, выходы нижнего ассоциативного регистра соединены с входами памяти tl 20

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

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

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

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

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

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

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

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

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

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

На фиг. 1 изображена структурная схема устройства управления памятью; 51 на фиг. 2 - функциональная схема бло ка управления; на фиг. 3 пример выполнения групп элементов И; на фиг. - пример реализации блока памяти замещения; на фиг.5 временная диаграмма сигналов, управляющих работой устройства. . Устройство управления памятью содержит регистр 1 совпадения страниц, группу 2 элементов И, дешифратор 3, блок памяти замещения, блок 5 управления и регистр 6 отключения страниц (фиг. 1) . На чертеже также представлены первый такто.вый вход 7, вход 8 кода отключения, второй тактовый вход 9. вход 10 кода совпадения, вход 11 сопровождения микрокоманды, третий тактовый вход 12, выход 13 замещения, вы, ход 1 отключения и выход 15 призна- ка отключения. Вход блока соединен с выходом группы 2 элементов И, первый ВХОД которой соединен с выхо,дом регистра 1, первый вход которого соединен с входом 7 устройства. Выход блока соединен с входом дешиф ратора 3, выход которого соединен с выходом 13 устройства. Вход регистра 6 соединен с входом 8 устройства, а первый выход соединен с выходом 1 t устройства. Второй выход регистра 6 соединен с первым входом блока 5, вт рой вход которого соединен с выходом дешифратора 3 и выходом 13 устро стча. Третий, четвертый, пятый и шее той входы блока 5 соединены соответственно с входами устройства. Выход 15 устройства сое.динен с первы выходом блока 5, второй выход которого соединен с вторым входом регист ра 1, а третий выход блока 5 соедине с вторым входом группы 2 элементов Блок 5 управления (фиг. 2) содержит первый элемент И 1б, первую группу 17 элементов И, вторую группу 18 элементов И, второй элемент И 1 третью группу 20 элементов И, тригге 21 отключения, первый и второй элементы ИЛИ 22 и 23 и группу 2k элемен тов ИЛИ.Блок 5 предназначен для управления работой устройства и организации отключения какой-либо страницы п выполнении алгоритма замещения страниц LRU,реализованного в устройстве. Выход триггера 21 соединен с выходом 15 устройства и первым входом элемента И 16, второй вход которого сое динен с входом 11 устройства и с первыми входами элементов И группы 17, 00 « группы 18 и элемента ИЛИ 22. Второй вход элемента 22 соединен с выходом элемента И 16, а выход соединен с первым входом элемента И 19. Второй . . вход элемента И 19 соединен с входом 12 устройства, а выход соединен с входом группы 2 элементов И. Первый и второй входы группы 20 соединены соответственно с выходами дешифратора 3 и регистра 6, а выход группы 20 соединен с вторым входом группы 18 и входом элемента ИЛИ 23, выход которого соединен с первым входом триггера 21. Второй вход триггера 21 соединен с входом 9 устройства, выход группы 2k .соединен с входом регистра 1, вход 10 устройства соединен с вторым входом группы 17, выход которой соединен с первым входом группы 2. Второй вход группы 2k соединен с выходом группы 18. Группа 2 элементов И (фиг. З) содержит п элементов И 25 ,.. . ,25,, где п - число страниц, содержащихся в устройстве. Группа 2 предназначена для получения сигналов, осуществляющих модификацию информации в блоке k. Первый вход каждого элемента 25,..., 25г, соединен с соответствующим разрядным выходом регистра 1, а выход каждого элемента 25 соединен с входом блока k. Вторые входы каждого элемента 25 соединены друг с другом и с блоком 5 управления. Блок 4 памяти замещения (фиг.4) содержит К трис.геров 2б,...,2бк , К.- 11П1:11.Блок k предназначен для хранения информации о последовательности обращений к страницам, позволяющей выделить страницу, наименее используемую в последнее время (алгоритм LRU). Входы триггеров 26 соединены с выходами группы 2, а выходы триггеров 26 соединены с входом дешифратора 3. Обозначим триггеры 26 через , где , . Они образуют треугольную матрицу, так как 12 13 V 23 af ,rl- I становочные входы S всех триггеров строки L (Тцц41,Ти,и42,. Тцп) соеди710нены между собой и также с входами сброса R всех триггеров столбца L (Т, ц,. .. , Тц). Дешифратор 3 предназначен для дешифрации информации, п $ступа1ощеи из блока k, с целью определения страницы, наименее используемой в последнее время. Дешифратор возбуждает один из п выходов F по следующему закону: . Возбужденный выход и определяет стра ницу по правилу замещения LRU. Регистр 1 предназначен для хранения ин формации о последнем запросе какойлибо страницы. Разрядность регистра равна п разрядам. Единичное состояние i-ro бита говорит о том, что была запрошена i-ая страница. Регистр 6 предназначен для )ранения информации об исключении какой-либо страницы при выполнении алгоритма LRU, реализуемого устройством. Разрядност регистра также равна п разрядам. Еди ничное состояние 1-го бита означает что из алгоритма исключена страница i. Устройство работает следующим образом. Устройство обработки, с которым соединено предлагаемое устройство, управляется микропрограммно. Оно выполняет различные микрркоманды. Рассмотрим выполнение микрокоманды А (фиг. 5), в которой осуществляется обращение к странице (микрокоманда В - это любая другая микрокоманда, реализуемая в устройст ве обработки). Вход 11 предназначен для передачи сигнала о том, что выполняется микрокоманда А. В ходе выполнения любой микрокоманды устройство .получает тактовые импульсы ТИ , ТИ„, ТИ, поступающие соответственно на входы 7,12 и 9. Регистр 6 доступен микропрограммнЬ устройству обработки. Для записи и считывания из регистра 6 используется вх 8 и выход 1 устройства, имеющие ра рядность п, равную разрядности регис ра отключения страниц. В случае, когда нет отключенных страниц, в регистре 6 все разряды равны нулю. Рассмотрим работу устройства в этом случае.В течение всего времени выполнения микрокоманды А на входе 11 устройства присутствует признак 0,8 микрокоманды А (единичный сигнал). Данный сигнал поступает на первый вход группы 17 (фиг. 2) и разрешает прохождение сигналов с входа 10 устройства на первый вход группы . На вход 10 (имеющий разрядностьп, равную числу страниц, на которое рассчитано устройство) поступает информация о том, какая страница запрошена в микрокоманде А. Единичный сигнал указывает на запрашиваемую страницу. Сигналы с выхода группы 2 подаются на второй вход регистра 1 и записываются по ТИ. , поступающему на первый вход регистра 1 с входа 7Сигнал с входа 11 проходит через элемент 22 (фиг, 2) , поступает на первый вход элемента 19 и разрешает прохождение ТИ2 с входа 12 через элемент 19 на второй вход группы 2. В группе 2 (фиг. 3) ТИ2 подается на вторые входы элементов 25 и так как на первом вхоле одного из элементов 25 присутствует единичный сигнал с выхода регистра 1, то вырабатывается сигнал обновления, поступающий на вход блока k и производится его обновление. Новое состояние блока дeшVlфpиpyeтcя дешифратором 3 сигналы с выхода которого поступают на п разрядный выход 13 указывая, какая страница является кандидатом на удаление согласно алгоритму LRU. Так как в регистре 6 все разряды находятся в нулевом состоянии (нет отключения), то на выходах элементов И группы 20 присутствуют нулевые сигналы, которые, проходя через элемент 23 записывают нуль в триггер 21 по сигналу входа 9Пусть после микрокоманды А выполняется микрокоманда В. В этой микрокоманде на входе 11 присутствует нулевой сигнал, которыГ, с выхода триггера 21 блокирует элемент 16, поэтому на выходе элемента 22 появляется нуль, так как на двух его входах присутствуют нулевые сигналы. Поэтому ТИл с входа 12 не проходит через элемент 19 на второй вход группы 2 и она не вырабатывает сигнала обновления. поступающего на вход блока . Таким образом, в случае нулевого состояния регистра 6 в микрокоманде А производится изменение блока согласно запрос м страниц. В других микрокомандах Визменения блока k не происходит. 910 Рассмотрим работу устройства в- то случае, если хотя бы один разряд (например К) регистра 6 равен единице. Микрокоманда А выполняется ана логично, т.е. происходит обновление блока 4 согласно запросу страницы. Если же после обновления дешифратор 3 указывает, что кандидатом на удаление не является страница К, то сигнал на выходе группы 20 равен ну лю и в результате триггер 21 не уст навливается в состояние 1. Это приводит к тому, что в следующей мик рокоманде В не будет обновления бло ка 4. Если же после обновления дешифратор 3 указывает, что кандидатом на удаление является страница К, то выход соответствующего элемента И из группы 20 будет находиться в состоянии единица и по сигналу ТИ с входа 9 триггер 21 устанавлива ется в состояние 1. В следующей микрокоманде В сигналы с выхода группы 20 через группы 18 и 2 подаются на вход регистра 1 . При этом сигнал на выходе элемент 16 равен единице, так как триггер 21 установлен в состояние единица, тем самым разрешая прохождение ТИ2 с входа 12 на второй вход группы 2. В результате происходит обновление блока k по сгенерированному запросу от страницы К. После обновления код на выходе дешифратора 3 указывает на другую страницу, т.е. триггер 21 не установится в состояние ед ница и устройство не обновляет блок k в последующих микрокомандах типа В Таким образом, устройство в микрокомандах типа А осуществляет обновле ние блока памяти замещения согласно запрашиваемой странице, а в микро командах типа В осуществляет обновле ние блока k согласно сгенерированному запросу от отключенной страницы, т.е. осуществляется обход отключенных страниц или, другими словами, устройство не может указать на отключенную страницу с целью ее замещения. Если в регистре 6 установлено в единичное состояние более одного разряда ( отключено несколько страниц )| то устройство в микрокомандах типа В осуществляет обновление блока памяти замещения до тех пор, пока не будет указывать на стра .ницу , которая не отключена. 010 . . Выход триггера 21 является выходом отключения устройства, который используется для индикации или микропрограммного анализа с целью обнаружения того.факта, что устройство на закончило процесс отключения страниц. Удаление страницы возможно в случае, если триггер 21 сброшен в нуль. Если в регистре 6 установлены в единицу все разряды, то устройство производит обновление матрицы замещения в каждой микрокоманде, т.е. будет реализован случайный алгоритм выбора страницы. Предлагаемое изобретение позволяет значительно расширить возможности применения алгоритма замещения страниц LRU. Расширение возможностей заключается в том, что исключение из процедуры замещения кааих-либо страниц может обеспечить постоянное нахождений в памяти наиболее необходимых страниц, а исключение из замещения всех страниц приводит к реализации другого алгоритма замещения со случайным выбором страницы, кото-. рый в определенных ситуациях может оказаться наиболее эффективным. Расширение возможностей заключается также в том, что при обнаружении ошибки в памяти или в списке замещаемых страниц данная строка списка замещаемых страниц или страница в памяти , содержащая ошибку ( если между ними существует однозначное соответствие),могут быть исключены из работы. Технико-экономический эффект изобретения по сравнению с базовым объектом ЕС-1035, являющимся также прототипом, состоит в том, что за счет продолжения вычислительного процесса при выходе из строя части оборудования, связанного с переадресацией при обращении к памя.ти, увеличивается время наработки на отказ, а наличие адаптивных свойств позволяет устройству оптимальным образом настраиваться на обработку конкретного набора задач и тем самым увеличивать производительность ЭВМ. Формула изобретения 1. Устройство управления памятью, содержащее регистр совпадения страниц, группу элементов И, блок памяти

111001

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

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

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

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

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

Источники информации,

принятые во внимание при экспертизе

1.Патент США № 3806883, кл. 3 0-172.5j опублик. 197.

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

i i k I (

Ц2 /

%a /

ы

9иг, J

23п