Электронный учебник по дисциплине "Системное программное обеспечение"

Впервые виртуальная память была реализована в Великобритании в компьютере Atlas (1960), созданном в Манчестерском университете.

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

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

V=(b, d),

где b - номер блока с виртуальным адресом, d - смещение адреса относительно начала блока b. Таблица отображения блоков обычно хранится в кэш-памяти.

Преобразование виртуального адреса в реальный. Реальный адрес a таблицы загружается в специальный регистр начального адреса таблицы блоков. Таблица содержит по одной строке для каждого блока процесса, причем эти строки идут в порядке возрастания номеров (блок 0, блок 1, ...). Hомер блока суммируется с адресом а, образуя реальный адрес строки таблицы для блока b. Эта строка содержит реальный адрес b' блока в реальной памяти. К b' прибавляется смещение d и образуется реальный адрес r=b'+d.

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

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

Процесс обращается по виртуальному адресу V. В таблице отображения ищется номер страницы p и определяется адрес в R страничного кадра p', а затем r, с учетом смещения d. Таблица отображения состоит из элементов, которые содержат номера страниц, в настоящий момент размещенных в памяти. Строка таблицы:

i - бит присутствия страницы в R (0 - нет, 1 - есть); S – адрес страницы во внешней памяти (при i=0); p'- номер страничного кадра в R (при i=1). Адрес R, с которого начинается кадр p' при размере страницы l определяется как r = l*p' + a.

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

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

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

1)     определяется расположение в памяти таблицы сегментов;

2)     по номеру сегмента s отыскивается его дескриптор и определяется базовый адрес таблицы страниц сегмента;

3)     Hомер страницы p прибавляется к базовому адресу, что позволяет определить дескриптор страницы, а значит и номер страничного кадра в реальной памяти;

4)     С учетом смещения d находится реальный адрес.

Такая схема применяется в ОС, которые используют защищенный режим процессора Intel и механизм трансляции страниц, поддерживаемых этим режимом (Windows 95, Windows NT).

ДВУХСТУПЕHЧАТАЯ СХЕМА ПРЕОБРАЗОВАHИЯ АДРЕСА

Hа первом шаге логический адрес, состоящий из 16-иразрядного селектора и 32-хразрядного смещения преобразуется в так называемый линейный адрес.

Линейный адрес выбирается из дескриптора, на который указывает селектор. Линейный адрес представляет собой структуру, состоящую из 3 полей:

-       индекса в каталоге таблиц страниц;

-       индекса в таблице страниц;

-       смещения на странице.

В системе может содержаться произвольное количество каталогов таблиц страниц. Адрес каталога, в котором производится поиск, содержится в регистре CR3. Элементами каталога являются дескрипторы, описывающие таблицы страниц. Формат дескриптора:

P - присутствие таблицы страниц в памяти;

W - разрешение записи в страницы;

U - страницы супервизора (0) или пользователя (1);

A - доступ: устанавливается в 1 перед записью или чтением;

D - устанавливается в 1 если была выполнена запись в таблицу;

AVL - зарезервированы за ОС.

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

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

-       страница находится в переходном состоянии;

-       страница обновлена, но не сохранена в файле страниц;

-       страница присутствует в памяти.

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

-       Свободная - доступна для использования после ее заполнения нулями;

-       Заполненная нулями - свободная страница, заполненная нулями и доступная для использования процессами;

-       Правильная - используется активным процессом;

-       Измененная - содержимое страницы было изменено, однако страница еще не сохранена в файле страниц;

-       Запасная - страница удалена из рабочего набора страниц процесса;

-       Плохая - при обращении к странице возникла аппаратная ошибка.

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

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

Сплошная модель памяти FLAT

Сплошная модель памяти FLAT реализует виртуальную концепцию адресации в ОС Windows 95 и Windows NT. В соответствии с этой моделью каждому процессу выделяется виртуальное адресное пространство протяженностью 4Гб.

