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

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

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

Итак, виртуальной памятью называется основная память процесса, адресное пространство которого соответствует диапазону непосредственной адресации системы команд ЭВМ и которая обычно не совпадает с объемом реальной памяти ЭВМ.

EC ЭВМ имеет 24 разрядную адресную шину, что позволяет адресовать 16 Мб оперативной памяти. Операционная система обеспечивает одновременную работу N процессам, выделяя каждому из них 16 Мб.

Начиная с процессоров Intel 386 (32 разрядный), для каждого процесса выделяется адресное пространство размером 4 Гб. При этом одновременно могут работать N процессов.

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

1.Обеспечить возможность создания и выполнения на ЭВМ программ максимально допустимого размера.

2.Облегчить жизнь программиста, сняв с него проблемы, связанные с ограниченным объемом реальной ОП (РОП).

3.Устранить временную фрагментацию, максимально эффективно используя ОП ЭВМ, которая образуется при отсутствии необходимого участка программы/данных в РОП и определяется временем, необходимым для размещения необходимых данных в РОП.

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

В ОС с реальной ОП привязка адресного пространства к реальным адресам осуществляется статически до выполнения программы на все время выполнения.

6.1. Концепция виртуальной памяти

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

Виртуальная память - это моделирование оперативной памяти во внешней памяти.

Механизм отображения виртуальных и реальных адресов устанавливает между ними соответствие и называется динамическим преобразованием адресов (ДПА) (рис.6.1)

Компьютер здесь уже выступает как логическое устройство, а не физическая машина с уникальными характеристиками. ДПА поддерживается на аппаратно-микропрограммном уровне. В МП Intel, начиная с 386 процессора, выполняется поддержка виртуальной памяти. Такая процедура выполняется для EC ЭВМ - ряд 2 и выше, для СМ ЭВМ- 1700, для IBM PC – PC/386 и выше.

Рис.6.1. Динамическое преобразование адресов

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

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

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

Еще один вопрос, который необходимо решать: Каким сделать размер блока?

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

Блоки могут быть фиксированного размера (страницы) и переменного размера (сегменты). В этой связи существует четыре способа организации виртуальной памяти:

1.Динамическая страничная организация.

2.Сегментная организация.

3.Комбинированная сегментно-страничная организация.

4.Двухуровневая страничная организация.

Виртуальные адреса в страничных и сегментных системах являются двухкомпонентными и представляют собой упорядоченную пару (p,d), где p - номер блока (страницы либо сегмента), в которой размещается элемент, а d - смещение относительно начального адреса этого блока. Преобразование виртуального адреса V=(p,d) в адрес реальной памяти r осуществляется следующим образом (рис.6.2).

Рис. 6..2.. Преобразование виртуального адреса в реальной адрес памяти

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

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

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

а) вталкивание по запросу - система ожидает ссылки на страницу/сегмент от выполняющегося процесса (прерывание по отсутствию страницы);

аргументы за:

• путь выполнения программы наверняка предсказать невозможно;

• гарантия расположения в ОП только нужных страниц;

• накладные расходы на определение требуемых страниц минимальны;

аргументы против:

• подкачка по одному блоку приводит к увеличению общего времени ожидания;

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

Достоинство: сокращается время ожидания.

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

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

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

Здесь основная проблема "пробуксовки", при которой вытолкнутая страница в следующий момент должна вновь размещаться в РОП.

Рассмотрим процедуры определения блоков для выталкивания из ОП.

а) выталкивание случайной страницы - в реальных системах не применяется;

б) выталкивание первой пришедшей страницы (FIFO – First In First Out). Для ее реализации необходимо устанавливать временные метки страниц.

Аргумент: у страницы уже были возможности использовать свой шанс.

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

в) выталкивание дольше всего неиспользованных страниц (NUR – Not Used Resently).

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

Недостаток - существенные издержки: постоянное обновление временных меток.

г) выталкивание реже всего используемых страниц (RFU Rare Frequently Used) - предполагает наличие счетчиков страниц (менее интенсивно, нежели обновляемые временные метки). Интуитивно оправдано, но тоже может быть не рационально.

д) выталкивание не использующихся в последнее время страниц (LRU- Least Resently Used) - самый распространенный алгоритм с малыми издержками. Реализуется двумя аппаратными битами на страницу: