Организация виртуальной памяти

В 1961 году группа исследователей из Манчестера (Англия) предложила способ автоматического перемещения сегментов программ и данных между оперативной и внешней памятью компьютера, т.е. между полупроводниковой памятью и накопителями на магнитных дисках. Автоматизм перемещения сегментов в многоуровневой памяти обеспечивается за счет использования ресурсов аппаратуры и операционной системы компьютера. Построенная таким образом память, объединяющая в себе и оперативную, и внешнюю память была названа виртуальной (фиктивной, кажущейся) памятью. За счет использования оперативной памяти была решена проблема объединения в единую систему оперативной памяти и накопителей на магнитных дисках, в результате чего программисты получили возможность работать с очень большими адресными пространствами – от 4 Гигабайт. При этом виртуальная память обеспечивает равнодоступность любых адресов команд и данных.

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

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

Процессы преобразования адресов и перемещения данных наиболее просто реализуются при страничной адресации памяти. Метод страничной адресации состоит в следующем. Множество адресов (слов, ячеек) разделяется на сегменты, состоящие из, например, 2¹² соседних адресов и называемые страницами. Так, адреса 0, 1, …,2¹² - 1 относятся к странице 0, адреса 2¹², 2¹² + 1, …,2¹³ - 1 – к странице 1 и т.д. В результате этого адрес рассматривается как совокупность двух полей

Здесь P – адрес страницы, принимающий значения 0, 1, …, 2²⁰ – 1, и А – адрес байта в странице Р , принимающий значения 0, 1, …, 4096.

Применительно к виртуальной памяти выделяются два типа адресов: виртуальные и физические. Виртуальный адрес - это адрес, которым идентифицируется некоторое слово в программе. Виртуальный адрес имеет структуру (5.1). Физический адрес – это адрес ячейки памяти. Физические адреса имеют структуру, совпадающую с (5.1), но поля адреса идентифицируются следующим образом:

Здесь S – адрес сегмента, принимающий значения 0, 1, …, 2²⁰ – 1, и А – адрес байта в сегменте S. Таким образом, страница – совокупность из 2¹² байтов, а сегмент - совокупность из 2¹² байтов, являющихся местом хранения страницы.

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

Текущее состояние памяти компьютера характеризуется таблицей страниц, структура которой приведена в табл. 5.1. Отдельной странице Р = 0, 1, 2, … соответствует одна строка таблицы, в которой указываются параметры, характеризующие страницу Р. Значение S_Р определяет адрес сегмента S_Р = 0, 1, 2, …, в котором размещается страница Р, иначе говоря, физический адрес страницы Р. Бит d_p называется признаком доступности страницы P. Если страница Р размещается в оперативной памяти, то d_p = 1, поскольку эта страница доступна для процессора. Если страница Р хранится во внешней памяти, то бит доступности d_p = 0. Таблица страниц размещается в оперативной памяти и в любой момент времени доступна процессору.

Порядок использования таблиц страниц для отображения виртуальных адресов иллюстрируется рис. 5.1. Таблица страниц должна содержать все данные о состоянии всех сегментов, относящихся к инициируемой программе, данным, которые будут обрабатываться программой, и прочей информации, относящейся к программе. Поскольку и программа, и множество данных, которое обрабатывает программа, ограничены, то таблица страниц также ограничена, т.е. содержит конечное число строк. Физически страницы могут размещаться как в оперативной памяти, где они доступны для процессорной обработки, так и во внешней памяти – в накопителях на магнитных дисках (см. рис. 5.1.). В рассматриваемом примере таблица страниц определяет, что страницы с адресами 0, 212, 1 и 2 доступны для процессорной обработки, а страница с адресом 32875 находится в накопителе на магнитных дисках и недоступна процессору.

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

Наиболее простая схема преобразования адресов изображена на рис. 5.2. Виртуальный адрес слова определяется путем нахождения адреса ячейки, указанного в команде. Для нахождения адреса ячейка, где хранится слово, производится обращение к ячейке (В + Р) оперативной памяти, где В – фиксированный базовый адрес таблицы страниц, и выбираются значения S_d и d_p, описывающие страницу Р. Если d_p = 0, то в данный момент времени страница P недопустима для обработки. По этой причине работа процессора прерывается сигналом d = 0 и управление передается средствам перемещения страниц. Если d_p = 1 , то S : = S_p и производится обращение к ячейке S.A оперативной памяти.

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

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

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

2) преобразование виртуальных адресов страниц в физические адреса.

В качестве запоминающего устройства модуля управления памятью используется ассоциативное запоминающее устройство небольшой емкости – обычно емкостью в 8 или 16 слов. Каждая ячейка ассоциативного запоминающего устройства имеет следующую структуру (рис. 5.3).Поскольку рабочее множество страниц невелико и в множество могут быть загружены самые различные виртуальные страницы, виртуальный адрес Р сравнивается со всеми адресами Р_α. Если адреса Р и Р_α имеют одинаковое значение, то значение физического адреса S_α выбирается из ячейки α и используется в качестве физического адреса стрвницы. Если же виртуальный адрес страницы Р не совпадает ни с одним из адресов Р₀, Р₁, Р_L, то фиксируется промах в ассоциативном запоминающем устройстве и производится об ращение к таблице страниц, в которой размещается вся информация о программе и данных. Естественно, что при полной занятости емкости ассоциативного запоминающего устройства, одна из его ячеек должна быть выделена для загрузки в нее данных о новой затребованной странице из таблицы страниц. Для решения задачи о выделении одной из ячеек ассоциативного запоминающего устройства для загрузки в нее новых данных о странице используется управляющее поле УП_α, в котором хранятся данные о занятости и об интенсивности использования ячейки α.

