Виртуальная память

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

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

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

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

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

Так как потребности программ в этом ресурсе могут быть весьма велики, а объем физической памяти ограничен, во всех современных ОС реализована виртуальная память.

Возможности 32-разрядной адресации современных процессоров обеспечивают доступ к 4 Гб памяти. Реально же объем физически установленной памяти бывает значительно меньше. Разработчики программ не знают, память какой емкости окажется доступной программе во время ее выполнения, поэтому пишут программы в расчете на виртуальное (воображаемое, кажущееся доступным) адресное пространство. Это пространство ограничивается возможностями адресации, потребностями самой ОС, которая также требует для своего выполнения ресурсов (в OS/2 в распоряжении прикладной программы остается 512 Мб, в Windows NT – почти 2 Гб). Но в действительности в распоряжении программы оказывается гораздо меньший объем физической памяти (обычно до 64‑ 128 Мб), которая, к тому же, должна быть распределена между несколькими параллельно выполняющимися программами. Эта проблема решается созданием виртуальной памяти.

Виртуальная память – это ресурс, моделирующий оперативную память большого объема, созданный на базе реальной оперативной памяти и памяти на внешних запоминающих устройствах (жестких дисках) с помощью программ ОС.

Физической памятью в системах с виртуальной памятью фактически является дисковая память и объем этого ресурса ограничивается лишь возможностями адресации процессора (по 32‑ разрядной шине адреса процессор может обратиться к 4 Гб памяти), потребностями ОС и объемом свободной памяти на диске. «Ненужные», временно не используемые данные выгружаются ОС на диск, освобождая оперативную память для текущей работы. При обращении к данным они снова загружаются в оперативную память. Это происходит незаметно для пользователя. Каждой программе «кажется», что ей выделена вся память (рис. 4.13). Однако в том случае, когда запущено большое количество программ, а объем ОЗУ невелик, система большую часть времени будет тратить не на выполнение программ, а на обмен данными между оперативной памятью и дисками. Такая ситуация называется «пробуксовкой».

В многопрограммных ОС адресные пространства программ практически изолированы друг от друга, что обеспечивает их защиту. В Windows 9x несколько программ могут работать с одной и той же областью памяти, поэтому данная ОС так ненадежна.

Организация виртуальной памяти позволяет адресовать пространство памяти, гораздо большее, чем емкость реальной памяти компьютера. Впервые виртуальная память была реализована в вычислительной машине Atlas, созданной в Манчестерском университете в Англии в 1960 г. В настоящее время системы виртуальной памяти нашли широкое распространение.

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

Рис. 4.14. Этапы отображения адресов

При написании программы программист работает с именами. Те адреса, на которые делает ссылки процесс во время выполнения, являются виртуальными адресами, а диапазон всех виртуальных адресов, к которым может обратиться процесс, называется пространством виртуальных адресов этого процесса. Адрес физической памяти – номер ее реально существующей ячейки – называется реальным или физическим адресом. Диапазон физических адресов компьютера называется пространством реальных адресов. Таким образом, для выполнения программы необходимо отобразить пространство имен на физическую память. Обычно это отображение выполняется в два этапа (рис. 4.14).

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

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

Таким образом, в основе виртуальной памяти лежат следующие средства:

– относительная адресация памяти,

– разрывное распределение памяти,

– возможность динамической настройки адресов.

Относительная адресация обеспечивает возможность создания перемещаемого кода (программа во время выполнения настраивается на произвольные адреса распределяемых ей блоков памяти).

Разрывное распределение памяти обеспечивает возможность разбиения всего пространства памяти, отведенного программе, на несколько несмежных разделов.

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

Так как пространство виртуальных адресов процесса больше пространства реальных адресов, то нельзя установить однозначное соответствие между виртуальными и физическими адресами: на одну и ту же ячейку физической памяти может отображаться несколько элементов программы. Поэтому те данные и код программы, которым «не хватило места» в реальной оперативной памяти должны быть сохранены во вспомогательной памяти большой емкости, размещаемой на внешних запоминающих устройствах (ВЗУ).

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

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

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

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

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

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

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

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

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

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

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

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