Из них 2Гб зарезервировано за ОС, а за пользовательским процессом закреплено пространство протяженностью 2Гб - 128 Кб, расположенное в области младших адресов. Блоки по 64 Кб используются для контроля за правильностью указателей. Физически виртуальное адресное пространство реализуется в виде файлов подкачки страниц, которые размещаются на внешних накопителях. Всего может быть создано до 16 файлов подкачки.

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

Функции для доступа к виртуальной памяти

У процесса есть две возможности заказать себе страницу виртуальной памяти:

1)     резервировать диапазон адресов в виртуальном адресном пространстве;

2)     получить в пользование страницу виртуальной памяти.

Оба способа реализуются одной и той же функцией: LPVOID VirtualAlloc(LPVOID lpvAddress, DWORD cbSize, DWORD fdwAllocationType, DWORD fdwProtect);

первый параметр - адрес области, резервируемой и/или передаваемой в пользование. При резервировании это значение должно быть равно нулю (NULL);

второй параметр - размер области в байтах;

третий параметр - способ получения:

четвертый параметр - флаги доступа

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

Освобождение виртуальной памяти BOOL VirtualFree (LPVOID lpvAddress, DWORD cbSize, DWORD fdwFreeType);

Функции передаются адрес и размер освобождаемой области.

Третий параметр может иметь значения: MEM_RELEASE – освободить MEM_DECOMMIT          - вернуть в зарезервированное состояние.

Фиксирование страниц основной памяти. Эта функция позволяет закрепить за объектом данных необходимое множество страниц физической памяти. В результате вызова функции будет зафиксировано столько страниц, сколько нужно для размещения объекта, адрес и размер которого передаются в качестве параметров: BOOL VirtualLock (LPVOID lpvAddress, DWORD cbSize);

Расфиксирование страниц выполняется следующей функцией: BOOL VirtualUnlock (LPVOID lpvAddress, DWORD cbSize); Страницы возвращаются ОС и могут быть переданы другому процессу.

По умолчанию процесс не может зафиксировать более 30 страниц основной памяти. Установка числа страниц, доступных для фиксирования, выполняется функцией: BOOL SetProcessWorkingSetSize (HANDLE hProcess, DWORD dwMinSize, DWORD dwMaxSize); позволяет для процесса (1 параметр) установить минимальное и максимальное число страниц основной памяти.

Текущее число страниц может быть получено: BOOL GetProcessWorkingSetSize (HANDLE hProcess, LPDWORD lpdwMinSize, LPDWORD lpdwMaxSize); задаются указатели, по которым функция вернет минимальное и максимальное количество страниц.

СТРАТЕГИИ УПРАВЛЕHИЯ ВИРТУАЛЬHОЙ ПАМЯТЬЮ

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

СТРАТЕГИИ ВТАЛКИВАHИЯ реализуют перенесение страницы из виртуального в реальное адресное пространство. Их цель - определить, в какой момент следует переписать страницу или сегмент из внешней памяти в основную. Применяются следующие подходы:

1)     вталкивание по запросу, т.е. при появлении явной ссылки (при обращении по некоторому адресу и отсутствии страницы с этим адресом в основной памяти происходит перемещение страницы из виртуального адресного пространства в реальное). Эта стратегия имеет свои проблемы. Процесс должен накапливать в памяти требуемые страницы по одной. При появлении ссылки на каждую новую страницу процессу приходится ждать, когда эта страница будет загружена в память. В зависимости от того, сколько страниц данного процесса уже находятся в основной памяти, эти периоды ожидания будут обходиться все более дорого, поскольку ожидающие процессы будут занимать все больший объем памяти. Для оценки использования памяти процессом используется произведение "пространство*время". Уменьшение этого произведения за счет периодов ожидания процессом нужных ему страниц является важнейшей целью всех стратегий управления памятью;

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

СТРАТЕГИИ РАЗМЕЩЕHИЯ должны определить место в реальной памяти для размещения очередного поступающего сегмента или страницы из виртуальной памяти. В системах со страничной памятью решение о размещении принимается достаточно тривиально, поскольку поступающая страница может быть помещена в любой свободный страничный кадр. В системах с сегментной организацией виртуальной памяти требуется использование более развитых средств размещения. Это обусловлено необходимостью борьбы с фрагментацией реальной памяти компьютера. Чаще всего применяются:

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

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

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