Схема и функциональная микропрограмма преобразования виртуальных адресов в физические адреса представлена на рис. 5.4 и рис. 5.5.

В ячейках α = 0, 1, … ассоциативного запоминающего устройства размещаются описания страниц Р₀, Р₁, …, Р_L, хранимых в таблице страниц оперативной памяти. Виртуальные адреса Р₀, Р₁, …, Р_L размещены в адресном поле АП. В рабочем поле РП представлены физические адреса S₀, …, S_L этих страниц , причем все физические адреса S_α принадлежат оперативной памяти. Управляющее поле УП состоит из признаков занятости z₀, …, z_L ячеек 0, …, L и признаков активности t₀, …, t_L этих ячеек. Бит z_α = 0, если ячейка α ассоциативного запоминающего устройства свободна (не содержит описания страницы), и z_α = 1, если описание

некоторой страницы загружено в ячейку α. Значение признака активности страницы tα определяется числом обращений к странице α. При каждом обращении к странице α значение признака активности страницы увеличивается на единицу: t_α := t_α + 1.

Преобразование виртуального адреса в физический адрес выполняется в соответствии с микропрограммой (рис. 5.5). Преобразование начинается с проверки наличия в ассоциативном

запоминающем устройстве описания страницы Р. Если Р Є АП, то преобразование сводится к выборке физического адреса S_α из ячейки α , в которой размещается страница Р_α = Р. В противном случае местоположение страницы Р определяется обращением к таблице страниц, из которой выбирается физический адрес SР и признак доступности d_p страницы Р. Если d_p = 1, то страниц Р доступна и ее описание заносится в ячейку γ ассоциативного запоминающего устройства, выделяемую управляющим полем УП. Ячейка γ назначается из числа свободных ячеек, отмеченных признаком t_γ = max. Заметим, что в данном случае информация, хранимая в ячейке γ, просто затирается описанием страницы, поскольку копия уничтоженного в ассоциативном запоминающем устройстве описания имеется в таблице страниц. Емкость ассоциативного запоминающего устройства выбирается исходя из предельно допустимой вероятности обращения к таблице страниц и зависит от количества страниц, отводимых задаче в таблице страниц оперативной памяти. Вероятность обращения к таблице страниц уменьшается с увеличением емкости ассоциативного запоминающего устройства и возрастает при увеличении числа страниц, принадлежащих обрабатываемой задаче. Обычно ассоциативное запоминающее устройство обслуживает не менее 90% обращений к таблице страниц, и, следовательно, затраты времени на преобразование виртуальных адресов определяются быстродействием ассоциативного запоминающего устройства.

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

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

Наиболее широко применяется алгоритм удаления наиболее неиспользуемой страницы из оперативной памяти, называемой алгоритмом LRU (Liast Recently Used). Хотя этот алгоритм работает достаточно хорошо, в ряде случаев возникает пробуксовка процесса. Например, пусть программа выполняет большой цикл, охватывающий девять виртуальных страниц, а в ассоциативном запоминающем устройстве имеется место только для восьми страниц. Когда программа перейдет к обработке страницы семь, в оперативной памяти размещается восемь страниц с адресами 0, 1,… , 7 и требуется вызвать страницу 8 из дисковой памяти. Алгоритм LRU в качестве удаляемой назначит страницу 0 как наиболее давно используемую, и на ее место будет записана страница 8, ранее находившаяся в дисковой памяти. В результате таблица страниц перейдет в состояние 8, 1, 2, …, 7. После выполнения команд из страницы 8 управление передается в страницу 0. Этот переход приводит к удалению страницы 1, на место которой будет записана страница 0. Затем происходит обращение к странице 1, которая только что была удалена в дисковую память, и т.д. Очевидно, что в этой ситуации алгоритм LRU работает плохо, но и другие алгоритмы назначения кандидатов на удаление из оперативной памяти также плохо работают в сходных ситуациях. Однако если расширить размер рабочего множества, число ошибок из-за отсутствия страниц конечно уменьшится.

Если страница, которую следует удалить, не менялась с момента вызова ее из дисковой памяти, например, представляла собой страницу программы, то нет смысла записывать эту страницу в дисковую память, поскольку там уже есть копия удаляемой страницы. Однако если страница изменилась, то копия на диске уже не соответствует данной странице, и страницу необходимо записать на диск. Чтобы избежать ненужных записей на диск и сэкономить значительную долю времени, в большинстве компьютеров используется специальный бит, который принимает значение 0 при загрузке страницы из диска и значение 1, когда аппаратура компьютера производила запись в эту страницу. По значению этого бита операционная система определяет, производилась ли хотя бы одна запись в страницу, и нужно ли записывать страницу на диск.