Размер страниц обычно кратен степени 2 (2 k), например, 2 Кб. Увеличение размера блоков приводит к уменьшению затрат памяти на реализацию механизма отображения. Но такие крупные блоки требуют больше времени на обмен между первичной и вспомогательной памятью. Кроме того, память внутри таких блоков может простаивать: блок, выделенный процессу, может быть занят им не полностью, то есть может возникнуть внутренняя фрагментация памяти, снижающая эффективность ее использования.

Многосегментная память предполагает разделение адресного пространства процесса на набор сегментов. Сегмент – это определяемый программистом при разработке программы блок, который может рассматриваться как логически независимая программная единица (например, программный код или данные, определенные в программе, или отдельные процедуры и блоки данных). Следовательно, блоки памяти, занимаемые сегментами, могут иметь различные размеры. При выделении под сегмент непрерывного блока памяти получается чисто сегментная организация памяти.

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

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

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

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

Когда сегмент Segment находится в первичной памяти (для него уже есть представляющая его таблица), обращение к таблице страниц может показать, что в памяти нет адресуемой страницы Page. В этом случае вырабатывается прерывание по отсутствию страницы. Для его обработки ОС возьмет управление на себя, найдет данную страницу во внешней вторичной памяти и загрузит ее в основную память (возможно, с замещением другой страницы, которая будет вытолкнута из первичной памяти и для нее бит присутствия будет сброшен). Загрузка страницы приведет к модификации соответствующей строки таблицы страниц: в нее будет записана ссылка на страничный кадр реальной памяти, распределенный для загрузки страницы, а также в ней будет установлен бит присутствия страницы в оперативной памяти.

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

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

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

– Стратегии выборки:

· стратегии выборки по запросу (по требованию),

· стратегии упреждающей выборки;

– Стратегии размещения;

– Стратегии замещения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Существует несколько стратегий выталкивания блоков для размещения новых блоков, если в оперативной памяти нет свободного пространства для размещения в нем загружаемого из внешней памяти по запросу процесса блока:

– принцип оптимальности,

– выталкивание случайного блока,

– выталкивание блока, который был загружен ранее всего (FIFO),

– выталкивание блока, который не использовался дольше всего (LRU),

– выталкивание наименее часто используемого блока (LFU),

– выталкивание блока, не использовавшегося в течение последнего фиксированного промежутка времени (NUR),

– сохранение рабочего множества.

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

Дисциплина выталкивания FIFO (First In First Out) также не может обеспечить эффективное использование памяти, так как долгое присутствие блока (страницы) в памяти может означать его постоянное использование, следовательно, замещенную страницу снова придется загрузить в память, затратив время на ее выгрузку и повторную подкачку.

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

Стратегии LRU (Least Recently Used), LFU (Least Frequently Used), NUR (Non Used Recently) приближаются к оптимальной стратегии. Для их реализации также нужны дополнительные средства: для каждого блока необходимо хранить информацию или о времени последнего обращения к нему, или о количестве обращений, выполненных за единицу времени, или о длительности промежутка времени, в течение которого к блоку не было обращений со стороны процесса. Эта информация может находиться в строке таблицы, описывающей блок.

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

Однако в ВС на базе микропроцессоров чаще всего используется упрощенный вариант алгоритма замещения (алгоритм NUR как “приближение” оптимальных, но более сложных алгоритмов LRU или LFU), требующий включения в строку-описатель блока в таблице лишь бита-признака обращения к блоку, который устанавливается аппаратно процессором при обращении к блоку с любым запросом, а сбрасывается программой ОС, вызываемой через установленный промежуток времени, и бита-признака модификации блока (признака записи в блок, устанавливаемого автоматически при выполнении операции записи в блок). Когда нужно выбрать блок для выталкивания, ОС пытается прежде всего найти страницу, к которой не было обращений. Вторичным признаком для выбора кандидата на замещение является состояние бита модификации блока.