СТРАТЕГИИ ВЫТАЛКИВАHИЯ. Целью этих стратегий является обеспечение процедуры смены блоков (страниц или сегментов), принадлежащих различным процессам, в реальной памяти. Hеобходимость выталкивания из основной памяти в виртуальное пространство обусловлена различной протяженностью реального адресного пространства компьютера и суммы виртуальных адресных пространств действующих процессов. Выталкивание позволяет разместить поступающие блоки, даже если реальная память полностью занята. Рассмотрим следующие подходы:

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

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

3)     FIFO (First In - First Out). Выталкивается та страница, которая дольше остальных находится в памяти. Аргумент для применения такой стратегии весьма существенен: у выталкиваемой страницы уже был высокий шанс использования, и пора дать подобные возможности другой странице. К сожалению, стратегия FIFO с большой вероятностью будет приводить к замещению активно используемых страниц, поскольку тот факт, что страница находится в основной памяти в течении длительного времени, может означать, что она постоянно в работе. Если ее вытолкнуть из основной памяти по принципу FIFO, ее почти немедленно придется вталкивать обратно.

Исследователями была обнаружена аномалия, присущая стратегии FIFO: при увеличении количества страничных кадров, выделенных процессу, возможно увеличение числа прерываний по отсутствию страницы в реальной памяти. Рассмотрим пример. Процесс в течении некоторого времени работает со страницами A, B, C, D и E. Последовательность работы со страницами определена левым столбцом на рисунке. В первом случае процессу выделено 3 страничных кадра, во втором - 4. При отсутствии страницы в памяти возникает прерывание. Подсчитаем количество прерываний:

4)     LRU (Least Recently Used). Выталкивается та страница, которая дольше не использовалась; Эта стратегия требует, чтобы при каждом обращении к странице обновлялась связанная с ней временная метка. Процедура выталкивания может найти страницу с максимальным значением временной метки.

5)     LFU (Least Frecuently Used).- Эта стратегия нацелена на выталкивание той страницы, которая реже использовалась. Здесь контролируется интенсивность использования страницы. Однако, велика вероятность, что наименее интенсивно используемой окажется страница, которая только что была загружена в основную память и к которой было только одно обращение;

6)     NUR (Not Used Recently). Стратегия обеспечивает выталкивание страницы, которая не использовалась в последнее время. Эта стратегия близка к LRU и характеризуется малыми издержками. Основанием для применения стратегии считается следующее утверждение: к страницам, которые в последнее время не использовались, вряд ли будут обращения в ближайшем будущем, так что их можно заменять на вновь поступающие страницы.

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

A - доступ (обращение): устанавливается в 1 перед записью или чтением;

D - модификация: устанавливается в 1 если была выполнена запись в таблицу.

Первоначально биты-признаки для всех страниц устанавливаются в 0. При обращении к какой-либо странице бит A устанавливается в 1, а в случае изменения содержимого страницы устанавливается D=1. Когда нужно выбрать страницу для выталкивания, находят страницу, к которой не было обращений (A=0). Если таких страниц нет, ищем страницу, у которой D=0.

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

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

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

1)     Малый размер страниц приводит к увеличению таблиц отображения и к табличной фрагментации.

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

3)     Обмен данными с дисковой памятью более эффективен при большом размере страниц.

4)     Свойство локальности распространяется на небольшие участки.

5)     При малых размерах страниц потери памяти на внутреннюю фрагментацию (то есть наличие не полностью занятых страниц) уменьшаются.

В целом страницы должны быть небольшими (не более 1К слов).

Поведение программ при подкачке страниц. Результаты кспериментов:

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

2)     Количество прерываний по отсутствию нужной страницы увеличивается с увеличением размера страницы при постоянном объеме реальной памяти.

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

4)     Число команд, выполняемых на странице, обычно не велико (<=200 команд на странице в 1К слов).